Chef and Pairwise Distances solution codechef

Chef and Pairwise Distances solution codechef

Chef has an array AA with NN elements. He wants to find NN points P1,,PNP1,…,PN with integer coordinates on the 2D coordinate plane such that, for all pairs of indices ii and jj (1i<jN1≤i<j≤N), the Manhattan distance from PiPi to PjPj is Ai+AjAi+Aj. Help him find any NN points satisfying the condition, or state that no such points exist.

As a reminder, the Manhattan distance between the points (x1,y1)(x1,y1) and (x2,y2)(x2,y2) is defined as |x1x2|+|y1y2||x1−x2|+|y1−y2|.

Chef and Pairwise Distances solution codechef

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains a single integer NN.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, if there is no set of points satisfying the stated condition, output NO.

Otherwise, output YES on one line, then output NN lines. Each line should contain two integers XiXi and YiYi (1018Xi,Yi1018−1018≤Xi,Yi≤1018) denoting the xx and yy coordinates of the point PiPi respectively.

It can be proven that if a solution exists, then a solution exists under the constraints above.

Output is case insensitive.

Chef and Pairwise Distances solution codechef

  • 1T1041≤T≤104
  • 1N21051≤N≤2⋅105
  • 1Ai1091≤Ai≤109
  • Sum of NN over all test cases does not exceed 21052⋅105

Sample Input 1 

5 13
8 4 20
2 9 12 3 8

Sample Output 1 

3 9
13 17
18 5
10 1
1 16


  • For the first test case, we can choose P1=(3,9)P1=(3,9) and P2=(13,17)P2=(13,17). The Manhattan distance between P1P1 and P2P2 is |313|+|917|=18|3−13|+|9−17|=18, and A1+A2=5+13=18A1+A2=5+13=18.

  • For the second test case, we can choose P1=(18,5)P1=(18,5)P2=(10,1)P2=(10,1), and P3=(1,16)P3=(1,16).

    • The Manhattan distance between P1P1 and P2P2 is |1810|+|51|=12|18−10|+|5−1|=12, and A1+A2=8+4=12A1+A2=8+4=12.
    • The Manhattan distance between P1P1 and P3P3 is |181|+|516|=28|18−1|+|5−16|=28, and A1+A3=8+20=28A1+A3=8+20=28.
    • The Manhattan distance between P2P2 and P3P3 is |101|+|116|=24|10−1|+|1−16|=24, and A2+A3=4+20=24A2+A3=4+20=24.
  • For the third test case, it can be proven that there does not exist 55 points satisfying these constraints.

Leave a Comment

Your email address will not be published.