We would like to invite you to CEOI 2024 online mirror, which will take place between Sunday, June 30 at 20:00 UTC and Monday, July 15 at 6:00 UTC. Please do not discuss the tasks until the end of the mirror in order not to spoil the tasks for others.
To participate in the contest, go to the contest system, register and then log in. You can solve any tasks in any order you like during the entire contest period.
The problems were prepared by Svizel_pritula, Dakto, David Kolář, MapleTree314, Yongaron, JiriKalvoda, osladky, rakdver, timreizin, -Wave- and me.
Lot of thanks goes to:
- JiriKalvoda for heavy lifting as the Head of SC.
- HaroldVemeno, Dakto and merlin_wizard for testing the competition.
- Martin Mareš and Jan Hadrava for herding the computers and running the contest system.
- Tom Pitner and local organizers for running the event
- And finally, all contestants and team leaders for the great atmosphere!
Update: You can find editorials and other task materials here.
Thanks for your efforts!
Just wondering, can there be an option for a virtual contest ?
Thanks for the mirror. I am also wondering could it be set to normal contests (as if 4-5h for 3-4 problems), otherwise this is simply the same as upsolving.
Nice contest
Will participate
why is 13 missing?
oolimry and I wrote an unofficial editorial since after asking organizers, it seems that editorial is not public?
Organizers said that it is ok to make the editorial public, so here it is https://errorgorn.github.io/2024/07/03/CEOI.html
Please don't directly copy codes here into the online mirror, thanks
I was actually wondering if there will be any editorial, Thank you!
Still working on it, sorry. Hopefully will have it published by the end of the week.
Re: covid, my approach was similar to the unofficial editorial but I think it's a bit cleaner.
We maintain two groups of students: one of which we know nothing about, the other of which, if nonempty, has at least one infected student. If the second group is nonempty, we query a subset of it, or else we query a subset of the first group. Initially, everyone starts in the first group, and the solution terminates when both groups are empty.
To determine the number of students to query: always query the number of students that causes the query to return true or false with closest to one-half probability. This works for all but one of the tests (and you can make a slight tweak to pass that one).
This avoids any explicit binary searching.
How can one calculate the expected number of queries for such a solution?
Suppose you can always find a query that returns true or false with exactly one half-probability. Then a string that occurs with probability $$$x$$$ requires exactly $$$-\log_2 x$$$ queries, and the expected number of queries is equal to the total binary entropy $$$NH(p)$$$. Here, $$$H(p)=-p\log_2p-(1-p)\log_2(1-p)$$$ is the binary entropy for a single coin flip that lands heads with probability $$$p$$$. This is actually a lower bound on the number of queries in general, though it's only exactly achievable for $$$p\in \{0, 0.5, 1\}$$$.
Let $$$dp[a][b]$$$ be the expected number of remaining queries needed when group 1 has size $$$a$$$ and group 2 has size $$$b$$$. There are $$$O(N^2)$$$ DP states and $$$O(1)$$$ work required for each, so this DP table can be filled in $$$O(N^2)$$$ time.
Note: You can also use the above DP to find the best number of queries over all strategies similar to the one I described (with the only difference being the number of students to query at each state $$$(a,b)$$$).
Suppose $$$N$$$ is large and you can't afford to compute the DP table exactly. Then assume that $$$dp[n][0]=cn$$$ for $$$n\in [N-\text{opt_group_size}, N-1]$$$ and solve for the $$$c$$$ that causes $$$dp[N][0]=cN$$$. This takes $$$O(\text{opt_group_size})$$$ time.
... Hello. I want to ask, why should we choose some B such that the first condition is correct? (Also I think you meant largest B not smallest B). I tried to find some B that satisfies the minimum possible value of the following:
$$$\lceil \frac{n}{B} \rceil + pnlogB$$$
The first part is the number of blocks, and the other part: the expected number of positive patients which is $$$pn$$$, and for each one I'm going to do a binary search inside a block of size B to find the patient. Why is my formula worse than your formula (it only got 64). I'd really appreciate it if you explain more the idea behind your condition of $$$(1-p)^B >= 0.5$$$ and why it's better than my formula. Edit: I just tried your condition too. It also got 64. Maybe I am implementing the binary search method wrong? Last Edit: your condition got 82 with my coding, while mine 79. Maybe they are too close? I still don't get why yours is better.
I think you should hide the above under a spoiler
done
I'll refer to the solution that uses "Binary Searching only once" in the link. The main reason why your formula is not accurate is that the $$$\frac{n}{B}$$$ term is underestimated. When you detect a block of size $$$B$$$ is positive, we binary search the first positive person in the block. Everyone afterwards is unknown, so we throw them back to the unknown queue. Hence the number of blocks we search is larger than $$$\frac{n}{B}$$$.
The most extreme case was when $$$p=0.2$$$, which gave $$$B=4$$$ using your formula when it should be $$$B=3$$$.
What this constant is I have no idea how to estimate, and so I use the probability of hitting a negative block as an estimate for what block size I should use. Anyways this is not 100% accurate and requires some engineering/ternary searching to determine the best $$$B$$$.
Regardless, I tested your formula and it got 95.6 in total so you might want to check your implementation:
Auto comment: topic has been updated by SK1PY (previous revision, new revision, compare).
Now that the mirror is over, is there any place we could upsolve the problems?
You can upsolve at https://www.acmicpc.net/category/1042
Thank you!
Nvm, I found how to do it :D