Ormlis's blog

XVIII Open Olympiad in Informatics (Unrated, Online Mirror, IOI rules)
By Ormlis, history, 8 months ago, translation, In English

Hi everybody,

In a few days there will be a Moscow Open Olympiad. This olympiad is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Olympiad in Programming, Moscow Team Olympiad, and Megapolis Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704, 707, 727, 751, 775, 802, 829, 852).

The Open Olympiad consists of the most interesting and difficult problems proposed by our authors' team. Therefore, we decided to conduct a non-rating mirror of the Olympiad on Codeforces. The Olympiad takes place in two rounds, each consisting of $$$4$$$ problems, not ordered by difficulty, and $$$5$$$ hours to solve them. The difficulty of the problems is comparable to the level of Div. 1. Each problem is worth $$$100$$$ points that are distributed into multiple subtasks with different constraints that allow the participant to earn partial score. Testing is done in the IOI format, where the participant receives a full testing report on all tests in the Online-subtasks during the competition. The feature of the Open Olympiad is that some problems have Offline-subtasks, the results of which will only be available after the end of the competition. Note, that you will not have access to the scoreboard during the competition.

The competition problems were created and prepared by Mangooste, vaaven, Tikhon228, ViktorSM, isaf27, TheEvilBird, sevlll777, Papaz239 и pakhomovee guided by Ormlis, grphil and Helen Andreeva.

The mirror on Codeforces will take place in Mar/08/2024 12:05 (Moscow time) and Mar/09/2024 12:05 (Moscow time).

Special thanks to MikeMirzayanov for the codeforces and polygon systems, which were used in preparing the problems for this Olympiad.

Many thanks to the Olympiad testers: dshindov, FelixDzerzhinsky, Adikolon, isaf27, adepteXiao, talant, AgafonovArtem, Dart-Xeyter, inhabitant, Kapt, Siberian, alexashkins, alexxela12345, Sweezy, v0s7er, MOHOXPOM, Titoffifee.

Good luck!

UPD1: The solutions were tested on offline-groups. The scoreboard for the first day is also available.

UPD2: The solutions were tested on offline-groups. The scoreboard for the second day is also available.

UPD3: Combined scoreboard

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

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Will there be an editorial after the contest?

→ Reply
»
8 months ago, # |
  Vote: I like it +27 Vote: I do not like it

Will there be a live scoreboard?

→ Reply
»
8 months ago, # |
← Rev. 7   Vote: I like it -76 Vote: I do not like it

[Deleted]

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it -26 Vote: I do not like it

.

→ Reply
»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

omg IOI rules official round

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it

    It's not an official round, it's an unrated mirror of an onsite contest that has nothing to do with CodeForces.

    → Reply
»
8 months ago, # |
  Vote: I like it -14 Vote: I do not like it

We can't see the standings during the contest?

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

GL & HF for you all guys!

→ Reply
»
8 months ago, # |
  Vote: I like it -53 Vote: I do not like it

please upvote this comment, thanks.

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

Goodluck everybody. Hope you're doing well.

After the contest, solutions and statements will be available in this site: https://inf-open.ru/?lang=en

And you can also see the Qualification stage of Open Olympiad 2023-2024 in that site.

If you want to upsolve problem for Qualification round go here: https://codeforces.me/gym/104922

And for editorial visit this link: https://inf-open.ru/2023-24/zaoch-materials/

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

    I think solutions are missing in the first link you provided.

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

      Hello sir. The site will be updated and the solutions will be available.

      → Reply
»
8 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Although i could only solve one problem,i had a wonderful time.

→ Reply
»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

