IITWPC4D - Arrangement Validity
n persons are standing in a line. Height of each person is between 1 and n and height of each person is distinct.
You a given array A where A[i] denotes how many persons are before i_th person having heights greater than H[i]. eg. For person 2, person 1 is considered before him. If A is given to be [0, 1] then one valid arrangements of height could be [2, 1] as number of persons having height > 1 before 2 are 1 because H > H
You have to find out whether this array can be valid for some arrangement of persons. If you can uniquely do so, then find out the array H. Otherwise output -1.
First line contains T : number of test cases. (1 <= T <= 20).
For each test First line contains an integer n. ( 1 <= n <= 10^5)
Next line contains n space seperated integers denoting A[i]. (0 <= A[i] <= n)
For each test case output single line
If there is a unique way of H. Then print n space seprated integers in the line.
Otherwise output -1.
In starting of each test case also put "Test : testNumber" (without quotes). Note that there is a space before colon and one space after colon.
0 1 1
0 1 0
Output: Test : 1
3 1 2
Test : 2
2 1 3
Can we really have multiple ways for H?
007: Name stolen:
Nice problem with good test cases. Similar problem gave AC but this gave TLE
@bloody_looser Test data was wrongly uploaded, Updated now.
shiv prasad chabarval:
is there any problem with i/o format. praveen123 plz tell me why i am getting WA