Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.
2033A — Sakurako and Kosuke
Video
2033B — Sakurako and Water
Video
2033C — Sakurako's Field Trip
Video
2033D — Kousuke's Assignment
Video
2033E — Sakurako, Kosuke, and the Permutation
Video
2033F — Kosuke's Sloth
Video
No G?
it's the same as this problem https://codeforces.net/problemset/problem/1904/E
Where is G?
plz tell me when Tutorial (en) will appear,thx
How this got hacked on tle https://codeforces.net/contest/2033/submission/287798279 ? Pretty sure this is O(N) only.
ump's hash collision
unordered_map has a worst-case time complexity of O(n), I think the hacker used that. Use map instead of unordered_map
In your code, add the following line
mp.reserve(n << 1), mp.max_load_factor(0.7);to reduce the number of rehashing and space allocation operations.thnx.
Now that's hacked, too. Can override the hash function, see https://codeforces.net/blog/entry/62393
Hi,in problem F I dont get the part why the length of the period is O(k) can someone elaborate on that?
check https://en.wikipedia.org/wiki/Pisano_period
downvotes is crazy
Most of them in top 10 of the official standings have cheated. No doubt about it. I feel useless doing contests now...
G can be solved with binary uplifting. For each v,k there are 2 way: travel from v to the lowest leaf in the subtree at v; or move up k0 <= k ancestors and travel down.
Use binary uplifting for when moving up.
Can you explain more?
With binary lifting I understood that I need to reach the _k_th ancestor of vi in logn. Then need to find the deepest node from that _k_th ancestor excluding vi.
How to do this excluding?
First, for each node, we calculate the deepest child, the parent, the longest path if moving up the parent and down another subtree. So we have all calculated k=1 for all nodes. For each node i, if kth ancestor is j, we have: 2*k th ancestor of i = kth ancestor of i; max_path_from_i_up_to_2*k = max(path_from_i_up_to_k, k + path_from_j_up_to_k).
For binary lifting we travel up the ancestors and update the longest path.
c is much harder than d e f...
C is simple
https://codeforces.net/contest/2033/submission/287733495