Блог пользователя wuhudsm

Автор wuhudsm, история, 8 месяцев назад, По-английски

A Minimum Black Cells

Idea:wuhudsm

code
solution

B Sequence Duplication

Idea:wuhudsm

code
solution

C Perfect Square Matrix

Idea:wuhudsm

code
solution

D Tree Merger

Idea:wuhudsm

code(solution 1)
code(solution 2)
solution1
solution2

E RBS Score

Idea:wuhudsm

code
solution

F Too Many BSTs

Idea:Yugandhar_Master

Solution:wuhudsm

code
solution
Разбор задач TheForces Round #28 (Epic-Forces)
  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
8 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

O(1) solution for A Minimum Black Cells

  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    solved it the same but you can remove the min since the constraints on k is <= 2*n-1 so it wont go above n*n anyways.

»
8 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

the quality of this round was insane!! i love TheForces

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wuhudsm Can you please tell where I can practice similar Tree Merging problems just like Problem D?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution for E.

As explained in the editorial, we need to find the changes when $$$p_i$$$ and $$$p_{i+1}$$$ differ. The change in $$$S_{p_i}$$$ is always +2 or -2. For simplicity let's take the case of +2. The other will be just inverse of that.

Now only those (l, r) pairs will change where l < $$$p_i$$$ < r, $$$S_{p_i}$$$ <= $$$S_l$$$ = $$$S_r$$$ <= $$$S_{p_i}$$$ + 2 and min($$$S_l$$$, $$$S_{l+1}$$$, ... $$$S_r$$$) = $$$S_l$$$ = $$$S_r$$$. This becomes a case by case scenario for $$$S_{p_i}$$$, $$$S_{p_i}$$$ + 1 and $$$S_{p_i}$$$ + 2 (Let's name these values $$$T_{p_i}$$$). The changes only depend on the no. of pairs (l, r) we lose or gain by this operation. This number can be calculated based on the frequency of suitable positions on the left and to the right of the $$$p_i$$$.

Now, how to calculate these values. We can store the occurrences of each value in an ordered set which we change with every swap. Since, the difference in $$$S_i$$$ and $$$S_{i+1}$$$ is always 1, we look for the latest occurrence of $$$T_{p_i}$$$ — 1 less than $$$p_i$$$. Now, we just have to calculate the no. of occurrences of $$$T_{p_i}$$$ in this range. The frequency on right can be calculated in the same way. The rest is just manipulating the answer based on the whether $$$S_{p_i}$$$ is decreasing or increasing. Don't forget the case where l or r can be equal to $$$S_{p_i}$$$.

The solution works much faster than the one provided in the editorial. You can look at my solution for reference. I couldn't find a direct link for my submission, so unable to provide the link here.