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

Автор hloya_ygrt, 4 года назад, По-русски

С 21 марта по 7 мая 2020 года пройдет X Международный открытый чемпионат БГУИР по спортивному программированию "BSUIR Open 2020" (г. Минск, Беларусь).

Полуфинал закончен, открыто дорешивание и разморожены таблички. Огромнейшая благодарность всем ребятам, которые сделали для вас этот контест: aropan, teleport, wilcot, Qwertenx, rui-de, Vladik, netman.

Для просмотра результатов: студенческий и школьный.

UPD3: Совсем чуть-чуть остается до окончания регистрации!

UPD: Канал в телеграмме. По кнопочке "обсудить" вы попадете в чат, где можно пообщаться с другими участниками чемпионата и найти себе команду.

UPD2: В связи с ситуацией в стране и мире, оргкомитет принял решение провести полуфинал заочно для всех команд. Регистрация для всех команд продлена до 6-го апреля (включительно). Четвертьфинал, обязательный только для команд БГУИР и школьников, также будет проходить до 6-го апреля.



К участию в Чемпионате приглашаются студенты, магистранты и аспиранты, а также учащиеся общеобразовательных учреждений.

Соревнование пройдет в несколько этапов:

  • первый отборочный тур (заочный четвертьфинал) — 21 марта — 6 апреля (включительно);
  • второй отборочный тур (заочный полуфинал) — 7 апреля (17:00 — 22:00 по минскому времени);
  • даты финалов чемпионата уточняются.

Первый отборочный тур обязательный только для команд БГУИР и школьников, но другие команды также могут принять участие. Второй отборочный тур обязателен для всех команд. Команды БГУИР и школьников г. Минска, прошедшие первый отборочный тур, участвуют в нем очно, остальные заочно. Полуфинал и финал будут проходить в формате ICPC (5 часовой контест).

Для участия в Чемпионате необходимо зарегистрировать команду из 3 участников до 6-го апреля (включительно)). Оргвзнос составляет всего ничего — ничего, участвуйте в свое удовольствие.

В студенческий финал проходят 42 команды, показавшие лучшие результаты во втором отборочном этапе, но не более:

  • 7 команд студентов и магистрантов БГУИР;
  • 2 команд от каждого вуза Республики Беларусь и стран зарубежья.

В школьный финал проходят не менее 15 команд, показавших лучшие результаты во втором отборочном этапе.

И еще немножко плюшек — команды высших учебных заведений, в состав которых входит не менее двух финалистов студенческого командного чемпионата мира по программированию ICPC сезона 2019-2020, а также команды средних общеобразовательных учреждений (школ, гимназий, лицеев), в состав которых входит не менее двух призеров заключительного этапа республиканской олимпиады по информатике 2020 года, допускаются к участию в финале соревнований без прохождения отборочных этапов и сверх установленной квоты.

Открытый чемпионат БГУИР по программированию проводится по правилам ICPC-олимпиад. В финале соревнования участникам предлагается от 8 до 12 заданий, которые следует решить за 5 часов. Задачи сформулированы на английском языке.

Более подробную информацию о Чемпионате, а также условия задач и результаты прошлых лет можно найти на портале acm.bsuir.by.

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

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

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

КУ

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

Дед будет?

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

А может ли команда состоять из студентов и школьников?

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

КУ

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

Допускаются к участию в финале соревнований без прохождения отборочных этапов призёры республиканской олимпиады любой страны?

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

    А также что делать, если финал респы 29 марта (после регистрации)

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

      Да, все правильно, так и надо — главное же, что финал чемпионата после республики.

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

    Нет, речь о белорусской республиканской олимпиаде. Всех остальных приглашаем участвовать в отборах.

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

Что за песни использованы в роликах?

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

    Kodaline — Follow Your Fire и Feel the Fire — Pluko&Pronouncedyea

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

....

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

Полуфинал начнется уже через ~30 минут.

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

Showing — " You cannot participate in the contest because the registration is closed " even though name of our team is shown in the paricipation list with the tag of 'semifinals' can anyone help with this!!! thank you in advance.

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

как решать А?

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

    Let's look at the cycles of the permutation. We can do swaps (first operation) in each cycle independently. For a cycle of length L we need L — 1 swaps. So for the permutation of length N with K cycles we need N — K swaps, and the cost will be A * (N — K). So only number of cycles matters.

    Number of permutations of length N with K cycles is Stirling numbers of the first kind, you can precalc this with DP.

    Now about our operations. Hypothesis is that you never do swaps (first operations) and then shuffle (second operation), because swaps would be useless then. So you either do only swaps, or do shuffle first.

    We can assume that for permutations with many cycles we do only swaps. Let's say that for permutations with at least X (for some X) cycles we do only swaps – it's easy to find cost for them. For permutations with < X cycles we do shuffle until we get permutation with >= X cycles, and you can find excepted cost here with simple equation.

    Let's find how many cycles input permutation has, then let's try all possible X values and take the minimum answer.

    Code.

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

How to solve F without fft?

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

    We are asked to calculate the probabilities of choosing a sequence $$$q$$$ so that its $$$d$$$-th order statistic is $$$>$$$ than $$$k$$$. Let's calculate the probabilities of choosing a sequence $$$q$$$ so that its $$$d$$$-th order statistic is $$$\leq$$$ than $$$k$$$ instead, that means that there are at least $$$d$$$ integers which are $$$\leq k$$$ in $$$q$$$. We fix a position $$$i$$$ ($$$0$$$-indexation) of exactly $$$d$$$-th one from the left, then the probability is $$$\binom{i}{d - 1} \cdot (\frac{k}{n})^{d} \cdot (\frac{n - k}{n})^{i - d + 1}$$$ and it affects answers in the segment $$$[i; n]$$$ of lengths of $$$q$$$.

