Please read the new rule regarding the restriction on the use of AI tools. ×

wuhudsm's blog

By wuhudsm, history, 7 months ago, In English

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
  • Vote: I like it
  • +32
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

O(1) solution for A Minimum Black Cells

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.