Qingyu's blog

XXII Open Cup, Grand Prix of BSUIR
By Qingyu, history, 3 years ago, In English

Let's discuss the tasks here.

How to solve problem B?

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

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Was bitset intended for I? My $$$O(\frac{n^3}{w})$$$ solution runs in only 350ms.

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

    No. There is simple $$$O(n^2)$$$ greedy solution.

    Note that $$$1$$$ is always in the answer. Then we should greedily add vertices $$$2$$$, $$$3$$$, ...

    For example, we want to add $$$i$$$ to the answer. We should also add all vertices from $$$i$$$ to $$$1$$$ and for each we should check that there are no bad vertices added. We can note that check for each vertex need $$$O(n)$$$ time, and if we check all vertices once, we will achieve $$$O(n^2)$$$.

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

      if we check all vertices once

      How can we accomplish this? Can you elaborate more? Other than that, my solution is same, except using bitsets to speedup the check to $$$O(\frac{n}{w})$$$.

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

        Suppose we are trying to add vertex $$$v$$$ to the current set $$$S$$$ and we find a path from $$$v$$$ to $$$S$$$: $$$v = p_1, p_2,...,p_l$$$ ($$$p_l \in S$$$). Then we just iteratively check if $$$p_i$$$ is consistent with $$$S \cup $$${$$$p_{i+1},...,p_{l-1}$$$}. If we find that some vertex $$$p_j$$$ is a not consistent and we stop at vertex $$$p_j$$$, we simply mark all vertices in {$$$p_1,...,p_j$$$} bad and do not need to re-calculate the consistency of them anymore. On the other hand, if no bad vertices are found, then we just add $$$p_1,...,p_{l-1}$$$ to set $$$S$$$. From this you can see that for each pair $$$(u,v)$$$ we check at most once if the path from $$$u$$$ to $$$v$$$ is a palindrome of length greater than $$$k$$$.

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

B: "Set of edges without cycles" is a matroid. "Set of edges after which deletion graph is still connected" is also a matroid. You need to find the largest element in the intersection of these two and check that the remaining edges form a tree.

How to solve F (in 10 minutes)? Is it well known in Japan? We had a solution, which we didn't even try to implement because we thought we need at least 1,5 hours to do so.

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

B: Firstly, divide the whole graph into a tree and a forest, then 1+3 is the tree and 2 is the forest. Division plan can be found by matroid intersection.

By the way, how to solve C?

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

    C: For a fixed $$$k$$$ we need to choose $$$g = gcd(a, b)$$$, then $$$a' = a/g$$$ and $$$b' = b/g$$$ are coprime divisors of k, and $$$g$$$ should be a divisor of $$$k/a'b'(a'+b')$$$, so you can calculate the number of solution by trying all the possibilities for $$$a'$$$ and $$$b'$$$ and then calculating the number of divisors. So, to have a lot of solutions $$$k$$$ should have a lot of divisors, so let's generate some reasonable set of candidates (something like highly composite numbers but a bit looser) and check only them. With some very loose criteria (use only primes up to 40, each prime exponent starting from 5 is at most 1 greater than the previous one) works a couple of minutes on my laptop. I would not be surprised if it is possible to choose some tighter criteria so the solution can run on server and fit in TL.

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

