1478 Div2C Nezzar and Symmetric Array [Thinking Explained and Visualized]

Правка en1, от rav.gupta, 2021-01-31 23:26:13

Hi,

I wanted to explain you the method I used to upsolve the problem of [problem:https://codeforces.net/contest/1478/problem/C].

  1. First of all they define a new kind of thing called symmetric array A[] of where there are n distinct positive integers and n additive inverse (multiplied by -1) of same integers. Whenever a problem define a new property or a thing , I find it better to make some specific and general example of it i.e A = {1, 2, 3, 4, -1, -2, -3, -4} or {a, b, c, d, -a, -b, -c, -d}

  2. Second thing they define are D[] where each i-th term is the sum of absolute differences between a[i] to all other possible a[j], j \epsilon [1,n]. For ex: n = 3, D[0] = |a[0] - a[0]| + |a[0] - (-a[0])| + |a[0] - a[1]| + |a[0] - (-a[1])| + |a[0] - a[2]| + |a[0] - (-a[2])| Similarly for all other D[1], D[2], D[3], D[4], D[5]. It is easy to see that this D value would be same for a[i] and -a[i].

Question is to tell whether its a valid D[] or not ?

  1. I don't like absolute function but it has this property |negative value| = -1*(negative_value) (basically distances between values or locations) Lets call it distance sum for future reference. so I try to visualize all numbers in sorted order since order of a[] doesn't matter I can freely choose to look at them in sorted way (make a 2d graph) so I know which distance is going to have what value as it always equal to (larger value — smaller value) and its easy to easy what is bigger and smaller in a picture.

This is what we are working with in a generic example of n = 4 A[] = {a, b, c, d, -a, -b, -c, -d}. I assumed a < b < c < d

  1. Now lets choose the smallest one and start calculating the total distances from a to every other number. Now from the picture, it might be easy to see why D (distance sum) value would be same for a[i] and -a[i].
  1. Here you will see that distance sum for a is 2*(a + b + c + d) and same for -a. I drew the negative terms right below the positive terms for better clarity

  1. You will notice that distance sum terms are
 2 * (a + b + c + d) , 2 * (b + b + c + d), 2 * (c + c + c + d), 2 * (d + d + d + d),  2 * (a + b + c + d) , 2 * (b + b + c + d), 2 * (c + c + c + d), 2 * (d + d + d + d)

They all are even and distinct (if you ignore the distances sum generated by -a[i])

looks great to me which means that the largest distance sum is 1. (d * 4) * 2 and in general let's say we sort all distance sum then D[2n] = 2 * n * a[2n] => a[2n] = D[2n] / (2n) where (D[2n] % (2n))=0 otherwise a[n] will be in floating points which contradicts that a[] are positive distinct integers.

  1. Let's get back to our convenient example of {a, b, c, d, -a, -b, -c, -d} and distance sums as above. 2nd largest distance sum is 2 * (c + c + c + d) and we know d now so we can easily calculate c = (D[6] - 2 * d) / 2 * (3) but generally a[2n - 1] = (D[2n - 2] - 2 * a[2n] ) / 2 * (n - 1) Note check if its perfectly dividing and positive after subtracting.

  2. You can get the whole a[] back like this. Lastly check that they is no zero created as it also contradicts the properties of a[]. If you want to check my code 105777562. Yeah this was a long tutorial but I hope its understandable. If anyone has a suggestion on how to improve the reasoning Please share it. Thank you.

Теги #tutorial, #math

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский rav.gupta 2021-02-01 00:24:43 3 Tiny change: 'ce sum is 1. `(d * 4) ' -> 'ce sum is `(d * 4) '
en4 Английский rav.gupta 2021-01-31 23:48:52 0 (published)
en3 Английский rav.gupta 2021-01-31 23:48:01 228
en2 Английский rav.gupta 2021-01-31 23:35:22 444
en1 Английский rav.gupta 2021-01-31 23:26:13 3553 Initial revision (saved to drafts)