XIX Open Olympiad in Informatics (Unrated, Online Mirror, IOI rules)

#	User	Rating
1	Benq	3792
2	VivaciousAubergine	3647
3	Kevin114514	3603
4	jiangly	3583
5	strapple	3515
6	tourist	3470
7	dXqwq	3436
8	Radewoosh	3415
9	Otomachi_Una	3413
10	Um_nik	3376

#	User	Contrib.
1	Qingyu	157
2	adamant	152
3	Proof_by_QED	146
3	Um_nik	146
5	Dominater069	144
6	errorgorn	141
7	cry	139
8	YuukiS	135
9	TheScrasse	134
10	chromate00	133

Hello everyone!

Soon, the Open Olympiad in Informatics will take place, which you may know from the online mirror of last year or from the rounds 345, 469, 545, 626, 707, 775. This olympiad is prepared by Moscow Olympiad Scientific Committee. Archives from previous years, problems from qualifying stages, and other information can be found on the olympiad website inf-open.ru.

The Open Olympiad consists of 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 mirror on Codeforces will take place in Mar/07/2025 11:05 (Moscow time) and Mar/10/2025 11:05 (Moscow time).

The competition problems were created and prepared by Kapt, allvik66, stepanov.aa, Mangooste, AgafonovArtem, dyrbulshchyl, RP-1, valerikk, yunetive29, Kniaz, Alexdat2000 guided by Mangooste, grphil and Helen Andreeva. Special thanks to Tikhon228 for his contribution to the preparation of the problems.

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: Ormlis, isaf27, allvik66, AgafonovArtem, RP-1, Qwerty1232, kostylevGO, katyaporay, FairyWinx, a.stepanov281005, EgorUlin, pakhomovee, ArtAlex, Sweezy, Be_dos, valerikk, alexsushin, Dart-Xeyter, yunetive29, AndreyPavlov, Mikhango, v0s7er.

Good luck!

UPD1: The results of the first day are available.

UPD2: The materials and editorial are published at inf-open.ru.

Comments (32)

Write comment?

wasif2397

14 months ago, hide # |

+10

what difficulty will be the easiest problem?

→ Reply

Mangooste

14 months ago, hide # ^ |

The difficulty of the problems is comparable to the level of Div. 1

I can't spoil any more, unfortunately, since the difficulty might vary. But you're welcome to check out last year's.

suboptimal

+82

Standings??

MisterGir

Copy the competition to mashup and set the IOI round rating in mashup. And see the results.

+32

If you don't know how, here is a link to the competition. link

NuclearMint

Is there a way to check other submissions as well ? they are not loading for me at least.

Yes, you can, just open the status in the competition. link

Oh thanks

Jelefy

good Not my problem for not solving A and B -o-

YipChip

What do you think the difficulty of the questions should be?

D 1600 AB >2400 maybe

THX. Allow me to ask one more question. Did FFT should be used in B or not?

idk I did not solve A and B...

OK, but still thanks you for your time:)

I don't think FFT would help though

sunsetinParis

-39

This contest will only take me 5 seconds to complete

tyristik

+23

You mean cUmplete? 5 seconds for you should be enough to do so, I believe in you!

litvinas

Is HLD the only solution for C?

N29

You can do sqrt decomposition on height, but it is worse than HLD.

asdasdqwer

Can anyone explain the intuition behind the solution of D? I've been trying to grasp it but without any success

KK_1729

← Rev. 2 →

Let's say that the $$$k$$$ indices that contribute to the value of their respective subsequence(They have the maximum $$$a_{j_{m}} + m$$$ value in their subsequence) are $$$i_{1} \lt i_{2} \lt ... \lt i_{k}$$$

The observation here is that the answer is always going to be $$$(\sum_{j=1}^{j=k} a_{i_{j}}) + i_{k}$$$ regardless of how we distribute the remaining $$$n-k$$$ elements into the k subsequences.

So the solution is to go from $$$i = k ... n$$$ and try to maximize the answer by choosing the current index and the $$$k-1$$$ indices with maximum value from $$$1 ... i-1$$$

Husanboy

How can we add tags on problems with pdf statements?

Mousa_Aboubaker

This solution for problem B should get 0 points, but it got 79 points

Code

