2 is the same dp as longest common subsequence.

For problem 7 I had the following approach:

Let's do binary search on the answer $$$|V|$$$ where $$$V=(V_x;V_y)$$$ is needed initial velocity.

The equation of the parabola might be found from the system of equations:

This equation might be as well rewritten as $$$2V_x^2 \Delta y = 2V_x V_y \Delta x - g\Delta x^2$$$. Now we should find those $$$(V_x;V_y)$$$ that it also holds that $$$V_x^2+V_y^2=|V|^2$$$. Solution to this equation may be reparametrized as:

Putting this into initial equation we'll obtain:

Now we should move from $$$\alpha$$$ to $$$2\alpha$$$, thus obtaining linear equation:

Which may be rewritten as $$$A \cos 2\alpha + B\sin 2\alpha = C$$$ where:

From this equation $$$\cos 2\alpha$$$ and $$$\sin 2\alpha$$$ may be almost uniquely determined if we additionally consider $$$\cos^2 2\alpha + \sin^2 2\alpha=1$$$. We may return to $$$\cos \alpha$$$ and $$$\sin \alpha$$$ as $$$\cos\alpha = \sqrt{\frac{1+\cos 2\alpha}{2}}$$$ and $$$\sin\alpha = \pm \sqrt{\frac{1-\cos 2\alpha}{2}}$$$.

Only thing left to do now is to check that for each point $$$(x_i;y_i)$$$ our parabola determined by the equation $$$\Delta y = \frac{V_y}{V_x} \Delta x - \frac{g}{2V_x^2} \Delta x^2$$$ lie higher than $$$y_i$$$ for every point $$$x_i$$$. I implemented this solution, but unfortunately got WA on test 6. Is this more likely to be a precision issue or I have some mistakes in the logic of solution?

How to solve 4. My idea was finding the node that maximize information (the number of nodes to discard) in the worst case, but to find this node I used heavy computations with bitsets that got TLE on test 10.

Our problem 4 solution

Precalculate reachability matrix ($$$R(u,v)$$$ is $$$true$$$ IFF there exists a path from $$$u$$$ to $$$v$$$)

For each bug we can maintain list of all candidate vertices that cause this bug. As we only have binary queries, for some candidate $$$x$$$ we can split all other candidates into two groups depending on answer about $$$x$$$. In order to reduce amount of candidates as fast as possible we want to ask about such candidate $$$x$$$ that will minimize the difference between two groups. Let's find optimal candidate in $$$\mathcal{O}(candidates^2)$$$ This solution already gives $$$\mathcal{O}(T \cdot n^2)$$$.

To optimize it further we can see that our information is very limited, we only have $$$20$$$ queires with binary answers and a starting position. And our questions are determined with sequence of previous answers. We can memorize this information with perfect binary tree, starting at root for every new bug and moving left with each $$$good$$$ answer and right with each $$$bad$$$ answer. Each vertex in this tree will have predetermined list of candidates and optimal candidate $$$x$$$. We can precalculate such tree in $$$\mathcal{O}(n^2)$$$ or in $$$\mathcal{O}(n^2 \cdot log(n))$$$ if we are storing explicit list of candidates in each node. Or we can calculate this tree lazily.

But it seems that to be able to start from every vertex we need $$$\mathcal{O}(n)$$$ such solving trees resulting in $$$\mathcal{O}(n^3)$$$. However we can safely discard information about starting vertex and think that we always start from the last vertex and it is guaranteed to be reachable from any previous vertex, this gives $$$\mathcal{O}(n^2)$$$ solution, possibly $$$\mathcal{O}(n^2 \cdot log(n))$$$, with some additional time $$$\mathcal{O}(T \cdot Q)$$$ to answer queries using this tree.

Problem 8 solution.
If $$$\phi$$$ is current angle of rotation, then each detector calculates $$$\lambda cos(\phi + \delta) + \beta$$$. Since $$$\phi\in{0, \pi/2, \pi, 3\pi/2}$$$, this gives us the following equatons:
$$$x_1 = \lambda cos(\delta) + \beta$$$
$$$x_2 = -\lambda sin(\delta) + \beta$$$
$$$x_3 = -\lambda cos(\delta) + \beta$$$
$$$x_4 = \lambda sin(\delta) + \beta$$$
So we can obtain $$$\lambda, \delta, \beta$$$. Knowing these numbers, we can compute $$$cos(\phi), sin(\phi)$$$ for each query and restore the angles.

11: consider the set $$$I(d)$$$ of all points inside the polygon at least $$$d$$$ away from its boundary. One can maintain the boundary of $$$I(d)$$$ as a set of initial sides shifted by $$$d$$$ with events "a side is eliminated by its two neighbours". Once all sides of a single color are eliminated completely in $$$I(d)$$$, print the only vertex of $$$I(d)$$$ of that color.

Can Anyone explain fucking input in the problem 5 ??? We got wa1 -_- and how to solve 10 and 6 ?

Are we the only one who got "check failed" verdict on problem 5? Anything we submitted on that problem got the same verdict.

How to solve 10?

Is it true that Benq is on 125th place? Like, how?

Худший контест, который я писал... Мне кажется, авторам лучше заниматься чем-то другим, явно не составлением задач. Никогда больше не буду писать всесиб!

Anyway I can get case 6 of problem 10?

What's the trick in problem 5? Why do some teams have +13?