I_love_ProParThinkNot's blog

Invitation to The Tough Winter Spar 2019
By I_love_ProParThinkNot, 4 years ago, In English

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.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Google OAuth is not working on Toph atm and I am also not able to request password

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually seems like OAuth is working again, but thanks

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will editorial get published :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wrong handle for Rafid(reborn). It's rebornplusplus

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B and J?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply