IOI 2016 contest review

(Ali Bahjati suggested for English translation, so I added some translation below. Thanks for the suggestion!)

Day1

여태까지 봤던 올림피아드 중 가장 힘들었던 거 같습니다. railroad / shortcut 콤보에 정신을 못 차리고 아무것도 하지 못한 채 멘탈붕괴... 대회 전에는 별 생각없이 들어갔다가 정말 말 그대로 박살나서 나왔습니다. 이렇게 박살난 건 저만 그런건 아닌듯.. 배점이 너무 이상한 탓에 성적에 큰 상관은 없었던 것이 다행이지만, 여러모로 아쉬움이 많이 남는 날이었습니다.

This was the most painful contest that I’ve ever been. I wasn’t really worried about the competition before, but right after encountering railroad / shortcut combos, I was simply out of my mind, and I could really do nothing in contest.. I think I was not the only one who was out of mind. Because of the weird subtask scoring, this day didn’t affected my medals at all, but I still regret a lot of things about day1.

molecule

제약 조건을 박은 knapsack을 빠르게 푸는 문제였습니다. 집합 크기 k를 고정시킨다는 식으로 생각하면, 증명 및 풀이 접근 모두 쉽습니다. 실제로도 역대 IOI 중 가장 만점자가 많은 문제 중 하나입니다. 하.. 대체 day1의 컨셉은 무엇인가..

This problem was some kind of “restricted knapsack”. If we fix the set size (=k), It’s trivial to prove / solve it. Actually, this problem is one of the most solved problem in recent IOI history. I don’t know what was the concept of day1...

railroad

이상한 그래프에서 TSP를 빠르게 푸는 문제였습니다. 그냥 그래프로 바꾸고 bitmask dp 돌리면 34점이 나옵니다. railroad 64점이냐 shortcut이냐 가지고 저울질을 많이 했는데, 몇가지 trivial한 그리디가 안 나와서 그냥 버리려고 생각을 했.. 으나, 많이 미련이 남더라고요 ㅠㅠ euler tour에 대한 관찰이 없으면 반례 없는 64점 풀이를 만들기 상당히 힘든데, 당시 멘탈로 생각가능한 풀이인거 같지는 않습니다 ㅋㅋ

In this problem, we should solve TSP faster in some weird graphs. Using bitmask dp without thinking about all the “weirdness” suffices for 34 points. At the contest, I didn’t know what to do : railroad 64p, or shortcut. At first I tried some trivial greedy algorithms, and it didn’t worked, so I just tried to gave up… but it was not easy to just give up since I thought that this problem might be the easy one. After the contest, I thought that it’s really important to think about euler tours in order to make “correct” 64p solution (and go beyond). I don’t think I can come up with that in those in contest, especially in such bad conditions..

shortcut

말 그대로 멍해지는 문제였습니다. 커다란 산이 보인다고 해야 하나.. 이 문제를 잡고 뭘 했는지 전혀 모르겠네요. N^2 * binary search는 대회 당시에는, 가능하다고 쳐도 너무나 복잡할 거 같다 + 그런 접근으로는 71점 초과로 못 올라갈 거 같다는 생각에 버렸는데 둘 다 틀린.. 거 같네요. 사실 복잡한 건 그냥 참으면 되는데..;; 정말로 대회 때 제가 뭘 했는지 모르겠습니다... 좌절 끝에 마지막에 N^3을 긁고 끝났습니다. 이 문제의 고득점자가 생각보다 많지 않은데, 그냥 다들 비슷한 경험을 하지 않았나 싶습니다 ㅋㅋ..

I was just stumped upon looking this problem... It felt like a big mountain for me :) Seriously, I don’t know what have I done while solving this. In contest, I was pessimistic about the N^2 * (binary search on answer) solution, since it sounded too complicated, and I thought it will just end in 71 points. But after the contest I think eh.. my both assumptions seems to be wrong. Actually, I don’t know why did I care about complication, in the contest time! Near the end of the contest, I just submitted N^3 solution and gave up. I thought that any other top contestants who didn’t get over 38p, would share simillar experiences with me.

Day2

오늘은 뭔가 300점을 받을 수 있을거 같다라는 굉장히 근거없는 자신감에 차서 시험을 봤습니다. 도대체 왜 이런 자신감이 생겼는지 전혀 모르겠지만.. 덕분에 상당히 부드럽게 시험을 볼 수 있었습니다.

scoreboard를 보면 Day2 성적으로 금메달이냐 아니냐가 완전히 갈렸습니다. Day1 점수차가 크지 않아서 이렇게 결과가 갈리네요. Day2가 어느 선 이상에서 전혀 변별력이 없다는 사실은 상당히 아쉽게 느껴집니다 ㅠㅠ..

