### awoo's blog

By awoo, history, 2 years ago, translation,

1644A - Doors and Keys

Idea: BledDest

Tutorial
Solution (awoo)

1644B - Anti-Fibonacci Permutation

Idea: BledDest

Tutorial
Solution (Neon)

1644C - Increase Subarray Sums

Idea: BledDest

Tutorial
Solution (awoo)

1644D - Cross Coloring

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1644E - Expand the Path

Idea: BledDest

Tutorial
Solution (awoo)

1644F - Basis

Idea: BledDest

Tutorial
• +54

| Write comment?
 » 2 years ago, # |   0 Approach of D problem was great
•  » » 2 years ago, # ^ |   0 yup, somewhat similar to this question's approach( two contests ago) https://codeforces.com/problemset/problem/1638/D
 » 2 years ago, # | ← Rev. 3 →   0 In problem D why we process the queries backward?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 When you process backwards, the query is equivalent to "color all squares in this row and column which are not yet colored". This way, each square will be colored at most once. So now your answer will be $k$ raised to some power(which is actually the number of queries where at least one square was colored).
•  » » » 2 years ago, # ^ |   0 I processed all the queries forwards but ended up getting WA, but I am unable to understand how is there a difference between processing it forwards or backwards? Even if we are doing it forwards then, yes it might be possible that some square is getting colored more than once but in the end I am counting the different number of colors for all the squares so that shouldn't make a difference.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 For each query you want to determine something that happens in the future — in the later queries. So to tell something about query $i$, you have to first process queries $i+1$..$q$. That is exactly the same as going backwards over queries: you first determine the status of the query, then add the information about it to some data structure.
 » 2 years ago, # | ← Rev. 2 →   0 looks legitupd. already fixed
 » 2 years ago, # | ← Rev. 2 →   0 Can anyone help why is this giving me TLE for D 147473308 ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 You have initialized arrays visr and visc of size n and m respectively. Hence your time complexity is O(t*(n+m)) or larger, which in the worst case will be 2*1e9 since there is no limit on sum of m,n over all test cases.
•  » » » 2 years ago, # ^ |   0 Woah! I was facing the same issue. I would've never figured this out without your comment.
 » 2 years ago, # |   +3 Can anyone please explain problem E?
 » 2 years ago, # |   +9 No need for FFT in problem since we need only sum of those Stirling's number and this can be done in O(i): Since S(i,j) = sum(1<=t<=j) C(j,t) * t^i * (-1)^(j+t) / j! we have: S(i,1)+S(i,2)+..+S(i,k) = sum(1<=j<=k,1<=t<=j)( t^i * (-1)^(j-t)/((j-t)! * t!) ). Let d = j-t, then ans = sum(1<=t<=k,0<=d<=k-t)( (t^i/t!)*((-1)^d / d!) ) iterate over t and sum(0<=d<=k-t) ((-1)^d / d!) can be precomputed
•  » » 2 years ago, # ^ | ← Rev. 18 →   +9 I really like this formula. It is elegant and works under any prime modulo. Thank you for sharing it!Here's a more detailed explanation and another way to look at it: Let $n \geq 1$ be a fixed integer.As in tutorial, let $p_i = \frac{(-1)^i}{i!}$ and $q_j = \frac{j^n}{j!}$.Then $S(n, k) = \sum\limits_{i+j=k} p_i \cdot q_j$. Consider a matrix $M$ in which $M_{i, j} = p_i \cdot q_j$ for $0 \leq i, j \leq n$.Then $S(n, k)$ is the sum of entries on the antidiagonal $i+j = k$.Suppose we want to find $S(n, 0) + S(n, 1) + ... S(n, k)$ for some $k$.That is to sum the entries above the antidiagonal $i+j=k$.We can sum these values column by column.For a fixed column $j$, the sum is $q_j \cdot \sum\limits_{i=0}^{k-j} p_i$.Thus, $S(n, 0) + S(n, 1) + ... S(n, k) = \sum\limits_{j=0}^{k} q_j \cdot \sum\limits_{i=0}^{k-j} p_i$. To compute this efficiently, note that $\sum\limits_{i=0}^{k-j} p_i$ is just the sum over a prefix of $p$.My implementation: https://codeforces.com/contest/1644/submission/148117254
•  » » 2 years ago, # ^ | ← Rev. 3 →   +6 I have a question, though. To compute $S(i,1)+S(i,2)+...+S(i,k)$, the formula requires to find $t^i$ over $t=0,1,...,k$. Can this be computed (or precomputed) in $O(i)$?
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +6 Oh I get it.We can use linear sieve to find all primes $p$ and compute $p^i$.For a composite $x = a \cdot b$, compute $x^i$ as $a^i \cdot b^i$.This is $O(k \log i / \log k) = O(i)$
 » 2 years ago, # | ← Rev. 3 →   0 C can be done with 2D DP. My submission is linked below 147347109Note that I only used the custom "getbigger" function instead of the max function because the max function was being annoying for me.
