We observe that for $a_1$ to be turned to $0$, we need $a_1$ to be a multiple of $a_0$. If this is not the case then the answer is no. Else we can make $a_1=a_0$, so we can inductively repeat the argument. Hence we only need to check that $a_i$ is a multiple of $a_0$ for $1\leq i<n$.
We observe that $\gcd(i, a_i)\in\{1,...,i\}$. Then we must have $\gcd(i,a_i)=i$. Suppose not, then $\gcd(i-1,a_{i-1})$ has $i-2$ possible values, $\gcd(i-2, a_{i-2})$ has $i-3$ possible values, ..., $\gcd(1,a_1)$ will have no possible values. This means that $a_i$ must be any multiple of $i$ in the range $[l,r]$, for $1\leq i\leq n$.
We observe that if we can take $x$ tests, then we can take $x-1$ tests. Therefore, we can do a binary search. How can we check if we can take $\geq x$ tests? We iterate through $a$ maintaining the current IQ $k$ and current tests taken $c$. If $k\geq a[i]$, then it definitely won't hurt to take test $i$. If $k<a[i]$, then we should only take the test $i$ if we have $n-i\leq x-curr$, i.e. the number of tests remaining is at most the number of tests needed to hit our minimum target of $x$ tests taken. The intuition is that taking such a test earlier decreases our IQ, so it may prevent us from taking a test we could otherwise have taken.
I did not get very far on this problem. I will update this section later once/if I solve it.
No comments:
Post a Comment