Saturday, March 02, 2013

Another week another TCO 2013 editorial: 1B

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 :

wolfwood said...

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

Miki said...

Could you give the solution for 500 using dp please?

vexorian said...

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.