Блог пользователя aropan

Автор aropan, 5 лет назад, По-русски

Результаты и дорешивание полуфинала доступны по ссылке. Огромнейшая благодарность всем ребятам, которые сделали для вас этот контест: 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.

Немножко прошлогодней атмосферы:

  • Проголосовать: нравится
  • +248
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Оплачивается ли дорога на финал организаторами?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +49 Проголосовать: не нравится

    Если бы это было так мы бы об этом обязательно написали. )

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

А аспиранты могут участвовать?

»
5 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -18 Проголосовать: не нравится

    so they have time to rig it

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А какая музыка в первом видео? Если не сложно)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А известно в какое время будет проходить второй полуфинал (20 марта)?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А как решать H с первого отборочного тура?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Нам уже отправили логины/пароли на сегодня?

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Когда закончится разморозка?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Разморозка закончилась на четвертом часу контеста. )

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Кажется уже можно наслаждаться результатами.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Will the problems be avaliable for upsolving?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve L?

  • »
    »
    5 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

    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.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +28 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

        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$$$

»
5 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

How to solve D and I?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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.com/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]$$$.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Что за игра на 4:35