kostka's blog

By kostka, 3 weeks ago,

... has started today. Best of luck to all the participants!

Is anyone aware of any mirror?

The website: https://ceoi2024.fi.muni.cz/

• +53

 » 3 weeks ago, # |   +17 Rafi22 will win CEOI 2024!!!
 » 3 weeks ago, # |   +24 Ranking and task statements: https://ceoi2024.fi.muni.cz/blog/2024/06/25/ranking/
 » 3 weeks ago, # |   0 I suppose we can talk about the problems now. If so, how can we optimize the obvious binary search solution?
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +3 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.
•  » » » 3 weeks ago, # ^ |   +1 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: $(1-p)^x \ge \frac{1}{2}$i can write my solution fully, just tag me (my solution got 99.12 but after some tweaking itll be 100)
•  » » » » 3 weeks ago, # ^ |   +1 I initially had like 83 with this.
•  » » » » » 3 weeks ago, # ^ |   0 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$
•  » » » » 3 weeks ago, # ^ |   0 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 :)
•  » » » » » 3 weeks ago, # ^ |   +1 Unfortunately no,sorry( this was the only solution that I got to.
•  » » » » » » 3 weeks ago, # ^ |   0 Ok, thanks!
•  » » » » 2 weeks ago, # ^ |   0 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 total2) 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 totalAll 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.
•  » » » » » 2 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # |   +14 Mid
 » 3 weeks ago, # |   +18 Error-42 will win CEOI 2024!
•  » » 2 weeks ago, # ^ |   +13 Error-42 has in fact won CEOI 2024!
 » 3 weeks ago, # |   0 We plan to start the mirror in the next week and keep it running for about two weeks.
 » 3 weeks ago, # |   0 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 wont 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.
•  » » 2 weeks ago, # ^ |   0 Do you know roughly when this will open?
•  » » » 2 weeks ago, # ^ |   0 Unfortunately no,sorry. We'll just have to wait untill the official information
 » 2 weeks ago, # |   0 Day2 ranking and task statements: https://ceoi2024.fi.muni.cz/blog/2024/06/27/day2/