aropan's blog

9th BSUIR Open Programming Championship
By aropan, 6 years ago, translation, In English

The results and upsolving of the semifinal are available at link. Many thanks to all guys who made this contest for you: hloya_ygrt, teleport, wilcot, Qwertenx, rui-de, Vladik, vilcheuski, netman, Tkach1024 and jklementseva.

The 9th BSUIR Open Programming Championship will be held from March 13 till April 25, 2019 (Minsk, Belarus). Undergraduates and postgraduates of BSUIR, students of other educational institutions, students from other universities and countries are invited to participate in the Championship.

The competition will take place in several rounds:

  • first qualifying round (distance, problems in Russian) — March 13-16;
  • second qualifying round (distance/onsite semi-final, russian and english problems) — March 20 (17:00 — 22:00 UTC+03);
  • Championship final for school teams (onsite) — April 19-20 (April 20, 10:00 — 15:00 UTC+03);
  • Championship final for students teams (onsite, only english problems) — April 23-25 (April 24, 10:00 — 15:00 UTC+03).

First qualifying round is required only for BSUIR and high school teams but other registered teams can also take part in it. Second qualifying round is required for all teams. BSUIR and high school teams from Minsk take part onsite, other teams — online.

To participate in the Championship teams need to be registered prior to March 15, 2019 incl. Participation is free of charge — have fun.

The finalists are 42 teams, showed the best results in the qualifying rounds, but no more than:

  • 7 teams of undergraduates and postgraduates of BSUIR;
  • 2 teams from each of the university of Belarus and abroad.

University teams, which include at least two ICPC finalists 2018-2019, as well as high school teams, which include at least two winners of the final stage of the National Belarusian Olympiad in Informatics 2019, are allowed to participate in the finals of the Championship without passing the qualifying rounds.

Open BSUIR Programming Championship is held by the ACM rules. During the Championship, the teams will be given 5 hours to solve 8 to 12 programming problems.

More information about the championship, as well as the problems and results of previous years, you may find at acm.bsuir.by.

A little bit of last year video:

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

Comments Comments (30)
| Write comment?
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Why is each round (qualifying/final) hosted in multiple days? Does each consist of a 5-hour contest like ICPC? Could you give me the exact start time of each round?

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

    In qualifying round you need to solve not less than the half of all the tasks during these days. Final round is a 5-hour ICPC-format contest (other days are for environment testing and non-contest activities).

    aropan correct me if I'm wrong

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

      Is it for high school students from around the world or not because i haven't seen other teams in results but russian teams or something like that

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

        High school teams from any country can take part in the Championship.

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

    so they have time to rig it

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

    First qualifying round — March 13-16. The team need to solve half or more problems within 96 hours, anytime, without penalty. This round isn't required for university teams except BSUIR. But you can use it for training.

    Second qualifying round — March 20 (17:00 — 22:00 UTC+03). 5-hours ICPC-contest.

    Championship final for school teams (onsite) — April 20 (10:00 — 15:00 UTC+03); Championship final for students teams (onsite, only english problems) — April 24 (10:00 — 15:00 UTC+03).

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can we find the previous year problem statement? It asks for a Yandex login provided to only participants.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So we have to go through first qualifying round to go the second but it only contains Russian problem statements ?

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

    We're adding English statements for first qualifying round this year.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I see if my team is registred for the contest tomorrow?

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

Will the problems be avaliable for upsolving?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve L?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it

    Let`s suppose we match $$$1$$$ with some another guy $$$i$$$. So guys $$$2, \ldots, i-1, i+1, ... 2n$$$ remain. Now we can notice that the remain part will be equivalent to matching guys for the array $$$1, \ldots, 2 \cdot n - 2$$$ and then increasing sum in all the pairs by $$$2$$$. Continuing this reasoning, we can conclude that all task equals to choosing exactly one element from each of intervals

    $$$[3; 2 \cdot n + 1], [5; 2 \cdot n + 1], \ldots, [2 \cdot n + 1; 2 \cdot n + 1]$$$

    with condition that minimum is unique. It can easily be solved if we fix minimum.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      As for me, it seems that it is equivalent to match guys for the array $$$1,…,i - 2 , i,…,2n - 1$$$, but not $$$1,…,2⋅n−2$$$. I can't get it.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 4   Vote: I like it +10 Vote: I do not like it

        I should mention that I solve the problem for minimum instead of maximum, if somebody doesn't understand

        So it is equivalent to $$$1, \ldots, 2 \cdot n - 2$$$ because we aren't really interested by any pairs containing numbers more or equal than $$$i+1$$$ as minimum is already at most $$$i+1$$$, so even when $$$i+1, \ldots, 2 \cdot n$$$ is transformed to $$$i-1, \ldots, 2 \cdot n - 2$$$, it doesn't spoil anything because even in worst case $$$1 + (i-1) + 2 > i+1$$$

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

How to solve D and I?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Task I can be solved as follows. If number $$$A$$$ changes after taking $$$A\ mod\ B$$$, than it decreases at least two times, this can be easily proven. Thus, for each $$$a[l]$$$ we can get next integer in the array after it, which is less than or equal to $$$a[l]$$$ (this can be done with segment tree or binary search + sparse table), let it be integer $$$x$$$. Then we can apply mod operation, $$$a[l]\ mod\ x$$$. For this new value, we can get next integer, which less than or equal to $$$a[l]\ mod\ x$$$ and apply mod operation again and so on. So, if number decreases at least two times, we will get $$$log\ n$$$ "groups" with equal mods for each $$$a[l]$$$. Then let's iterate array from right to the left and do event processing. We will have events: our current R-bound changed it "group" for some $$$L$$$ from "group" with $$$MOD1$$$ to $$$MOD2$$$. And let's have $$$3\cdot10^5$$$ ordered sets (see https://codeforces.me/blog/entry/11080 for reference), each one for separate $$$MOD$$$. So for each event we will delete $$$L$$$ from $$$orderedSet[MOD1]$$$ and insert it into $$$orderedSet[MOD2]$$$. And then let's iterate through "groups" with equal $$$MODS$$$ for our R-bound(from right to the left, we will get $$$log\ n$$$ "groups" again). Assume that for some group we have $$$groupL$$$, $$$groupR$$$, $$$groupMOD$$$. Then lets just add to the total answer number of elements in $$$orderedSet[groupMOD]$$$ in range $$$[groupL, groupR]$$$.

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

      Lol, I came up with the same solution, but I didn't hope that it can pass, because it's $$$O(N*log^2(N))$$$ and I thought that it can be too slow because of ordered sets. And almost always, when I come up with such kind of solution, I'm trying to get rid of ordered sets.

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

        In this task, it is almost impossible to generate test cases, such that there will be a lot of groups and there will be a lot of requests to big sets. In average, sets are small. Although, you can solve the task without ordered set. You can solve separately for each $$$MOD$$$ and to do this, you can find number of intersecting vertical(for groups belonging to left borders) and horizontal(for groups belonging to right borders) segments on a grid. This can be done with event processing and BIT.

        → Reply