### -Wave-'s blog

By -Wave-, history, 3 years ago,

Congratulations to tourist, ksun48 and Um_nik!

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

• +48

 » 3 years ago, # |   0 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**bif the first digit is not 1, I'll ** after it and solve for the suffixif 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?
•  » » 3 years ago, # ^ |   +50 Can you make 21**9?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 No, I can't. thanks.
•  » » » 3 years ago, # ^ |   0 Wow, thanks.
•  » » » 3 years ago, # ^ |   +61 There are problems with corner cases and there are problems where corner cases have corner cases...
 » 3 years ago, # |   +28 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)$
•  » » 3 years ago, # ^ |   +10 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.
 » 3 years ago, # |   0 I had strange TL in B using unordered_map. After change it to map I got AC with 0.2s time. How could this possible?
•  » » 3 years ago, # ^ |   +10 I don't know the tasks, but is some anti-hashmap test possible?
•  » » » 3 years ago, # ^ |   0 I used different reserve constants, may be it is not enough
•  » » » » 3 years ago, # ^ |   0 I have WA5 in B. Any ideas?
•  » » 3 years ago, # ^ |   +20 I think your solution TL's due too many calls of map.clear(). (seems it's your one)
•  » » » 3 years ago, # ^ |   0 Could you please provide tests for this problem?
•  » » » » 3 years ago, # ^ |   0
•  » » » » » 3 years ago, # ^ |   0 Yes, you right, code with 250k unordered_map clear works 16s.
 » 3 years ago, # |   0 Could anyone share the solution for F?
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 Thanks!
•  » » » 3 years ago, # ^ |   +10 Well, that's like explaining the problem statement only. The real difficulty is to find that more compact construction, right?
•  » » » » 3 years ago, # ^ |   +10 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.