The art of know all the required tricks, and just “getting” the problem, and writing the solution. I have so much to learn.
I entered TopCoder SRM 258, and end with a zero score for the second time. But this time at least I submitted a problem that I thought worked. My score is was not too affect this time and I’m still in Division I. I plan to turn the slope of this graph around.
The first problem was calculating the interest rate given the start price, monthly payment and number of months. I’ve done a lot of self discovery in the finance area driving by our (Michaela and me) desire to purchasing a house. The problem reminded me of my book of formula’s so much I couldn’t get over it and just write a program to solve this problem. So after the event was over last night I worked on it. I almost had it solved correctly, but the way I was generating the correct interest rate was ugly (it just required a binary search due to the limit of 0% to 100% stated in the problem) and the exit conditions. The latter was a bigger issue. The problem stated 1e-9 precision, so I comparing the money owning at the end of the term to 1e-9 not the interest rate. So using the binary search also solves that problem.
The second problem was a compression problem. The problem that got my code rejected was a challenge of “ASD”. Although the problem stated the input was from 1 to 50, I had thought that the two compression keys needed to be unique, thus my inner loop would not use the same key as the outer loop. There was also a problem where my inner loop was from 0 to n-1 not n as it should have been. But looking at other peoples solutions I worked out that one correct way was to use Dynamic Programming, which I had been reading about that morning. So failing to spot the change to use it make me feel a little silly, but boy, from now on, DP is going to be on my check list.
The third problem was a really hard DP problem. Work out the probability of each play (1-4) winning a game of snakes and ladders (though they used a different name). That just messed with my head. But the people that did get it had very compressed but elegant solutions. Another learning opportunity.
Anyway the first two problems were opened, read, coded, tested in 5 minutes by the best people, so I’m just thinking they really grok there comp sci algorithm courses.