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...
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 )
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).