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.
Modular division and inverse elements.
ExcludedMatrix multiplication and exponentiation.
ExcludedTheory of combinatorial games, e.g., NIM game.
ExcludedRandomized algorithms.
ExcludedString 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 discussionHeavy-light decomposition and separator structures for static trees.
Excluded, but open to discussionTwo-dimensional tree-like data structures (such as a 2D statically balanced binary tree or a treap of treaps) used for 2D queries.
ExcludedMaximum flow. Flow/cut duality theorem.
Excluded, but open to discussion
I have some questions though:
Does
Excluded, but open to discussionmean that it can't appear in IOI? What about other OI such as APIO?Does
7.mean that 2D Binary Indexed Tree is also excluded?Could someone list the other side? The topics that are hard but it is allowed in IOI syllabus.
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...
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).
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.
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.
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
I guess you are right, sorry for the misinterpretation XD.
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.
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
Fantastic work!
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?
Summoning misof.
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.
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.
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.
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.
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:
Good luck and have fun at IOI (IOI is the most interesting event I have been to)! Enjoy your IOI!
Thank you for your advice!
IOI 2018 syllabus states that:
"Frankly", Strongly connected components seems to be allowed now in IOI 2018.
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
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.