ITACPC Competition 2024 | Our @PoliMI team

I took part in ITACPC 2024, an online programming contest held on 19 October 2024. The full list of challenges can be found on the official task page. I cannot write about all of them, so here are the five I found most interesting, in no strict order.

1. Pancake Rotation Challenge

Marcella drops a pile of pancakes, and the only move allowed is rotating three consecutive pancakes to the left or to the right. The question is whether the pile can be sorted. This was my favourite, because the answer is short but you have to see it first.

A rotation of three elements is a 3-cycle, and a 3-cycle is an even permutation. So a rotation can never change the parity of the arrangement. If all sizes are different, the answer is YES exactly when the permutation that sorts the list is even. If two pancakes have the same size (the limits allow this), you can swap them without changing anything visible, so any list with at least three pancakes and a repeated size is always sortable. Lists of size one or two need a separate check, since no rotation fits.

def solve(s):
    n = len(s)
    if n <= 2:
        return s == sorted(s)
    if len(set(s)) < n:
        return True
    order = sorted(range(n), key=lambda i: s[i])
    seen = [False] * n
    cycles = 0
    for i in range(n):
        if not seen[i]:
            cycles += 1
            while not seen[i]:
                seen[i] = True
                i = order[i]
    return (n - cycles) % 2 == 0

I like this kind of task because the code is tiny. All the work happens in the head, and the edge cases are easy to handle.

2. Fast Ferret Transform

Ferris wants to turn the concatenation of a list of numbers into the concatenation of the same list with every number increased by one, using as few digit insertions and deletions as possible. With only insertions and deletions, the answer is the length of the first string plus the length of the second, minus twice their longest common subsequence.

The trap is the size. The strings can have 10⁵ digits in total, so the usual quadratic LCS is far too slow. The way out is to look at what "add one" really does: the trailing 9s of a number become 0s, the digit before them grows by one, and an all-9 number gains a leading 1. Everything else stays the same, so the two strings are almost equal, and that structure is what you have to exploit. A problem that looks like a generic string exercise turns into a careful case analysis, which I enjoyed a lot.

3. Quantum Frog

A frog particle sits in a state (i, j), two energy levels at once. In one jump it moves only one of the two coordinates, and the value |a_i − a_j| must strictly increase. We must count how many distinct states can be reached, with (i, j) and (j, i) being the same state, and N goes up to 500000.

The first instinct is to say that every state with a larger difference is reachable. The second sample shows that this is false: a state with a bigger entropy can still be out of reach. So you need to understand which chains of jumps exist, and you need to do it in roughly linear time after sorting the values. I liked that the statement gives you the counterexample you need to avoid a wrong idea.

4. ITACPC Sabotage!

This one is the hardest of my list, and the story is fun: you are a hacker who wants to infect at least one node in every cluster of the contest network, without entering the same node, the same cluster or the network twice. Clusters only connect to neighbouring clusters, and the answer counts distinct sets of infected nodes, not paths.

Some structure appears quickly. Because you enter each cluster only once and links only join adjacent clusters, the virus has to sweep through the clusters in order, from the first to the last or the other way round. Inside a cluster, the staff disabled links until only as many remain as there are nodes, so each cluster is connected and contains exactly one cycle. The difficult part is counting sets instead of paths, because different routes and the two sweep directions can produce the same set. It is a nice mix of graph structure and counting modulo 10⁹ + 7.

5. Desperate Recovery

Sara had a permutation and M tokens, each one saying that one element is smaller than a second one, which is smaller than a third. After an accident, she cannot tell the orientation of any token, since (x, y, z) could mean x < y < z or z < y < x. We only need to output any permutation that satisfies at least half of the tokens, rounded up.

What I found interesting is the change of goal. Recovering the original permutation means facing a huge number of possible orientations, and it is not even required. The task only asks for something good enough, and the constraints (N and M up to 10⁶) tell you that the intended solution has to be simple and fast. You win by understanding how little the statement really demands, which is a good reminder for many contest problems.

Final thoughts

It was a nice challenge. The tasks had a good variety, the stories were funny, and several of them, like the pancakes and the ferret, reward one clean observation more than a heavy algorithm. I am happy I took part, and I would gladly do it again.