Hello codeforces!
With the conclusion of APIO 2020, we have compiled an unofficial editorial for all 3 problems.
Credits to bensonlzl oolimry for helping with the compilation. The editorial can be found at the following link:
https://drive.google.com/file/d/1ZZIUOhvEl-sldF9eY8HSjTMnusHsbGsM/view?usp=drivesdk
Special thanks to APIO committee for an interesting problemset this year!
Does anyone have a solution that is lesser than O(n sqrt(400000)) for A? or is official solution also that .-.
Oops, I wasn't able to pass this approach for C ... I think this should work (for $$$N\le 500$$$) but I'm not sure why this takes care of the "edge" cases.
EDIT: Nvm, I see why it works.
It doesn't work :(
Edit: I didn't read the code — this approach does work (it just uses too many queries in this instance)
For the edge case, here's what I did.
Terminology: Let the centroid be R, the subtrees be X,Y,Z. wlog let X be the biggest subtree.
This edge case occurs is at the point where SZ(X) = SZ(Y) + SZ(Z) + 1, we are currently in subtree Y, where ht(X) < ht(Y) < ht(Z). In this case, we will jump from Y, then to X, then to Z.
However, we cannot do this as ht(Z) + ht(X) > ht(Y) + ht(X). To resolve this, we make an additional jump from Y to Z.
This is my implementaton:
Edit: tidied up my code a little bit, https://pastebin.com/Fq3hDrGB
Does anyone know when are they releasing the results?
Friday, 21 August 2020 19:00 (UTC+7) is the closing ceremony
Is B solvable with MST?
Yes, but it is a bit simpler.
I think there is a solution that uses kruskal reconstruction tree to solve the problem
Is there any place to submit solutions yet?
https://tlx.toki.id/problems/apio-2020