SRM 518

SRM 518

Today I did the SRM 518 and it was pretty fun.

As usual, I started at the 250 points problem that seemed easy and I tried to do it the smart way, by calculating how much was repeated at the end of the string and trying to fill just what was needed. Turns out I implemented it wrongly and spent most of my time on it without success. Then I figured: "wtf, this is so easy", and started from scratch. All I did then was concatenate last i elements to the string and checking if the resulting i-end was equal to the first i-len characters and that did the job. :)

Then on the 500 points the solution was clear at first sight. Just go thru the string and get the higher value char on each step until you can't add more chars to the result. That could be the 250 points problem and it would be just as fair in my opinion.

Now the 1000 points problem. When I first saw it I thought I would not be able to do it. There were only around 20 minutes left to end the match and I had no idea where to start. Then I stepped out, grabbed a cup of coffee and started to think how to do it again. Picked up pen and paper and scratched an idea. Five minutes later I had the solution and coding it took about 1 minute. :)

Basically, I thought if it was possible to calculate the number of heads on each step and how to get the number of heads on the next step. Turns out it is very easy too. The number of heads on step i will be the number of heads of step i-1 - the number of heads turning into tail + the number of tail turning into heads. The same can be said to the number of tails on step i.

The formula for the new heads goes like this:

  h_i = h - h * a[i] / n + t * a[i] / n

  t_i = t - t * a[i] / n + h * a[i] / n

Then just assign h = h_i and t = t_i for the next step calculation and you are done. Easy, right?