CHGORAM2 - Editorial

I didn’t understand half of what you wrote🤣
But it was pretty fun to read XD

3 Likes

Which implementation details - the O(N^2) version? If so, here it is :slight_smile:

2 Likes

No i meant that part for the editorial, sorry. I managed to implement the O(n^2) but struggled to implement the lca dp.

1 Like

Oh right - hopefully my commented cpp implementation plus @tmwilliamlin’s pending write-up will help to clear up any confusion :slight_smile:

1 Like

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.

2 Likes

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! :slight_smile:

1 Like

For those who haven’t seen it, I created a video solution as a substitute until I finish writing up the editorial.

5 Likes

Editorial finished and updated!

4 Likes

That’s not mine - that’s the Tester’s again (which, admittedly, I submitted - but only to check its progress against the current testcases ) :slight_smile: Mine is in the first reply to this thread.

2 Likes

Oops, I took whatever the best submissions page on campus showed me lol

2 Likes

Hehe :slight_smile:

Updated with related problems

1 Like

+1 happens wayy too often with me XD

2 Likes

Is the current setter’s solution yours @ssjgz?

1 Like

Yes

1 Like

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 :

https://imgur.com/a/vNUPCsm

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

1 Like

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