SuperMo's blog

problem C today help!
By SuperMo, history, 4 months ago, In English

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 ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Here

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

actually linearity doesn't really matter, the only thing that matter is that after one operation, c[i] is always congruent to c[i] mod __gcd(x, y). so all you need to check is arrange the array in such a way (whether replace c[i] with c[i] mod __gcd(x, y) or c[i] mod __gcd(x, y) + __gcd(x, y) to minimize the maximum difference.

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply