Qingyu's blog

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

Let's discuss the problems here.

How to solve H. (Hoshi Sudoku) and I. (Imbalance)?

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

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

How to solve G, M?

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

    G can be solved by finding a partition s.t. every vertex has more neighbours in other part than in its part. This can be done by iteratively taking a vertex that does not satisfy this condition and moving it to the other part. The number of inner edges decreases and thus this process converges.

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

    G: If you can find a cycle of even size in every connected component, you can keep a tree with 1 edge added such that the only cycle in the result will be that even cycle, so the graph will obviously be bipartite. To find a cycle of even size, find a maximal path. Because it's maximal, all 3 of the endpoints' neighbours will be on the path; one will obviously be right next to it on the path, one will be $$$a$$$ edges away and one will be $$$b$$$ edges away. If $$$a$$$ is odd, you found an obvious even cycle. If $$$b$$$ is odd, you found an obvious even cycle. If $$$a$$$ and $$$b$$$ are even, you can make an even cycle of the path between those 2 neighbours and the original endpoint.

    M: Make a graph with edges $$$x$$$ -> $$$(x+c_i)$$$ $$$mod$$$ $$$c_0$$$ with cost $$$c_i$$$, now the answer is (the maximum distance from $$$0$$$ to any other node)-$$$c_0$$$. You don't have to run dijkstra with $$$n \cdot c_0$$$ edges for each query; you can keep the distances from the previous iteration of dijkstra and just use the edges using the new $$$c_i$$$ because the order in which the $$$c_i$$$ are added doesn't matter, so you can answer each query in $$$O(c_0$$$ $$$log$$$ $$$c_0)$$$.

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

      M: you don't even need log, you can update values greadily: staring from each s, try s->s+c, s+c->s+2c while you do better. You can see that this way you try each edge O(1) times

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

        Or now that I think about it, as I said (and implemented) it doesn't seem to be true

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

          It will work, if you run each cycle twice.

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

            yeah, if you run full two cycles, then yes. What I did was "do it while it's better approach" and I think it should be $$$\Theta(c_0^2)$$$ in bad cases

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

    Thank you!

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

How to solve F?

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

    Let dp[i][j] be the minimum amount of money required for the first $$$i$$$ days if the $$$j$$$-th student wasn't working on the $$$i$$$-th day, and let pref[i][j] be the prefix sum by rows of $$$c$$$. If dp2[i][j] is the minimum amount of money required for the first $$$i$$$ days if the $$$j$$$-th student was working on the $$$i$$$-th day, then dp2[i][j] is the minimum from

    Unable to parse markup [type=CF_MATHJAX]

    to $$$k=i-1$$$ of dp[k][j]+pref[j][i]-pref[j][k]. You can separate pref[j][i] from dp[k][j]-pref[j][k] and minimizing dp[k][j]-pref[j][k] can easily be done using one monotonic queue for each $$$j$$$. dp can easily be computed from dp2.
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

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

      An alternative solution: note that the optimal solution always uses one of the three cheapest students on each day (otherwise, you could use one of them instead, since there are only 2 potentially forbidden students, the neighbors of this day). Thus, we can do the naive dp where we store the cheapest cost if the last student was $$$s$$$ and has been awake for $$$d$$$ days, but we only process the 3 cheapest students on each day.

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

H: There are about 10^12 solutions to the puzzle. If we consider permutations of 1-9 in the solved puzzle as equivalent, the number of solutions drops to about 2 million. We can fix the numbers in one region and use recursion/backtracking to enumerate all the solutions. This can be done in a way similar to classical sudoku solvers: go through the cells in some order and try all digits that don't share a row or region with another instance of the same digit.

After precomputing these solutions, we need to check whether each one is compatible with the clues with some permutation of 1-9, and if so, the number of permutations. This turns out to always be (number of digits that do not appear in the clues)!

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

Is there a mirror / website where you can upsolve the problems?

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

I: we will construct the tree bottom to top. Fix $$$h$$$, and consider lowest vertices with height $$$\geq h$$$. Consider these vertices left to right, and write down heights of their children in a sequence. Initially $$$h = 2$$$, and the sequence consists of $$$0$$$'s and $$$1$$$'s. Going from $$$h$$$ to $$$h + 1$$$, we can:

  1. combine two adjacent $$$h - 1$$$'s into a single $$$h$$$;
  2. combine adjacent $$$h-2$$$ and $$$h-1$$$ into an $$$h$$$, increase imbalance by $$$1$$$;
  3. leave an $$$h - 1$$$ as it is (note that in this case imbalance will increase by $$$1$$$ on the next step).

