### Betlista's blog

By Betlista, 7 years ago,

In SRM there were 1303 registered participants — DIV1 562, DIV2 628 + 113 newcomers

### DIV2 — easy (250)

Ona have to return the length of binary number T/K without the zeros at the beginning.

### DIV2 — medium (500)

Greedy — check, whether after pair removal, the number of components is increased, if so, remove the pair. Return the number of such pairs.

### DIV2 — hard (1000)

Inspired by hippie (room 61).

DP: We can calculate for each AC, BC and CC (A count, B count, ...) and PC (Pair Count), whether it is possible or not. Once we know it is possible, we can run the same algorithm, to find the string.

### DIV1 — easy (250)

Same as DIV2 hard, but with only two characters instaed of three.

Note: as always I will write more detailed descripton a little later...

• 0

 » 7 years ago, # |   +3 DIV2 medium would have got accepted if done by brute force . otherwise it has a nice algo for it . see the comment of ping128 .( previous version of the comment )
 » 7 years ago, # | ← Rev. 2 →   +11 Div-2 1000 pointer :Here is my dynamic programming solution :- Let us define the state as follows:- (currentPos, A's till now, B's till now, pairsTillNow) with the meaning, can we reach state where we have exactly 'k' pairs and currentPos=n ?TRANSITIONS:- 1) Fill in 'A', to move to the state (currentPos + 1, A's till now + 1, B's till now, pairsTillNow). 2) Fill in 'B', to move to the state (currentPos + 1,A's till now, B's till now +1, pairsTillNow + (A's till now) ) 3) Fill in 'C' to move to the state (currentPos + 1,A's till now, B's till now, pairsTillNow + (A's till now) + (B's till now) ).If from the present state, any of the future state yields the value true, then the value of present state is true as well. Finally, a string can be constructed if the value of state (0,0,0,0) is true. After this, a simple backtracking can be done to get one of the required string(s).