Yay! We all get medals! If you haven't seen already, the results are here: http://sc1.ioi2011.net/scoreboard/ (No, I don't know how to make links and everything on the browser here is in Thai). You can click on Australia on the right to only show Australian scores. If you look you can see I came last (of the Australians). Now look at Day 1 and Day 2 scores...
Yeah, I failed pretty hard on the first day. The three problems were known shorthand as Rice, Race and Garden (although for maximum confusion, it would have been way better to call Garden, Rose (Disclaimer: I didn't come up with that)).
The easiest one was Rice which I should have scored 100 on but only scored 68 on. I saw the easy 68 solution and thought, "Okay, I've gotten 68, that's pretty good... and the 100 solution is going to be really hard right? Because all IOI problems are really hard right?" So, yeah... 30 points lost there.
Garden was a graph problem which I may or may not have gotten the solution for. I spent 2 hours making observations about state explosion and cycles. Then I coded up half of it and started doubting myself because I really wasn't actually sure about the solution I'd thought up. So basically I wasted half an hour coding half of a possible solution. Then I decided to code the partial mark solution which was 49 points... but it didn't work! 49 points lost there.
The last one, Race was another graph problem involving a tree and finding the smallest number of edges summing to a certain distance. After the competition I heard Jarrah and Evgeny talking about the solution and realised it was similar to something I'd thought of in the competition. The thing was, I hadn't been thinking clearly at the time (because I was really annoyed at Garden) and hadn't given it much thought. In the end, I only coded the 9 point solution. Not that much of a loss since I doubt I could've gotten the solution anyway but some of the others got 21 points so... 12 points "lost" there I guess.
So, basically I failed the first day, missing out on what could have been another 90 points. I missed out on more points than I gained! So by the end of that I was feeling pretty... bad.
Luckily, I totally pwned on the second day.
The three problems were Parrots, Elephants and Crocodile.
Parrots was a task somewhat similar to a compression or encryption problem in that you had some data, had to "encrypt" it, and "decrypt" it. The thing is, the encrypted data, (a series of integers) could be sent to the decryptor in any order. I managed to get 81 points, Evgeny got the same and Eliot got 95.
Crocodile was another graph problem which required a few observations to reduce it to a kind of "reverse dijkstra". I got 100 along with Evgeny and Robert but (from what I heard) Eliot didn't realise he needed a priority queue so he only got the 46 partial marks.
We still can't figure out the solution to Elephants which we assume is a crazy data structure problem. This was an amusing problem in a few ways. Firstly, the problem had 5 subtasks but on the problem statement they were labelled, 1, 2, 2, 3, 3. Yay, duplicate subtasks. Also, the last two subtasks were worth, respectively, 47 points and 3 points. There was also a note in the problem statement saying something along the lines of "The c++ STL may be too slow to solve subtask 5". As Chris said, subtask 5 is there to separate Gennady and the Russians :). The other three got the 26 point subtask. Eliot told me he used the set solution which did a whole bunch of binary searches to "skip" stuff and make it faster. That was the theory anyway. It turned out to make the algorithm O(N^2 lg N) instead of the simple brute force which was O(N^2). I submitted the bruteforce expecting just 26 points but instead, I got 50!
The second day went much better than the first allowing me to scrape enough points for a medal. Well, I'm not sure if they've finalised the medal cutoffs yet but I certainly hope so.
No comments:
Post a Comment