Could someone explain why it's possible to obtain any permutation in a connected component for problem C? Editorial says that we can swap A and D in a sequence A-B-C-D, where we can swap connected elements, by a sequence of adjacent swaps. But after we swap A and B, we get a sequence B, A, C, D, where it might be impossible to swap A and C. What obvious fact am I missing?

I managed to solve it with a standard $$$O(n^2 2^n)$$$ DP for a given string $$$x$$$ by exploiting the similarity between sequential strings, which in most cases differ only in a couple of lower bits. Therefore, when solving for string $$$x$$$, you can reuse a lot of the memoized solutions for DP states that you computed for string $$$x-1$$$.

Not including tests with loops in the One-Way Streets problem was a minor oversight on our part. I think that making an assumption that the graph is connected is a mistake and shouldn't need an explicit clarification.

The problemset was too easy as indicated by three full scores. However, with the exception of the top contestants it did rank the others just fine.

Regarding the Mousetrap problem, you can calculate how many moves are required to get the mouse out of a subtree once it enters it. With this information you can use a binary search to determine which branches along the path to the trap you have to block to prevent the mouse from entering the corresponding subtree and force it into the trap in time.

Yes, the judge will stay available for a short time. Afterwards the tasks will be accessible for solving at CS Academy.

"Registration will be enabled after the conclusion of the on-site contest on Friday." I'll post an update at that time to notify everyone.

Note that CS Academy does not currently support the simulation of the onsite contestants. So you would be competing against virtual ones. However, with IOI rules it's trivial to check where you would end up in the onsite ranking.

The online contest is not intended as a mirror but as a separate contest featuring the same tasks. It will run as scheduled. After the conclusion of CEOI we will coordinate with CS Academy to set up the virtual contests of individual competition days.

I agree, but we're short on various resources (mostly the manpower to monitor the contest), which is why we decided to pack everything into a single online contest. Despite this, we hope the contest will be a good experience for online contestants.

Has anyone managed to get the local testing tool working on Ubuntu with a C++ solution? All I get is a bunch of undefined references to MyNodeId() etc. :(

Thanks. Btw, when can we expect to see the problemset and test data? I'm looking forward to solving them.

Could someone please outline the alternative solution to problem F, which doesn't involve Karatsuba or FFT.

Anyone wants to point out where I'm wrong instead of just downvoting to oblivion?

I'm fairly certain that some test cases for problem E of Day 5 are wrong (e.g., test 14)! Accepted solutions fail the following simple test case:

7 2
0 0
0 4
2 4
1 3
2 2
1 1
2 0
1 -1
1 6

The correct answer should be 21.656854.

Another keyword is a constricted set.

Nice to hear that I wasn't the only one 100% certain of my "proof" that 3 colors are all you need. :) However, I'm not that confident that 60 points will be enough ... but there's still hope.

Could you elaborate on the first problem. I don't see how your state in dynamic programming is sufficient. My understanding is that it's also important how the other gifts (those that were not added between the processed families) are distributed.

You can solve Problem 2 with dynamic programming in O(n). You can count the remaining three pairs from those with higher maximum numbers towards lower. Let's say that pair (x, y), x < y will be the largest. If you fix y, you can choose x from somewhere in the range 1..x'. When you'll have to choose the next pair (a, b), b<y, you know that the range of possible values for a will be 1..a', x' ≤ a'. Therefore, it doesn't matter which x was chosen in the previous step, only how many pairs were chosen before.

In fact you're solving a generalized problem f(k, n) of choosing k pairs from numbers 1..n such that their sum is at most c₁ + c₂. Time complexity is just O(kn). You either use n as a part of the largest pair or not. There are a couple of things to consider, like how to handle used values c₁, c₂ and make sure that x < y, but it can be done.

Use binary search over a sorted list of existing numbers from the table instead of an entire range [1,10^9]. This gives you O(log(n^2)) = O(log(n)) as mentioned in the editorial.

I disagree that all 4 requests are trivial. I'll give an example with k=3. Lets say we have the following request L1=3, R1=6, L2=5, R2=12. We divide it into two requests on level k-1: L1=3, R1=6, L2=5, R2=7 and L1=3, R1=6, L2=1, R2=4. These two requests are not trivial. You would have to go at least one step further to prove that you are left with just trivial requests in some small, constant number of steps.

I don't think it's that simple or perhaps I misunderstood something. You say that a single request on level p results in 4 requests on level p-1. This gives you exponential time complexity, not linear.