Qingyu's blog

By Qingyu, history, 11 months ago, In English

Let's discuss problems here.

How did you solve problem L?

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

»
11 months ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

How to solve H, M?

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it +31 Vote: I do not like it

    M: If we take out a prefix of the given expression, it will be of the form $$$E_1+E_2+\cdots+ E_m + x_1 \times x_2 \times \cdots x_k \times \overline{y_1y_2\cdots y_t}$$$, where $$$E_i$$$ is an expression contains only '$$$\times$$$'. So you can have a straightforward linear DP solution by memorizing the sum of $$$E=(E_1+E_2+\cdots+E_m)$$$, the sum of $$$X=(x_1\times x_2 \times \cdots x_k)$$$ and the sum of $$$Y=\sum_i 10^{t-i} y_i$$$. Then, the DP transitions will be one of the following:

    • Append a digit $$$d$$$ to the expression. ($$$Y \leftarrow Y \times 10 + d$$$)
    • Append a $$$\times$$$ to the expression. ($$$X \leftarrow XY, Y \leftarrow 0$$$)
    • Append a $$$+$$$ to the expression. ($$$E \leftarrow E + XY, X \leftarrow 1, Y \leftarrow 0$$$)

    After carefully handling of the invalid cases (such as two adjacent operators), we can obtain a linear DP approach. Then we can put everything into a matrix and use the matrix multiplication to optimize it to $$$O(\log n)$$$.

    Also, it can be shown that the answer sequence will be a linear recurrence, so we can also apply the Berlekamp-Massey algorithm directly.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wtf, I just insta plugged in to BM and it failed to find solution. On the other hand, the P-recursive interpolator found the solution, so I thought it was a hard problem... (Also I didn't thought only 25 teams solved a simple BM problem)

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

        Weird, I just copy-pasted a BM implementation and it worked well.

        Spoiler

        (The implementation is copied from the MIT_Copypaste TLE.)

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it +26 Vote: I do not like it
    I used generating functions for M 🤡

    I think the better strategy in contest would just be to guess that it is a linear recurrance and use berlekamp massey, no idea how someone can solve it in 15 mins otherwise.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How exactly do you go about calculating the n'th coeficient of G(x)H(x) in O(logN)

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

        Lets say $$$\frac{1}{1+a_1x+a_2x^2+a_3x^3}=1+b_1x+b_2x^2+b_3x^3+\ldots$$$, we have $$$b_i=b_{i-1}a_1 + b_{i-2}a_2 + b_{i-3}a_3$$$.

        This is the linear recurrence so we can find $$$b_k$$$ in $$$O( \log n)$$$ with any linear reccurence algorithm since we are dividing by a polynomial of degree $$$6$$$ here.

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

    H: let $$$f(n, m)$$$ be the answer to the problem. Since every $$$x\in{a, b, c}$$$ is a solution to the equation $$$x^3 = sx^2 - tx + u$$$, we have $$$f(n, m) = sf(n - 1, m) - tf(n - 2, m) + uf(n - 3, m)$$$ and similarly with $$$m$$$.

    Let $$$x^n\equiv a_0 + a_1x + a_2x^2\pmod{x^3 - sx^2 + tx - u}$$$ and $$$x^m\equiv b_0 + b_1x + b_2x^2\pmod{x^3 - sx^2 + tx - u}$$$. The coefficients $$$a_i$$$ and $$$b_i$$$ can be found using binary multiplication. Then the answer is

    $$$\sum_{i=0}^2\sum_{j=0}^2 a_ib_jf(i, j).$$$

    It turns out that $$$f(2, 1) = -1$$$, $$$f(1, 2) = 1$$$, and all other summands are zeroes, therefore the answer is $$$a_1b_2 - a_2b_1$$$.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 3   Vote: I like it +11 Vote: I do not like it

      Another approach that relies on Google more heavily: searching [anti-symmetric polynomial] leads to this page which explains that the polynomial in our numerator is divisible by the polynomial in the denominator, and directs to Wikipedia for [Schur polynomial], which turns out to be exactly what we need, and which has a formula how to compute it via a determinant of a 3 by 3 matrix, the elements of which are described in another Wikpedia page which has a linear recurrence of size 3 for them that uses the 3 given numbers as coefficients, so we can use matrix exponentiation to compute them.

»
11 months ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve F?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    It seems to me that you have to prove that it is a min 0/1 knapsack with weights less than 5, and then find the convolutions (min, +) using mikowski sum. Although I don't know if this idea is overkill.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But none of our arrays are convex/concave no?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I meant that for each amount of 1s of profit, I order by weight ($$$a_i$$$). Seeing that the best way to buy an object is always individually.

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

    Note that we to essentially have a knapsack problem where every item has an utility in $$$1 \ldots 4$$$, and a weight. The key is now to use the fact that 4 is small.

    Brute force whether we take an even or odd number of items with utility 1, and whether we take an even or odd number of items with utility 2. If we chose to have an odd number of items with utility 1, pick the cheapest one. The rest of the items with utility 1 we can group into pairs and move them to the list of items with utility 2. Do the same thing, pushing pairs from 2 to 4. Now we have only utility 3 and 4, which can be solved naively.

»
11 months ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve k (King’s Palace) ? (div2)

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

    We can use a weird version of meet in the middle. We will split the walls into sections $$$[1,13]$$$ and $$$[14,22]$$$.

    First, we brute force all possible $$$3^9$$$ possibilities of the walls in $$$[14,22]$$$. Now, we will add it to an array of size $$$7^9$$$, where the array indexes on $$$7-bit$$$ numbers. This number stores information about what color restrictions the $$$i$$$-th bit has (example: the $$$5$$$-th bit can only be red or green). Usually, there is $$$2^3$$$ possible choices for this but there is no point storing information that we cannot choose any color. We can use some FWHT-like idea to do this summing quickly instead of doing it in $$$O(4^X)$$$ per element.

    Then we can do brute force on the $$$[1,13]$$$ side with our $$$7^9$$$ lookup table.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      LOL, is this technique well-known? As a rookie this is mind-blowing to me.

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        The FWHT idea is from my blog (shameless advert) but this is the first time I have seen "unbalanced" meet in the middle, maybe its more well known in other countries?

        If it's about the FWHT idea, I can explain in a simpler way for this context.
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think it appeared in a problem named "SNAKE" or something like that in some JOI contest.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      One easier solution than FWHT is Sum Over Subsets dynamic programming. FWHT might be overkill.

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

        SOS DP is essentially the same as FWHT though?

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it +26 Vote: I do not like it

      FWHT-like tricks are not really necessary here. Let's just do a brute force of all $$$3^{22}$$$ options, but as long as there are 8 or less walls remaining, let's add memoization based on the allowed colors for each remaining wall. So the first 14 walls will lead to $$$3^{14}$$$ recursive calls, and on the last 8 walls we will have at most $$$8^8$$$ states in the memoization, and $$$3^{14}+8^8$$$ is small enough (there are some other smaller terms in this summation, but this gives the right order of magnitude).

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +74 Vote: I do not like it

    K is possible in $$$\mathcal{O}(n \cdot 2^n)$$$.

    First, compute for every mask, how many ways there would be to colour that mask with 0 and 1 assuming other vertices didn't exist. To do this, try setting the color of the first node in the mask to both colours, propagate, and if you didn't get a contradiction, add the DP value of the remaining mask.

    To compute the actual answer, loop over which mask you set to color 2, then propagate what information that gives you, and add the DP of remaining mask to answer if you didn't get a contradiction.

    Propagation done naively takes $$$O(n^2)$$$, but the only $$$O(n^2)$$$ part is finding first set bit in a mask, so the actual complexity is $$$\mathcal{O}(n \cdot 2^n)$$$.

    Code
»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Sadly Perl is not back here yet, although many languages are allowed.

»
11 months ago, # |
Rev. 7   Vote: I like it +8 Vote: I do not like it

I couldn't solve L but have ideas for it.

For a fixed query $$$v, d$$$ let $$$f_u = min_{dist(w, v) = d} dist(u, w)$$$. Then the answer is the maximum of $$$f_u$$$ over all vertices such that $$$f_u > dist(u, v)$$$.

Let's make the condition simpler. if $$$dist(u, v) > d$$$ then obviously it can't be considered as an answer. Suppose we relax the condition to $$$dist(u, v) \le d$$$. Then we may have a false candidate with $$$f_u \le dist(u, v)$$$. But they have $$$f_u \le d$$$, and these can not beat trivial solution $$$d$$$ in $$$u = v$$$, so the relaxation works.

Now we should take the maximum of $$$f_u$$$ over $$$dist(u, v) \le d$$$. Let's assume, that the query vertex $$$v$$$ is fixed but we have to answer for all $$$d$$$. Instead of fixing the vertex $$$u$$$, let's fix the deepest node $$$l$$$ where it contains both $$$u$$$ and at least one node with depth $$$d$$$. Given the depth $$$d$$$, we have to check the existence of node with depth $$$d$$$, and the deepest subtree which doesn't contain depth $$$d$$$ nodes. Say the subtree's depth is $$$x$$$, then we update the answer to $$$d + x - 2 depth_l$$$.

Then we extend this algorithm to update its value for all possible $$$d$$$. For each subtree of $$$l$$$, what only matters is the deepest node in each child's subtree of $$$l$$$. And for fixed $$$d$$$, what only matters is the two subtrees, the shallowest one with depth at least $$$d$$$ and the deepest one with depth at most $$$d - 1$$$. This means, we only have to update for adjacent subtrees in terms of deepest node. For example, if we have depth sequence $$$x_1 \le x_2 \le \ldots \le x_k$$$, then for $$$d \in [x_i + 1, x_{i+1}]$$$ we can have answer $$$d + x_i - 2 depth_l$$$. This is a classic problem. I think using sweeping is the best option.

To support arbitrary $$$v$$$, we can simply build a centroid decomposition where for each layer the above structure is stored. For each query $$$v$$$ we want to find $$$u$$$, that is in this centroid layer, but not from the subtree which contains $$$v$$$. This can be found with the above structure, but the subtree shall not contain $$$v$$$, which you can solve by maintaining two maximas or likewise.

»
11 months ago, # |
  Vote: I like it +31 Vote: I do not like it

L: We explicitly present an optimal strategy. The intuition is that the zebra should try to walk towards the lion to get information/space, and then backtrack and run away once the lion gets too close (within 2).

Let the zebra start at vertex $$$v$$$, and the lion is initially distance $$$d$$$ away. Let $$$t$$$ be the vertex furthest from $$$v$$$, and let $$$u$$$ be the furthest vertex from $$$t$$$ (so that $$$u-t$$$ forms a diameter). Our plan will be to walk around until we decide on an endpoint, and then go towards the endpoint and wait for the lion; the survival time will be the distance from the original lion location to the endpoint. This is clearly an upper bound, as the lion always makes progress every turn. Then, the precise strategy is:

Walk towards $$$t$$$ while the distance to the lion is greater than $$$2$$$ and has kept decreasing. There are 2 break conditions:

Case 1

The lion did not get closer after our last step, i.e. we walked away from the lion, and we are distance at least 3 away. Let our last step be from $$$p$$$ to $$$c$$$. Then, since we were walking towards the lion up until now, the lion must be in a different subtree of $$$p$$$ aside from $$$c$$$ and the subtree containing $$$v$$$. Because we're distance at least 3, we can use a turn to step back from $$$c$$$ to $$$p$$$.

Now, consider the furthest point from $$$p$$$; it's either $$$t$$$ or $$$u$$$. We claim this furthest point is not in the lion's subtree, so it's also the furthest point from the lion's start and thus necessarily the optimal ending point. $$$t$$$ lies in the subtree of $$$c$$$, so if $$$t$$$ is further, then we're good. If $$$u$$$ is strictly further from $$$p$$$ than $$$t$$$, then $$$u$$$ must be in the subtree of $$$p$$$ containing $$$v$$$, since we chose $$$t$$$ to be the furthest point from $$$v$$$ (otherwise, $$$u$$$ would be further from $$$v$$$).

Thus, we can always safely get to the furthest point from $$$p$$$, which is also the furthest point from the lion, which is always optimal for the lion's starting position.

Case 2

The distanced started at or decreased to at most $$$2$$$. This occurs after exactly $$$\lfloor (d-1)/2 \rfloor$$$ steps. Let the final step be from $$$p$$$ to $$$c$$$ (let $$$p$$$ be $$$\varnothing$$$ if we started at $$$d \le 2$$$). Then, note that walking in any direction which possibly contains the lion could result in dying that turn, which is always suboptimal. Thus, we should walk to and wait at the furthest vertex in a "safe" subtree (directed away from $$$c$$$), i.e. one which cannot contain the lion. There are two types of safe subtrees: (a) the $$$p$$$-subtree, which is safe because our last step took us closer to the lion, or (b) subtrees which are too shallow to contain the lion initially (all points are within $$$d-1$$$ from the start $$$v$$$). Note that the subtree of type (a) always has a path of length at least $$$\lfloor (d-1)/2 \rfloor$$$, namely the one back to $$$v$$$, and any subtree of type (b) has max depth at most $$$\lceil (d-1)/2 \rceil$$$, so subtrees of type (b) can only be useful if $$$d$$$ is even and they have max depth exactly $$$\lceil (d-1)/2 \rceil$$$.

Thus, we should look for the furthest vertex from $$$c$$$ in the direction of $$$p$$$; let this distance be $$$l$$$. If $$$c$$$ has any subtree of max depth exactly $$$\lceil (d-1)/2 \rceil$$$, let $$$l = \max(l, \lceil (d-1)/2 \rceil)$$$. Then we can survive for time $$$d + l - \lfloor (d-1)/2 \rfloor$$$.

This concludes the strategy. It turns out case 2 is always better for the lion/worse for the zebra, since they block off the furthest path, so the lion should wait along the path from $$$v$$$ to $$$t$$$ at distance $$$d$$$. (The lion can also always do at least this well by starting at this point, so this strategy is indeed optimal.)

Thus, we just need to evaluate the time that the zebra lives in case $$$2$$$. We can calculate the value described above by precomputing, for each vertex $$$c$$$, the max depth vertex in each direction/subtree, as well as the set of subtree max depths (in order to check for $$$\lceil (d-1)/2 \rceil$$$). We can do this with a simple tree DP.

Spoiler
»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve J?

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

    Consider the set of balls eventually taken as parts of tricks. These balls must be colored to form disjoint substrings, each of which contains exactly $$$kr$$$ red balls and $$$kb$$$ blue balls for some integer $$$k$$$. In fact, this condition is sufficient: for any interval of $$$kr$$$ red balls and $$$kb$$$ blue balls, we can find some subinterval of length $$$r+b$$$ with exactly $$$r$$$ red balls and $$$b$$$ blue balls by the intermediate-value theorem. Thus, we can take one such substring and repeat with the remaining balls $$$(k-1)(r+b)$$$ balls.

    Now, this condition immediately gives us a $$$O(N^2)$$$ DP solution: let $$$dp[i]$$$ be the maximum number of tricks we can take from the first $$$i$$$ characters. Then, we initialize $$$dp[j] = dp[j-1]$$$ and for each interval $$$[i,j)$$$ of length $$$k(r+b)$$$, if it's possible to color the white balls so there are exactly $$$kr$$$ red and $$$kb$$$ blue balls, we set $$$dp[j] = \max(dp[j], dp[i] + k)$$$. This gives $$$O(N^2)$$$ transitions.

    We can speed this up using data structures. Note that, for each $$$j$$$, we want to find the max (shifted) DP for all $$$i < j$$$ such that $$$i \equiv j \pmod{r+b}$$$ and there are at most $$$kr$$$ red balls and at most $$$kb$$$ blue balls between $$$i$$$ and $$$j$$$. The latter condition is simply a 2D range query on the prefix counts of red/blue balls, so we can build a separate 2D seg tree for each value mod $$$r+b$$$ and perform 2D point updates/range-max-queries to do all transitions. Using static 2D seg trees or BIT's, this takes $$$O(n \log^2(n))$$$ time with pretty good constant.

    Is there a faster solution that perhaps uses more greedy ideas? We had some thoughts, but found this solution and just submitted it.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We have exactly the same solution, it also feels like something more greedy is possible, but I could not put a finger in it.