awoo's blog

Educational Codeforces Round 133 Editorial
By awoo, history, 2 years ago, translation, In English

1716A - 2-3 Moves

Idea: vovuh

Tutorial
Solution (vovuh)

1716B - Permutation Chain

Idea: BledDest

Tutorial
Solution (awoo)

1716C - Robot in a Hallway

Idea: BledDest

Tutorial
Solution (awoo)

1716D - Chip Move

Idea: BledDest

Tutorial
Solution (Neon)

1716E - Swap and Maximum Block

Idea: BledDest

Tutorial
Solution (BledDest)

1716F - Bags with Balls

Idea: BledDest

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +172
  • Vote: I do not like it

Comments Comments (51)
| Write comment?
»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

My $$$O(n\sqrt n)$$$ solution for problem D that works in just 78 ms!

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

    The expression 'sum[q] -= (sum[q] >= mod) ? mod : 0' will be auto-vectorized in GCC with AVX enabled so that's a reason I guess.

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

My approach for problem C, Binary search the waiting time before starting to move. https://mirror.codeforces.com/contest/1716/submission/166993379

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

Solution to 1716F - Bags with Balls using the multinomial theorem.

Let $$$ B $$$ iterate through all the ways $$$ (b_1,\dots, b_n) $$$ to take the balls out of the bags and define $$$ g(x):= x\text{ mod } 2 $$$, and $$$F(B):=\text{# of odd balls}$$$. The answer we want to compute is

$$$\begin{align} \sum_{F}F^k = \sum_{B}F(B)^k &= \sum_{B}\left(\sum_{i=1}^n g(b_i)\right)^k \\ &=\sum_{B}\sum_{\substack{j_1+\cdots+j_n=k \\ j_i\geq0}} \binom{k}{j_1,\dots,j_n}\prod_{i=1}^ng(b_i)^{j_i} \\ &=\sum_{B}\sum_{\substack{j_1+\cdots+j_n=k \\ j_i\geq0}} \binom{k}{j_1,\dots,j_n}[g(b_i)=1,\forall j_i\geq1] \\ &= \sum_{\substack{j_1+\cdots+j_n=k \\ j_i\geq0}} \binom{k}{j_1,\dots,j_n}\sum_{B}[g(b_i)=1,\forall j_i\geq1] \end{align}$$$

Now suppose $$$c$$$ of the $$$n$$$ indices are positive, there are $$$\binom{n}{c} $$$ ways to choose them. Also notice that we can just erase the indices equal to $$$ 0 $$$ from the multinomial coefficient (the answer remains the same). So rewriting the sum

$$$\displaystyle =\sum_{c=1}^k \binom{n}{c} \sum_{\substack{j_1+\cdots+j_c=k \\ j_i\geq1}} \binom{k}{j_1,\dots,j_c}\sum_{B}[g(b_i)=1,\forall j_i\geq1] $$$

we can compute the last part since the indices of the bags from which we pick odd balls are fixed

$$$\begin{align} &=\sum_{c=1}^k \binom{n}{c} \sum_{\substack{j_1+\cdots+j_c=k \\ j_i\geq1}} \binom{k}{j_1,\dots,j_c} \left\lceil\frac{m}{2}\right\rceil^cm^{n-c} \\ &=\sum_{c=1}^k \binom{n}{c} \left\lceil\frac{m}{2}\right\rceil^cm^{n-c}\sum_{\substack{j_1+\cdots+j_c=k \\ j_i\geq1}} \binom{k}{j_1,\dots,j_c} \\ &=\sum_{c=1}^k \binom{n}{c} \left\lceil\frac{m}{2}\right\rceil^cm^{n-c}S(k,c)\cdot c! \end{align}$$$

We arrive at finall formula we can compute in $$$O(k)$$$ (not taking in account the precomputations) after noticing that

$$$\displaystyle \sum_{\substack{j_1+\cdots+j_c=k \\ j_i\geq1}} \binom{k}{j_1,\dots,j_c} = S(k,c)\cdot c! $$$

Where $$$ S(i,j) $$$ is the stirling numbers of the second kind.

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

In problem C, at least for me, letting a_ij+1 be the time limit instead of aij is somehow frustrating, and the lack of explanation for samples make it even worse.

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

video Editorial for Chinese:

Bilibili

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

Question on problem D. There is an approach that calculates the same as in the editorial, but in a slightly different way, and gets WA. The solution is the following: let's calculate $$$dp_i,_j$$$ — the number of ways to achieve $$$i$$$ using $$$j$$$ steps. $$$dp_0,_0 = 1$$$. Transition is presented in full form and can be calculated faster.

$$$dp_i,_j$$$ = $$$\sum_{w=1, q=k+j-1}^{i - wq >= 0} dp_{i - wq},_{j - 1}$$$

What is the difference between calculated $$$dp_i,_j$$$ from the solution described above and calculated $$$dp_s,_i$$$ from the editorial?

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

    I'm a little confused by the expression, since it has a single summation controlled by two variables, so do you mean that we try every possible combination of $$$w$$$ and $$$q$$$ that satisfies $$$w \geq 1$$$, $$$q \geq k + j - 1$$$, and $$$i - wq \geq 0$$$?

    I think a simple counterexample is $$$dp_{3, 1}$$$ for $$$k = 2$$$ (the third entry in the sample output 2 of the problem). Your formula would include $$$dp_{0, 0} = 1$$$ ($$$w = 1$$$, $$$q = 3$$$) in the summation, but the actual value of $$$dp_{3, 1}$$$ is $$$0$$$.

    My guess is that your approach allows skipping steps, e.g., it allows you to take a step of size $$$(k + i + 1)$$$ without taking a step of size $$$(k + i)$$$. The problem requires that you must take at least one step for each value between $$$k$$$ and the largest step size inclusive.

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

      I think what they mean by the 2 variables is that, $$$q$$$ is the constant denoting the number whose multiple was the last step length, i.e, $$$q = k + (j - 1)$$$ and $$$w$$$ varies freely. Hence for $$$dp[3][1]$$$, $$$q$$$ can't be 3.

      Romiros : Your approach is correct (and is in fact the same as the editorial solution, except that your DP takes contribution from old states, while the editorial's solution provides contribution to new states).

      You have 2 small bugs in your implementation though. You can take a look at Ticket 15995 from CF Stress for a counter example.

      Hints for Bug 1
      Hints for Bug 2:
      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Got it, thanks. But why are $$$cnt$$$ steps not enough?

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

          $$$sum1 += K$$$ implies that the step length is $$$K$$$. Therefore, $$$K$$$ should be overwritten with $$$k+1$$$ at each stage. However, $$$K + = k + cnt$$$ makes it increment by that amount instead of overwriting it.

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

      Summation controlled only by variable $$$w$$$ and continues until $$$i - wq >= 0$$$, $$$wq$$$ is length of the move on $$$j$$$-th step, $$$q$$$ is the number that should divide length of the move on $$$j$$$-th step.

      The solution passes pretests and gets WA3. Somehow it counts fewer number of ways than needed.

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

Would any kind-hearted person mind explaining to me why "the sum of F^k over all possible combinations is equal to the sum of G(t) over all possible tuples t"? I am not able to figure out why they are equal, what is the intuition behind and how could we prove it (the rest is straightforward tho, just can't comprehend the rephrased problem)

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

    In essence, the problem asks for you to get the sum of F^k for all combination of ball selection. However, if you look at a specific selection with F odd numbers, the number of tuples of length k, where each element is an index of a bag from which we have taken an odd ball is exactly F^k.

    So in order to get the sum of all F^k, we can just look at each possible tuple, and look how many times this tuple appear across all ball selection, which is the definition of G(t).

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

Can anyone who used prefix sums for calculating $$$dp[i][j]$$$ for D share their code? I'm having trouble implementing it.

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

    Here is my submission

    There is a commented while block that may be easier to read, since it builds the entire 2D table instead of maintaining only 2 rows. It still uses a colsum vector that keeps track of the sum of each column so far.

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

In problem $$$A$$$, can anybody explain solution using modulo. I don't want to deal with rounding. It's confusing for me. If $$$n$$$ $$$mod$$$ $$$3 = 0$$$ then answer is $$$\frac{n}{3}$$$, else if $$$n$$$ $$$mod$$$ $$$2 = 0$$$ then answer is $$$\frac{n}{2}$$$. But what in other cases ?

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

    If $$$n \bmod 3 = 0$$$, then the answer is $$$\frac{n}{3}$$$.

    If $$$n \bmod 3 = 1$$$, then there are two cases. For $$$n = 1$$$ (the only special case), the answer is $$$2$$$. Otherwise, the answer is $$$\frac{n - 4}{3} + 2$$$. Since we excluded the special case of $$$n = 1$$$, the value of $$$n$$$ must be at least $$$4$$$, and $$$n - 4$$$ must be divisible by $$$3$$$. So we can keep taking $$$3$$$-length steps until we have $$$4$$$ left, which we can cover with two $$$2$$$-length steps.

    If $$$n \bmod 3 = 2$$$, then the answer is $$$\frac{n - 2}{3} + 1$$$. Keep taking $$$3$$$-length steps until you have $$$2$$$ left, which you cover with a single $$$2$$$-length step.

    Note that your suggestion of using $$$\frac{n}{2}$$$ for $$$n \bmod 2 = 0$$$ is not necessarily optimal, e.g., you can reach $$$8$$$ using $$$3 + 3 + 2$$$, which is 3 steps instead of $$$\frac{8}{2} = 4$$$.

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

With how unusually long the editorial for C is, I'm surprised that the problem-setters still felt it was appropriate to keep it as a Div2C.

For D, the editorial should probably mention how we need to keep track of the first non-zero value in each row (variable $$$mn$$$ in the solution) and only start filling it up from there, since it seems like starting from the beginning resulted in many TLEs.

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

    I think I maybe overexplained things for C. A lot of people got stuck in it, so I decided it's reasonable to explain just everything in the problem as thoroughly as possible.

    Really, I think half of these things are pretty intuitive and the other half is neither that hard to come up with, nor is the only way to come to the solution.

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

    No, keeping first non-zero element is not necessary. I didn't do that, and had not big time.

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

Does anyone have a testcase that breaks my submission for C? 167164510

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

    Check these:

    input

    Your submission returns [19, 28, 20, 22], result is [17, 26, 18, 20]

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

      wait, shouldn't the top left element in each grid be 0?

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

        fixed it

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

          Thanks, I had swapped my row variable with my col variable.

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

F can be solved more easily by using Stirling Number and Descending Power.

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

There is a much easier way to solve F.

A classic conversion is that:

$$$ n^k=\sum\limits_{i=0}^k S(k,i)\binom{n}{i}i! $$$

Using the above formula:

$$$ \begin{aligned} \sum\limits_{F} F^k&=\sum\limits_{F}\sum\limits_{i=0}^k S(k,i)\binom{F}{i}i!\\ &=\sum\limits_{i=0}^k S(k,i)i!\color{red}{\sum\limits_F \binom{F}{i}} \end{aligned} $$$

Consider the combinatorial meaning of the red part. It chooses some boxes to take out balls with odd numbers, then it chooses $$$i$$$ of them, and calculate the number of ways. Let's reverse the steps, we can find out that the answer to the red part is equal to the number of ways to perform the following steps:

  1. Choose $$$i$$$ balls.
  2. Let the chosen balls be odd numbers. No constraints on the rest of the balls.

Thus, the answer can be simplified as follows:

$$$ \begin{aligned} \sum\limits_{i=0}^k S(k,i)i!\sum\limits_F \binom{F}{i}&=\sum\limits_{i=0}^k S(k,i)i!\binom{n}{i}m^{n-i}\left\lceil{m\over 2}\right\rceil^i \end{aligned} $$$

which can be solved in $$$\mathcal{O}(k^2)$$$.

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

    Amazing solution, thanks for the help!

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

    But when I read your code, I see your formula is (n!/i!) instead of i!. Can you help me ? (Sorry for bad English T_T)

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

How to solve problem C if you can visit the cell more than once??

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

Problem C can also be solved in super ugly way using binary lifting and segment tree.

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

    can you explain ur idea,Thank You.

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

      First, let's normalize the array in such a way that the order of elements is $$$(0,0) => (1,0) => (2,0)...=> (m-1,0) => (m-1, 1) => (m - 2, 1) => ... (0,1)$$$ (zero-indexed). Let this array be $$$a_{i}$$$ and let' call this way of ordering forward order. Similarly, let the reverse of $$$a_{i}$$$ be $$$b_{i}$$$ and let's call way of ordering be backward order. Let's consider the case when we enter the cell $$$(i,0)$$$ in time $$$t$$$ and til then we moved snakely(?). Then, what we want to compute is:

      $$$ f_{i}(t) := \text {Total time taken to move from $$$a_{i}$$$ to $$$a_{2m-i-1}$$$ when we enter $$$a_{i}$$$ in time $$$t$$$} $$$

      Similarly, when we enter the cell $$$(i,1)$$$ in time $$$t$$$ then what we want to compute is:

      $$$ g_{i}(t) := \text {Total time taken to move from $$$b_{i}$$$ to $$$b_{2m-i-1}$$$ when we enter $$$b_{i}$$$ in time $$$t$$$} $$$

      Now, these two cases are almost equivalent, so I'll ignore the latter case here. Let's call an element $$$a_{j}$$$ blocking to $$$a_{i}$$$ if we enter $$$a_{i}$$$ in time $$$a_{i}+1$$$ we cannot move to $$$a_{j}$$$ without being stuck (which means that we cannot enter $$$a_{j}$$$ without being stuck at $$$a_{j-1}$$$). Then it is obvious that $$$a_{j} \gt a_{i} + j - i$$$ must hold. We only need to consider blocking elements to $$$a_{i}$$$ because the total time taken to reach $$$a_{2m-i-1}$$$ from $$$a_{i}$$$ only depends on the last blocking element with position less than or equal to $$$2m-i-1$$$ (Let's call this position $$$p_{i}$$$). Now, it follows that:

      $$$ f_{i}(a_{i}+1) = 2m - i - p_{i} + a_{p_{i}} $$$

      And if we let $$$q_{i}(t)$$$ be the first position of blocking element to $$$a_{i}$$$ when we enter $$$a_{i}$$$ in time $$$t$$$, then it also follows that:

      $$$ f_{i}(t)=2m-i-p_{q_{i}(t)}+a_{p_{q_{i}(t)}} $$$

      Notice that if we store $$$a_{i}-i$$$ for each $$$i$$$ then $$$q_{i}(t)$$$ can easily be calculated using segment tree (we only need to find the first position $$$j (\gt i)$$$ such that $$$a_{j} - j \geq t - i$$$). Also, if we store position of $$$2^k$$$th blocking element to $$$a_{i}$$$ when we enter $$$a_{i}$$$ in time $$$a_{i}+1$$$ for each $$$i$$$ and $$$k$$$, $$$p_{i}$$$ can also be calculated easily using binary lifting. The formulas are quite ugly but I tried my best to explain my logic.

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

Video Solution for Problem C.

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

Can somebody help with this submision, It takes O(m) time and I get time limit. https://mirror.codeforces.com/contest/1716/submission/167315560

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

    You fill the calc array until N in each test case, that's why it takes so much time — it now works in $$$O(tN)$$$

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

F can also solved this way: The answer can be represented as:

$$$ \begin{align} \sum_{t=0}^{n} \binom{n}{t}t^k(\lceil{m/2}\rceil)^t(m - \lceil m/2 \rceil)^{n-t} \end{align} $$$

If we let $$$p$$$ $$$=$$$ $$$ \frac {\lceil {m/2} \rceil}{(m - \lceil{m/2}\rceil)}$$$ then our objective is to compute the following sum:

$$$ \begin{align} (m - \lceil{m/2}\rceil)^{n}\sum_{t=0}^{n} \binom{n}{t}t^{k}p^t \end{align} $$$

Let:

$$$ \begin{align} dp(i) = \sum_{t=0}^{n}\binom{n}{t} t^i p^t \\ f_{i}(x) = \frac {d}{dx^i}{(1+x)^n} \end{align} $$$

Then it's clear that the answer is $$$dp(k) (m - \lceil{m/2}\rceil) ^ {n}$$$. Now it follows that:

$$$ \begin{align} f_{i}(p)p^{i} &= \sum_{t=0}^{n} \binom{n}{t} t(t-1)(t-2)\dots(t-i+1)p^{t} \\ &= \sum_{t=0}^{n} \binom{n}{t} \sum_{j=0}^{i} s(i,j) t^{j} p^{t} \\ &= \sum_{t=0}^{n} \sum_{j=0}^{i} s(i,j)\binom{n}{t} t^{j} p^{t} \\ &= \sum_{j=0}^{i} s(i,j) \sum_{t=0}^{n}\binom{n}{t} t^{j} p^{t} \\ &= \sum_{j=0}^{i} s(i,j) dp(j) \end{align} $$$

where $$$s(i,j)$$$ is stirling number of the first kind. If we let $$$g_{i} = f_{i}(p) p^{i}$$$, then:

$$$ \begin{align} g_{i} = \sum_{j=0}^{i} s(i,j) dp(j) \iff dp(i) = \sum_{j=0}^{i} S(i,j) g_{j} \end{align} $$$

where $$$S(i,j)$$$ is stirling number of the second kind.

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

How to solve Question D during contest because I'm not able to think about such transitions between sum[] and dp[] array?

Can anyone explain how to approach these kind of dp questions?

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

For problems like C, I found it's incredibly time-consuming for me to get every +1/-1/0 right, like the indices starting from 0/1, the number of steps required starting from the first cell/before the first cell. Does anybody have suggestions for dealing with this?

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

Is D's time limit too strict? Just adjusting some int/long long representations and whether printing the newline operator can change TLE to AC.

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

    I replaced long long with int everywhere and it didn't give TLE (T_T).

    → Reply