### awoo's blog

By awoo, history, 9 days ago, translation, 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)  Comments (52)
 » My $O(n\sqrt n)$ solution for problem D that works in just 78 ms!
•  » » 8 days ago, # ^ | ← Rev. 2 →   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.
 » C. Robot in a HallwayBetter intuitive approach to the problem C Solution#include "bits/stdc++.h" using namespace std; #define int long long int void whenASC(int l, int r, vector &asc, int &timer) { timer = max(timer + (r - l) + 1, asc[r]); } void whenDSC(int l, int r, vector &dsc, int &timer) { timer = max(timer + (r - l) + 1, dsc[l]); } void solve() { int m; cin >> m; vector row1(m), row2(m); // for row input vector row1M(m), row2M(m); // for ascending prefix sum vector rowM1(m), rowM2(m); // for descending prefix sum int timer = 0; for (int i = 0; i < m; i++) { cin >> row1[i]; if (i > 0) row1M[i] = timer = max(timer + 1, row1[i] + 1); else timer = row1[i]; } timer = 0; for (int i = 0; i < m; i++) { cin >> row2[i]; if (i > 0) row2M[i] = timer = max(timer + 1, row2[i] + 1); else timer = row2M[i] = row2[i] + 1; } timer = 0; int timer1 = 0, timer2 = 0; for (int i = m - 1; i >= 0; i--) { rowM1[i] = timer1 = max(row1[i] + 1, timer1 + 1); rowM2[i] = timer2 = max(row2[i] + 1, timer2 + 1); } timer = 0; whenASC(1, m - 1, row1M, timer); whenDSC(0, m - 1, rowM2, timer); bool flag = true; int ans = timer, temp = 0; timer = 0; for (int i = 0; i < m; i++) { if (flag) { timer = max(timer + 1, row2[i] + 1); if ((i + 1) < m) { temp = timer; whenASC(i + 1, m - 1, row2M, temp); whenDSC(i + 1, m - 1, rowM1, temp); ans = min(ans, temp); timer = max(timer + 1, row2[i + 1] + 1); } } else { timer = max(timer + 1, row1[i] + 1); if ((i + 1) < m) { temp = timer; whenASC(i + 1, m - 1, row1M, temp); whenDSC(i + 1, m - 1, rowM2, temp); ans = min(ans, temp); timer = max(timer + 1, row1[i + 1] + 1); } } flag = !flag; } cout << min(ans, timer) << endl; } signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cout.tie(0); int T = 1; cin >> T; while (T--) { solve(); } return 0; } 
 » 9 days ago, # | ← Rev. 2 →   My approach for problem C, Binary search the waiting time before starting to move. https://codeforces.com/contest/1716/submission/166993379
•  » » can you explain your approach. Thank you
•  » » » 9 days ago, # ^ | ← Rev. 15 →   my ideasorry I don't know how to make a new line... The idea is if I can check whether I can walk through all the grid without getting stuck with a certain starting waiting time.I came out with a greedy approach in O(m).First you go with snake and if it get stuck at the position xcase 1: |1|4|5|?|?| |2|3|x|?|?| then there is only one possible way to work around |1|4|->|->|->| |2|3|<-|<-|<-| case 2: |1|4|x|?|?| |2|3|?|?|?| way to work around |1|<-|<-|<-|<-| |2|->|->|->|->| I renamed some function and deleted some useless code to make it a little bit more readable: https://codeforces.com/contest/1716/submission/167143217
•  » » » » 8 days ago, # ^ | ← Rev. 2 →   redin2022 Awesome approach bro !!I was looking for binary search sol and came across yours.my implementation https://codeforces.com/contest/1716/submission/167190887
•  » » » » Actually whenever there is involvement of some time concept in problem. Generally there will be a way to solve that problem with Binarysearch
•  » » » » awesome !!!
 » 9 days ago, # | ← Rev. 2 →   Solution to 1716F - Bags with Balls using the multinomial theorem SolutionLet $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 $\displaystyle \ \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}$ $\displaystyle =\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]$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 $\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} \left\lceil\frac{m}{2}\right\rceil^cm^{n-c}$ $\displaystyle =\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!$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.
•  » » If it isn't Saucy Jack!
 » 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.
 » video Editorial for Chinese:Bilibili
 » 9 days ago, # | ← Rev. 4 →   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?
•  » » 9 days ago, # ^ | ← Rev. 3 →   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.
•  » » » 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$, $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 1There are 2 possible ways to reach 12 for the given counter example. $(0 \rightarrow 12)$ and $(0 \rightarrow 3 \rightarrow 7 \rightarrow 12)$. Try to print the entire DP table and take a look at entries $dp$ and $dp$ and $dp$. Hints for Bug 2:Your precompute a safe limit for $cnt$ by iterating with the smallest steps. You even multiply it by 3 to handle off by one errors. However, your current implementation results in a value of $cnt$ that is way smaller than the correct count that should be used.
•  » » » » Got it, thanks. But why are $cnt$ steps not enough?
•  » » » » » $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.
•  » » » » » » Oh, my bad, thanks again.
•  » » » 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.
 » 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)
•  » » 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).
•  » » » Thank you so much, I have got it ,your explanation is extremely easy to understannd!
 » Can anyone who used prefix sums for calculating $dp[i][j]$ for D share their code? I'm having trouble implementing it.
•  » » Here is my submissionThere 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.
 » 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 ?
•  » » 9 days ago, # ^ | ← Rev. 2 →   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$.
•  » » » Thank you very much
 » 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.
•  » » 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.
•  » » No, keeping first non-zero element is not necessary. I didn't do that, and had not big time.
 » Does anyone have a testcase that breaks my submission for C? 167164510
•  » » 9 days ago, # ^ | ← Rev. 2 →   Check these: input4 5 0 3 2 8 8 6 4 16 6 11 7 0 15 1 12 12 13 15 2 10 19 18 16 15 6 4 0 3 14 6 7 12 17 7 6 0 5 6 6 14 15 9 7 5 18 13 10 Your submission returns [19, 28, 20, 22], result is [17, 26, 18, 20]
•  » » » wait, shouldn't the top left element in each grid be 0?
•  » » » » fixed it
•  » » » » » Thanks, I had swapped my row variable with my col variable.
 » F can be solved more easily by using Stirling Number and Descending Power.
 » 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: Choose $i$ balls. 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!m^{n-i}\left\lceil{m\over 2}\right\rceil^i \end{aligned}which can be solved in $\mathcal{O}(k^2)$.
•  » » Amazing solution, thanks for the help!
 » How to solve problem C if you can visit the cell more than once??
 » Problem C can also be solved in super ugly way using binary lifting and segment tree.
•  » » can you explain ur idea,Thank You.
•  » » » 8 days ago, # ^ | ← Rev. 2 →   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.
 » Video Solution for Problem C.
 » Can somebody help with this submision, It takes O(m) time and I get time limit. https://codeforces.com/contest/1716/submission/167315560
•  » » 8 days ago, # ^ | ← Rev. 2 →   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)$
•  » » » Thank you!!
 » 7 days ago, # | ← Rev. 5 →   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.
 » Does anyone have a testcase that breaks my submission for C? https://codeforces.cc/contest/1716/submission/167923498
•  » » Take a look at Ticket 16020 from CF Stress for a counter example.
•  » » » thanks
 » 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?