The SOIminar is an invite-only seminar-style training for IOI candidates.
- Julian Steinmann
- Nicolas Camenisch
- Johannes Kapfhammer
- Daniel Rutschmann
- Timon Gehr
How it works
Each edition takes about three months and you have to prepare two reports. The deadlines for the first one look like this:
- week 0: topic of the first report is final
- week 3: hand in your first report, topic of the second report is final
- week 4: review somone else’s first report and implement it yourself
- week 6: hand in your second report and the final version of your first report
- week 7: review someone else’s second report and implement it yourself
- week 9: hand in the final version of your second report
- week 10-12: on-site meeting where you present both of your reports and listen about other reports. The presentation is done on the blackboard (or beamer if you insist) and should take around 20min. Following your presentation there is a small discussion of around 10min.
- 2 weeks after the meeting: you’ve implemented the task/data structure/algorithm of at least 2 other papers (not reviewed by you).
A report is a written article about a particular topic (see below for proposed topics). This report will be published on our website. Topics have to be approved by your advisor, who will assist you if you get stuck and helps you to structure your report. Your report will be reviewed by another seminar member, while you will review another member’s report. The advisor will review your final report.
All reports will be presented and discussed in an on-site seminar, and subsequently be published on soi.ch. After the seminar, you’re invited into a fancy restaurant, a concert or another treat (voted by you).
You can only attend the seminar if you have two accepted reports. Failure to finish the reports in a reasonable quality within the deadline disqualifies you for the on-site seminar. A report consists of between 4 (minimum), 6 (recommended) up to 8 (maximum) A4 pages (excluding source code), together with an implementation in C++, and has to be written in English. The text has to be written by yourself, with citations where they are due. The write-up has to be produced with the following LaTeX template: soiminar.cls. You can use that just as any documentclass. Look at the LaTeX sources of other reports or ask your mentor if you’re unsure how to use it.
The presentation can be done in German if all attendees speak German.
Why you profit
- The way to learn solving very hard tasks in a few hours is to train by thinking about even harder tasks for a long time. Many of the concepts and problem solving strategies required for hard tasks can also be applied for easier tasks.
- Learning advanced techniques is good for similar reasons: They give new insights about how to think about problems, and some of those ideas can also be employed in other areas.
- Implementing something you’ve understood is actually not that hard.
- During a contest, you need intuition: “This approach looks optimal, so let’s try coding it”. However, you can only gain this intuition if you have a lot of experience in rigorously proving similar problems. You learn doing that by writing a report.
- You learn a lot of secondary things: how to write a scientific paper in English, how to do a technical presentation, how can I write something in LaTeX, etc.
- … and on top of that you get a nice seminar day with a treat!
You can propose any topic. Below are some suggestions.
Note that you don’t have to cover everything, it is fine if you focus on only the most basic application of some advanced data structure (discuss that with your advisor). By default, both reports are not building on top of each other, but if you think the topic is sufficiently sophisticated and you can make two parts out of it, feel free to discuss this with your advisor.
- Plot purchase: https://codeforces.com/blog/entry/61239
- Pigeonhole Principle: https://petr-mitrichev.blogspot.com/2017/05/a-zero-pigeon-week.html
- two trees: https://petr-mitrichev.blogspot.com/2017/07/a-week-with-two-trees.html
- Archive reloaded: https://codeforces.com/blog/entry/56693?#comment-403722
- Most tasks from here (check back with advisor): https://docs.google.com/spreadsheets/d/1-kY6uiLOo1AKSBCSjbpGRBZbIldO_3dg6oTRKIJzT-g/edit#gid=0
- Segment tree beats: https://codeforces.com/blog/entry/57319
- Sqrt-tree: http://codeforces.com/blog/entry/57046
- Open-Close interval trick: https://codeforces.com/blog/entry/47764
- Change the object to dp: https://codeforces.com/blog/entry/47764
- Connected component dp: https://codeforces.com/blog/entry/47764
- × 2, + 1 trick: https://codeforces.com/blog/entry/47764
- Knuth optimization: https://codeforces.com/blog/entry/8219
- non-adaptive max with binary search: https://codeforces.com/blog/entry/62602
- Dominator tree: https://tanujkhattar.wordpress.com/2016/01/11/dominator-tree-of-a-directed-graph/
- Heavy-light decomposition: https://codeforces.com/blog/entry/53170
- Wavelet tree: https://codeforces.com/blog/entry/52854
- Manacher’s algorithm: https://codeforces.com/blog/entry/12143
- Segment intersection: https://cp-algorithms.com/geometry/intersecting_segments.html
- Median of medians: https://en.wikipedia.org/wiki/Median_of_medians
- Balanced binary search trees. One of:
- splay tree
- AVL tree
- scapegoat tree