Can you share the tasks? The analysis mode is not operating.

It should be in: http://cms.boi2019-online.eio.ee/tasks/something/statements/en (replace "something" to flash, nautilus, and valley). But currently 504 Gateway Timeout.

Day 1 problem statements: http://fpaste.dy.fi/R6K

I can't believe I didn't think of this.

Root the tree at E.

Let x and y be the 2 vertices on the queried edge. You can escape iff at least one of them isn't an ancestor of r, which you can check quickly with binary lifting.

To find the minimum distance, let dp[i] be the minimal distance to a shop that is in the subtree of i, and let h[i] be the distance from i to the root E. We need to find min(dp[i]-h[i])+h[r], where i is any ancestor of r that is under both x and y. We can find this again with binary lifting.

Take $$$E$$$ as the root of the tree. Suppose the edge $$$(a, b)$$$ was removed, where $$$a$$$ is $$$b$$$'s parent, and you are at node $$$u$$$. You you can reach $$$E$$$ iff $$$b$$$ isn't an ancestor of $$$u$$$ (we can check that by seeing if $$$lca(u, b) \neq b$$$).

For the case where $$$b$$$ is $$$u$$$'s ancestor, calculate for each vertex $$$v$$$ the distance to the closest shop in his subtree with a dfs and call this value $$$sub(v)$$$. Now, the answer to the query will be $$$min(dist(u, w) + sub(w))$$$, for any $$$w$$$ that is an ancestor of $$$u$$$ whose depth is greater than or equal to $$$b$$$'s depth.

We can calculate this using binary lifting on values ($$$sub(v)-dist(E, v)$$$) for each $$$v$$$ and then adding $$$dist(E, u)$$$ to the minimum value found.

Even if E is not fixed and given with query, we can solve this problem with time complexity O(Q log^2 N) by centroid decomposition + segment tree (I solved this problem with this method)

Already

The solutions for problems from day 1 have already been posted in the official website.

Some thoughts: your solution and the official solution use the same idea, with 'addition mod 256' playing the same role as 'xor', and the block size $$$k=8$$$ replaced by $$$k=11$$$. This idea should be very close to achieving the theoretical upper bound, except for the step where you have to divide into $$$m/k$$$ subproblems. The reason it's close is because if we have $$$z$$$ 0s left, then we should except to need to write $$$o$$$ 1s, where $$$o$$$ is minimal such that $$${z \choose o} \approx 2^m$$$. I assume the dp used to calculate $$$P$$$ just makes this idea more precise. Assuming our decoding function is 'sufficiently random', we shouldn't need to write much more than $$$o$$$ 1s, and the dp makes sure that we don't write more 1s than necessary. But the subproblems part messes with this analysis, and also introduces another problem: As soon as one subproblem fails, we can't write any more data. So we don't want too many subproblems, I think.

Here is a variant that should let you increase $$$k$$$ from 11 to about 16: Instead of doing dp (which is $$$O(z2^k)$$$), use meet-in-the-middle ($$$O(2^{k/2})$$$, more or less): enumerate the smallest subsets that we can choose, and check if we can combine (i.e. xor) two of them to get the desired result. (Now it is important that we use xor rather than addition mod $$$2^k$$$, because otherwise we might need to write 2's.) For birthday reasons, once we've enumerated about $$$\sqrt{2^k}$$$ subsets, we can expect to be done. Using a map for lookups seems to be too slow when $$$m=16$$$ and $$$b$$$ is small, but vector worked fine. (At least for $$$m=16$$$; I haven't tried the 'divide into subproblems part.)

It would be nice if we could always take $$$k = m$$$, but it seems hard. (If $$$m$$$ is big enough, and $$$b/m$$$ is not too big, then I guess that instead of dividing into subproblems we might want use Gaussian elimination to 'write a subset of size about $$$m/2$$$' rather than 'the smallest subset'.)

Anyway, a very nice problem!

C++ compiler is just too smart. We noticed that if you write the 66p solution in a rather clean way (from the compiler's point of view — such as not put if statements inside innermost loops etc), and then add pragmas, the result is almost as fast as the official bitset solution. This would pass for example: https://ideone.com/Xf7Ybh

On my pc,

• this solution: 0.3s with pragmas, 1.6s without
• An official bitset solution: 0.15s with pragmas, 0.26s without

(YMMV with the exact runtimes, but notice the tiny difference between 0.26s and 0.3s)

Test sets are given on the contest's website.

I'm afraid making Flash available online somewhere may prove difficult — as far as I know, the task is a complete nightmare from a technical standpoint. There is a testing script included with the test set, maybe it's possible to include one that more closely simulates the contest.

Ah shit, here we go again.

You can listen to this while waiting ;)

We should find the longest $$$a + b$$$ where $$$s[i-a, i) = t[j, j+a)$$$ and $$$s[i, i+b) = t[j-b, j)$$$. So, if we fix $$$i$$$ and $$$j$$$, we can independently calculate the largest $$$a$$$ and $$$b$$$. If we do naively and use rolling-hash, we can calculate maximum $$$a$$$ and $$$b$$$ in $$$O(n)$$$, so it takes $$$O(n^3)$$$ overall.

But we can speed-up this approach. It means we can get maximum $$$a, b$$$ in $$$O(1)$$$. We can use DP and let $$$dp_A[i'][j']$$$ the maximum $$$a$$$ when $$$i = i'$$$ and $$$j = j'$$$. Also same for $$$dp_B[i'][j']$$$. We can calculate this DP in $$$O(n^2)$$$. We can reduce memory, by typical approach, "reusing" DP array, because we only need $$$dp_A[i' - 1][?]$$$ for calculating $$$dp_A[i'][j']$$$, and so on for $$$dp_B$$$.

National teams consisting of 6 contestants per country. Countries participating are nations next to the Baltic sea. Teams are selected through their country's respective national olympiad.

Good luck with implementing Flash, you have our blessing. :D