[Solution] House Planning solution codeforces

House Planning solution codeforces – There are 𝑛n houses in your city arranged on an axis at points 1,2,,𝑛h1,h2,…,hn. You want to build a new house for yourself and consider two options where to place it: points 𝑝1p1 and 𝑝2p2.

As you like visiting friends, you have calculated in advance the distances from both options to all existing houses. More formally, you have calculated two arrays 𝑑1d1𝑑2d2𝑑𝑖,𝑗=∣∣𝑝𝑖𝑗∣∣di,j=|pi−hj|, where |𝑥||x| defines the absolute value of 𝑥x.

Table of Contents

[Solution] House Planning solution codeforces

After a long time of inactivity you have forgotten the locations of the houses h and the options 𝑝1p1𝑝2p2. But your diary still keeps two arrays — 𝑑1d1𝑑2d2, whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of 𝑑1d1 and 𝑑2d2 may correspond to different houses. Pay attention, that values from one array could not get to another, in other words, all values in the array 𝑑1d1 correspond the distances from 𝑝1p1 to the houses, and in the array 𝑑2d2  — from 𝑝2p2 to the houses.

Also pay attention, that the locations of the houses 𝑖hi and the considered options 𝑝𝑗pj could match. For example, the next locations are correct: ={1,0,3,3}h={1,0,3,3}𝑝={1,1}p={1,1}, that could correspond to already shuffled 𝑑1={0,2,1,2}d1={0,2,1,2}𝑑2={2,2,1,0}d2={2,2,1,0}.

Check whether there are locations of houses h and considered points 𝑝1p1𝑝2p2, for which the founded arrays of distances would be correct. If it is possible, find appropriate locations of houses and considered options.

[Solution] House Planning solution codeforces

The first line of the input contains a single integer 𝑡t (1𝑡1031≤t≤103) — the number of test cases. The description of test cases follows.

The first line of each test case contains one integer 𝑛n (1𝑛1031≤n≤103) — the length of arrays 𝑑1d1𝑑2d2.

The next two lines consist arrays 𝑑1d1 and 𝑑2d2 (0𝑑𝑖,𝑗1090≤di,j≤109) respectively.

It is guaranteed that the sum of 𝑛n over all test cases doesn’t exceed 21032⋅103.

[Solution] House Planning solution codeforces

For each test case, output a single line “NO” if there is no answer.

Otherwise output three lines. The first line must contain “YES“. In the second line, print 𝑛n integers 1,2,,𝑛h1,h2,…,hn. In the third line print two integers 𝑝1p1𝑝2p2.

It must be satisfied that 0𝑖,𝑝1,𝑝221090≤hi,p1,p2≤2⋅109. We can show that if there is an answer, then there is one satisfying these constraints.

If there are several answers, output any of them.

[Solution] House Planning solution codeforces

input

Copy
4
1
5
5
2
10 12
5 20
2
10 33
26 69
4
0 2 1 2
2 2 1 0
output

Copy
YES
5 
0 10
NO
YES
0 43 
33 69
YES
1 0 3 3
1 1

[Solution] House Planning solution codeforces

In the image below you can see the sample solutions. Planned houses are shown in bright colours: pink and purple. Existing houses are dim.

In test case 11, the first planned house is located at point 00, the second at point 1010. The existing house is located at point 55 and is at a distance of 55 from both planned houses.

It can be shown that there is no answer for test case 22.

In test case 33, the planned houses are located at points 3333 and 6969.

Note that in test case 44, both plans are located at point 11, where one of the existing houses is located at the same time. It is a correct placement.

For Solution

“Click Here”

Leave a Comment