The editorial is "ready" (I am legally bound to put ready between quotes).
Check it out at: http://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+1B
It was a fine problem set. It was easier than 1A as expected. But I still managed to make a very lame mistake in the hard problem in my first try (Forgot about the last character in odd strings). I would have scored 245 + 433. This is not counting for the usual nervousness that strikes me during a real match. I am not sure if it would make my scores worse or better. I solved 500 with dynamic programming the first time, it was overkill.
I spent all my clear-brain time this afternoon trying to think of a good argument to prove 250. Everyone seems to know to use that solution. But at least to me it is hard to find out why it works. It is *not* something as simple as pairing min with max minimizes the maximum" , because in an example like: 1,7,7,8, the pairs are 1+8, 7+7, note how the maximum is in the middle this time.
I am also going through tons of stress related to a loved one being sick. So I thought it was better to finish the editorial quick and maybe later when/if I find the proof update the editorial, instead of waiting too much before releasing it (Must focus). Hopefully the editorial is not awful.
3 comments :
>> Everyone seems to know to use that solution.
Not really. It was intuitive but I thought there was a catch and solution may fail systest. Since N can be atmost 50, can't we simply bruteforce for all possible values ?
Looking forward to the proof.
Could you give the solution for 500 using dp please?
You have a set of elements you want to remove.
Like ---x---xxxx-xx--- , you want to remove the xs. We represent this as a bitmask: 00010001111011000_2
f( mask ) finds the minimum number of steps.
Base case: mask == 0, then we need 0 steps.
Then we can do this: Pick i - position which we use to remove the L consecutive spaces.
You modify the mask and replace the L bits starting at i with 0s. This new mask is a new case that we can call f(new_mask). The final result is 1 + min( f(new_mask_i)) for each i.
Post a Comment