prabowo's blog

By prabowo, history, 7 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +150
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 2   Vote: I like it +93 Vote: I do not like it

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.

»
7 weeks ago, # |
Rev. 2   Vote: I like it +42 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Thanks for standing

»
7 weeks ago, # |
  Vote: I like it -81 Vote: I do not like it

i am not coder, ioi contests is like div2 in Codeforces?

»
7 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Will there be an official tutorial this year?

»
7 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

i can't see day 2 tasks where are they can someone please link?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    I hacked them, it was pretty easy to get access. Very much olympiad in informatics, very much effort. You can access them here

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Day 2 contest only happens on Friday (tomorrow)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't there any Russian team this time?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

2 ez 4 me

»
7 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

»
7 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    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 in the machine. If 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$$$.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 7   Vote: I like it +5 Vote: I do not like it

        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.)

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting tasks

»
7 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

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.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I think the problem was a great addition to the set. Thank you for proposing it!

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like 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.