I didn’t understand half of what you wrote🤣
But it was pretty fun to read XD
No i meant that part for the editorial, sorry. I managed to implement the O(n^2) but struggled to implement the lca dp.
Oh right - hopefully my commented cpp implementation plus @tmwilliamlin’s pending write-up will help to clear up any confusion
Hotels from POI XXI is very similar to this problem, and although an O(N^2) solution is good enough to solve it, one of the tester’s solutions is O(NlogN). This solution can be found here. I’ve used this code to solve the problem, and on skimming through some other contestant’s solutions, it seems a few of them have as well. Just want to bring this up before I’m accused of plagiarism.
The POI problem has an increased data range version on BZOJ.
Well written. Never could have thought that the story behind setting a problem could be so interesting!
For those who haven’t seen it, I created a video solution as a substitute until I finish writing up the editorial.
Editorial finished and updated!
That’s not mine - that’s the Tester’s again (which, admittedly, I submitted - but only to check its progress against the current testcases ) Mine is in the first reply to this thread.
Oops, I took whatever the best submissions page on campus showed me lol
Hehe
Updated with related problems
+1 happens wayy too often with me XD
Yes
In editorial i did not understood following :
dp1_v,j+1 = dp1_v,j (and dp1_v,0 = 0) .
In above line , if dp1_v,0 = 0 then by equality dp1_v,j+1 = dp1_v,j , dp1_v,j = 0 for all j which is not possible .
Also i did not understood how you got dp1_v,j+1 = dp1_v,j . Suppose take following tree :
suppose vertex 1 is root .
for vertex ‘v’ marked , number of legs of length 1 from v is 2 whereas number of legs of length 2 from v is 3 .
dp1_v,j is the old value
if you just explain the following i may get enough hint to understand .
according to point C , dp2_u,j = dp1_v,i * dp1_u,i . Let us take following graph , then let us take leg p1 and leg p2 of length 2 from u and v respectively . How they form fork ?
that happens when we combine into u