»
4 года назад, # |
  Проголосовать: нравится +87 Проголосовать: не нравится
A
B
C
D
F
G
H
I
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Hello! Maybe anybody could share their solutions for K and J? Also, H and A would be nice, but not necessary. Thank you!

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

    J — lets calc two functions: f(x), s(x) — f(x) is a number of different towers with x blocks, and s(x) is a number of symmetric towers with x blocks, that all floors are correct. There are easy reccurent formula: f(x) = f(x-1) + 3*f(x-2) + f(x-3), because we see to 1st floor, there is 5 options — 010, 110, 011, 101, 111.

    And for s(x) we can use only 010, 101, 111. so s(x) = s(x-1)+s(x-2)+s(x-3)

    OK, so answer for task will be ((f(n)+s(n))//2)+f(n-1). If the last floor is correct, it means that we have ((f(n)+s(n))//2, because non-simmetric towers was calculated in f two times. And if the last floor is incorecct, there is only 2 options — 100, 001. It means, that tower is non-simmetric, and variables for other floors is f(x-1). SO answer is ((f(n)+s(n))//2+f(n-1)

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

      So i forgot to tell, that you need to calc f(n), s(n) using matrix exponentation, because n is very large.

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

    A: If we are using only the swap move, the answer only depends on the number of cycles in the permutation — if there are $$$c$$$ cycles, the answer is $$$a * (n - c)$$$. However, there is also a possibility that we do the random_shuffle move, where we get to a permutation with $$$c'$$$ cycles with $$$p(c')$$$ probability, where $$$p(c')$$$ can be easily calculated (look up Sterling numbers of the first kind). So, if $$$e(c)$$$ is a solution for the permutation of $$$c$$$ cycles, following equality must hold for each $$$c$$$: $$$e(c) = \min(a * (n - c), b + \sum_{i = 1}^{n} p(i) * e(i)) $$$. We can start with any random solution and iterate this until it converges (it will converge fast, trust me).

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

Would be nice to hear how to solve these problems from Semifinal: D. Dull game, E. Elegance in moves and G. Geometric shapes. Thanks in advance!

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

    $$$G$$$. When $$$nm$$$ — 1 is not divisible by 4, answer is obviously no. Otherwise, both $$$n$$$ and $$$m$$$ are odd and equal modulo 4. Cases where $$$n$$$ = 1 or $$$m$$$ = 1 are trivial. For $$$n$$$ = $$$m$$$ = 3 it is easy to construct answer on paper, and because of this one can prove that answer always exists in this case. So let's do the following process: while we can cut top 4 rows (but not getting 1xM strip), cut them. Do same for bottom, left and right. So, now we have small field (up to 7x7). To solve this you can write recursion, that will consider all possible cases. To do this, our team hardcoded ~20 figures and their rotations, but maybe there is easier approach to do this.

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

      It's possible to hardcode only $$$3$$$ cases where $$$n = 3, m = 7$$$ and the cell is in the middle by $$$y$$$. Else we can either subtract $$$2$$$ from $$$n, m$$$ just paving the border and, probably, considering another cell as a new forbidden one in the reduced task (if the old cell was on the border), or just take $$$4$$$ columns if $$$n = 3, m > 7$$$. Considering $$$n < m$$$ initially we are going to avoid any rotations.

      It's not pleasant for writing though, but I considered it's better than hardcoding all those cases.

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

    D: The problem is basically about solving the system of linear equations $$$x^TA = (a_0)^T$$$ in $$$F_2$$$, where $$$A$$$ is constructed by stacking the binary representations of $$$a_1, a_2, \ldots, a_n$$$ vertically. $$$x$$$ can be found by computing $$$A^{-1}$$$ in $$$O(\frac{n^3}{64})$$$ with std::bitset. The modification of $$$a_p$$$ can be modeled as adding some $$$u$$$ to the $$$p$$$-th row of $$$A$$$, and the inverse of the modified matrix can be found, according to Sherman–Morrison formula, with some multiplications between matrices and vectors in $$$O(\frac{n^2}{64})$$$ time. The overall time complexity is $$$O(\frac{n^3+n^2m}{64})$$$.

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

    G. Geometric shapes

    During the contest I got accepted using the same awful(because of implementation) ideas, that were written higher, but found a nice way to solve it after.

    Firstly we should fill first $$$n-1$$$ rows and $$$m-1$$$ columns with squares and everything else(except for cell $$${0, m - 1}$$$) with sticks and corners.

    Let's think that $$$r \leq \frac{n}{2}$$$ and $$$c \leq \frac{m}{2}$$$ because other cases are simmetrical.

    The last step is just consistently swap cells using one of two ways(choice depends on $$$c$$$ $$$mod$$$ $$$2$$$)

    It's easy to check that all figures stay being tetraminos after all moves.

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

    I believe that E can be solved with four scanlines (vertical, horizontal, two diagonal ones) and simple combinatorics, but during contest we thought that this is next to impossible to implement.

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

Any idea on how to solve K?

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

    K: Let's fix the highest non-zero bit of $$$x$$$ at position $$$p$$$, then we can see that whether $$$a_i \oplus x$$$ is greater than $$$a_i$$$ is uniquely determined by the $$$p$$$-th bit of $$$a_i$$$. Therefore, we can calculate the contributions of each bit $$$j < p$$$ and mark the $$$k - 1$$$ largest bits (according to their contributions) in $$$x$$$ to be 1. With the enumeration of $$$p$$$, the time complexity is $$$O(m^2n)$$$.

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

As we haven't got any update about the contest after qualification round, what is the final status of competition ? Are you planning to organize it later after the end of "corona crisis"?