•  » » 22 months ago, # ^ |   0 Could you explain the idea of your code?
 » 2 years ago, # | ← Rev. 4 →   +33 Here are two alternate solutions for F. (Neither one uses any prior knowledge about the Stirling numbers.) Simple no-FFT solutionAs in the main editorial, consider the related problem with only operations of type $G$. Applying several operations of type $G$ to an array is equivalent to applying some permutation to the codomain $\{1 \ldots k\}$ of the array. Since these operations are invertible, and we need to count equivalence classes with respect to this operation, it makes sense to try Burnside's lemma. That gives an explicit formula: $\displaystyle A_n = \frac{1}{k!} \sum_{\sigma \in S_k} \bigg|\{a \in (\{1 \ldots n\} \to \{1 \ldots k\}) : a = \sigma \circ a\}\bigg|$For a given permutation $\sigma \in S_k$, we have that $a = \sigma \circ a$ if and only if $a$ maps $\{1 \ldots n\}$ into the set of fixed points of $\sigma$. So the formula can be simplified to $\displaystyle A_n = \frac{1}{k!} \sum_{i=0}^k \bigg|\{\sigma \in S_k : \left|\{j \in \{1 \ldots k\} : j = \sigma(j)\}\right| = i\}\bigg| \cdot i^n.$Each permutation on $\{1 \ldots k\}$ with exactly $i$ fixed points is uniquely determined by the set of its fixed points, and by the derangement (no-fixpoint-permutation) it induces on the other $k - i$ points in its domain. So, the formula further reduces to $\displaystyle A_n = \frac{1}{k!} \sum_{i=0}^k \binom{k}{i} \cdot D_{k-i} \cdot i^n.$Counting derangements is easy and well-known, so this formula allows direct calculation of $A_i$ in $O(k \log{i})$. But since it is impossible to use more than $i$ different values in an array of length $i$, this can be reduced to $O(i \log{i})$ by just replacing $k$ with $\min(i, k)$.The solution to the original problem in terms of $A_i$ is the same as described in the main editorial.Implementation: 147499995 EGF+ODE solutionThe editorial describes how to solve the problem in terms of $\sum_{j=0}^k S(i, j)$ for various values of $i$. This is another way to compute only that quantity.Let $g_j(t) = \sum_{i=0}^\infty S(i, j) \frac{t^i}{i!}$ as a formal power series. It is the EGF of the $j$-th column of the Stirling numbers. Since multiplication of EGFs corresponds to partitioning, it can be seen that $g_j(t) = \frac{(g_1(t))^j}{j!}$: The $j!$ in the denominator forgets the order in which the sets were used in the partition. It's also easy to see that $g_1(t) = e^t - 1$.To solve the problem, we need to calculate $\sum_{j=0}^k S(i, j)$ for various values of $i$. So, we can consider the function $h(t) = \sum_{j=0}^k g_j(t) = \sum_{j=0}^k \frac{(g_1(t))^j}{j!}$ and calculate its coefficients. There is obviously not enough time to evaluate all terms of this sum; we will have to cancel most of them out and then undo this. One way to achieve this by noticing that $h(t)$ is almost the same as $\exp{(g_1(t))}$. So, $h$ satisfies $h'(t) \approx h(t) \cdot g_1'(t)$. We can calculate the exact value easily and then solve the resulting ODE as follows: Spoiler$\begin{array}{rl} h'(t) & \displaystyle = \sum_{j=0}^k j \cdot \frac{(g_1(t))^{j-1} \cdot g_1'(t)}{j!} \\ & \displaystyle = g_1'(t) \cdot \sum_{j=0}^{k-1} \frac{(g_1(t))^j}{j!} \\ & \displaystyle = g_1'(t) \cdot \left(h(t) - \frac{(g_1(t))^k}{k!}\right) \\\displaystyle h'(t) - g_1'(t) \cdot h(t) & \displaystyle = - \frac{d}{dt} \frac{(g_1(t))^{k+1}}{(k+1)!} \\\displaystyle e^{-g_1(t)} \cdot (h'(t) - g_1'(t) \cdot h(t)) & \displaystyle = - e^{-g_1(t)} \cdot \frac{d}{dt} \frac{(g_1(t))^{k+1}}{(k+1)!} \\\displaystyle e^{-g_1(t)} \cdot h(t) & = \displaystyle e^{-g_1(0)} \cdot h(0) - \int_{s = 0}^t e^{-g_1(s)} \cdot \left(\frac{d}{ds} \frac{(g_1(s))^{k+1}}{(k+1)!}\right) ds \\\displaystyle h(t) & = \displaystyle e^{g_1(t)} \cdot \left( 1 - \int_{s = 0}^t e^{-g_1(s)} \cdot \left(\frac{d}{ds} \frac{(g_1(s))^{k+1}}{(k+1)!}\right) ds \right)\end{array}$This formula can be directly implemented in $O(n \log n)$, at least if you have access to a library/template for the necessary formal power series/generating function operations. Implementation: 147380982
 » 2 years ago, # |   0 In problem D, why is the answer equal to k to the power of valid queries that have at least one cell belong to them? I am unable to understand. Why is "to the power"?
 » 2 years ago, # | ← Rev. 3 →   0 In problem D, why TLE with vector(int) and AC with vector(bool) , time complexity doesn't change. AC code with bool,TLE code with vectorUPD: People already answered this in Announcement for this contest
 » 2 years ago, # |   +8 As for problem F, I think the solution described in the tutorial is in $O(n\sqrt{n}\log n)$ time complexity, because we have $O(\sqrt{n})$ $\lceil\frac{n}{i}\rceil$ s, and calculating each of them takes $O(n\log n)$. But the solution of F says it takes $O(n\log^2n)$, am I wrong or the tutorial made a mistake? Can anyone help me?
•  » » 2 years ago, # ^ |   0 The polynomial describing $A_i$ has $\min(i, k) + 1$ terms, so the complexity of calculating $A_i$ is $O(i \log i)$ and the total complexity is $\sum \limits_{i = 1}^n O(\frac n i \log \frac n i) = O(n \log^2 n)$.
•  » » » 2 years ago, # ^ |   0 Oh, I see! Thanks!
 » 2 years ago, # | ← Rev. 3 →   0 I am doing question D the same way, but getting a wrong answer. I have used a set to store the rows and columns and then proceed with the maximum size among the two. Can anyone help me out, please? Link for my solution: https://codeforces.com/contest/1644/submission/155271519
•  » » 2 years ago, # ^ |   +1 Failing testcase: Ticket 6147
 » 23 months ago, # |   0 My submission for problem D. https://codeforces.com/contest/1644/submission/157867234 Anybody please tell me where and why the code fails