PROBLEM LINK:
Author: Bogdan Ciobanu DIFFICULTY:Hard PREREQUISITES:Number Theoretic Transform, Combinatorics PROBLEM:You are given an array of length $N$. Initially, each element of array is painted with color $0$. You are given $K$ turns. In $i^{th}$ turn you can paint any nonempty subarray with color $i$, while overwriting any color already present. You need to answer how many distinct colorings of the final array are possible modulo $163577857$. EXPLANATION:Lets try to find the expression for $F(K,N)$. Here $F(K,N)$ will represent the answer to our given problem. For doing the same, we will iterate over number of visible colors at the end. Say, number of visible colors are $r$ in final array. Then, the number of ways of choosing $r$ colors from $K$ given colors will be $ \binom {K1}{r1} $, because you need to select only $r1$ colors from $K1$ colors, as $K^{th}$ color will always be visible. Hence, we can write: where, $e(r,N)$ represents number of ways in which $r$ colors can be visible finally in array of length $N$. Finding an expression for $e(r,N)$ Lets try to think in reverse manner. Say $r^{th}$ color occupy an interval of length $x_1$. Number of ways of doing the same will be $Nx_1+1$. Now, say $(r1)^{th}$ color occupy an interval of length $x_2$ in remaining $Nx_1$ places. You can notice that $x_1$ wont affect $x_2$. Basically, you can write: Try to expand the formula more and you will end up here, If you observe it closely, you will find that it is nothing but sum of product of numbers taken $r$ at a time from the set $ \{ 1,2,3,....N \}$. Hence, we can say that $e(r,N)$ is coefficient of $x^{nr}$ in polynomial $P_N(x)$ where: All we are left is now computing the polynomial $P_N(x)$ and we will be done. Computation of $P_N(x)$ subtask #1 and #2One can compute the product naively using brute force in order to pass these subtasks in $O(N^2)$. subtask #3This subtask can be passed with an $O(nlog^2n)$ solution using divide and conquer, along with NTT. The task here is to compute the product of $n$ polynomials of the form $(x+i)$. Let $A(x)$ be the product of the first half of $(x+i)$'s, and $B(x)$ be the product of rest $(x+i)$'s. We compute $A(x)$ and $B(x)$ recursively, and then compute $A(x)⋅B(x)$ by NTT. The time complexity is $T(n)=2T(n/2)+O(nlogn)$, so $T(n)=O(nlog^2n)$. This idea is illustrated by the following pseudocode:
subtask #4We will try to devise an $O(nlogn)$ solution because $O(nlog^2n)$ wont pass here because of strict Time Limit. Informal way down to the solution Let's take a closer look at time complexity of divide and conquer solution: Since merge here is $nlogn$, $T(n)$ comes out to be $O(nlog^2n)$. But what if we can somehow compute $right_{half}$ using $left_{half}$ in $O(merge)$ too. This way the recurrence relation will be: $\Rightarrow T(n) = T(n/2) + O(nlogn)$ which eventually results in $T(n) = O(nlogn)$ with some constant factor. So we are left with computing $right_{half}$ using $left_{half}$. Formally, We can compute $P_{2N}(x)$ using the identity: Main problem here is, finding $P_{N}(x+N)$ when $P_{N}(x)$ is known to you. Say, $\Rightarrow P_N(x+N) = \sum_{i=0}^N h_i.x^i$ where, $\Rightarrow h_i = \frac{1}{i!} \sum \limits_{j=i}^N (c_j.j!)\left (\frac{n^{ji}}{(ji)!} \right )$ $\Rightarrow h_i = \frac{1}{i!} . ($coefficient of $x^{Ni}$ in $A(x)B(x))$ Now we have an algorithm to find $P_N(x+N)$ in $O(NlogN)$ using convolution of $A(x)$ and $B(x)$ when $P_N(x)$ is known to us. Now let's take a look at the pseudocode to solve this subtask:
Only thing, that is left out is how to multiply two polynomials modulo 163577857. Notice that $163577857 = 39.2^{22} + 1$, which is NTT friendly. This reduces pain for us. For those who are not familiar with NTT may refer this link. OptimizationsWhen you implement this algorithm naively, you might notice that it takes too much time to process an input for $N=10^6$. Unfortunately, the constant hidden in the $O$ notation seems to be too high! The time complexity is correct, so we will need additional tricks to cut down this constant and be able to squeeze the solution into the time limit. Here are a few optimizations:
Alternate SolutionThis solution was not intended. However, $40\%$ of the solvers used this trick. The idea is to use the solution for subtask #3 to pass subtask #4 too. A naive implementation of subtask #3 for all the test cases leads to $O(T.N.log^2N)$ solution. If we can remove the $T$ part and do some optimization we will be able to pass subtask #4 too. How to remove the $T$ part? Let's say that value of $N$ over different test cases is represented by $N_1, N_2, N_3, ..., N_T$. We will take all input at once and sort the values of $N$ in ascending order. Let $n_i's$ represent the sorted sequence of $N$ now. We will now call MUL(1,$n_1$), MUL($n_1+1$,$n_2$), .... , MUL($n_{T1}+1$,$n_T$). Now, we can use prefix multiplication of these terms to find the answer for all test cases. The time complexity of the same can be found approximately using following sum: Time Complexity:$O(T.N.logN)$ or $O(N.log^2N)$ AUTHOR'S AND TESTER'S SOLUTIONS
This question is marked "community wiki".
asked 02 Mar, 22:32

