[Solution] Min-Max Array Transformation solution codeforces

Table of Contents

Min-Max Array Transformation solution codeforces

Min-Max Array Transformation solution codeforces – You are given an array ๐‘Ž1,๐‘Ž2,โ€ฆ,๐‘Ž๐‘›a1,a2,โ€ฆ,an, which is sorted in non-descending order. You decided to perform the following steps to create arrayย ๐‘1,๐‘2,โ€ฆ,๐‘๐‘›b1,b2,โ€ฆ,bn:

  1. Create an arrayย ๐‘‘dย consisting ofย ๐‘›nย arbitraryย non-negativeย integers.
  2. Setย ๐‘๐‘–=๐‘Ž๐‘–+๐‘‘๐‘–bi=ai+diย for eachย ๐‘๐‘–bi.
  3. Sort the arrayย ๐‘bย in non-descending order.

Min-Max Array Transformation solution codeforces

You are given the resulting arrayย ๐‘b. For each indexย ๐‘–i, calculate what is the minimum and maximum possible value ofย ๐‘‘๐‘–diย you can choose in order to get the given arrayย ๐‘b.

Note that the minimum (maximum)ย ๐‘‘๐‘–di-s areย independentย of each other, i.ย e. they can be obtained from different possible arraysย ๐‘‘d.

Input

The first line contains the single integerย ๐‘กtย (1โ‰ค๐‘กโ‰ค1041โ‰คtโ‰ค104)ย โ€” the number of test cases.

The first line of each test case contains a single integerย ๐‘›nย (1โ‰ค๐‘›โ‰ค2โ‹…1051โ‰คnโ‰ค2โ‹…105)ย โ€” the length of arraysย ๐‘Ža,ย ๐‘bย andย ๐‘‘d.

The second line containsย ๐‘›nย integersย ๐‘Ž1,๐‘Ž2,โ€ฆ,๐‘Ž๐‘›a1,a2,โ€ฆ,anย (1โ‰ค๐‘Ž๐‘–โ‰ค1091โ‰คaiโ‰ค109;ย ๐‘Ž๐‘–โ‰ค๐‘Ž๐‘–+1aiโ‰คai+1)ย โ€” the arrayย ๐‘Žaย in non-descending order.

The third line containsย ๐‘›nย integersย ๐‘1,๐‘2,โ€ฆ,๐‘๐‘›b1,b2,โ€ฆ,bnย (1โ‰ค๐‘๐‘–โ‰ค1091โ‰คbiโ‰ค109;ย ๐‘๐‘–โ‰ค๐‘๐‘–+1biโ‰คbi+1)ย โ€” the arrayย ๐‘bย in non-descending order.

Additional constraints on the input:

  • there is at least one way to obtain the arrayย ๐‘bย from theย ๐‘Žaย by choosing an arrayย ๐‘‘dย consisting ofย non-negative integers;
  • the sum ofย ๐‘›nย doesn’t exceedย 2โ‹…1052โ‹…105.

Min-Max Array Transformation solution codeforces

For each test case, print two lines. In the first line, printย ๐‘›nย integersย ๐‘‘๐‘š๐‘–๐‘›1,๐‘‘๐‘š๐‘–๐‘›2,โ€ฆ,๐‘‘๐‘š๐‘–๐‘›๐‘›d1min,d2min,โ€ฆ,dnmin, whereย ๐‘‘๐‘š๐‘–๐‘›๐‘–diminย is the minimum possible value you can add toย ๐‘Ž๐‘–ai.

Secondly, printย ๐‘›nย integersย ๐‘‘๐‘š๐‘Ž๐‘ฅ1,๐‘‘๐‘š๐‘Ž๐‘ฅ2,โ€ฆ,๐‘‘๐‘š๐‘Ž๐‘ฅ๐‘›d1max,d2max,โ€ฆ,dnmax, whereย ๐‘‘๐‘š๐‘Ž๐‘ฅ๐‘–dimaxย is the maximum possible value you can add toย ๐‘Ž๐‘–ai.

Allย ๐‘‘๐‘š๐‘–๐‘›๐‘–diminย andย ๐‘‘๐‘š๐‘Ž๐‘ฅ๐‘–dimaxย values are independent of each other. In other words, for eachย ๐‘–i,ย ๐‘‘๐‘š๐‘–๐‘›๐‘–diminย is just the minimum value among all possible values ofย ๐‘‘๐‘–di.

Example
input

Copy
4
3
2 3 5
7 11 13
1
1000
5000
4
1 2 3 4
1 2 3 4
4
10 20 30 40
22 33 33 55
output

Copy
5 4 2
11 10 8
4000
4000
0 0 0 0
0 0 0 0
12 2 3 15
23 13 3 15

Min-Max Array Transformation solution codeforces

In the first test case, in order to getย ๐‘‘๐‘š๐‘–๐‘›1=5d1min=5, we can choose, for example,ย ๐‘‘=[5,10,6]d=[5,10,6]. Thenย ๐‘bย ==ย [2+5,3+10,5+6][2+5,3+10,5+6]ย ==ย [7,13,11][7,13,11]ย ==ย [7,11,13][7,11,13].

Forย ๐‘‘๐‘š๐‘–๐‘›2=4d2min=4, we can chooseย ๐‘‘dย ==ย [9,4,8][9,4,8]. Thenย ๐‘bย ==ย [2+9,3+4,5+8][2+9,3+4,5+8]ย ==ย [11,7,13][11,7,13]ย ==ย [7,11,13][7,11,13].

For Solution

“Click Here”

Leave a Comment