hloya_ygrt's blog

By hloya_ygrt, 4 years ago, translation, In English

The X BSUIR Open Programming Championship will be held from March 21 till May 7, 2020 (Minsk, Belarus).

Semifinal is over, upsolving is open and standings are unfreezed. Thanks to the problemsetters: aropan, teleport, wilcot, Qwertenx, rui-de, Vladik, netman.

Results here: students и school.

UPD3: Registration deadline comes in 30 hours.

UPD: Telegram channel. There's a link there to a chat, where you can talk to other participants and team up.

UPD2: With respect to the situation in the world, organizing committee decided to make online second qualifying for all teams. Registration deadline is extended to April 6 (included). First qualifying round, which is required only for the teams from BSUIR and schools, is also extended to April 6.



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 21 — April 6 (both included);
  • second qualifying round (distance/onsite semi-final, russian and english problems) — April 7 (17:00 — 22:00 UTC+03);
  • the dates of championship finals will be announced later.

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. Second qualifying round and finals will be in ICPC format (5h contest).

To participate in the Championship teams need to be registered prior to April 6, 2020 incl. Participation is free of charge — have fun.

The finalists are 42 students 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.

And 15 school teams, showed the best results in the qualifying rounds.

University teams, which include at least two ICPC finalists 2019-2020, as well as high school teams, which include at least two winners of the final stage of the National Belarusian Olympiad in Informatics 2020, 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
  • +208
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F without fft?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +32 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    $$$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 years ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 3   Vote: I like it +23 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Any idea on how to solve K?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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"?