kostka's blog

CEOI 2024
By kostka, 4 days ago, In English

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

Is anyone aware of any mirror?

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

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

»
4 days ago, # |
  Vote: I like it +17 Vote: I do not like it

Rafi22 will win CEOI 2024!!!

→ Reply
»
3 days ago, # |
  Vote: I like it +24 Vote: I do not like it

Ranking and task statements: https://ceoi2024.fi.muni.cz/blog/2024/06/25/ranking/

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I suppose we can talk about the problems now. If so, how can we optimize the obvious binary search solution?

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

    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.

    → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 it`ll be 100)

      → Reply
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I initially had like 83 with this.

        → Reply
        • »
          »
          »
          »
          »
          3 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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$$$

          → Reply
      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          3 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Unfortunately no,sorry( this was the only solution that I got to.

          → Reply
      • »
        »
        »
        »
        25 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
3 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Mid

→ Reply
»
3 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Error-42 will win CEOI 2024!

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

We plan to start the mirror in the next week and keep it running for about two weeks.

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Day2 ranking and task statements: https://ceoi2024.fi.muni.cz/blog/2024/06/27/day2/

→ Reply