Adhami's blog

Topics Excluded From IOI
By Adhami, history, 6 years ago, In English

I was reading IOI 2018 syllabus, but I was overwhelmed by the system of it. Some common known algorithms were placed under Excluded, but open to discussion or Excluded. So I decided to list them for ease of use.

  1. Modular division and inverse elements. Excluded

  2. Matrix multiplication and exponentiation. Excluded

  3. Theory of combinatorial games, e.g., NIM game. Excluded

  4. Randomized algorithms. Excluded

  5. String algorithms and data structures: there is evidence that the inter-reducibility between KMP, Rabin-Karp hashing, suffix arrays/tree, suffix automaton, and Aho-Corasick makes them difficult to separate. Excluded, but open to discussion

  6. Heavy-light decomposition and separator structures for static trees. Excluded, but open to discussion

  7. Two-dimensional tree-like data structures (such as a 2D statically balanced binary tree or a treap of treaps) used for 2D queries. Excluded

  8. Maximum flow. Flow/cut duality theorem. Excluded, but open to discussion

I have some questions though:

  1. Does Excluded, but open to discussion mean that it can't appear in IOI? What about other OI such as APIO?

  2. Does 7. mean that 2D Binary Indexed Tree is also excluded?

  3. Could someone list the other side? The topics that are hard but it is allowed in IOI syllabus.

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

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Q1. It can appear on IOI if it's part of a very nice problem and the IOI people decide it's ok. You can read it as: probably won't appear.

Q2. Yes, that's how I read it. I'm surprised it's an excluded topic considering there was a 2d segtree in IOI 2013, but if that's excluded now, then 2d BIT probably is too.

Q3. Ad-hoc problems, mostly. Weird greedy ideas, ways to efficiently use some oracle...

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

    Thank you for your response.

    Regarding your answer for Q1, should I mind learning them and mastering them? I know the basics but sometimes can't write the code without checking the implementation.

    And about HLD, why it is on this section? It is a very basic and useful algorithm. It even appeared in AOI 2018 (The Arab Olympiad In Informatics).

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

      Well, sure, you should know those advanced topics simply because it means you know them and it can help you at IOI as a different way of thinking. If you have limited resources (time/effort), I can't tell you what's best for you.

      I guess IOI doesn't want to be about standard algorithms. That's not to say they won't be used, but not as the main/only part of some problem.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      AOI 2018 was not an official contest, it doesn't qualify to anything, just for fun and for students to get to know each other. So it wasn't bound by the syllabus. But for EOI (2018 at least), we made sure it didn't including any task with intended solutions outside of the syllabus.

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

      As I was a participant in AOI 2018 I think that you are talking about the second problem (funding) which can be easily solved using DFS order of tree and segment tree without any need to use HLD :3

      Problem: https://drive.google.com/file/d/17YgGIhaxwwCTnLvpeha4qKpV5Y52Yori/view Solution: https://ideone.com/701deJ

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

        I guess you are right, sorry for the misinterpretation XD.

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

    I always thought like this, it could appear as a subtask or part of another simpler/harder solution.

    For example Friend from IOI 2014. It had a subtask that can be solved with flow based algorithm and it was sufficent to got 69 points if I remember correctly. (Refer to blog written by bmerry, here.) But full solution haven't required flow.

    So is this the case for 'open the discussion' or are you sure it's like the one you mentioned? I'm asking because I'm not sure about my claim but not sure about even it has a chance to appear as the expected full solution, either.

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

I went through the syllabus document in a stream, and listed everything interesting.

Included:
-Inclusion-exclusion
-Combinatorics
-Euler’s tour on a tree
-Bipartite matching in O(V*E)
-Basics of combinatorial game theory, winning and losing positions, minimax
-BST, BIT/Fenwick
-Creating persistent data structures by path copying

Outside of focus:
Discrete probability
Using fractions to perform exact calculations
Randomized algorithms
Online algorithms

Excluded:
Gcd
Chinese remainder theorem
Modular division/inversion
3d geometry
Precision issues
Trigonometry
Burnside
Linear algebra, matrices, Gaussian elimination
Calculus
NIM
Max flow
KMP
Heavy-light decomposition
“Separator structures for static trees” — centroids?
Understanding hash tables
2D trees
Center of mass of a 2D object

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

    Fantastic work!

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

    Excluded: Gcd

    I can understand the reason behind most of this excluded list. But Gcd? That's like the most basic algorithm. Can anyone give a possible explanation?

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

      Summoning misof.

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

        Answering summons :)

        There's some confusion here. Euclid's algorithm to compute GCD is "included, not for task description" (section AL3a.). What's banned are just its applications to modular division and inverse elements.

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

      I think the idea is excluding the problems that involves them. Like you said, gcd is a very basic algorithm. But you can create lots of problems includes gcd and very hard and require other algorithms (maybe knowing a solution to a similar problem could help).

      For example flow isn't a complicated algorithm. Very simple ones are mostly sufficent to solve many of them. But when you include it, you create a complex area that participants should practice. Same thing applies to KMP, NIM and Heavy-light I think.

      But I'm not against you. I'd just ask 'why exclude gcd' if I have one question left. I just think it makes sense to exclude some topics/algorithms and expose the creativity/thinking/intelligence/problem solving/whatever you call it, in students, and not the recalling similar problems/ideas.

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

        But you can create lots of problems includes gcd and very hard and require other algorithms

        I think you misunderstood what I wanted to ask. What I wanted to ask is which type of hard problems is hard because of GCD — usually hard problems are hard because of other parts, not because of GCD.

        Anw misof already commented above so it is clear now.

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

          Actually I meant the problems require gcd as a core part but solution isn't just gcd function but more like a number theory problem. Like, there're so many gcd problems requiring inclusion-exclusion and really hard. But solution only requires knowing what gcd means actually.

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

Frankly I did not pay much attention to the IOI syllabus. I did read it when I was preparing for IOI, however, solving IOI-style problems to have a taste of them is a much more important job.

The fact that strongly connected components, modular inverse or even NIM are excluded, does not help me much as I must be familiar with all these things in order to become a Vietnamese IOI contestant. These two things below are critical to you:

  1. Most IOI problems require hard critical thinking, brainstorming, logic. Solving is difficult, but implementing is very likely to be simple. Personally, it's hard to put most IOI problems into some common categories (greedy, dp, data structures,...).
  2. Being "excluded" from IOI does not mean that knowing such things is completely useless. For example, task "horses" can be solved using modular inverse; a subtask of "teams" (both tasks are from IOI'15) can be solved by maximum matching; even though these two algorithms were excluded.

Good luck and have fun at IOI (IOI is the most interesting event I have been to)! Enjoy your IOI!

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

    Thank you for your advice!

    IOI 2018 syllabus states that:

    Included, not for task description: Connectivity in directed graphs (strongly connected components).

    "Frankly", Strongly connected components seems to be allowed now in IOI 2018.

    Good luck and have fun at IOI (IOI is the most interesting event I have been to)! Enjoy your IOI!

    Team selection in Jordan haven't been done yet XD, but I have good chance of reaching IOI. Thank you for your advice again =D

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

    To be honest, I don't think the implementation is too often trivial for hard idea IOI problems. Look at most hard problems from 2017 and 2018.

    → Reply