Just some tricks to optimize mod operations, instead of actually writing c = (ab)%MOD where MOD = 163577857 , one should directly write c = (ab)%163577857 , this is because for the MOD of the form n2^k+1, compiler automatically optimizes the MOD for constant values in terms of some multiplications and additions. Also when you have a operation of this kind = c = (ab+MOD)%MOD one can optimize it as c = (ab) ; if(c<0) c+=MOD , but one can have even better version of this as c = (ab) , c = (cMOD(c>>63)) ,this basically takes only 4 primitive operations, and it does work better in many cases. Similar analogue exists for the operation c = (a+b)%MOD as c = (a+b) , if(c>=MOD) c=MOD , can be also done by c = (a+bMOD) , c = (cMOD*(c>>63)), although this takes 5 primitive operations and may not always give a speedup. Note : I assume a,b,c are of long datatype in Java, long long int datatype in C++ answered 13 Mar, 18:46

Can anyone please help me find where this solution fails? (for 60 points). I am doing exactly what is stated in editorial for $O(N*log^2 N)$ solution, but getting WA (was doing this even during contest, but was getting WA even there.) answered 14 Mar, 16:02
1
Found Bug: Overflow in NTT part :(
(15 Mar, 08:43)
1
Have the test cases been updated after the contest to prevent Alternate solution submissions??? My submission is continuously getting TLE for last file only.
(16 Mar, 16:25)

Actually we can prove the stirling numbers identity via differentiation too. I was playing with differentiating generating functions, and then I got a pattern that lead me to stirling numbers of the first kind. answered 12 Mar, 17:45

Can anyone prove how the coefficient of x^(nr) in (x+1)(x+2)(x+3)....(x+n) is the sum of product of nos taken r at a time from the set {1,2,3,4,5....N}. Your answer will be appreciated :D answered 14 Mar, 10:42
Think of it this way. When you evaluate the polynomial product, you make $n$ choices from each of the $n$ terms of the form $(x + k)$. From a single term, you choose either $x$ or the number. You then multiply your choices together and get a part of the final product. If you make all possible $2^n$ selections and add them together, you get the final result.
(15 Mar, 22:57)
Now out of these $n$ terms if you choose the number $r$ times, the rest $nr$ times you must choose $x$. In this case the result of multiplication is the product of those $r$ numbers you chose, times $x^{nr}$. So you can see that all possible selections with $r$ numbers contribute to the coefficient of $x^{nr}$ in the final result. You can also take a look at Vieta's formulas, a more general rule.
(15 Mar, 23:21)
Starting from the expression for $e(r,N)$ \begin{equation} e(r,N)=\sum_{x=1}^{Nr+1}(Nx+1) \times e(r1,Nx) \end{equation} write down expression for $e(r,N+1)$, and manipulate \begin{equation} e(r,N+1) = \sum_{x=1}^{(N+1)r+1}((N+1)x+1) \times e(r1,N+1x) \end{equation} \begin{equation} ~~ = (N+1)e(r1,N)+\sum_{x=2}^{(N+1)r+1}((N+1)x+1) \times e(r1,N+1x) \end{equation} \begin{equation} ~~ = (N+1)e(r1,N)+\sum_{x=1}^{(N+1)r}((N+1)x) \times e(r1,Nx) \end{equation} \begin{equation} ~~ = (N+1)e(r1,N)+e(r,N) \end{equation} From here one can build a proof by induction argument.
(16 Mar, 03:32)

When you got the formula for e(r, N), at that point one can directly notice that it resembles to formula for Stirling Numbers of First Kind.
Cool method to get $P(x+N)$ from $P(x)$. Thanks for the problem, learnt something new :)