misof's blog

IOI 2015 task authors
By misof, history, 9 years ago, In English

Here are the authors of tasks used at IOI 2015.

Day 1:

  • boxes: Monika Steinová (SUI)
  • scales: Eryk Kopczynski (POL)
  • teams: Adam Karczmarz (POL)

Day 2:

  • horses: Mansur Kutybayev (KAZ)
  • sorting: Weidong Hu (CHN)
  • towns: Bang Ye Wu (TWN)

Backups (not public):

  • Ulugbek Adilbekov (KAZ)
  • Vytautas Gruslys (LTU)
  • Michal Forišek (SVK)

Which task did you like the most?

  • Vote: I like it
  • +77
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

I couldn't solve any of them but I liked boxes and horses the most. Also scales was very interesting.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +139 Vote: I do not like it

Here are my unfiltered opinions on the tasks, and I will include some personal stories that relate to my assessment of the tasks:

boxes: I didn't understand why the limits were 107. It seems like you tried to fail , but I passed with that anyway. It's an okay easy task, although I missed a really clever observation (only one circle trip is necessary) and wasted a lot of time on this. I heard it's a duplicate problem from somewhere very recently though, which is kind of unfortunate.

scales: My initial solution got 45.45. I then spent a lot of time writing another program to find a smaller set of queries to solve the problem, but it wasn't very good (it searched top-down instead of bottom-up) and it only found a solution with 8 queries, which was only about a 10 point improvement from my initial solution. That was really disappointing, but I didn't want to have wasted over an hour for nothing, so I tried (without success) to modify my solution to actually solve the problem. I didn't think I could debug the code and solve teams within the remaining time, so I gave up on the 10 points (it was really not worth it in hindsight). Anyway, I might have liked this task if the circumstances were different. I still like the idea of the solution though.

teams: I didn't have too much time to solve this task (because of the reasons above), but it had a lot of different ways you could approach it (only some of which lead to a good and fast solution). I came up with some solution (not the one with Hall's marriage theorem) in and coded and submitted it, but it turned out that there were too many bugs to count and fix before the contest ended (As the graders had a massive queue and I was pretty confident in this solution, I started to relax, but decided to write a maxtest anyway and found my code was wrong). Also, while debugging this problem near the end of the contest, I spilled water all over my desk and then CodeBlocks IDE froze my whole laptop while in debug mode, so after these two events I knew there was no way I would finish this problem in time. This had a really big impact on my enjoyment of the task, so I ended up not liking it that much (more so when I heard one of the fast solutions is just to optimize the 34 point solution).

horses: I thought this one was pretty standard — a greedy idea optimized with segtrees (just take logarithms and use doubles). I was 100% sure precision wouldn't be an issue when I coded this. After the contest while discussing solutions, another participant (who wishes to remain anonymous) seemed to think that this solution was really satanic, and told me a "better" solution that used integers only. Anyway, I think it fulfilled its purpose as the easiest task pretty well, although I know for sure some others disagree with me.

sorting: First, I want to say that I prefer "standard" OI-style tasks over interactive-type problems. Many participants found this task easy (and boring), but this is personally my favorite task of IOI 2015. The initial impression of this problem and your perspective were very important in how easy solving this task was. During the contest, I was thinking about some solution involving cycles in the permutation, but it was really complicated and I wasn't confident I could implement it in time. After the contest, I learned of the nice interpretation where the first player is swapping indices and the second player is swapping values, which was really cool and made it obvious you could consider the two players separately. I'm still pretty salty about not seeing this during the contest after spending a good amount of time thinking about it, but I still think the solution is cool.

towns: This task was difficult for me to get a good score. The time spent versus points earned ratio on this problem was really low for me, and even the first subtask wasn't really trivial like the other problems. Kuroba wanted a nonzero score on every problem, but ran out of time before getting any points on this problem (which affected his points earned on sorting, a sad story indeed). I recalled the majority algorithm during the contest, but since I never implemented it I forgot it works even if you don't know the exact candidates. I know for some this problem is their favorite, but to me it feels really artificial — it's just a combination of two easier tasks to form a much harder task (optimize majority algorithm + check if a hub lies on the path between two leaves). Anyway, the main point is that I thought the subtask scoring was harsh — a lot of work for very little improvement in score, at least for me.

On an semi-unrelated note, is there any chance that IOI will get a live scoreboard for the contestants? Having a live scoreboard would change my (really bad) strategy a lot. I might have done better if I chose a proper order for solving (1-2-3 and 1-3-2 on the two days, based on a initial 10 second feeling), but spending time to assess the difficulty of a problem is risky (since you may not get any new ideas after all).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Choosing the best contest strategy is almost 70% of the winning ioi style contest for a ready and well prepared student! BTW I believe it's better not to have online scoreboard! One of the reasons is many people are more relaxed in this situation

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +72 Vote: I do not like it

    At least in the next few years the contestants will not have access to the live scoreboard during the contest. The presence of such a scoreboard would change the contest in ways we dislike. We want the contest to be about independent problem solving.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Thanks for the reply! Your logic makes sense, I only asked because I'm used to seeing a live scoreboard and I recently realized I have no real strategy without one. I guess I should work on that!

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Towns was certainly the best one for me. I liked it a lot and we came up with solution idea just 10 hours after the contest! Scales and teams were also very cool problems. Having said that I solved neither of those three I mentioned, but I still think they were great (costed quite alot of push-ups though)