It was a good contest, so could you open standings?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? I have a naive O(N^2*W) solution , which will fail eventually.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    Noticed that for each state that the current player choosing switches, the number of minutes he is falling behind always satisfies $$$t\le a_{r+1}$$$. So you can optimize the number of states to $$$O(n\cdot \sum w)$$$.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Will you please elaborate? How is number of states optimized to O(n⋅∑w) ?

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I had the same observation but my code was failing miserably so I set the upper bound to be $$$t \leq 2*a_r$$$ which was enough to pass only up to subtask 5 :((((

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      So inspiring!

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

      I now get this. Earlier I don't know why I was feeling even with this restriction it shall be O(N^2*W). if we define dp[i][j][w] , then for fixed j , there will be j values of i. so it will take sum(j*w[j+1]) , which is less than O(N * W)

      → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +69 Vote: I do not like it

A is an enjoyable problem :)

btw when will the standings be public

→ Reply
»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Can anyone explain why this solution for D gives WA on group 2 test 12?

Code
→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody explain the solution of problem D? I thought if they play optimally then the minimum difference of their sum will be the answer. So following this I used dynamic programming on O(n*W) but it is showing wrong answer from group 3 to 5

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your greedy is incorrect, you just need to do smth like dfs on states. It is $$$O(n^2W)$$$ but can be optimized to $$$O(nW)$$$

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

      how can I optimize from $$$O(n^2W)$$$ to $$$O(nW)$$$? currently my states are $$$[l,r,t,num]$$$ means that the remain subarray is $$$[l,r]$$$, $$$t=0/1$$$ shows the current player and $$$num$$$ is the remaining sum from player $$$t$$$.

      → Reply
»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

HOW TO SOLVE THAT TREE PROBLEM B? ANY HINTS PLEASE....

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest a case for this? link

Second test group fails, but the worst case i could make runs locally in 0.6 seconds.

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

    Link not opening..

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

      mostly it's because you have no access to other's solutions. Maybe you need to be manager of contest, or possibly wait some time. Some old contests allow you to look into other's solutions. However, this contest is unique, because it's not Codeforces round.

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

    For C Time Limit is very tight. I did some simple optimizations like int instead of long long(wherever you can use) and unordered_map instead of map and by avoiding modulo operations it got accepted

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share their full AC code for D? Is your complexity better than $$$ O(n*W) $$$.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve day2 C?

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

    you can use sqrt descompose, this can pass in 3s

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    For each element, let's find the last value it can reach in 1 move; let's call this $$$nxt_i$$$.

    A correct greedy solution for answering the queries would be, at each step, to find the greatest value on the interval $$$[u, nxt_u]$$$ that isn't bigger than $$$a_v$$$ and jump to it.

    To do this efficiently, we will use square root decomposition. At each step, we will solve all queries with $$$a_v$$$ in the range $$$[k \cdot \sqrt{n}, (k+1) \cdot \sqrt{n}]$$$ for some $$$k$$$. For each element, let's compute the fastest way we can reach any value in this range and store where we will land 1 move before.

    Now, for each query, at each step, we will jump 1 step before a value in a range and decide whether we want to move to it or jump further. We will repeat this process $$$O(\sqrt{n})$$$ times for each query.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      Also, your solution is easy to remake to D&C. And get $$$O(n \cdot log^2 n)$$$

      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      Wth that's so based

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

      Wouldn't calculating fastest way to reach any value in range itself be $$$O(nlog(n))$$$

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        When you move to the next bucket, the values can change to only $$$\sqrt{n}$$$ different values. So, you can calculate RMQ in $$$O(\sqrt{n}^2)$$$ and then just look based on the first to the right from $$$i$$$ and the first to the left from $$$nxt_i$$$.

        Although I actually had to squeeze a monotonic queue and binary search for it to pass.

        → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D is too short code this is my code : https://ideone.com/HwO0wc

→ Reply
»
8 months ago, # |
  Vote: I like it -21 Vote: I do not like it

May someone help me with C question Day 1. With my solution I was able to get only 14 points by passing group1 testcases and on rest testcases some are passing some are giving WR and time limit exceed. Also I can't think of an idea to make it fast. Here is my Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>
int main(){
    // int p;
    // scanf("%d", &p);

    // while(p--) {

        int n, k, t;
        scanf("%d %d %d", &n, &k, &t);

        int temps[n];
        for(int i = 0; i < n; i++) scanf("%d", &temps[i]);

        int arr[n * k];
        int count = 0;
        for(int i = 0; i < k; i++) {
            for(int i = 0; i < n; i++) arr[count++] = temps[i];
        }

        int i = 0;

        int ans = 0, prev = -1;
        int temp[k];
        memset(temp, 0, sizeof(temp));
        int cnt = 0;
        int len = n * k;
        int numGift = t;

        while(i < len) {
            while(i < len && numGift > 0) {
                // printf("i : %d\n", arr[i]);
                bool flag = true;
                for(int j = 0; j < cnt; j++) {
                    if(arr[i] == temp[j]) {
                        flag = false;
                        break;
                    }
                }

                if(flag) {
                    temp[cnt++] = arr[i];
                    --numGift;
                }

                prev = arr[i];

                while(prev == arr[i]) ++i;
            
                if(numGift == 0) {
                    ++ans;
                    memset(temp, 0, sizeof(temp));
                    numGift = t;
                    cnt = 0;
                }
            }

        }

        if(numGift != 0 && numGift < t) ++ans;

        printf("%d", ans);

        printf("\n");
    // }

}
→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try using array of size n instead of k*n.. and fetch the value using index%n

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B is Dp ?

→ Reply
»
8 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Will we have a merged scoreboard?

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

the scoreboard of day2 is not fully rejudged, please fix this sir Ormlis

edit: fixed

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

How to solve B day2 ?

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

Will there be official scoreboard and editorials in the near future?

→ Reply
»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

is there any editorial? Ormlis

→ Reply