# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
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?
Can you make 21**9?
No, I can't. thanks.
Wow, thanks.
There are problems with corner cases and there are problems where corner cases have corner cases...
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)$$$
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.
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?
I don't know the tasks, but is some anti-hashmap test possible?
I used different reserve constants, may be it is not enough
I have WA5 in B. Any ideas?
I think your solution TL's due too many calls of map.clear(). (seems it's your one)
Could you please provide tests for this problem?
Sure, https://yadi.sk/d/F0Mz2kSwJdsCcQ
Yes, you right, code with 250k unordered_map clear works 16s.
Could anyone share the solution for F?
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.
Thanks!
Well, that's like explaining the problem statement only. The real difficulty is to find that more compact construction, right?
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.