Hello, Codeforces community.
It is winter in Bangladesh and in Toph, a traditional long contest named Tough Winter Spar is currently ongoing. There are 10 problems in this contest to be solved in 10 days, and the difficulty was intended pretty hard.
Although the contest already started before, the last 2 problems were unlocked an hour ago, and I believe you might enjoy solving the problems of this contest, thus this post.
The problems of the contest were authored and reviewed by mainstring. fsshakkhor, 0pangktey0, rebornplusplus, souravvv, Mohaimin66, Hasinur_, ishtupeed, Muhimin_Osim, upobir, TarifEzaz, hjr265 and myself.
We look forward to your participation and hope that you find them useful for practice, best of luck in the contest.
Google OAuth is not working on Toph atm and I am also not able to request password
Hey Egor, I can help you with that. Can you please send an email to [email protected] from the same email address which you have used for your Google Account? This will let me verify and restore your access to your Toph account.
Actually seems like OAuth is working again, but thanks
When will editorial get published :)
Quite soon, hopefully.
Also, if you want to discuss about any specific problem, may be you can comment about it here and someone might be able to help as well.
Has it been published? I can't seem to find it.
Sorry, it wasn't :/
Wrong handle for Rafid(reborn). It's rebornplusplus
Fixed.
How to solve B and J?
Can't help you about B.
As for J, here is what setter wrote in editorial section which will become public soon:
We’ll hash both the array A and the frequency array. p
Maintain a segment tree to hash the array A. The update operation is just a point update in segment tree. Can be done in O(lg(n)). Also to find the hash value in the [L, R] subarray, just query in the segment tree.
Also, maintain a global frequency array. We will hash this array the same way we did with previous array, using a segment tree.
Now using a technique called DSU on tree a.k.a Sack, we can compute the frequency array at each of the vertices. In other words, we can compute $$$F_v$$$ for each v in O(n*lg(n)) time. So all we have to do is get the hash value of this array using segment tree.
Overall complexity: O($$$n*lg^2(n)$$$)
My alter solution used same algorithms and had same time complexity. But there is a n*lg(n) solution as well that another alter wrote, I will leave that for your thinking for now.