### prabowo's blog

By prabowo, history, 6 weeks ago,

IOI 2022 Day 1 has just ended.

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!

• +150

 » 6 weeks ago, # | ← Rev. 2 →   +93 You can solve all Day 1 tasks here: https://oj.uz/problems/source/615In case you want to solve it in 5 hours, you can try here: https://oj.uz/contest/view/IOI2022DAY1Also, you will be able to solve it on Codeforces archive (https://ioi.contest.codeforces.com/) soon, according to this comment.
 » 6 weeks ago, # | ← Rev. 2 →   +42 First day problems are available to submit on https://ioi.contest.codeforces.com/group/32KGsXgiKA/contest/103877There 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.
•  » » 6 weeks ago, # ^ |   +14 These are hopefully the final versions of English markdown for day 1: day1-markdown.zip
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -45 -
 » 6 weeks ago, # |   -10 Thanks for standing
 » 6 weeks ago, # |   -81 i am not coder, ioi contests is like div2 in Codeforces?
 » 6 weeks ago, # |   +8 Will there be an official tutorial this year?
 » 6 weeks ago, # |   +26 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.
 » 6 weeks ago, # |   +11 i can't see day 2 tasks where are they can someone please link?
•  » » 6 weeks ago, # ^ |   +47 I hacked them, it was pretty easy to get access. Very much olympiad in informatics, very much effort. You can access them here
•  » » » 6 weeks ago, # ^ |   +37 Wow I thought that they never gonna give the problems up.
•  » » 6 weeks ago, # ^ |   +11 Day 2 contest only happens on Friday (tomorrow)
 » 6 weeks ago, # |   0 Isn't there any Russian team this time?
•  » » 6 weeks ago, # ^ |   +16 The Russia and Belarus teams are competing under the IOI flag (https://codeforces.com/blog/entry/100834)
•  » » » 6 weeks ago, # ^ |   +60 They aren't teams. They are "individuals under the IOI flag, and not under any national name, flag or symbols".
 » 6 weeks ago, # |   0 2 ez 4 me
 » 6 weeks ago, # |   +18 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.
 » 6 weeks ago, # |   +10 For problem insects, how to improve from 99.89 to 100?I did 99.89 as follows: Find a set of unique insects with N operations. Using this set, we can write a function check(x) to check whether each type of insects appear at least x times. Binary search for the answer. This uses $12*N$ operations and got around 47 points. To improve, I noticed that we can reduce the number of operations based on results of previous binary search iterations: When check(f) is true, we do not remove any insects from the machine. When check(f) is false, we only use the set of insects inside this machine in future iterations. This uses slightly more than $3*N$ operations and got 99.89 points (though I don't know why). My code: https://oj.uz/submission/628167
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +8 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. As before, find the number of distinct types using N operations; suppose it is K. To check whether the answer is >= some threshold T, first empty the machine. Then add the insects one by one. If adding an insect causes the counter to go above T+1, remove it. In the end check if the total number of insects in the machine is K*T. If we perform the above check for some threshold T and find that the answer is =T, in the following iterations it suffices to restrict ourselves to the set of insects outside the machine and add T to the final answer. If there are N insects and K distinct types, an obvious upper bound is N/K. Do the above threshold test for T=N/2K. Then, in either case, in the next iteration we restrict ourselves to atmost N/2 insects. Repeat. 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$.
•  » » » 6 weeks ago, # ^ |   +5 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.
•  » » » » 6 weeks ago, # ^ | ← Rev. 7 →   +5 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.)
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 I'd just like to say, for bragging reasons, that I binary searched with a simple optimisation and got 85.something points (whenever I binary search and go too high, i take the set of values that i've constructed with frequency < value searched, and continued searching from there, basically the same thing, just 3 times more inneficient)
 » 6 weeks ago, # |   0 Interesting tasks
 » 6 weeks ago, # |   +44 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.
•  » » 6 weeks ago, # ^ |   +13 I think the problem was a great addition to the set. Thank you for proposing it!
•  » » 6 weeks ago, # ^ |   +8 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.