PROBLEM LINK:
[Practice][111]
[Contest][222]
Author: [Yurii Rebryk][4444]
Tester: [Istvan Nagy][5555]
Editorialist: [Xellos][6666]
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Computing binomial coefficients, polynomial multiplication (fast Fourier Transform, Karatsuba’s algorithm).
PROBLEM:
There are “tetrahedron” objects specified by their sizes. Each of them can be destroyed in multiple ways (according to complicated rules) or left unchanged. For given N,K, there are tetrahedrons with sizes 1..N and you should find the number of ways to destroy at least K tetrahedrons out of those N.
QUICK EXPLANATION:
Find the number of ways to destroy each tetrahedron. The answer is a coefficient in a polynomial found by multiplying polynomials assigned to the tetrahedrons.
EXPLANATION:
Note: all ways to destroy things are computed modulo the given MOD. For clarity, we won’t be writing \% MOD everywhere.
This problem has 2 parts: counting the number of ways dest(k) to destroy a tetrahedron of size k (for each k \le N) and suitably combining them to find the answers. Let’s look at both parts in order.
We can bruteforce or infer from the sample that dest(1)=9.
For k > 1, there are 3 segments incident on each vertex independently; we may erase at most one of them. Therefore, the number of ways to destroy a of those segments is {4\choose a}3^a - we choose the vertices that should have one erased incident segment and then one of the 3 segments to erase for each of those vertices. Let’s bruteforce all possible a.
There are 6k-12 segments left and we must erase at least k-a of them (without any other conditions). There are S(6k-12,k-a)=\sum_{j=k-a}^{6k-12}{6k-12\choose j} ways to do that. We’re able to compute individual binomial coefficients quickly (see below), but computing this sum is much harder.
Let’s make some reductions first: we only need S(6k-12,k) - the rest can be computed by adding bin. coefficients, and let’s instead try to compute bad(k)=\sum_{j=0}^{k+1}{6k\choose j} - it turns out that $S(6k-12,k)=2^{6k-12}-\sum_{j=0}^{k-1}{6(k-2)\choose j}=
=2^{6k-12}-bad(k-2)$. Then, we have a recurrence for $bad(k)$ using Vandermonde's identity ($k \ge 1$):
bad(k)=\sum_{j=0}^{k+1}{6k\choose j} = \sum_{j=0}^{k+1}\sum_{b=0}^6 {6k-6\choose j-b}=\sum_{b=0}^6 \sum_{j=0}^{k+1-b}{6(k-1)\choose j},.
The inner sum for $b=1$ is $bad(k-1)$. For any other $b$, it can be computed by adding/subtracting bin. coef., which can be done in $O(1)$. When we know all inner sums, the outer sum can be computed in $O(1)$ again; we just need to precompute $6\choose b$ and $4\choose a$ and we can find all $bad(k)$ for $k \le N$ in $O(N)$ time.
Of course, the values of $dest(k)$ should be computed only once before processing the queries.
- Finding the answers
We'll count $Sdest(N,K)$ - the number of ways to keep $K$ tetrahedrons out of the first $N$. First, let's make a dynamic programming solution. We know $Sdest(N-1,K)$; then,
Sdest(N,K)=Sdest(N-1,K-1)+Sdest(N-1,K)\cdot dest(N),.
The answer is $\sum_{j=0}^{N-K} Sdest(N,j)$ (if at least $K$ are destroyed, at most $N-K$ are kept).
This is slow, but it can be improved a lot. The trick is writing the DP formula compactly as a convolution or product of polynomials: $P_N(x)=p_N(x)\cdot P_{N-1}(x)$, where $p_N=x+dest(N)$ and the coefficient of $x^k$ in $P_N$ is $Sdest(N,K)$. Our problem reduces to multiplying $N$ polynomials of degree 1.
Here's the asymptotically fastest way: divide and conquer, with FFT merging. The product of some polynomials can be split into 2 products of approximately equal degrees $\prod_{j=L}^R P_j = \left(\sum_{j=L}^{(L+R)/2} P_j\right)\left(\sum_{j=(L+R)/2+1}^R P_j\right)$; each of those two products is computed recursively and they're multiplied together by FFT. Since we multiply polynomials of degree around $N/2^d$ in any recursive call with depth $d$, there are $O(\log{N})$ depths with $O(N\log{N})$ total time of multiplications at each depth and the total time is $O(N\log^2{N})$ per test case. Win.
However, FFT is imprecise and rather slow (we can use Karatsuba, which is precise, but even slower), so why not make something simple that makes use of small $N$? And small degrees of $p_N(x)$. Basically, something like sqrt-decomposition: if we choose a number $S$ and precompute $P_{kS}(x)$ for all $k$, then the above mentioned DP lets us compute $P_N(x)$ in $O(NS)$ time per test case from $P_{N-N\%S}(x)$. Then, with $S\doteq500$, this is pretty fast (DP has a good constant), so we can just focus on computing $P_{kS}$.
We're multiplying blocks of $S$ polynomials, so we can multiply all polynomials in each block by the same brute force / DP to get polynomials $R_j(x)$; $P_{kS}=\prod_{j=1}^k R_j$ is a "prefix product" of them. The most obvious way to find them is by simply multiplying $R_{j+1}$ and $P_{jS}$ sequentially. FFT isn't suitable for multiplying polynomials of significantly different degrees, but Karatsuba can be modified to do it pretty quickly. This is nearly or fully enough to pass.
We don't need all $P_{kS}$, though, just $T$ of them. What lets us compute products of some subsegments/subintervals when we don't have division (polynomial multiplication behaves a lot like max/min in that sense - we can't find $a$ from $\text{min}(a,b)$ and $b$)? Segment trees - or, in the case without updates, something like range minimum query. We'll split the array of polynomials $\texttt{R}[j]$ into blocks of size $2^p$ for all meaningful $p$ and compute the product of $\texttt{R}[j]$ in each block as a product of two blocks of size $2^{p-1}$ ($p=0$ is trivial). When we want the product of some prefix for $j \le N$, we can always keep cutting off the last 1 in the binary representation of $N$, which corresponds to cutting off one of the precomputed blocks from the subarray $\texttt{R}[1..N]$. We can then just multiply the polynomials of those blocks, for example with Karatsuba's algorithm.
The time complexity analysis is quite difficult here. Karatsuba can multiply polynomials of size $N$ in time $O(N^{\log_2 3})$. In the precomputation, we multiply polynomials of degrees $2^p S$ for blocks of size $2^p$ around $\frac{N}{2^p S}$ times and for each query, $O(\log{N})$ polynomials with degrees $N/2^p$ for several (distinct) $p$; when we sum up the resulting geometric series, we find the time of precomputation to be around $O(N^{\log_2 3}S^{\log_2 3 -1})$ and the time per query around $O(N^{\log_2 3})$. Summing up everything, the total time is $O(N^{\log_2 3}S^{\log_2 3 -1}+TN^{\log_2 3}+TNS+MOD\log{MOD})$ (the last term comes from several precomputations).
- Counting binomial coefficients
We'll take $N\choose K$ to be $0$ for $N < K$ or $K < 0$.
The modulo used here is a prime. We can precompute modular inverses of all numbers in the range $[1,MOD)$. We'll also precompute factorials and then, we're able to compute ${N\choose K }= \frac{N!}{K!(N-K)!}$ by simple multiplication. You may read more about it [here][9].
However, it can happen that $N$ in such a coefficient is larger than the modulo. Since $K$ will always be smaller than $MOD$ and $N < MOD^2$, we can still use a modular inverse of $K!$; the other two factorials must be modified by "cutting out" $MOD$ as their divisor when precomputing them - for example, $(2\cdot MOD)!=(2\cdot MOD-1)!\cdot2$. Then, we just need to check if the product $N(N-1)..(N-K+1)$ contains a number divisible by $MOD$ - if $N-N\%MOD > N-K$; in that case, the bin. coefficient is $0 \% MOD$.
### AUTHOR'S AND TESTER'S SOLUTIONS:
The author's solution can be found [here][333].
The tester's solution can be found [here][444].
The editorialist's solution can be found [here][555].
### RELATED PROBLEMS:
[a recent problem which includes faster polynomial multiplication][8]
[111]: http://www.codechef.com/problems/REBTET
[222]: http://www.codechef.com/NOV15/problems/REBTET
[333]: https://www.codechef.com/download/Solutions/NOV15/Setter/REBTET.cpp
[444]: https://www.codechef.com/download/Solutions/NOV15/Tester/REBTET.cpp
[555]: https://www.codechef.com/download/Solutions/NOV15/Editorialist/REBTET.cpp
[4444]: http://www.codechef.com/users/rebryk
[5555]: http://www.codechef.com/users/iscsi
[6666]: http://www.codechef.com/users/xellos0
[9]: https://discuss.codechef.com/questions/3869/best-known-algos-for-calculating-ncr-m
[8]: https://www.codechef.com/problems/CLOWAY