Before the start of contest, I thought I can get 300 points - yep, I was really confident that moment. Although I don’t know why I was that confident, this feeling helped me to do my best.

Looking upon the scoreboard, I found out that day2 results are almost the only thing which divided gold / silver medal. I think this is because of weird subtask scoring of day1.. It’s quite disappointing, because there were so much 260 scorers, and there were no way to separate those…

paint

전형적인 DP 문제로 음.. 사실 할 말이 없네요. 코딩이 썩 쉽지는 않았던 기억..?

This is a classical DP problem which I have nothing to say. Well.. the coding part was bit hard.

messy

문제 제목이 messy지만 이름값 못하는(?) 깔끔한 interactive 문제입니다. O(N) / O(N^2) 풀이를 찾고, 몇가지 생각을 더 하면 + 복잡도 힌트를 얻으면 (...) O(NlgN) / O(NlgN)에 풀 수 있습니다. N = 2^b이고 제한이 7 * 128이었는데, 굳이 그렇게 제한을 줄 필요가 전혀 없자는 점을 감안하면 난이도 조절을 위해서 일부러 힌트를 많이 풀어낸 게 아닐까.. 싶네요. 만점자는 대충 작년 sorting급으로 나왔습니다.

Although it’s name is “messy”, this was a clean interactive problem. It didn’t deserved it’s name :) We should first find O(N) / O(N^2) solution, and with some observation ( + complexity hints in problems ) we can solve this in O(NlgN) / O(NlgN). I don’t know why did they come up with N = 2^b / 7 * 128 limits. I think they intended to give a lot of hints, in order to balance the difficulties.. I don’t know if that was the reason, but it was solved by quite many contestants (slightly more than IOI2015 sorting)

aliens

의미없는 점들을 제거하고 DP를 사용해서 최소 cost를 계산하면 25점이 나오고, convex hull trick을 사용해서 60점을 받을 수 있습니다. CHT를 IOI에서 다시 만날 수 있어서 반가웠습니다 ㅋㅋ 60점까지는 http://koistudy.net/?mid=prob_page&NO=2046 문제랑 비슷하지 않나 싶네요.

260점 띄우니까 2시간 정도 남아서, 할 게 aliens밖에 없는 상황이 왔습니다. 집중할 수 있는 상황이라 최선을 다해서 생각을 했지만 접근 방법 자체를 전혀 종잡을 수가 없었습니다. 풀이를 들어보니까 만점자가 없길 바라고 낸 문제인거 같은데... 그걸 푸는 jcvb (…) 대회 후 얘기를 해봤는데, 중국 내 'small contest'에서 비슷한 유형의 문제를 풀어봤다고 하네요. 도대체 그들의 small contest에서는 무슨 문제들이 오가는 건가..;;

By removing some unnecessary points, and combining DP yields 25 points. For the speedup we could use convex hull trick. I was happy (and quite surprised) to meet CHT at IOI again. Until 60 points, It resembled http://www.spoj.com/problems/ACQUIRE/ problem a lot.

After getting 260p, I had two extra hours. Since I had nothing to do other than solving aliens 100p, I tried really hard to come up with something. But seriously, I couldn't even got a small piece of observation.. After contest I got some solution sketches from our tutors. and I thought the problemsetters surely wanted some unsolvable problems. But jcvb solved it.. I asked him after the contest, and he said that he solved simillar problems at some ’small contest’ inside China. I can’t imagine what’s going on in those ‘small contests’…

총평

작년에는 모든 문제들에서 "풀 수는 있다" 라는 느낌을 받았지만, 올해 3번 문제들에서 인간미 따위는 전혀 느낄 수 없었습니다. APIO/CEOI 등 올해 여러 올림피아드를 보면서 OI에 특이점이 온다는 느낌을 계속 받고 있습니다. 과연 그 끝은 어디인가.. 그리고 그 와중에 중국은 대체 무엇인가... 지금이라도 OI 은퇴해서 참 다행입니다 ㅋㅋ;

대회 전반에 대해서는... 결론만 말씀드리자면 작년보다 훨씬 잘 지내고 있어요 ㅋㅋㅋㅋ 나중에 정리해서 올리도록 하겠습니다.

Last year, I thought every problem was at least “solvable”. But sadly this year’s third problems didn’t bear any humanities… Looking for lots of olympiad problems (including APIO/CEOI) I think OI problems are consistently being harder and harder. Will it reach an end.. and what are the Chinese guys doing… It’s quite fortunate that I’m retiring OI this year :)
Soon I will write something about the whole contest, (also with English ones, I’ll try) But I think I’m having much better times compared to last year :)