prabowo's blog

IOI 2022 Tasks
By prabowo, history, 2 years 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

Comments Comments (23)
| Write comment?
»
2 years 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.

→ Reply
»
2 years 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.

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Will there be an official tutorial this year?

→ Reply
»
2 years 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.

→ Reply
»
2 years 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?

→ Reply
  • »
    »
    2 years 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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

      Wow I thought that they never gonna give the problems up.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Day 2 contest only happens on Friday (tomorrow)

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't there any Russian team this time?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

2 ez 4 me

→ Reply
»
2 years 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.

→ Reply
»
2 years 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

→ Reply
  • »
    »
    2 years 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$$$.

    → Reply
    • »
      »
      »
      2 years 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.

      → Reply
      • »
        »
        »
        »
        2 years 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.)

        → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    A + B

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting tasks

→ Reply
»
2 years 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.

→ Reply
  • »
    »
    2 years 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!

    → Reply
  • »
    »
    2 years 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.

    → Reply