-Wave-'s blog

Yandex.Algorithm Final
By -Wave-, history, 4 years ago, In English

Congratulations to tourist, ksun48 and Um_nik!

Is an editorial available anywhere? I'd be interested in C and F, specifically.

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

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

I have the following solution for second subtask of D:

I go from left to right:
if only two digits left I check what's better just concatenation ab or a**b
if the first digit is not 1, I'll ** after it and solve for the suffix
if the first digit is 1, I'll set ** after second digit and solve for the suffix

Now, if the last group consist of only digit and this digit is 1, I unite two last groups.

Any hints where it gives wrong answer?

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

C:

The answer to the query $$$(v, u)$$$ is $$$dist(v, u) - \max(0, 2 \cdot len - dist(a, b))$$$, where $$$len$$$ is the length of intersection of paths $$$(v, u)$$$ and $$$(a, b)$$$. Therefore, to get answer to the query less than $$$dist(v, u)$$$ we have to choose $$$(v, u)$$$ such that the path covers more than half of the path between $$$(a, b)$$$.

Root the tree in some leaf, now every vertex has no more than 2 sons. The path $$$(a, b)$$$ has some LCA $$$c$$$ and (at most) two downwards paths from it. Let's say that $$$a$$$ is the lower end. Query $$$(root, v)$$$ for each v. If $$$a$$$ is strictly lower, then answer for all $$$v$$$ in subtree of $$$a$$$ will be smaller than $$$dist(root, v)$$$, and the difference will be max for them, so $$$a$$$ is just the highest of vertices with greatest difference. When we have found $$$a$$$ we can just try all the $$$b$$$.

So now $$$a$$$ and $$$b$$$ should have the same height. One way to choose $$$(v, u)$$$ such that the path covers more than half of the path between $$$(a, b)$$$ will be to choose $$$v$$$ in subtree of $$$a$$$ and $$$u$$$ in subtree of the other son of $$$c$$$ (for example, just take that other son). So, let's try all possible $$$c$$$, and try all the $$$v$$$ from one of the sons. We can restrict $$$v$$$ to leaves, and if we will traverse the smaller (by the number of leaves) son the number of queries will be $$$L \log L$$$ where $$$L$$$ is the number of leaves. Since degrees of all vertices are at most 3, $$$2n - 2 = \sum_{v} deg_{v} \le L + 3(n-L) \Rightarrow L \le n/2 + 1$$$. Now we have found some good $$$v$$$, move it up until the decrease in distance remains the same. When we stop, we have arrived at $$$a$$$.

So, the number of queries should be bounded by $$$\frac{n(\log n + 5)}{2} + O(\log n)$$$

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

    Thanks for the solution, nice problem. I thought that $$$O(n \log n)$$$ queries would be too much but didn't realize that $$$L \log L$$$ fits.

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

I had strange TL in B using unordered_map<ll, int>. After change it to map I got AC with 0.2s time. How could this possible?

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

Could anyone share the solution for F?

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

    Let us decide that all odd cycles must pass through the single vertex — root. Now you need to construct something like a DAG of paths of the same odd length ($$$k + 1$$$ or $$$k + 2$$$) from root to root such that when you take any $$$k$$$ colors the path doesn't exist but when you take any $$$k + 1$$$ colors it does. The simplest construction which requires too many edges is to use separate paths for each set of $$$k + 1$$$ colors (duplicating some edge to get the old length if necessary). You just need to find more compact construction.

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

      Thanks!

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

      Well, that's like explaining the problem statement only. The real difficulty is to find that more compact construction, right?

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

        It is much easier to reason about paths in a layered DAG than bipartite graphs.

        The difficulty is that not all DAGs work because edges are not oriented.

        → Reply