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[1] > H[2]

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 
Test : 1
3 1 2
Test : 2
2 1 3

hide comments
sobir_bobiev: 2019-07-27 06:45:00

Can we really have multiple ways for H?

amulyagaur: 2018-03-02 14:52:58

pbds rocks!

RIVU DAS: 2014-05-24 07:35:05

Finally AC!!

007: Name stolen: 2014-03-25 09:49:01

can u check my submission : http://www.spoj.com/files/src/11322713/

i have checked for over more than 100 test cases but still WA

Last edit: 2014-03-25 09:49:14
Ujjwal Prakash: 2014-02-08 21:59:34

Nice problem with good test cases. Similar problem gave AC but this gave TLE

praveen123: 2014-02-04 00:47:43

@bloody_looser Test data was wrongly uploaded, Updated now.

shiv prasad chabarval: 2014-02-04 00:46:16

is there any problem with i/o format. praveen123 plz tell me why i am getting WA

Added by:praveen123
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge