Roundgod's blog

GP of Eurasia
By Roundgod, history, 5 years ago, In English

Let's discuss problems. How to solve 2,5,8 and 11?

  • Vote: I like it
  • +72
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

2 is the same dp as longest common subsequence.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain solution in more detail?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      My solution to 2

      We can do this in $$$\mathcal{O}(n^4)$$$ iterate a pair of vertices ( $$$(i,j)$$$ — first from upper polygon, second from lower) that we want to be connected. Then we can define $$$dp(u,d)$$$ to be the best arrangement of edges in segments $$$[i, u]$$$ in upper region and $$$[j, d]$$$ in lower region. Transitions are

      $$$dp(u,d) = min(dp(u-1,d), dp(u,d-1), dp(u-1,d-1)) + $$$ distance between last points

      In order to make it $$$\mathcal{O}(n^3)$$$ we can notice that each point in upper region must be connected with some point in lower region, so we can calculate this $$$dp$$$ only for $$$i = 0$$$ instead of all possible $$$i$$$.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

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:

$$$\begin{cases}V_x t = \Delta x,\\ V_y t - \frac{gt^2}{2}=\Delta y\end{cases} \implies \Delta y =\frac{V_y}{V_x} \Delta x - \frac{g}{2V_x^2} \Delta x^2$$$

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:

$$$\begin{cases}V_x = |V| \cos \alpha,\\ V_y = |V| \sin\alpha\end{cases}$$$

Putting this into initial equation we'll obtain:

$$$2|V|^2 \cos^2 \alpha \Delta y = 2 |V|^2 \cos\alpha \sin\alpha \Delta x - g \Delta x^2$$$

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

$$$|V|^2(1+\cos2\alpha) \Delta y = |V|^2\Delta x \sin2\alpha - g \Delta x^2$$$

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

$$$\begin{cases}A=-|V|^2\Delta y,\\B=|V|^2\Delta x,\\C=g\Delta x^2 - |V|^2 \Delta x\end{cases}$$$

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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We need to use long double to get AC. Also, notice that for fixed initial velocity there are two possible angles, you should always choose the parabola with higher angle.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used long double.. Didn't help somehow. :(

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +34 Vote: I do not like it

      I would say as a rule of thumb try to avoid anything looking like asin, acos or $$$\sqrt{1 - c^2}$$$ in your solution. This inevitably has precision issues when argument is near unit. Use atan2 if you can get both components or atan if you can only get the ratio, they don't suffer from precision issues.

      Most of jury solutions use ordinary doubles.

      P.S. x87 arithmetics must die already, and long double with it =)

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    No need to binary search.

    The smallest answer given two points $$$(0, 0), (x, y)$$$ is $$$v = \sqrt{g(y + \sqrt{x^2 + y^2})}$$$, $$$\tan \alpha = v^2 / gx$$$. Either all points are below this trajectory, or the answer is a parabola through three points $$$(0, 0), (x_1, y_1), (x_2, y_2)$$$ with parameters $$$\tan \alpha = \frac{x_1^2 y_2 - x_2^2 y_1}{x_1^2 x_2 - x_2^2 x_1}$$$, $$$v = \sqrt{\frac{gx_i^2(1 + \tan \alpha)^2}{x_i \tan \alpha - y_i}}$$$ ($$$i = 1, 2$$$ is unimportant since $$$\tan \alpha$$$ is obtained from equiating these two velocities). Choose the largest $$$v$$$.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Yep, that seems much simpler and having less precision issues, thanks!

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Test 6 is the test with maximum possible answer.

    For the condition that rock hits the eye and fixed velocity $$$V$$$, I substituted everything related to angle with its tangent $$$\tau = \tan \alpha$$$. Finally, I got the following:

    $$$ \frac{g X}{V^2} \tau^2 - 2 \tau + \left( 2 \frac{Y}{X} + \frac{g X}{V^2} \right) = 0 $$$

    This allows to find starting angle. Moreover, this equation is unit-less, and it is in fact rather clear what numbers $$$\frac{Y}{X}$$$ and $$$\frac{g X}{V^2}$$$ mean.

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Precalc the decision tree once. It's $$$\mathcal{O}(n^2)$$$ (the input bug vertex is irrelevant, complexity can be boosted even further with bitsets), AC.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there any way to prove that your solution always fits into 20 queries?

    The original idea was that you can provably reduce graph size at least twofold with one or two well-placed queries. This gives a hard upper bound that 20 queries is enough.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      You can always choose a vertex such that there are between $$$n/3$$$ and $$$2n/3$$$ vertices reachable from it. Just pick a root and go into it's biggest son until the number of reachable vertices is greater than $$$2n/3$$$. So, if this works, then greedily picking the best vertex on each step also works.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Even considering just the first part of the solution (find a vertex which minimizes the difference), we can prove that the size of the graph reduces to at most two-thirds. Because assume otherwise, all vertices have reachable sizes either < N / 3 or > 2 * N / 3, but for any vertex reachable(V) <= reachable(C1) + reachable(C2) + 1, and we get a contradiction.

      → Reply
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh so both accelerators also could deviate their axis only in $$$Oxz$$$

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it 
    FILE *in = fopen("input.bin", "rb");
int n, a[N];
fread(&n, sizeof(int), 1, in);
fread(a, sizeof(int), n, in);
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      You can also have

      int input[int(1e7)];
fread(input, 4, sizeof(input) / 4, fin);

      (it's a bit more convenient due to 1-based indices)

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +18 Vote: I do not like it

    For 6 do radix sort. Compress all the numbers to 0-index. Push all of them into the last bin and do radix sort by extracting numbers into the corresponding of the first 10 bins and pushing them back into the last one.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +73 Vote: I do not like it

    But why did they use that format?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +81 Vote: I do not like it

      I second this. If I calculated everything correctly, this compression reduces the maximum input size from 8MB to 4MB, and the maximum correct output size from 20MB to 16MB.

      Was this really worth it? Sorry, I can't see any reasons other than making the world a worse place.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +44 Vote: I do not like it

How to solve 10?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    First, let's change the strings into numbers. If we fix permutation of teams, we can greedily find the lowest possible number of the largest team (or $$$\infty$$$ if the permutation is not possible). We want to find maximum of this number across all permutations. Let's do it with subset dp. To find dp value for subset $$$S$$$ we try all possible last teams. If we choose team $$$i$$$ as last then the value is the lowest number that team $$$i$$$ has that is greater than $$$dp[S \setminus {i}]$$$. $$$dp[S]$$$ is the maximum of these values across all $$$i \in S$$$. Of course it's too slow for $$$n \leq 350$$$. But if $$$n > \sqrt{350}$$$, then answer is always no and you can change $$$n$$$ to 20.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      What is the minimum possible value of $$$K = \sum K_i$$$ that can produce "YES"?

      I guess $$$K = N(N-1)+1$$$, but I can only prove that $$$K \geq N(N+1)/2$$$.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        It is an open problem: OEIS A062714

        Also, you can read about the coNP-completeness of the problem 10 here link

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          Doesn't it say coNP-complete?

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How are these 2 problems equivalent? I can see some sort of resemblance, but I can't see any clear equivalence (or even implication). The main difference is that here you may use intermediate values and you ought to choose exactly one element from each part of a fixed partition of the sequence. I'm not sure if I'm missing something

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

            Sort pairs (name; id of the list)

            Now permutation can be a good order if you can find a subsequence of the second element in pairs that is equal to the given permutation.

            Of course, also you can convert any sequence to the instance of our problem.

            → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      I did about the same thing. How can you prove that if n > sqrt(350), the answer is no?We could only prove that N > 44 or something like that doesn't work (because then the max product of the sizes of the lists would still be smaller than N!).

      And in case N > sqrt(350) how do you find a permutation that can't be obtained? I've randomly generated permutations until one failed but I see no way of proving that there are enough many uncovered permutations for this to work in reasonable time.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        We proved for $$$N>25$$$, by each time choosing the set of words with the largest minimum valid value. It follows that $$$26+25+\dots+1=351>350$$$. Also, cases when $$$N>25$$$ can be easily constructed this way.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't prove it. My intuition was that to get all sequences of length $$$n$$$ we obviusly need $$$n^2$$$ elements. And getting all permutations didn't seem much easier.

        To find a permutation I solve the problem for the first $$$20$$$ teams and then add $$$21 \ 22 \ ... \ n$$$ to answer.

        → Reply
»
5 years ago, # |
  Vote: I like it -26 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Only Spencer was participating and not for the whole contest. :P

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Oops I would've taken it seriously if I knew that Ben and Zhezheng were on my team.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyway I can get case 6 of problem 10?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply