Betlista's blog

Betlista's TopCoder SRM 648 editorial
By Betlista, 10 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 )

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

→ Reply