TIDUAFT - Editorial

Contest: ICO 2018 Practice Contest 1

Author: Udit Sanghi

Tester: Shashwat Goel

Editorialist: Shashwat Goel

Problem Statement

Given 3 numbers N,X and K you need to tell the number of ways of making an array of size N with all numbers being positive \leq 100 with number X appearing exactly K times where every adjacent pair of integers are coprime.

Explanation

We can straight away write a brute-force for subtask 1.

Notice that for each element, the next element must be a number coprime to it, so if we can make a list of all coprimes to all numbers less than 100, we can use this list to find the next number every time.
We do this by running an O(N^2) Precomputation using O(N^2) memory to store a list of numbers coprime to i in cop[i].
Now, we run N loops. The first loop fixes the first element say A. The second loop iterates over the elements coprime to A, say B. The third loops iterates over the elements coprime to C, and similarly for n=4. This way we can generate all possible 4 element combinations, we just need to count the number of combinations in which the value X came exactly K times.

This is sufficient for subtask 1.

Subtask 2 requires us to apply a little more math (combinatorics).

Since \dfrac{N+1}{2} positions are filled and N is odd, we can only do this by filling X in alternating positions. This leaves \dfrac{N-1}{2} positions empty. In each of these positions, we can fill any of the numbers coprime to X and all conditions will be satisfied. So we have to fill \dfrac{N-1}{2} positions with cop[x].size() elements, the possibilities of this are cop[x].size()^\frac{N-1}{2} giving us an O(N) [Naive] and O(LogN) [using fast exponentiation]

Both pass, so you can do any of the above.

Now comes the real part of the question, Subtask 3.
We are going to use dynamic programming to solve the problem. Let the dp states be, dp[ind][curr][numofxs], that is, from index 0 to ind, how many ways to select numofXs ‘X’ and keep the value of arr[ind] as curr. One can notice that if curr is not equal to X, this is equal to the sum of all dp[ind-1][Y][numofXs] for Y = 1 to 100, and Y co-prime to curr. This is because, for the we can simply append curr to all the arrays built till ind-1. If curr = X, the numofXs has increased by 1 so we take the summation of dp[ind-1][y][numofXs-1] for Y = 1 to 100 and Y coprime to curr (or X for this case). We could precompute a coprime boolean array in N^2 to store which pairs are coprime, but this only reduces the complexity by log(N) and is not necessary to pass the constraints.

Author Soln: here

Tester Soln: here

3 Likes

can anyone explain me editorial of sub task 3???

Weird. My O(N^4 . logN) solution gave TLE, but O(N^4) gave AC, after pre-computation. Pre-computation was probably necessary after all.

can you please explain your approach ?