Rules
The draft for this year's rules is available on the competition website.
As it is highlighted, there are two important changes. First of all, it is officially confirmed that Java is among the languages that can be used at IOI 2015. Secondly, since the JVM uses threads "under the hood", threads are now allowed for submissions in any programming language, but the runtime of a solution is counted as the sum of the runtime of all threads.
I don't think that these changes are really significant to any participants not using Java, because there is no point in using threads if the runtime for each thread is counted separately.
The rules promise "generous time limits", which is interesting, because experience shows that Java solutions tend to be slower even when simple wall time is considered, but counting all the JVM threads separately could result in an even more significant slowdown (compared to other languages).
I'm a little bit concerned that this might mean that we're going to see 20s time limits again (and, consequently, long testing queues, just like during IOI 2013). This happened at the Baltic Olympiad in Informatics this year, where the jury had "optimal" Java solutions working for ~10-15s on maxtests, while C/Pascal solutions spent less than 0.5s, and the TLs were nevertheless set at around 20s (which did make feedback unavailable for a short period of time during the contest, but the jury dealt with it quickly).
Another change in rules which surprised me a bit is that the graders are not guaranteed to use the same hardware as contestants' machines. But then again, with full feedback on 100 submissions per task, perhaps this is not a very serious issue.
Syllabus
The IOI syllabus is a document describing topics (most importantly, algorithms) which IOI participants are expected to know, as well as those that must not be necessary to solve an IOI task.
The new version of the IOI syllabus is already available, and a list of changes should be available soon on misof's IOI Syllabus page.
Meanwhile, most of the changes in the syllabus appear to consist of moving stuff from "Explicitly excluded" to other parts of it, most often "Excluded, but open to discussion". I understand this new category as "these are still excluded, but we should consider including them in IOI 2016 or later", although one should be cautious with this, since the syllabus is not binding for the task authors anyway, so, if someone comes up with a really cool task concerning an excluded topic, it could theoretically be allowed, especially if the topic is "open for discussion".
Another interesting change is that planar graphs were moved from "explicitly excluded" to "included, not for task description", although planarity testing is still excluded. Bipartite matching was also moved from "explicitly excluded" to "included, not for task description", and maxflows and strongly connected components are now "excluded, open for discussion". Balanced binary search trees are now included, and string hashing is "excluded, but considering inclusion".
I hope that this overview of the changes will be useful to other IOI participants (or teachers, or spectators), and I'm looking forward to hearing more information from the organizers.
The changes in the syllabus seem to reflect the fact that with every year, more and more algorithms are becoming "widely known", and the olympiad organizers are trying to reflect this, which means that the olympiad is getting harder over time. Perhaps the organizers have decided that now is the right time to formalise this by including more advanced algorithms in the syllabus (as hinted by the results of the participant surveys in 2013 and 2014). However, at this particular moment, most of the changes seem to be in the "excluded, but open for the discussion" category, and it is certain that many discussions will be held on this topic, both at IOI and outside. Perhaps a part of this discussion might happen right here, on Codeforces.
I noticed that it specified O(VE) bipartite matching algorithms, so Ford-Fulkerson is enough for the time being.
Also, I think Java is often slowed down significantly by slow input/output, which shouldn't be a factor since IOI has signature grading.
Another thing is that Excluded topics can't even be useful for subtasks anymore, so the situation with Robots (in 2013) and Friend (in 2014), where max flow could get points on some subtasks, won't happen again.
Hehe, "won't happen again" are strong words, but that is certainly the intent :)
Java. I get a feeling this won't go well.
I was lucky enough to get 100 points for problem Dreaming with effectively blind submits in IOI 2013, but it was still a reminder not to set large limits. While adding Java may seem like a benefit for Java coders, it's actually a benefit for C++ coders, since it means more chances to squeeze a submission into time limit — what's more, with full feedback... I can sense the shitstorm already.
I wouldn't say that wider syllabus = harder problems. If there are more topics to choose from, there are more standard, yet not completely milked out topics to choose from. Standard problems should be easier than ad-hoc wtfmagic, since they can at least be prepared for. Of course, the actual selection can go either way, but there are wider possibilities.
Yeah, I am a bit scared of Java as well :)
But not really. It's just something you have to take into account when selecting the problems. For instance, we didn't select a problem where limiting your memory consumption played an important role.
It's certainly possible to have an IOI where there will be no difference between Java and C++. For instance, the Canadian IOI comes very close. Of course, I'm not saying that this will be the case this year :) and I certainly do expect most top competitors to code in C++. The main point of having Java, at least at this moment in time, is to make the contest more approachable to some of the less experienced countries where Java is the main language taught in schools.
I agree with your comment on the breadth of the syllabus.
Thanks for your interest in the syllabus, popoffka!
If anyone has any questions or comments, I'll be glad to hear them and I'll try to answer.
Also, I'm currently working on a short document outlining the changes you mention and our rationale for doing so. Once it's ready, it will be on the syllabus webpage, and I can also post here.
"Bipartite matching", "maxflows", "strongly connected components" were explicitly excluded so far?? Come on, is it a competition for best high school programmers all over the world or competition for disabled programmers? These are something really basic, going to IOI without knowing how bipartite matching or SCC works is a shame.
Btw, problems featured in IOI are often much harder than those algorithms, which makes this even more peculiar.
What is so basic for you may be really hard for other people. I don't see anything shameful about not knowing this topics. I myself did not, and I still don't (bipartite matching and maxflows).
"What is so basic for you may be really hard for other people". Yes, it is true, but is it ok for some really slow runner to go to Olympic Games with an excuse "not everybody has to be that fast..."? You kinda missed here that Olympiad is a place were excuses like that are invalid. If someone goes to International Olympiad than he should be aware that he represents its country and should feel some responsibility for his knowledge which definitely should include bipartite matching.
Note that here I do not demand for everyone to be the better than Gennady, but aren't matchings and SCCs among first few graph algorithms people learn right after DFS, BFS and Dijkstra?
Your comparison is bad because IOI includes many topics and running is just about running. One can get a medal in IOI without any knowledge of some specific topic. If you compare IOI to football, for example, a player can be slow but be an amazing free kick taker.
I think there are still quite many things to learn about graphs before matching and flows (dfs, bfs, shortest path algorithms, mst, topsort, scc, lca, ...). Anyway, I don't know much about matchings and flows, maybe they are easy :D
OK, maybe runners will argue, but running can be indeed just about running, but you also described football player example which in fact is on my behalf :P. Indeed one can be slow and be good free kicker and one also can be good at strings and bad at graphs, but isn't being both fast and good free kicker making him a better player in the same way as being good both in strings in graphs makes someone better competitive programmer :P. Of course on IOI there are only 6 tasks and such a small problemset can't and is not meant to cover all possible subjects and that causes that some people on more or less similar level of skills can got different scores, but being wide knowledge always makes your chances higher :P.
My kind advise for you would be to learn firstly bipartite matching in O(VE) complexity and then try to understand Ford-Fulkerson (about maxflows, I agree — these are first kind of algorithms where some more involved observations are included — but who never tries never improves) :P.
Thanks for advice ;)
Well, but you are not getting better football player when you just kick asses for whole opponent team so that your teammates play without a resistance.
Maybe they try to make IOIs point to be to come up with solution, but not to write all-those-creepy-standard algos.
While IOI does strive to give interesting hard problems, it's my belief that it's better to build such problems on a set of tools that most contestants are familiar with. Furthermore, these tools should remain relevant to things that contestants are likely to see in the future. In other words, I think it's useful to minimize the incentive to read up on lots of literature with the hope that something in they may turn out to be useful.
The main rationale for excluding the topics that you mentioned is that they're fairly prone to escalation: if flows/cuts are allowed, it would be difficult to ban phrasing problems as duals of flow linear programs. Some forms of SCC codes are closely related to other directed graph DFSs such as dominating sets and triconnectivity. Actually, both of these topics are fairly rich areas of algorithmic research, so a line needs to be drawn somewhere: matching and undirected DFS were the choices this time.
I don't think that flow algorithms and SCC are easy. Of course, they are standard textbook algorithms, and easy to implement and use as black boxes if you have memorized them. But it's much more difficult to really understand why they work or invent them from scratch.
Good IOI problems should require thinking and creativity, not memorizing lots of textbook algorithms.
Now you gave me additional motivation to improve my knowledge of all that stuff — I was recently told that I have no idea why flow works and how exactly it works :) So now it turns out that in your opinion I am disabled programmer :)
Thank you for noticing and highlighting the key changes!
To all people that commented on my comment: I understand your arguments and that competitive programming is not all about learning tons of different algorithms, but what differs us seems to be different placement of that border between basic and nonbasic algorithms. I learned SCCs literally in first few months I started competitive programming, about the same time as DFS, BFS, Dijkstra, Floyd-Warshall and it was crystal clear for me first time when I heard about it. When I was in high school I have heard at least three or four lectures about bipartite matchings on different camps and also few about maxflows etc. On my first final of POI there was a problem which demanded bipartite matching and one year earlier there was problem demanding maxflow. Final of POI is designed for about 100 people. Then best 4 of them is chosen to represent Poland in IOI and there even SCC and matchings are explicitly excluded >_>.
I know that IOI problems should mainly test someone's ability to come up with creative solutions, but going to international olympiad representing country with knowledge about only DFS, BFS, simple dp and KMP is pretty pathetic. We need some balance between being creative and having some knowledge.
Poeple going to some international biological or chemical olympiad need to have extremely wide knowledge and I don't think that average knowledge of algorithms of people going to IOI amounts to at least 10% of their knowledge and what you're trying to do is to restrict needed knowledge to 1% xd.
Well, do you think that IOI is too easy at the moment?
Last year only 3 people got 600 points, and only 11 people got 500+ points. So it seems that even with the current syllabus, it is possible to challenge the best students.
A much bigger problem is that last year 78 people got less than 100 points, so they could not solve any of the problems completely. I don't think that the level of IOI will increase if we add more textbook algorithms to the syllabus.
And please remember: even if SCC is a trivial technique for you, it is not for everybody (for example, for me).
"Well, do you think that IOI is too easy at the moment?" — You misunderstand a bit my point. IOI problems are challenging, because they demand high creativity, but I do not see much sense in forbidding such basic algorithms. As I said, we need some balance between needed creativity and needed knowledge.
Last year problem "Holidays" demanded technique which is known, but not that widely. It is not very likely that someone can come up with it during a contest. Knowing it in advance could have helped much. Isn't it like demanding much more sophisticated knowledge, but don't putting it explicitly into syllabus, because it is not that widely known to give it a specific name?
I don't consider many people with small scores as a problem we should concern ourselves. In some countries algorithmics is completely not developed. People sent by some countries are often worse than average guy who started learning algo month ago. Should countries with more serious attitude concern about countries which simply do not give a %^$# about algorithmic which send some random guys? There is not much point in forbidding them particiption, but their participation is somehow ridiculous. By the way, I think that it is a topic for a different discussion :P.
I agree that it is a problem that some more difficult techniques do not appear in the syllabus. For example, in IOI 2011 a task required tree centroid decomposition, while heavy light decomposition (a simpler technique, I think) is now excluded in the syllabus.
Low scores are a problem, because a contest should be designed for the actual participants, not for some ideal people that do not exist. It is not encouraging to attend IOI and get a near-zero score.
It is not encouraging to attend IOI and get a near-zero score.
I don't agree with you on this one. For some people (e.g me) getting a low score is far more encouraging than getting a high one.
It depends on the person.
I think they do not really hurt those who give a %^$#), as the number of medals increase ( ͡° ͜ʖ ͡°)
Poeple going to some international biological or chemical olympiad need to have extremely wide knowledge
That's the reason why I'm always a bit ashamed to talk with my friends who are going to IMO or IPhO. They all know tons of different facts and theorems, while I know like 30 algorithms and most of them could be learned in 15 minutes.
That is not true. You use those 30 algorithms in a different way for different tasks. The same do they for their subjects. The difference is that programming is easy to you and it make you feel weak in knowledge. Try to teach others programming or algorithms, and you'll get crazy.
Okay that's a common misconception, it looks easy in your head but try to think back for example the first time you tried to solve DP.
What does "with full feedback" means? Does this mean verdict for each test case will be shown separately like USACO?
Not necessarily. Full feedback means that you will see your total score and the overall verdict for each subtask. As for individual test cases, it is up to the organisers: sometimes verdicts are shown for all cases, but sometimes you only see the verdict of the first case that your solution failed in each subtask.
That is correct.
The trend is actually to avoid showing detailed information on each test case, because that often makes it easier to "milk" the grader: i.e., to use submissions to obtain information about test data, and to use that information to tweak an incorrect solution to pass.
Balanced binary search tree is hard to implement and I hope it is not included.
But..
There are kinds of balanced BST that are very easy to implement, for example treap. At least in Russia strong students are all familiar with it and are able to easily implement it.
Moreover, even though the balansed BST was excluded in the syllabus before, there were tasks that could've been solved easier by using BST. For example, on IOI2012 there was a task "tournament" that was much easier (as for me) to implement with BST, and that was exactly what four members of Russian team did. It is not prohibited to use excluded technics, isn't it? =)
Isn't treap random-based algorithm?
Yes, it is. Why are you asking?
Maybe he meant a deterministic balanced BST.
I thought random is not perfect solution but I realized solution on IOI do not have to be perfect.
Don't you use hashtables or string hashing? They are also not "perfect" but work... perfectly :)
Well, I would not call expected 2logN depth as imperfect in terms of scoring 100 points where N equals 10^5?
It is imperfect since for some worst data, height is N-1. If the problem is on Codeforces, someone might hack your code finding worst case.
Nope, I am afraid you are wrong. Expected depth of Treap is 2logN whatever the input is.
Also having a treap with depth N is so unlikely that instead of that you can expect to happen some software crash.
It is same as calling Binary search tree is perfect solution because probability of getting skewed tree is same. Difference is solution using binary search tree is easy to find counter-example while treap isn't.
I'm not saying whether you can use it IOI or such competition. But I am saying about the solution is perfect, I mean lower bound is O(n lg n) especially, mathematically.
Treap is probablistic algorithm. It works on many "random" datas for extremely high probability. but, The probability is not a guarantee that, it is also hard to find a hack data for treap. Trying random data to hack treap is like a brute-force algorithm. There might be a clever way to hack it. (Of course maybe not — cause it can be NP-hard, but I didn't heard of any proof for that :) )
For example, I like string hashing (cuz I even can't code KMP) when solving problems. that's why I tried to solve APIO'14 palindrome with string hashing — which made my code fail on subtask #3. I debuged my code over and over again, but I really didn't know why. And then I found about Anti-hash test. I was really shocked — since I never expected such test exists. Also, IPSC 2014 H shows, even hashsets have it's worst-case data.
I don't think we can meet those hack datas in upcoming IOI — since finding hack data for treap (with given random generator) is a hard algorithmic task. but I think Konijntje's mathematical perfectionism is enough meaningful.
Would you mind learning what treap is before commenting please.
I don't know what is the problem with my argument.
Treap with depth N happens if random value assigned is same as key or its reverse. With fixed seed, PRNG always gives same random value. So if we give input data as random value sequence used by treap, it will be skewed making worst case. Am I wrong?
So, you are claming that one can find a test case to hack a solution that uses rand() function.
I would like to point out, this case is not same as antihash tests.
We need to find a test case which should hack the solution that uses seed with current miliseconds. And we are not trying to make the depth of the tree 2logN+1 or something. We need significiant increase. I probably can not prove that we can not find such a case yet it sems like impossible.
talking about perfectness.
If we want to compare splay tree and treap splay has a advantage for being deterministic, but this does not make it perfect neither from this point of view.
If we will compare balanced bst snd find weakness relativly to each other to describe them imperfect this all conversation becomes pointless:)
It was not a reply to you. All of the comments are in the same depth, because we have reached maximum level.
The problem is you can not find the value seed while hacking if one is using current miliseconds to seed.
Random solution has counter-example even it is low probability. There IS case for treap running O(n)
I gave example of Codeforces, but what if other competition such time related system call is prohibited?
I'll stop saying any-more.
I suggest you stop being so stubborn and try to understand what people are saying. You are red so it's expected that you know a little bit more about randomness.
Treap is not similar to hashing. Hashings can be hacked much easier by using both the birthday problem idea and making use of the fact that hash is deterministic in a sense (fixed modulo and base).
Hacking a treap is in my opinion just practically impossible. Maybe you will find 3logN depth, maybe 5logN, maybe even 10logN or 20logN if you work hard, but getting depth of O(N) order? That's just something that won't happen.
The chance of that happening is so low, I'm pretty sure in the whole history of treaps, if we took all the treaps that were ever written by anyone (using randomised priorities) and check them, we would still not find anything even partially close to O(N) depth. "There is such case even if it's low-probability" is just not an argument.
On your second note I agree — it might be inconvenient if there is a competition with prohibition to time related system calls and allowed hacks. There are probably ways to go around that too, but I haven't seen such competition myself so far.
Treap is my tree of choice and I personally never understood the concept of Splay (always looks like linear time to me) but I don't go around claiming it's worse than other trees.
About prohibited time call.
I can get hash of input as random seed. Try to find test, good luck :)
About "there is such test with low probability"
Probability of this have same order, as random bit in memory will change, because of some quantum effect with electricity in it, or anyway else. Do you have any ideas how to fix this problem?
And about Splay tree.
It's not easy to understand, but it really works in O(nlogn) total time, for n requests, although any one request can work in O(n) time. And it have really small constant factor in this O()
Since expected depth is 2logN, the higher the deviation of that the lower the chance. Getting a tree with height N-1 randomly is probably less likely than winning the lottery thrice and getting struck by a lightning all in the same day.
I was impressed last year at JBOI in Belgrade when I saw some competitor from Romanian team using treap to solve a task from the competition. JBOI is a elementary school competition. :)
:o That's weird, I think that a little number of polish contestants would be able to implement at least one balanced BST in a competition (I wouldn't). Did you mean that balanced tree was easier for you than standard segment tree ._.? For me that's extra weird! For now I quite don't recall that problem (though I got it accepted during IOI), but was it specific in some way that caused that using BBST was easier than segment tree?
Maybe I should learn treaps?
Of course I'm familiar with a standard segment tree, but those are structures solving different problems. BST is designated for storing a set of elements ordered by a key. You may make a segment tree simulate such behavior if keys are integers, but when they are doubles it becomes much harder. On the other hand, BST may implement any kind of query that segment tree is able to do (though, usually with larger constant), so
.
That task was about a tournament of following form: there is a line of n knights and each tour looks like "knights from l-th to r-th (in order from left to right) fight with each other and the winner returns back to the line on his place" and some complicated question about where should a knight being late stand in order to blah-blah-blah.
One of the subproblems raised in that problem was how to understand which knights will fight in the i-th tour. By using BST this is not a problem at all: you just simulate the tournament since BST allows queries of form "split out the segment [l, r] from ths structure" in
(if only an std::set was able to shift iterators in 
=( ...). In this particular case it was also possible to handle this part by using segment-tree and storing some mapping from old indices to new indices in it, but this segment tree should be able to perform group operations... I think in this case it is strictly harder to use segment tree instead of a data structure that is designated for queries of such type.
I don't really know why many strong coders are afraid of BSTs. Here is the complete implementation of what I described above: the data structure that holds a sequence of integers (node::x is a value of element) and that is able to perform arbitrary merges and splits in
time. It looks no harder than a segment tree with group operations.
So, I think you should definitely learn treaps since there are sometimes tasks where segment tree and std::set are not enough.
Wow, indeed, as you described it, it now seems to me that BSTs are a "true solution" to this problem and doing it with segment tree is just making someone's life harder on his own request. Thanks!
If key is integer value, We can make OSRank with segment tree with dynamic memory allocation. And I am using it when I have to implement OSRank. (If I have to Implement just BBST, I use std::set)
One trick is changing double to long long with preserving order is easy.
So we can just implement OSRank with segment tree just for double.
Action splitting out can be done by lazy propagation.
It might be just my fear of BBST since I have never implemented that one while competition, even BST, I feel segment tree is much more easier than BBST solving problems.
But I am going to study BBST. Maybe, after I learned treap well, I might feel embarrassed writing "segment tree is much more easier than BBST."
Your code is less scary because you don't do rotations. How then do you keep the x's in order? Doesn't this merge destroy the order?
It seems like the ratio C++/Java working time is slightly descending to 1.0, as the Java compiler becomes more and more efficient (not considering IO here). Moreover, during the practise session of ACM ICPC 2015 World Finals my team (and some other teams as well) was stunned by an incredible fact that floyd algorithm (with "if", not "min") worked significantly faster if written on Java, instead of C++. The ratio was about 1.2 — 1.3. One who is interested may check the versions on the official competition site, AFAIR they were 4.9.2 for gcc and 8 for Java.
It is not accurate to tell that Java becomes to work as good as C++ by comparing them on simplest routines like Floyd algorithm. The main bottleneck (as well as one of the main advantages) is the Java's model of memory that starts to slow down the program when memory usage exceeds ~20 Mb (that's my empirical observation from writing solutions for all Codeforces problems on Java).
To make Java work as fast as C++ you have to discard almost all Java benefits that involve dynamic object allocation and fall back to the primitive types and almost static arrays. After that there is no big difference between your Java code and equivalent C++ (or even pure C) code.
Regarding the surprising fact that Java worked faster in ICPC finals environment, was that on your local machine or are you talking about time consumption while testing on a judging machine?
Judging machines were equivalent to contestants, but I guess you're talking about the way of measuring time. Do not actually remember — need to ask meshanya. Anyway, it felt like ordering a filet mignon in MacDonalds :)
Two pieces of useful information:
A detailed changelog: http://people.ksp.sk/~misof//ioi-syllabus/ioi-syllabus-2015-diff.pdf
A note about IOI 2015 tasks: http://people.ksp.sk/~misof/ioi-syllabus/note2015.html
Do we have a line scoreboard for IOI 2015 ?
http://scoreboard.ioinformatics.org/Ranking.html