Minus 161 rating points, that cannot ever feel good. Even those guys that claim that rating does not matter would not enjoy it. This was however a fair result and a consequence of me not following my own rules. What rules? I have two rules when solving SRMs.
Rule #1: "Always make sure to have at least 35 minutes to solve the easy problem".
Rule #2: "Do not challenge! No, not even when you are 100% sure the solution is wrong. Do not challenge! If your life depended on it, kill yourself. Challenging is not worth it!"
450 points: CutSticks
At first I didn't get why they made it a 450 points problem the constraints were very large. I was not able to understand it completely well after the first attempt to read the statement, so I bothered the admins with 3 silly questions. Once I finally understood the question I first thought it needed a greedy or math solution so I was discouraged since those things are not my strength.
I eventually noticed that if a math solution was available it is way too hard for a 450 points problem. I also noticed that even if we had some sort of direct greedy solution, the simulation would still run too slow as there may be up to 1000000000 steps. That's when I noticed the output is continuous and not integral - that's the sort of thing that hints for a binary solution. There it is! We can use a binary search and then ask "For a given length X, return whether it is possible for the K-th stick to have a length larger than or equal to x".
Unfortunately, an algorithm that answers that question was still a little tricky for me to implement. At first I was not considering the max cuts constraint which made me fail a single example, and when I added it I started failing all the other examples... I think I just had too many bugs and debugging was taking a good while. That's when I noticed... 25 minutes left! Darn I missed the deadline to open the easy problem. I had 10 minutes less than planned. My only hope was that I could solve 250 fast enough.
250 points problem - SilverDistance
#|@~! Ad hoc shortest distance problem. By the time I noticed that it was one of such problems, I knew I was doomed. I tried to simplify the problem and avoid as many pitfalls as possible. As usual, these problems can be converted to ones in which you start at (0,0) (then subtract x and y from gx and gy). I tried to take a look at what options we have in two moves:
#####
.$$$.
##*##
.$.$.
#.#.#
* is the silver (0,0), $ are the cells accessible by one step and # are the cells accessible by two steps. I noticed that (-2,-2), (0,2), (2,-2), (-2,0), (2,0), (2,-2), (-2,2), (0,2) and (2,2) are all accessible with two steps, so I concluded that if both x and y are even, the solution is as easy as : 2*( x/2 + y/2 - min(x/2,y/2). And if they are not, then we must just move the silver to another square until the parities change.
Blunder: Huge mistake, I assumed that just one move is required to change the parities correctly. I did not notice that it is not possible to exclusively change the x parity without changing the y parity in one step. My solution would just try any of the 5 possible directions when the coordinates are not even (and pick the minimum distance among the ones that make the differences even) This was evident after I failed the example tests.
Only five minutes left and I had to fix the mistake. I assumed that two steps should be enough (and they are), so I changed my brute force loop to consider move costs and then manually generate the 2-step moves that exclusively change x. This was not brilliant as it turned out a little complicated to do those things manually. I only had one minute left when I finished but then I had to fix typos like forgetting to change [5] to [11] ... I swear that the match ended just at the second I finished all those typos! 5 extra seconds and I could have submitted it...
Challenge phase
For some reason, the fact I had 0 points and that my golden rule says "Do not challenge" I still managed to make an unsuccessful challenge. I was sure it would fail because I knew that tantian's solution was going to return 3 for {0,0, 2,1} and it did! - unfortunately, 3 was the right result. Somehow when solving the case manually by hand I thought the correct result was 2.
.W.
..C
*..
What happened is that when I tested in paper I thought (2,1) was at the W cell instead of the C cell...
---
The correct version of my 250 did pass system tests in the practice room. I later noticed that the worst mistake was approaching the problem that way. The real simpler solution was just to notice that the difficulty of the problem lies in the asymmetric "up" step. If it was gone the problem would be very easy, and in fact we can get rid of it! Just brute force for the number of "up" steps to take, then call a function that solves the simpler problem, and pick the minimum result for all the possible "up" counts - due to the constraints, we can try all possibilities from 0 "up"s to 2000010 (the extra 10 is just in case).
--
So, there we go, if I followed rule #2, I would have gotten a good 0.00 and my rating drop would have been lighter. If I didn't fail to follow rule #1, I would have had a positive score like 130 that would probably still lose rating, but perhaps not enough points to fall bellow 2000.
The real issue is the long time it is taking me to actually code a correct solution. In fact, the real time consumer is debugging the solution. I need to practice yet again on being able to get a solution right in the first try. With that skill I could have easily gotten decent scores in both 450 and 250. That will be my focus for practice before the next match.
0 comments:
Post a Comment