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

Правка en5, от rav.gupta, 2021-02-01 00:24:43

Hi,

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

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}

Second thing they define are D[] where each i-th term D[i] is the sum of (absolute differences between A[i] to all other possible A[j], j in [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 ?

I don't like absolute function but it has this property |negative value| = -1*(negative_value) = positive (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 get an idea which distance is going to have what value as it always equal to (larger value — smaller value) and its easy to see what is bigger and smaller in a picture.

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

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 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

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 negatives)

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

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[n - 1] = (D[2n - 2] - 2 * A[n] ) / 2 * (n - 1) Note [check if its perfectly dividing and positive after subtracting.] . (We use D[2n-2] because D[2n-1] is same as D[2n] , but you can use std:set and make implementation easy at log(n) insertion cost)

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)