On a side note, will author solutions be posted?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Hopefully, yes, but it will certainly take a while -- at the moment, only very short solution sketches exist.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I can post my Java solutions (on the problems where I wrote them) if no one objects

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sure, feel free to post those.

        (Just to clarify: I was talking about English solution writeups, not about code.)

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

I've solved the boxes first, it was pretty simple one. After then started think about teams. Come up with the idea that M < 1000, implemented a solution and expected to get 77 points. It turned out this solution was able to get 100 from the test data. Here comes the sad part. There was 2.5 hours left for scales. I tried to implement some backtracking algorithm. After 1.5 hours of debugging and implementing I realized that I would not be able to finish it in time. Then I implemented quick sort to see how much points it would get. Because of stupid bugs and slow feedback could able to implemented in an hour. Anyways, end up with 26.5 points which is much less than selection sort.

Second day first problem was easy as well, just like boxes, I come up with with an idea that uses keeping answer in log and lazy propagation. After 1 hour I got accepted.

Towns was a non-standart problem, that's why I decided to go for sortings. I thought about cycle permutations for 30-40 minutes, but could not come up with something alltough I was pretty sure that this problem was about cycle permutations :(. Then I've decided to try towns. First thing that came to mind that center of the tree has to be laying on diameter of the tree. And for every node u fartest node to u should be one of the ends of the diameter. It's is quite easy to find the diameter with 2 * N queries. And for deciding if center is balanced or not, we need to be able to answer if any two nodes are in the same subtree or not. If center of the tree is C then A, B are in the same subtree if and only if dist(A, C) + dist(C, B) > dist(A, B). I forgot that there could be two centers, and thought that I had some bug in the implementation, it was just 13 points more(35 to 48) so I decided to go for sorting again and let it go.

I thought about a solution that tries to put numbers each time to their place with other person's swaps but I was not sure that it guarantees the solution if there is one. Then I implemented O(NM) solution to see if it passes the subtask with N ≤ 500. It got wrong answer from just 1 test case. I thought may be test cases were a bit week and my solution was completely wrong:(. It turns out my bug was I forgot to add swaps that does not change anything after guaranteeing that every number will be placed with second person's moves. That's why left with 36 points and silver medal. And then I turned back to towns and realized that there could be two centers got more 13 points.

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Without going into details, my overall impression is that the problemset is much better than 2010-2014 (2010 and 2013 were especially horrible), but still not so goddamn hot as it used to be in 2007-2009.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why the hate for 2010? I was solving problems from past years before this IOI as a practice, and 2010 was one of my favourites. Also I liked problem set from 2012 quite a lot too. Sure this year it had some nice problems but in my opinion not "much better" than 2010-2014.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Imagine the fun discovering languages and maze with no prior warning that tasks of these types are even possible on the competition floor. Furthermore, a lot was decided on those 2 tasks (at least in gold/silver boundary). If you look at the results, you'll see a considerable amount of 450 for 5 tasks, 75+ for hottercolder and the rest is determined by those two tasks. I, personally, wasn't prepared for these types of tasks at all and as a results completely hated the problem set. Having said that, saveit from 2010 is my favourite problem of all time.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, it is true that they were different but at least for Maze it wasn't the first of its kind, so it's not "with no prior warning that tasks of these types are even possible".

        Maze for example is an output-only problem without an optimal polynomial-time solution, requiring contestants to use approximation algorithms. IOI 2006 had two output-only problems — "Forbidden Subgraph" and "A Black Box Game" of which "Forbidden Subgraph" had no optimal solution and required approximation algorithms. Output-only problems with no optimal solution are given back at IOI 2003 too — problem "Reverse", even though it is not very similar.

        Languages was an interactive machine learning problem, which must have been indeed very surprising as machine learning wasn't given previously, but the problem didn't require any prior knowledge in the field. Analyzing the frequency of a few consecutive symbols gave 95+ points and I think that creating new and original types of problems for the IOI is good, as long as it doesn't use anything explicitly excluded in the syllabus and does not require prior knowledge in some specific fields.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, maze was less of surprise than languages, especially after languages in the first day. My issue with maze was that it was second (+ 1/4 of hottercolder) approximation task in the competition.

          As for languages, I'm not denying that I failed this task miserably by perhaps panicking, but here is my experience during the contest with it:

          Implement what is written in the statement for 55 points
While contest is not over:
     Think of improvement I
     Implement I
     Receive less than 55 points
     Delete I
          → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The plot here is that having a problem that require approximation algorithms and so on isn't a bad idea. The bad idea is to have three problems of these kind among 8 problems of IOI. Author of hottercolder had a solution that could get 100, but it was just a huge collection of crutches and ad-hocs.

          I said 8 problems of IOI, but we definitely should exclude two not-a-problem-at-all tasks and a very straightforward and amazingly common tree problem. So here we are with only 5 problems left. One of them was a nice binary search problem, while saveit is for sure among the best problems of IOI of all times. Unfortunately, the beauty of this problem was spoiled by a strange scoring boundaries and onsite problems with running it locally. Yep, that ruined my IOI and I'm still dissapointed.

          → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I read the problems and submit solutions? Please someone tell me.

→ Reply