Let $$$x, y$$$ be the number of $$$h - 1$$$'s and $$$h - 2$$$'s in the sequence. Note that:

  • $$$y \leq k$$$ at all times;
  • for $$$h = 2$$$ values of $$$x$$$ and $$$y$$$ determine $$$n$$$ unambiguously, this is our base case.

Compute $$$dp[x][y][b] =$$$ the number of ways to obtain a sequence with given $$$x$$$ and $$$y$$$, and accumulated imbalance $$$b$$$ ($$$h$$$ is unimportant!). Crucially, upon careful examination of the above $$$h \to h + 1$$$ transformation, we find that reachable permutations of $$$h - 1$$$ and $$$h - 2$$$ are equally distributed if $$$x, y$$$ are fixed. The new values $$$x', y'$$$ depend only the number of elements chosen with option 3, and the number of ways to proceed (assuming equal distribution) is found with simple combinatorics in each case. The answer is $$$dp[1][0][k]$$$. Complexity is $$$O(nk^3)$$$.

Elaborating on the transtition: suppose that $$$y'$$$ copies of $$$h - 1$$$ are carried over. Then:

  • $$$y'$$$ copies are reserved;
  • further $$$y$$$ copies are matched with the $$$h - 2$$$'s,
  • the remaining $$$x - y' - y$$$ copies are split into pairs.

Then $$$x' = p + y$$$, where $$$p = (x - y - y') / 2$$$ is the number of pairs. The number of ways to do choose a permutation and do this is $$$W = {x' + y' \choose y', p} \times 2^y$$$. Thus, we should add $$$\frac{dp[x][y][b]}{x \choose y} \times W$$$ towards $$$dp[x'][y'][b + y]$$$.

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

    Come to think of it, top-to-bottom version of this is significantly easier: start from $$$dp[1][0][0] = 1$$$, and successively choose how many copies of $$$h$$$ will be decomposed into $$$h - 1, h - 2$$$.

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

      You can do this without the dp; the number ways of writing a number as at most 20 powers of $$$2$$$ is quite small, so you can just do recursion with pruning (adding memoization makes the complexity the same as yours).

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

        Actually, I didn't realize exactly what your solution is. I'm pretty sure there are only $$$O(poly(k) polylog(n))$$$ different reachable states if you go top down, so this problem should be solvable for very large $$$n$$$.

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

          Yes, my submit from the contest is $$$O(\log n \cdot k^4)$$$ dp (probably there is an additional $$$\log k$$$ for how much bigger than $$$\log n$$$ height can be, not sure), if ignore $$$O(n)$$$ precalculation of factorials, which is not necessary.

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

          Very nice observation!

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

How to solve K? We tried sampling but we could not reach the precision error in the statement.

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

    We integrated numerically over $$$z$$$; within a plane, we used black-box halfplane intersection and circle-polygon intersection, both from KACTL.

    We found that surprisingly, you only need to take $$$z$$$ in increments of $$$0.01$$$ ($$$10^{-2}$$$) in order to have enough precision to pass all tests.

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

      Amazing! Thanks for the solution!

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • A: whats the proof that the answer is always in the shape of young table?
  • C: whats the efficient way to implement it? i did bfs with 25 bit bitmask. ran the bfs for each of the 5 numbers. I implemented the operations in ~5 bitwise operations. got tle. not sure if generating/storing the string along with the mask is costly or not.
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    For C, you can do a single BFS from the target state, so you shouldn't have to repeat it for each number/each testcase.

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

    For C there are only $$$\binom{25}{5} \approx 53000$$$ useful states, so naive implementation (each state takes $$$5^2$$$) should be enough for the time limit, no need to struggle on bitwise operation. The key point is to do BFS only once.

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

    For A, I think you can just you can just make the figure compact and see that the number of sides shared by two cells does not decrease: suppose all cells have positive coordinates $$$(x, y)$$$ and you first keep moving all cells downward (i.e. along $$$y$$$-axis) as long as cells have positive coordinates and no two cells coincide. Then you do the same thing but along $$$x$$$-axis. You can see the figure then has the shape of Young tableau.

    This gives you the maximal perimeter you can achieve while the area is fixed. And the perimeter is equal to the perimeter of the bounding box of the figure. It is also easy to see that you can achieve any perimeter (which has to be even) between the lower bound shown above and the trivial upper bound (by moving one cell to the border and thus making bounding box larger).

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

How to be as strong as Qingyu?

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

How to solve A, L?

→ Reply