Topcoder SRM 534; The one I didn’t participate in

UPDATE 3: Made change to the explanation of why the DP recurrence works.

UPDATE 2: Even though the DP recurrence for medium problem works flawlessly, I am now in doubt about the chain of reasonings I followed to prove it. If you can see the missing links, please comment. Until then, expect a 3rd update.

UPDATE 1 : Added a single dimension DP solution to medium problem.

Each month there is always one SRM whose timing just doesn’t suit me at all. The early morning SRM! And this SRM was one of those, a 7AM one for me. I either end up not performing well in such an SRM, or not participating at all. And this time it was the latter case. But I just tried it in practice room, and proves I would have done pretty well, as I was able to get both the easy and medium without much hassle. I didn’t bother with the hard problem yet.
Continue reading

Topcoder SRM 533; A disappointment

Just as the title suggests, this SRM was a bitter disappointment for me. The easy problem was easy, but it took me some time to come up with a simplified solution. I made up for this delay with a successful challenge in the challenge phase. But the sad part was the medium problem. By reading the problem statement, I instantly knew it was a DP, and that the greedy solution won’t work. Part of my jumping straight to a DP solution was because of my current love for DP problems and thus being always preoccupied with a solution containing DP. But alas, things didn’t work as planned…
Continue reading