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:
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?
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
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
High school teams from any country can take part in the Championship.
so they have time to rig 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).
А когда будет известен список команд (вузы), приглашенных на финал ?
Сегодня сформируем список команд, приглашенных на студенческий финал, через неделю — список школьных команд.
http://acm.bsuir.by/wps/wcm/connect/olymp/site/content/bsuir-open-2019/final/participant_teams
Where can we find the previous year problem statement? It asks for a Yandex login provided to only participants.
It is fail. We fix it today.
You can look here. Gym of 8th BSUIR Open is coming soon.
So we have to go through first qualifying round to go the second but it only contains Russian problem statements ?
We're adding English statements for first qualifying round this year.
Okay thanks very much
How can I see if my team is registred for the contest tomorrow?
Are you in list?
No, my team is not in list. We registered yesterday and it was written Pending.
Fixed. Your team will appear soon.
Thank you very much!
Will the problems be avaliable for upsolving?
Yeap. Now.
How to solve L?
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.
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.
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$$$
How to solve D and I?
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.net/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]$$$.
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.
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.