IOI 2022 Day 1 has just ended.
- The tasks for IOI 2022 have been published on the IOI 2022 website.
- Final ranking can be seen from https://ranking.ioi2022.id/
- Live streaming (containing tasks discussion) for day 1 and day 2 from the official IOI 2022 YouTube channel.
- Tasks will soon be available on Codeforces IOI archive (https://ioi.contest.codeforces.com/)
UPD. Day 2 has ended.
UPD. The IOI 2022 has officially ended, the editorial is ready on the task page as well.
Thanks to the authors and organizers. Congratulation to all participants!
You can solve all Day 1 tasks here: https://oj.uz/problems/source/615
In case you want to solve it in 5 hours, you can try here: https://oj.uz/contest/view/IOI2022DAY1
Also, you will be able to solve it on Codeforces archive (https://ioi.contest.codeforces.com/) soon, according to this comment.
First day problems are available to submit on https://ioi.contest.codeforces.com/group/32KGsXgiKA/contest/103877
There are no native HTML statements on codeforces now, you can use official ones. If someone has markdown versions of statements they would appear much faster.
These are hopefully the final versions of English markdown for day 1: day1-markdown.zip
Will there be an official tutorial this year?
For problem towers, is there any easier (idea-wise) solution when offline queries are allowed? Since queries are given online, I had to add 60 lines of code that were completely meaningless.
I think this problem is just standard and okay, but not enforcing online queries will make it look much better.
Anyway, the other two problems were very good.
i can't see day 2 tasks where are they can someone please link?
I hacked them, it was pretty easy to get access. Very much olympiad in informatics, very much effort. You can access them here
Wow I thought that they never gonna give the problems up.
Day 2 contest only happens on Friday (tomorrow)
Isn't there any Russian team this time?
The Russia and Belarus teams are competing under the IOI flag (https://mirror.codeforces.com/blog/entry/100834)
They aren't teams. They are "individuals under the IOI flag, and not under any national name, flag or symbols".
2 ez 4 me
Haven't looked at the tasks yet, but since I have been critical of IOI's difficulty distribution for the past few years and just looking at the results from this year I wanted to congratulate the ISC for doing a much better job this year.
For problem insects, how to improve from 99.89 to 100?
I did 99.89 as follows:
check(x)to check whether each type of insects appear at least x times.check(f)is true, we do not remove any insects from the machine. Whencheck(f)is false, we only use the set of insects inside this machine in future iterations.My code: https://oj.uz/submission/628167
I did not code it up yet but I have a proven solution using at most 3N operations of each type which is similar to yours except with a small change in the end.
We need N operations for finding the number of distinct types. After that the number of operations is N+N/2+N/4+...<=2N.
I am traveling currently so cannot code this right now. I am not sure whether this is supposed to get 100 or $$$100-\epsilon$$$.
What exactly is the small change in the end? I don't see any difference between your solution and I_love_Hoang_Yen's.
"Then, in either case, in the next iteration we restrict ourselves to atmost N/2 insects."
That's not true; you restrict yourself to at most $$$K \cdot \left \lceil{\frac{N}{2K}}\right \rceil$$$ insects. If $$$N=34K$$$, you'll ask $$$34K+33K+17K+9K+5K+3K+2K+K=104K=(3+\frac{1}{17})N$$$ queries in the worst case.
Right, sorry. I did not notice the rounding issue. As of now I am not sure how to fix this. I guess this isn't the 100pt solution...
The difference from I_love_hoang_yen's solution is that I am setting the threshold to be ~ N/2K which roughly halves the number of insects in the next round, whereas he is setting the next threshold to be the midpoint of the currently known bounds. (Edit: Never mind, just looked at his code. That is what he is doing too.)
A + B
Interesting tasks
I should write about Day 1 Problem "Prisoner Challenge" here. Did you enjoyed this task? Maybe some of them were confused because the problem setting was too rare as a competitive programming problem... But I am really glad that many people told me that they enjoyed the problem :)
Actually I (along with E869120) proposed this problem for IOI 2022. We are very happy about it, and very thankful to scientific committee for preparing it. Before the contest, I predicted that this problem would be solved by only one. But it was actually solved by 8 contestants. I was really astonished, and congratulations!
I would like to share one question behind this problem here, because it may be more interesting to think about it. Currently, the best $$$N$$$ we obtained for this problem for each $$$X$$$ is exactly the same as the the value $$$dp[X]$$$ (for definition, look at the editorial in IOI website). It means, for example, no solution is currently found for $$$N = 5589$$$ and $$$X = 20$$$. I conjecture that it is optimal. And it would be interesting to know if the conjecture is true or not.
I think the problem was a great addition to the set. Thank you for proposing it!
I think it is an amazing problem! One of the thing I like about IOI is that it allows this kind of problem to appear (another similar one I remember is Parrots from IOI 2011). I really enjoyed the process of gradually optimizing my 80 point solution to 90 and then 100.