Is there any proof to show that k is always small?
7 Likes
I just thought the max value of k would be 2
Please prove your observations. I would understand that we should prove it ourselves, but this is an editorial after all. I think it should be included…
14 Likes
does an observation need a proof? I would certainly enjoy having one, but I have no clue how hard that proof is. Since the constraints are small (N <= 10⁴), you can find out the maxK pretty fast with a few lines of code.
public static void getMaxK() {
int maxK = 0;
for (int i = 1; i <= 1e4; i++) {
int curMaxK = 0;
int curK = 0;
for (int j = 1; j <= 1e4; j++) {
if(gcd (i, j) == 1) curK = 0;
else curK++;
curMaxK = max(curMaxK, curK);
}
maxK = max(maxK, curMaxK);
}
out.println(maxK);
}
Output: 13
Runtime: 3819ms (for those wondering)
1 Like
i think you should loop till 1e6 as the editorialist is taking about |Ai-Bi| and Ai range from 1 to 1e6
4 Likes
my bad yes. Well then it would probably not be a trivial observation anymore.
1 Like
It turns out that k = 2 works lol (submission) and its quite far away from 20, so are you not sure about the proof either?
I did the same dp in contest but I didn’t submit it because I expected k to be around 30-40 and that would overflow and mess up the mod
2 Likes
my solution is giving tle for k=20 but wa for 16
CodeChef: Practical coding for everyone wa
CodeChef: Practical coding for everyone tle
Proof k=20 works (actually works for k\geq 3 as well), we will prove that there are no x,y\leq 10^6 such that we can’t make their gcd 1 with such moves:
Lemma
Firstly notice that \gcd(X,Y) > 1 \implies \exists p\in\text{Primes}:\, p|X \text{ and } p|Y.
We define those p as representative.
Some Definitions
Now for i,j\in[-k,k] and for some x,y\leq 10^6\, there are, not necessarily distinct,
C = (2k+1)^2 values \gcd(x+i,\, y + j).
We suppose that all of them are >1, so each of them has a representative prime, let P be the multiset holding such primes and c_x the be number of times x appears in P.
Notice that c_p \leq \left \lceil \frac{2k+1}{p}\right \rceil^2.
Proof for k = 20
We can compute the maximum values of c_x
(c_2,c_3,c_5,c_7,c_{11},c_{13},c_{17}, c_{19},c_{23}, c_{29}, c_{31}, c_{37}, c_{41}, \dots) =
(441, 196, 81, 36, 16, 16, 9, 9, 4, 4, 4, 4, 1,\dots)
So there are at least 12 + C - (441 + 196+\cdots+4) = 873 distinct primes each of which divides one of [x-k,x+k]. So by the pigeonhole \exist x'\in[x-k,x+k]: \lceil\frac{873}{2k+1}\rceil=22 distinct primes divide it , let them be q_1\dots q_{22} so now x+k\geq x' \geq q_1\cdots q_{22}\geq 2^{22} > 10^6+k \implies x>10^6 which is a contradiction, we are now done.
5 Likes
in 3rd sample test case
if array b=[9 16 7 19 10 7 1]
then cost would 7 but how 8?
I got ac just by initializing my ans with LLONG_MAX rather than 1e18 .somebody please explain this behaviour .
Hi! Great job! I solved this problem during the contest, but I didn’t come up with a proof. I am amazed at the negligence of the authors who did not bother to provide proof in the analysis. Thanks a lot for the explanation!
2 Likes
Hi! i think your proof just proves that we can make 2 numbers have gcd = 1 with k = 2 but how do we arrive at the conclusion that abs(Ai-Bi) <= k.
let’s say that there are 3 numbers A1, A2, A3. now your proof said that we can make gcd(A1, A2) =1 for k = 2 but let’s say there is only one pair of numbers (A1, A2) which have gcd = 1 with changes <= k now for pair (A2, A3) we again apply the theorem but how do we guarantee that there will be a pair of (A2, A3) with gcd=1 and changes <= k with same A2 as the (A1, A2) pair.
1 Like
I think there is a mistake in your explanation: why you divide 17 by 2? In proof for k = 20 you divided 873 by 41 (41 = 2 * k + 1). And in proof for k = 2 you divide 17 by 2 but 2 != 2 * k + 1. So why do you divide by 2, not 5?
Submission
So i did this, with k=2 and without even taking modulo and i get AC for this. Taking modulo is not even needed as max will be 4e4. No proof by editorialist though, so disappointed with this contest.
1 Like
Because it was, in fact, wrong. k=3 barely worked and for a second I thought k=2 also works. I deleted that part of the proof so I don’t confuse anybody
1 Like
Editorial doesn’t contain proof. Didn’t expect this from codechef.
What is the proof that k would be less than 20, what if it becomes of the order 10^3 or more?
I think the complexity is (n * k * k * log(max(a[i] + k))
My Explanation for k=20
Ai and Bi are two numbers. These two numbers must have gcd == 1.
1st we assume that Ai and Bi have gcd != 1. That means Ai and Bi have something in common. if we add 1 to Bi and if still Ai and Bi have gcd!=1.
Similarly,
Ai and Bi → gcd!=1
Ai and Bi +1-> gcd!=1
…
Ai and Bi+20 → gcd!=1
Maximum Output from this observation is that
Ai can be max = (Bi) * (Bi+1) * (Bi*2) * … * (Bi+20);
minimum Ai can be if we take Bi=0;
then ignore the values that are not prime that are Bi+4 (that will be 4 not prime)
So Ai can be minimum = 1 * 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 = 9,699,690
when Bi is 0
So Ai goes above the given limit that is 1,000,000
So between 20 numbers Bi to Bi+20 there will at least be 1 number whose gcd with Ai will be 1.