void solve()
{
  int n, m, t;
  cin >> n >> m >> t;
  vec<int> a(n), b(m);
  for (auto &i : a)
    cin >> i;
  for (auto &i : b)
    cin >> i;
  vec<int> lg(n + 1);
  lg[1] = 0;
  for(int i = 2; i <= n; i++)
    lg[i] = lg[i >> 1] + 1;
  vec spt(n, vec<int>(21));
  for(int i = 0; i < n; i++)
    spt[i][0] = a[i];
  for(int j = 1; j < 21; j++)
    for(int i = 0; i + (1 << (j - 1)) < n; i++)
      spt[i][j] = min(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
  auto query = [&](int l, int r) -> int
  {
    int x = lg[r - l + 1];
    return min(spt[l][x], spt[r - (1 << x) + 1][x]);
  };
  map<int, vec<int>> mp;
  for(int i = 0; i < n; i++)
    mp[a[i]].push_back(i);
  vec<ll> pref(n + 1);
  for(int i = 0; i < n; i++)
    pref[i + 1] = pref[i] + a[i];
  int mx = 0;
  for(auto i: b)
  {
    if(a[i - 1] > t)
    {
      continue;
    }
    int l = 1, r = i, ans = i;
    while(l <= r)
    {
      int md = (l + r) / 2;
      if(pref[i] - pref[md - 1] <= t)
      {
        r = md - 1;
        ans = md;
      }
      else
      {
        l = md + 1;
      }
    }
    int j = query(ans - 1, i - 1);
    int lb = lower_bound(all(mp[j]), i) - mp[j].begin() - 1;
    lb = mp[j][lb];
    int res = (i - 1) - lb;
    res += (t - pref[i] + pref[lb + 1]) / j;
    chmax(mx, res);
    l = i, r = n, ans = i;
    while(l <= r)
    {
      int md = (l + r) / 2;
      if(pref[md] - pref[i - 1] <= t)
      {
        l = md + 1;
        ans = md;
      }
      else
      {
        r = md - 1;
      }
    }
    j = query(i - 1, ans - 1);
    lb = lower_bound(all(mp[j]), i - 1) - mp[j].begin();
    lb = mp[j][lb];
    res = lb - i + 1;
    res += (t - pref[lb] + pref[i - 1]) / j;
    chmax(mx, res);
  }
  cout << mx;
}

Counter-testcase

5 1 12
2 7 3 7 2
3

output: 4

my code output: 3

and I just made a little modification for it to get 100 points (the counter-testcase got AC after this modification, but I'm not sure if there isn't any other counter-testcases or no)

Code after modification

void solve()
{
  int n, m, t;
  cin >> n >> m >> t;
  vec<int> a(n), b(m);
  for (auto &i : a)
    cin >> i;
  for (auto &i : b)
    cin >> i;
  vec<int> lg(n + 1);
  lg[1] = 0;
  for (int i = 2; i <= n; i++)
    lg[i] = lg[i >> 1] + 1;
  vec spt(n, vec<int>(21));
  for (int i = 0; i < n; i++)
    spt[i][0] = a[i];
  for (int j = 1; j < 21; j++)
    for (int i = 0; i + (1 << (j - 1)) < n; i++)
      spt[i][j] = min(spt[i][j - 1], spt[i + (1 << (j - 1))][j - 1]);
  auto query = [&](int l, int r) -> int
  {
    int x = lg[r - l + 1];
    return min(spt[l][x], spt[r - (1 << x) + 1][x]);
  };
  map<int, vec<int>> mp;
  for (int i = 0; i < n; i++)
    mp[a[i]].push_back(i + 1);
  vec<ll> pref(n + 1);
  for (int i = 0; i < n; i++)
    pref[i + 1] = pref[i] + a[i];
  int mx = 0;
 
  for (auto i : b)
  {
    if (a[i - 1] > t)
    {
      continue;
    }
    int l = 1, r = i, ans = i;
    while (l <= r)
    {
      int md = (l + r) / 2;
      if (pref[i] - pref[md - 1] <= t)
      {
        r = md - 1;
        ans = md;
      }
      else
      {
        l = md + 1;
      }
    }
    int op = 3;
    while (op--)
    {
      int j = query(ans - 1, i - 1);
      int lb = upper_bound(all(mp[j]), i) - mp[j].begin() - 1;
      lb = mp[j][lb];
      int res = i - lb;
      res += (t - pref[i] + pref[lb]) / j;
      chmax(mx, res);
      ans = lb + 1;
      if (ans > i)
        break;
    }
    l = i, r = n, ans = i;
    while (l <= r)
    {
      int md = (l + r) / 2;
      if (pref[md] - pref[i - 1] <= t)
      {
        l = md + 1;
        ans = md;
      }
      else
      {
        r = md - 1;
      }
    }
    op = 3;
    while (op--)
    {
      int j = query(i - 1, ans - 1);
      int lb = lower_bound(all(mp[j]), i) - mp[j].begin();
      lb = mp[j][lb];
      int res = lb - i;
      res += (t - pref[lb - 1] + pref[i - 1]) / j;
      chmax(mx, res);
      ans = lb - 1;
      if(ans < i)
        break;
    }
  }
  cout << mx;
}

$$$Results$$$ $$$2$$$ $$$days$$$, follow this link!

AlRntn

is there anyway to share both days standings combined?

No, I can’t, because I’m not one of the authors of the contest.

qbf

+56

When will there be a solution to the problem?

ItsNotMeItsYou

Can anyone explain to me how to solve Day 2 Problem C: Card Flip?

og.kostya

← Rev. 3 →

For sorted pair {$$$a_i$$$, $$$b_i$$$}, the first $$$b_i$$$<$$$a_{i+1}$$$ (or the last, if no such pair is found) is the winning card, because that card determines who takes next winning card (or the last card). For such $$$a_i$$$, search backward for the largest $$$a_j$$$ where $$$b_j$$$ < $$$a_i$$$ (the card that has the lattest influence on the taker of $$$a_i$$$) and so on. If no such $$$a_j$$$ is found, then the parity $$$_i$$$ in combined sorted array $$$a$$$ with $$$c$$$ is the answer.

strapple

13 months ago, hide # |

+36

How soon will the editorial come out?

Still no editorial? Hello?

Asim020202

6 months ago, hide # |

-18

Mangooste's blog