Contest: ICO 2018 Practice Contest 1 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 bruteforce for subtask 1. Subtask 2 requires us to apply a little more math (combinatorics). 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[ind1][Y][numofXs]$ for $Y = 1$ to $100$, and $Y$ coprime to $curr$. This is because, for the we can simply append $curr$ to all the arrays built till $ind1$. If $curr = X$, the $numofXs$ has increased by 1 so we take the summation of $dp[ind1][y][numofXs1]$ 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.
This question is marked "community wiki".
asked 13 Oct '17, 23:37

can anyone explain me editorial of sub task 3???????????????? answered 15 Oct '17, 12:20

Weird. My O(N^4 . logN) solution gave TLE, but O(N^4) gave AC, after precomputation. Precomputation was probably necessary after all. answered 23 Oct '17, 12:46
