aropan's blog

8th BSUIR Open Programming Championship
By aropan, 7 years ago, translation, In English

The 8th BSUIR Open Programming Championship will be held from February 16 till April 13, 2018 (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) — February 16-19;
  • second qualifying round (distance/onsite semi-final, russian and english problems) — February 21;
  • Championship final for students teams (onsite, only english problems) — March 14-16;
  • Championship final for school teams (onsite) — April 11-13.

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 20.02.2018 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 near and far abroad.

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.

There is good news for foreign teams who are participating in the final. Belarus introduced a visa-free entry procedure for up to 5 days at the entrance to the National Airport Minsk for citizens of 80 countres.

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 BSUIR Open into training: http://mirror.codeforces.com/blog/entry/49057

A little bit of last year video:

  • Vote: I like it
  • +143
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

The 8th BSUIR Open semi-final is already today and will start very soon.
The contest takes place at 17.00 at MSK. You will be given 5 hours to solve problems.
Join the contest here: https://official.contest.yandex.ru/bsuir2018/contest/7517/enter/.
Logins and passwords will be sent out soon.
Make sure that your team is on the list of semi-finalists: http://acm.bsuir.by/wps/wcm/connect/olymp/site/content/champ2018/semifinal/participant_teams.
If you have any questions, please contact support: acm.bsuir.by@gmail.com

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    What about final participants. We are waiting!

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem K?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    For every edge in the path, calculate the expected number of moves until you use that edge in that direction. The answer is the sum of these numbers. To calculate these numbers, it's just the expected number of times you pass through the vertex * expected number of moves until getting back to it + 1 or something like this. http://mirror.codeforces.com/problemset/problem/712/E it's similar to this problem. You can calculate the expected number to the up edges using one dfs and then the rest in another, then just use binary lifting to calculate the path. We just passed it like this but during the contest we had no time to code binary lifting :(

    → Reply
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve G and D?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D: 22(n - 1)(n + 1) due to some combinatorical reasons.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you explain the reasons or at least a idea about this formula ?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The number of edges is equal n*n-1 The number of subgraphs is equal K = 2^(n*n-1) The answer is K / 2 But we can’t approve that

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Actually, the number of edges is equal to 2*n*n-1.

          → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Proof for the problem D is very elegant and easy. Try to rotate the grid by 90 degrees. And you can see that there exists a bijection between the grids with and without the path.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    My solution used precalc for all possible n with O(n^4) complexity.

    How to solve it for fixed n:

    Let's notice that we have got 209 single days and 52 groups with 3 days which all turn to Monday (Sat, Sun, Mon).

    Let's calculate dp[i] — probability that exactly i persons were born on this 209 single days (we can do it easily with O(n^2)).

    So, we have gotten this probabilities. Then we need to calculate the expected value for every i and we will have solved the problem.

    Let's fix i. Let's solve(a, b) — expected value for a days and b persons which were born all on those a days. So for every i we need to calculate solve(209, i) + solve(52, n-i) and multiply this with dp[i].

    We can calculate solve(a, b) with dp[i][j] — probability of the event where we have taken men so that on exactly i days several men were born, on exactly j days only 1 man was born. So we will recalculate this step by step, adding men. Answer eventually will be (sum i*dp[i][j]) for all (i, j). Total complexity of this dp is O(n^3), of solution O(n^4).

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +33 Vote: I do not like it

    There is simply solution from participants. ANS = 52 * p1 + 209 * p2

    p1, p2 — probability that there will be at least 2 people that were born in concrete 3 days / day, p1 for mondays and weekends, p2 about other days.


    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve I?

→ Reply