How to solve J? We guessed the answer by coding a naive solution with infinity being 500, but honestly to me it even sounds weird that the answer isn't always 1 (given $$$p \neq 1$$$).

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

    There is a well known problem about two players playing a game with probability of winning equal to p for the first player (see https://en.m.wikipedia.org/wiki/Gambler%27s_ruin). You just need to tend the amount of money for one of the players to infinity

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

      I see, thanks

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

      I have some different solution:

      Let's solve the problem for one dimension (for many dimensions we should multiply probabilities for separate dimension).

      Consider we are at position 1. Let's see all possible ways to get 0. We can count this ways using correct bracket sequences. For +1 we will use "(" and for -1 we will use ")". So, probability to get 0 we can calculate using this simple formula:

      $$$P = C_0 \cdot q + C_1 \cdot p \cdot q^2 + ... = (\sum_0^{\infty} C_i \cdot (p \cdot q)^i) \cdot q$$$.

      So we can use generating function of Catalan numbers: $$$G(z) = \frac{1 - \sqrt{1 - 4 \cdot z}}{2 \cdot z}$$$. We should calculate $$$G(p \cdot q) \cdot q$$$.

      Then we should understand, that if we was at position x, then answer is $$$(G(p \cdot q) \cdot q)^x$$$.

      Another solution:

      Let's $$$w$$$ — probability to get $$$-1$$$ after some movements. Then $$$w = p + q \cdot w^2$$$

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

Is the opencup website not available outside of contests? I haven't been able to load it in quite some time.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +23 Vote: I do not like it

Editorial for D:

Note that the rotation operation in a binary tree does not change the order of numbers during forward traversal.

Also pay attention to selection sort — it sorts the array using the least number of swap operations.

Thus, the minimum answer will be equal to the minimum answer for sorting the array, obtained by direct tree traversal.

Let's learn how to do $$$swap(i, j)$$$ for a tree. To do this, we can use the following algorithm:

  1. Raise vertex $$$i$$$ to the root.
  2. Raise vertex $$$j$$$ to the root.
  3. Make swap.

Thus, we can solve the problem using the minimum number of swap operations.

Unfortunately, this solution will not work, since the total number of operations will be exceeded (we can have $$$O(n^2)$$$ of them. One of two approaches can be used to solve this problem:

  1. Use the splay operation to raise vertices to the root. In splay trees, this operation is amortized for $$$O(\log n)$$$.
  2. Balance the tree. Next, we can implement the simplest lifting to the root of the tree, now it will work for $$$O(\log n)$$$. After raising, we perform the rotate operations in reverse order to restore balance to the tree.

In total, we obtain a solution in $$$O(n \log n)$$$.

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

Can anybody explain solution to problem F please?

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

    Consider the "tightest" constraint in each direction: the leftmost right edge, the rightmost left edge, the topmost bottom edge, and the bottommost top edge. Clearly, we should never place points further outside than these edges. If the leftmost right edge and the rightmost left edge cross, then all rectangles must share a common x-range, so 1D greedy; likewise with the other two. Otherwise, in order to cover all rectangles, there must be at least one point on each of these 4 edges.

    For $$$m <= 3$$$, this means at least one point must cover two of these edges, so we can pick one of the 4 corners and recurse on the remaining rectangles with $$$m-1$$$. This takes $$$O(4^m n)$$$ time.

    For $$$m = 4$$$, either one point covers two edges (in which case we pick a corner and recurse on $$$m = 3$$$) or there is exactly one point on each edge. Let's visualize the 4 edges as a rectangle, where we pick one point on each side. In this case, each shelter rectangle imposes one of a few types of constraints:

    • If the shelter fully contained, then $$$m = 4$$$ is impossible.
    • If the shelter fully covers one side, then it is always satisfied.
    • If the shelter covers a corner, then it imposes an OR constraint on the two adjacent sides.
    • If the shelter intersects two opposite sides, then it imposes an OR constraint on the two opposite sides.

    Now, let's pick/sweep over all possible locations of the point on the left edge. If this is fixed, then we should greedily pick the points on the top and bottom to be as far right as possible. In particular, casework on either the top point or bottom point to be further left, and choose it as far right as possible to avoid breaking OR constraints with the left side and top/bottom OR constraints. Then, choose the other top/bottom point as far right as possible. Finally, check if there is a valid choice of the right point.

    To implement this, we just need to be able to query, for a particular choice of one point, which range constraints does it impose on the others. This can be done with several range-update point-query-min/max seg trees, approximately one on each pair of sides. This leads to an $$$O(n \log(n))$$$ time solution.

    Interestingly, this paper claims to also give an $$$O(n \log(n))$$$ solution for $$$m = 5$$$: https://www.cs.bgu.ac.il/~segal/pierce.pdf.

    Code
    → Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Problem G's semantics seem a little strange. I managed to get AC by disabling liveness checks for direct references but not indirect references. In particular, my AC submission prints

2
fn input()
fn foo(&a, b)
2
a := input()
c := foo(&a, a)
Valid

versus 

2
fn input()
fn foo(&a, b)
3
a := input()
b := &a
c := foo(b, a)
Error in line 3

Is this intended? I would've thought that both are supposed to be errors. (My original code was getting WA on test 14.)

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

    My solution prints an error for both programs. There is a rule for this (which I'm sure you saw but anyway):

    You cannot pass a value variable and a reference to that variable at the same time on the same line.

    It seems that 34 tests is not enough for this kind of problem, considering that there are 100 tests for others.

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

      That makes sense, but my solution only passes tests when I changed it to allow the first case :'( Does anyone know what test 14 is?

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

        14 test case was:

        1
fn input()
4
a := input()
b := &a
a := a
b := &a

        Also, both previous examples should output "Error" due to the rule in the comment above. Here, indeed, 34 tests were not enough.

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

          Ah ok that explains my bug, I forgot to reassign a a new variable ID. Thanks!

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

      34 tests is not enough for this kind of problem

      I just noticed that my first attempt failed on the last test, which happened to not handle this rule correctly :(

      Screenshot 2022-05-02 155347.png

      For my first attempt, it prints Valid in the following test (excpected Error in line 2)

      3
fn input()
fn f(&x)
fn g(x, y)
2
x := input()
y := g(f(&x), x)
      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      One question: what does "at the same time" mean? Does it mean to the same function? Are you allowed to use the same variable if it is passed to different function call subexpressions? (Perhaps only if the borrow occurs before the move?) If this is the case, is there a well-specified order-of-evaluation for subexpressions?

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

        I believe in this problem for the sake of understanding you can actually omit "at the same time", since (I think) it only matters if they are on the same line (which we treat as one instruction in this problem).

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

        You cannot pass a value variable and a reference to that variable at the same time on the same line.

        By our design, this means that you can use the variable by name or you can use its references, but not both on the same line.

        This rule is necessary to resolve the uncertainty of the order of function calls, which is not described in the statements.

        → Reply