Problem Link — https://mirror.codeforces.com/contest/2085/problem/E
Code — https://mirror.codeforces.com/contest/2085/submission/312319353
Approach and Proof-
For the moment, consider that B isn't shuffled. In that case, a[i]%k = b[i].
So b[i] is just the remainder when a[i] is divided by k. From factor Theorem we know, dividend = divisor × quotient + remainder.
Say the quotient is q. Then rewriting this using factor Theorem-
a[i] = k*q + b[i]
So a[i] — b[i] = k*q.
Now let's do it for all elements ie,
a[1] — b[1] = k*q1 a[2] — b[2] = k*q2 ...... a[n] — b[n] = k*qn
Adding them all, we get
Sum of all of A — sum of all of B = k*(q1+q2+...qn)
Now in the start we assumed an unshuffled B. But this holds true for even shuffled B because no matter what the order the sum remains the sum.
Observation from this- No matter what the order of B, the difference of sums of both A and B must be a multiple of k. So, we can only have such a k which a divisor of (sum of A — sum of B). Let's call that difference of sums d.
Now we can consider 3 cases-
- If d = 0, then B must be a Permutation of A. Proof — notice that an element of B can never be greater than the corresponding element of A it got generated from because x%y must be less than x. So d = 0, every element of B must be equal to its generator. So B must be a permutation of A. So, we can always have max(A) + 1 as an answer because x%y for any x < y gives x.
- If d = 1, all elements of b must be 0. This is because the only divisor of 1 is 1 itself so we only have k = 1 as a valid answer and any number % 1 = 0. So if there is any non zero element in B and is -1 else it is 1.
- In every other case consider all the divisors of d as a valid answer and make a frequency map of a[i]%(divisor of d). If frequency map of b = this new freq map only then it's a valid k. This is literally brute force.
So what part of my proof is wrong which is causing the WA verdict?
