Блог пользователя awoo

Автор awoo, история, 2 года назад, По-русски

1716A - 2-3 Moves

Идея: vovuh

Разбор
Решение (vovuh)

1716B - Permutation Chain

Идея: BledDest

Разбор
Решение (awoo)

1716C - Robot in a Hallway

Идея: BledDest

Разбор
Решение (awoo)

1716D - Chip Move

Идея: BledDest

Разбор
Решение (Neon)

1716E - Swap and Maximum Block

Идея: BledDest

Разбор
Решение (BledDest)

1716F - Bags with Balls

Идея: BledDest

Разбор
Решение (BledDest)
  • Проголосовать: нравится
  • +172
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    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.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 3   Проголосовать: нравится +40 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

video Editorial for Chinese:

Bilibili

»
2 года назад, # |
Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

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?

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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:
      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          $$$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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
2 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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)

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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).

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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$$$.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Check these:

    input

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

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится

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)$$$.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain ur idea,Thank You.

    • »
      »
      »
      2 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Video Solution for Problem C.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

[submission:1716C] Can somebody help with this submision, It takes O(m) time and again says time limit.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня решена задача F, однако я в корне по понимаю второе предложение в ее разборе. Почему вдруг F^k можно биективно отразить в такие наборы, как это вообще связано логически? Объясните, пожалуйста.

немного рассуждений: Если посмотреть на любой набор из F нечетных и n — F четных, то таких (i1,...,ik) последовательностей сгенерируется F*F*F...*F = F^k, это вроде да, но с другой стороны, другой набор из F нечетных сгенерирует хоть и столько же наборов, но при этом могут быть совпадения. Например k = 4, и наборы (индексов) при F = 2: {1, 2} и {1, 3}. Первый набор {1, 2} сгенерирует (1, 1, 1, 1) и много других, и набор {1, 3} тоже сгенерирует (1, 1, 1, 1), поэтому у нас уже вклады размываются и это не будет F^k + F^k разных последовательностей (i1, ..., ik) на два этих набора, не сходится, значит неверно трактую

Объясните, пожалуйста, что это вообще значит и откуда берется, это же какая-то крайне запутаная вещь имхо

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.