I conducted a camp for Kazakhstan via the Internet and I was allowed to record it. I'm putting some of those lectures and problem analysis on Youtube. Maybe it will be useful for participants who are still practicing. See recent videos here, https://www.youtube.com/errichto2.
There are currently solutions for Innopolis Open 2018-19 (cool hard contest in CF GYM), two days of POI 23 (2015-2016) and also a lecture on wavelet trees. Innopolis Open solutions include these two methods:
Spoiler
Will soon add some more, including segment tree beats and Li Chao tree.
How are wavelet, segment tree beats and lichao relevant to IOI?
They are not-well-known data structures that can appear in IOI-style contest. Something quite valuable to know for people fighting for high medals.
In particular, I based the wavelet trees lecture on an article from IOI.
I doubt these can be of use in the IOI, since they try to stay strict with the syllabus. Maybe for some partial points. Anyway, good work.
Interesting. Are you saying they try to avoid something that is not explicitly mentioned in the syllabus but is known to part of the community? Wouldn't that disqualify e.g. parametric search in IOI 2016?
Wavelet trees and Li Chao are (more or less) alternatives to other methods so I'm quite sure they can appear as one of intended solutions.
EDIT: I don't see square root decomposition or Mo's algorithm in the syllabus. Does it mean it can't be the intended solution?
The syllabus addresses that too. Outside of Focus:
"Any topic that is not explicitly addressed by the Syllabus should be considered to belong to this category.
Contestants are not expected to have knowledge of these topics. Most competition tasks will not be related to any topics from this category.
However, this does not prevent the inclusion of a competition task that is related to a particular topic from this category. The ISC may wish to include such a competition task in order to broaden the scope of the IOI.
If such a task is considered for the IOI, the ISC will make sure that the task can reasonably be solved without prior knowledge of the particular topic, and that the task can be stated in terms of Included and To be Defined concepts in a precise, concise, and clear way."
Sqrt decomposition is so broad it isn't even a topic, but it usually falls under the harder topics from AL1 (complexity analysis, tuning parameters) plus another topic.
bump ^
I don't get this logic. Is it broader than segment trees?
And I would argue that everything I mentioned in the blog is some augmented segment tree.
I think it would.
Absolutely. Sqrt decomposition of what?
And this suggests that you should know algorithms/techniques outside of the syllabus.
Come on. You usually do sqrt decomposition of sequence (sometimes a sequence of queries), just like you can build a segment tree over it.
You should know and be able to solve everything to 100% win IOI. That isn't practical advice. It is possible that someone will wrap up wavelet trees in a way that will get it to the contest, but I'll bet you a beer it won't happen this year. With any of these three things.
How do you do it online, for example in Dynamic Diameter from our CEOI? Because it's possible.
You can do sqrt decomposition of a binary tree.
You don't have to use sqrt2 decomposition exactly, it can be sqrt3 decomposition if that gets you better complexity.
A segment tree is a specific data structure. There are variations, but would you call a treap "just a more general segment tree"?
No algorithm has high probability of appearing with a few exceptions like binary search. I'm betting that the number of times wavelet/lichao/beats will be useful is bigger than the number of times Euler cycle and quicksort (k-th smallest element) will be useful, both included in the syllabus. You win if it's smaller.
I can do both sqrt decomposition and segmenttree-like recursion (parallel binary search) in your Dynamic Diameter.
I don't feel confident enough about algorithms and nomenclature to argue about that segtree/sqrtdeco thing, I give up there.
Really? You really think wavelet/lichao/beats will be more useful in IOI than quicksort?
That's how I know I shouldn't take you seriously.
Speaking about IOI syllabus, I always have this problem about whether we needed to know splay/treap/etc or not.
It says, "Problems will not be designed to distinguish between the implementation of BBSTs, such as treaps, splay trees, AVL trees, or scapegoat trees"
Does that mean i only have to know how to use std::set?
I asked several people and most of them thinks we need to know to write our own BST, while i think otherwise. It also appears that IOI 2013 Game requires a treap or something (? not sure), but i dont know how to get the 2013 version syllabus.
What do you guys think?
IOI 2013 Game requires efficient 2D segment trees with path compression or similar structures. It was real cancer and I think 2D structures got excluded from the syllabus because of it afterwards.
I think what is meant, is that a problem requiring a BBST (unlike a set, possibly augmented with rank and such) is solvable using any of them, indifferent to constants in runtime or functionality — that is, you only need to know one of them, not all.
IOI13 Game requires a DS (on the 2nd dimension) that can update a cell and query for range gcd, when the array is of size 1e9. You can use a sparse segtree, but together with the 1st dimension this adds a log^2 factor to memory. The optimization is to instead use a BBST on the 2nd dimension, then you cut a log off memory. It doesn't need treap, you can use any BBST.
A BBST isn't necessary for Game btw, you can get 100 with a sparse segment tree if you add any path compression.
Sounds awful, I'd rather implement a treap 5 times in a row.
Compared to implementing the 2D Segment Tree, adding path compression isn't much more trouble. If you have a long chain of nodes you just skip all the intermediate nodes and jump from the top of the chain to the bottom.
Such implementation will use about \frac{log^2 C}{2}) nodes per update. It worked on the IOI problem narrowly (Also tests in IOI is weak)
How exactly do you do path compression on a dynamic segtree. do you have any blogs or codes with the technique?
I haven't come across any blogs on it, it's just something I came up when trying to get 100 on Game. Plus, I reckon ko_osaga is correct about it adding $$$\frac{log^2 C}{2}$$$ nodes in the worst case, it just needs to have a specific test designed to make it fail.
If you want you can have a look at my submission here, https://oj.uz/submission/54531, but it's not pretty and I'm not even sure it optimally compresses the segtree since I stopped improving it once I got the 100/100.
Are you basing that on the IOI syllabus?
Also, the journal Olympiads in Informatics is co-published by the IOI, but it has a much broader focus.
Eagerly waiting for the tutorials on segment tree beats and li chao tree even though I am an IOI participant.
I just watched your video about POI23 day 2. I found it quite enjoyable, and other similar videos as well, so thanks for making them. However, I do want to mention something about the last problem. You may have figured this out by yourselve in the meantime, but I think for Club members (KLU), the way you describe to choose the 'yellow edges' in your youtube video is wrong. Below I will use the same terminology (and colors) as you use in your video and I will talk about cubes and squares, but this generalizes to higher dimensions as well.
For example, for input '3 0 4 1 5 2 6 3 7', suppose you split the cube into the two squares (0123) and (4567) , and you choose the yellow edges 0-3 and 1-2 in the first square. Now before knowing the final cycle in the first square, there is no way to choose yellow edges in the second square that guarantees that there won't be multiple cycles when we merge the two subsolutions. More specifically:
The way to fix this is to first solve the subproblem in the first square, and then to choose the yellow edges of the second square such that they correspond to the 'blue' edges of the first square. Now we can prove that the merged result will always be a single cycle.
Informal proof: if we start from a vertex of the first square and start by first taking a blue edge, the only thing that can possibly go wrong is that from a vertex in the second square we prematurely (when there are other unvisited vertexes remaining) go to the vertex connected with a green crossing edge to first vertex. But the vertexes visited in the second square are consecutive vertexes of the cycle in the second square (when we take a blue edge from the first square, we have added a corresponding yellow edge to the second square, which must be in the cycle, and when we take a blue edge from the second square, it is by definition in the cycle). Since the cycle for the second square visits all its vertexes, this cannot happen.