... has started today. Best of luck to all the participants!
Is anyone aware of any mirror?
The website: https://ceoi2024.fi.muni.cz/
# | User | Rating |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
... has started today. Best of luck to all the participants!
Is anyone aware of any mirror?
The website: https://ceoi2024.fi.muni.cz/
Name |
---|
Rafi22 will win CEOI 2024!!!
Ranking and task statements: https://ceoi2024.fi.muni.cz/blog/2024/06/25/ranking/
I suppose we can talk about the problems now. If so, how can we optimize the obvious binary search solution?
Binary search would probably be fine for some small P, but here is a simple observation for P = 0.2 (generally for bigger P values)
Split the array in around sqrt(N) blocks. Here we can split the areay in blocks of length 30.
For each block we query if there are any positive patients, and if there are we apply the standard binary search.
my solution (tested today after the end, because i am just a TL, not a participant) was to divide blocks with length $$$x$$$ where $$$x$$$ is the maximal integer solution to this inequality:
i can write my solution fully, just tag me (my solution got 99.12 but after some tweaking it`ll be 100)
I initially had like 83 with this.
While doing binary search on the block,you search only for the first 1, when you know it's $$$pos$$$ ,you break the search and make a new block which starts at $$$pos+1$$$
That's a really nice solution.
Do you know how many points would the sqrt blocks solution score(applied on bigger P values).
Thanks in advance :)
Unfortunately no,sorry( this was the only solution that I got to.
Ok, thanks!
Is there something I'm missing here?
Let's say $$$p=0.2$$$. Then $$$x=3$$$. Let's first count the average number of queries we spend if $$$n=2$$$ if we know there's at least 1 positive sample: we test the first sample(1 query) and if it's positive($$$\frac{5}{9}$$$ chance) we test the other one; $$$\frac{14}{9}$$$ queries on average. If we didn't know there was at least 1 positive sample, it's optimal to first check that(1 query) and then ask $$$\frac{14}{9}$$$ queries with a $$$\frac{9}{25}$$$ chance, for an average of $$$\frac{39}{25}$$$ queries.
Now let's move back to this solution. There is a $$$\frac{64}{125}$$$ chance that the test is negative on a block(1 query). If the test is positive, let's test just the first sample. There are 2 possible outcomes:
1) It's positive($$$\frac{1}{5}$$$ chance): we need to solve the other 2 samples without any knowledge on them, total: 1 query on entire block, 1 query on first sample, $$$\frac{39}{25}$$$ queries on the last 2 samples, $$$\frac{89}{25}$$$ queries in total
2) It's negative($$$\frac{36}{125}$$$ chance): we need to solve the other 2 samples knowing that one of them is positive, total: 1 query on entire block, 1 query on first sample, $$$\frac{14}{9}$$$ queries on the last 2 samples, $$$\frac{32}{9}$$$ queries in total
All in all, on a block $$$\frac{64}{125} \cdot 1 + \frac{1}{5} \cdot \frac{89}{25} + \frac{36}{125} \cdot \frac{32}{9} = \frac{281}{125}$$$ queries are spent in total, and with $$$333$$$ blocks the average number of queries should be $$$748.584$$$, which means the number of points shouldn't be higher than 93 according to the formula in the problem statement.
The "optimal" solution is slightly different. When the first sample is positive, then you will not solve other 2 samples but you will move to shifted block starting from the second student.
Mid
Error-42 will win CEOI 2024!
Error-42 has in fact won CEOI 2024!
We plan to start the mirror in the next week and keep it running for about two weeks.
Official comment about mirror of CEOI 2024 from organisators:
"Due to the fact that servers are not ours, but from Masarikova university, we cannot guarantee that they won`t collapse if the contest is open (even as a mirror) to unofficial participants.After CEOI ends there would be a mirror published for +-2 weeks with all materials for anyone to host competition on their own server".
this is the official information because today after we (team leaders) were discussing first day I asked the same question.
Do you know roughly when this will open?
Unfortunately no,sorry. We'll just have to wait untill the official information
Day2 ranking and task statements: https://ceoi2024.fi.muni.cz/blog/2024/06/27/day2/
More info about the mirror here.