×

# 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

This question is marked "community wiki".

2.4k723
accept rate: 20%

19.8k350498541

 0 can anyone explain me editorial of sub task 3???????????????? answered 15 Oct '17, 12:20 12●1 accept rate: 0%
 0 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. answered 23 Oct '17, 12:46 3★sinbycos 33●2 accept rate: 0% can you please explain your approach ? (23 Oct '17, 18:59) pk3012★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852

question asked: 13 Oct '17, 23:37

question was seen: 483 times

last updated: 23 Oct '17, 18:59