Hi in problem C today the hard part is not the bezout it's the fact the when the linear combination might have some negative numbers it's still possible to apply it in our problem
I asked the author and he told me that:
if you add a or b to all the elements except ci , it is the same as decreasing a or b from ci . So it doesn't matter if X,Y are negative.
but I'm still confused like I would never in 100 years come up with this observation. so I want to ask you guys how did you knew that the negative combination is ok intuitively ?
Here
The thing is that in the array of n integers, decreasing $$$a_i$$$ by $$$x$$$ is the same as increasing all values exept $$$a_i$$$ by $$$x$$$. We will have different arrays, but the range will not change. The solution is based on this observation.
actually linearity doesn't really matter, the only thing that matter is that after one operation,
c[i]is always congruent toc[i] mod __gcd(x, y). so all you need to check is arrange the array in such a way (whether replacec[i]withc[i] mod __gcd(x, y)orc[i] mod __gcd(x, y) + __gcd(x, y)to minimize the maximum difference.sorry for this silly question
but can you tell me intuitively why we need to whether replace c[i] with c[i] mod __gcd(x, y) or c[i] mod __gcd(x, y) + __gcd(x, y)
like why we need to brute force on the maximum element ? I know because we might find a better answer but I can't visualize it in my mind
take x = 10, y = 5, c = {2, 4, 5, 9, 10} for example. first we have array c modulo __gcd(x, y) (sorted) equals to {0, 0, 2, 4, 4}, maxdiff is 4. if we choose 2 first elements and replace them with c[i] % __gcd(x, y) + __gcd(x, y), then the array c (sorted) equals to {2, 4, 4, 5, 5}, maxdiff is 3. you can do so by rotating the array, or using sliding window algorithm.