SRM 560
So, I did not like SRM 561, or specifically I did not like what I did in it (So much that I didn't even want to write the editorial). It is actually very tiresome to spend some little extra time debugging a solution for an easy problem and then getting penalized for solving it. Most people in that match solved only that problem, so speed was the only difference in there. And that blows.
I think made exactly the same paragraph in the past, but I am tired of this lame situation, I don't want my matches to depend only on the easy problem anymore. Therefore, from now on (or until I get bored of the strategy) I will only open div1 hard and div1 medium until 10 minutes before the end of the match, then I will open the div1 easy. If I solve div1 easy under 10 minutes, that would be a good score. If not, then so be it, 0.00 score, but knowing topcoder, if I take more than 10 minutes in div1 easy, then it is a bad result anyway.
SRM 561
So, time to apply that strategy. That match was not great for such a suicidal strategy...
I opened div 1 1000, oh so something with trees? I thought it was going to be some sort of dp. But a complicated one. The idea that rng_58 eventually shared with me is far more elegant and mathy. It was a good thing I decided not to give it a try to code my (possibly wrong) initial dp idea.
I immediately opened div1 550. And I thought I could solve it. I had most of the correct ideas to solve it (See it as a tree, if you remove a node a forest remains). But my knowledge of nimbers was ... null. Somehow I never learned that stuff. So I tried to use a game theory dynamic programming, unfortunately, without knowledge of nimbers, you do not know how to combine games into a single game in which you can play each of the sub-games at choice... For some reason I assumed that you could finish one of the games and then go on. This was a wrong assumption. I coded something that was of course wrong, although I initially thought it was wrong because of code mistakes and not because of the idea...
Until there were less than 10 minutes left... I opened the 250 points problem to find out the problem statement was huge. Once I finally understood what to do, I knew I was not going to finish in time. It required quite some long code and I had only 4 minutes left... I still tried and failed.
I wrote the editorial I wonder how noticeable it is that I had no idea what a nimber is until I had to write this editorial...
SRM 562 - HAH! canceled
This felt the same. The div1 500 was quite complex to come up with and even If I did I would not be able to solve it. I had plenty of ideas of how to solve it in O(N^3), but they were all wrong... The closest I got was to fix a black point. Then sort all the other points clock-wise. Then whenever you pick two white points, you have to make sure the angle of the third black point is between them . If in addition the distance to the black point is not too close, that is a valid quad. I tried as hard as possible to finish coding this two-pointers idea but I also needed a tree... eventually I figured that it was not viable anyway, because the too close distance depends on the two white points... so using two pointers is not that friendly.
I also opened 1000, it seemed, once again like a complicated dp on a tree. I wonder what it really is.
Less than 10 minutes and I open 250. It seems time flies while reading a problem because I only had 6 minutes left after reading it... I knew the simulation would become repetitive in at most 50 steps. But I had some difficulties at first coding the idea in a good way that took less than 6 minutes to code. In fact, I needed far more time... Once I finished coding it, the challenge phase was supposed to start... Yet I notice that it was just the end of the coding phase? So the timer reached 0:00 but nothing happened.
They canceled it! HAH!
That strategy...
I knew the strategy would be very bad for my rating. If yesterday's match was rated, I would probably be in the 1600s area.
But I think it is necessary. I think that when I started in programming competitions I was fast enough to code the division 1 problems of all these matches in less than 10 minutes. I am not sure what made me far slower... I suspect it may have something to do with the whole 4 minutes that magically disappeared after reading the statement in SRM 562... Either way - The pressure of having only 10 minutes to solve a problem will hopefully make me faster eventually. And the exposition to harder problems before that might allow me to go back to solving div1 medium or hard at least once every other match. I am giving up rating for long term improvement, I hope... Plus seriously, if I am gonna fail a match, I'd rather it not be because I scored 160 in an easy problem that everyone solved.
0 comments:
Post a Comment