Результаты и дорешивание полуфинала доступны по ссылке. Огромнейшая благодарность всем ребятам, которые сделали для вас этот контест: hloya_ygrt, teleport, wilcot, Qwertenx, rui-de, Vladik, vilcheuski, netman, Tkach1024 и jklementseva.
С 13 марта по 25 апреля 2019 года пройдет IX Международный открытый чемпионат БГУИР по спортивному программированию "BSUIR Open 2019" (г. Минск, Беларусь). К участию в Чемпионате приглашаются студенты и магистранты, а также учащиеся общеобразовательных учреждений.
Соревнование пройдет в несколько этапов:
- первый отборочный тур (заочный четвертьфинал) — 13-16 марта;
- второй отборочный тур (очно-заочный полуфинал) — 20 марта (17:00 — 22:00 по минскому времени);
- финал Чемпионата для школьных команд (очный) — 19-20 апреля (контест 20 апреля 10:00 — 15:00);
- финал Чемпионата для студенческих команд (очный) — 23-25 апреля (контест 24 апреля 10:00 — 15:00).
Первый отборочный тур обязательный только для команд БГУИР и школьников, но другие команды также могут принять участие. Второй отборочный тур обязателен для всех команд. Команды БГУИР и школьников г. Минска, прошедшие первый отборочный тур, участвуют в нем очно, остальные заочно.
Для участия в Чемпионате необходимо зарегистрировать команду из 3 участников до 15 марта 2019 (включительно). Оргвзнос составляет всего ничего — ничего, участвуйте в свое удовольствие.
В финал проходят 42 команды, показавшие лучшие результаты во втором отборочном этапе, но не более:
- 7 команд студентов и магистрантов БГУИР;
- 2 команд от каждого вуза Республики Беларусь и стран зарубежья.
И еще немножко плюшек — команды высших учебных заведений, в состав которых входит не менее двух финалистов студенческого командного чемпионата мира по программированию ICPC сезона 2018-2019, а также команды средних общеобразовательных учреждений (школ, гимназий, лицеев), в состав которых входит не менее двух призеров заключительного этапа республиканской олимпиады по информатике 2019 года, допускаются к участию в финале соревнований без прохождения отборочных этапов и сверх установленной квоты.
Для школьников будет проведен отдельный финал, где команды смогут на равных посоревноваться друг с другом.
Открытый чемпионат БГУИР по программированию проводится по правилам ACM-олимпиад. В финале соревнования участникам предлагается от 8 до 12 заданий, которые следует решить за 5 часов. Задачи сформулированы на английском языке.
Более подробную информацию о Чемпионате, а также условия задач и результаты прошлых лет можно найти на портале acm.bsuir.by.
Немножко прошлогодней атмосферы:
Оплачивается ли дорога на финал организаторами?
Если бы это было так мы бы об этом обязательно написали. )
А аспиранты могут участвовать?
Да, могут.
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
А какая музыка в первом видео? Если не сложно)
James Vincent McMorrow — West Coast :)
Спасибо, с праздником вас ))
А известно в какое время будет проходить второй полуфинал (20 марта)?
С 17:00 до 22:00 по минскому времени.
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!
А как решать H с первого отборочного тура?
Нам уже отправили логины/пароли на сегодня?
Пока нет.
Когда закончится разморозка?
Разморозка закончилась на четвертом часу контеста. )
Кажется уже можно наслаждаться результатами.
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 \gt 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.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]$$$.
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.
Что за игра на 4:35
Это условие задачи C.