Блог пользователя kostka

Автор kostka, 5 месяцев назад, По-английски

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

Is anyone aware of any mirror?

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

  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Rafi22 will win CEOI 2024!!!

»
5 месяцев назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
    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.

    • »
      »
      »
      5 месяцев назад, # ^ |
        Проголосовать: нравится +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 it`ll be 100)

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        I initially had like 83 with this.

        • »
          »
          »
          »
          »
          5 месяцев назад, # ^ |
            Проголосовать: нравится 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$$$

      • »
        »
        »
        »
        5 месяцев назад, # ^ |
          Проголосовать: нравится 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 :)

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 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 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.

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 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.

»
5 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Mid

»
5 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Error-42 will win CEOI 2024!

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 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 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.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

More info about the mirror here.