Codeforces Round #698 Nezzar and Symmetric Array - Construction

Solution

First let's choose any two numbers, $a_i$ and $a_j$. So There must be $-a_i$ and $-a_j$ in $a$. And so there is no need to consider the symbol. Let's assume  $a_i>0,\ a_j>0$.

Let's see: $\mid{a_i-a_j}\mid+\mid{a_i-(-a_j)}\mid$. Then we know: If $a_i>a_j$, then the result is $2\cdot{a_i}$, otherwise $2\cdot{a_j}$。

So we can know that: If $d_i$ is the maximum number of $d$, then $a_i$ must be the maximum value in $a$. And $d_i=2\cdot{n}\cdot{a_i}$.

In similar way, we can find the second maximum number of $d$: $d_j$. And then $a_j$ must be the second maximum number of $a$. And $d_j=2\cdot{a_i}+2\cdot{(n-1)}\cdot{a_j}$.

So we can follow this way to build $a$ back (positive part).

And if we found some of $a$ we build is negative. Then it fail. Also, be careful, all the number in $a$ we built should not be same.

Code

Submission #111835021 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge