• Post Reply Bookmark Topic Watch Topic
  • New Topic

Need help in analyzing this word problem.  RSS feed

 
beu curt
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have read it more than 100+, but I still can't figure it out.
The problem is confusing and I don't get what it wants me to do.

In Byteland it is always the military officer's main worry to order his soldiers on parade correctly.
Luckily, ordering soldiers is not really such a problem. If a platoon consists of n men, all of them have different rank (from 1 - lowest to n - highest)
and on parade they should be lined up from left to right in increasing order of rank.

Sounds simple, doesn't it? Well, Sgt Johnny thought the same, until one day he was faced with a new command.
He soon discovered that his elite commandos preferred to do the fighting, and leave the thinking to their superiors.
So, when at the first rollcall the soldiers lined up in fairly random order it was not because of their lack of discipline, but simply
because they couldn't work out how to form a line in correct order of ranks. Sgt Johnny was not at all amused, particularly as
he soon found that none of the soldiers even remembered his own rank. Over the years of service every soldier had only
learned which of the other soldiers were his superiors. But Sgt Johnny was not a man to give up easily when faced with a
true military challenge. After a moment's thought a solution of brilliant simplicity struck him and he issued the following
order: "men, starting from the left, one by one, do: (step forward; go left until there is no superior to the left of you; get back in line).".
This did indeed get the men sorted in a few minutes. The problem was solved... for the time being.

The next day, the soldiers came in exactly the same order as the day before, and had to be rearranged using the same method.
History repeated. After some weeks, Sgt Johnny managed to force each of his soldiers to remember how many men he passed
when going left, and thus make the sorting process even faster.

If you know how many positions each man has to walk to the left, can you try to find out what order of ranks the soldiers initially line up in?
Input

The first line of input contains an integer t<=50, the number of test cases. It is followed by t test cases, each consisting of 2 lines.
The first line contains a single integer n (1<=n<=200000). The second line contains n space separated integers wi, denoting how far
the i-th soldier in line must walk to the left when applying Sgt Johnny's algorithm.
Output

For each test case, output a single line consisting of n space separated integers - the ranks of the soldiers, given from left to right
in their initial arrangement.
Example

Input:
2
3
0 1 0
5
0 1 2 0 1

Output:
2 1 3
3 2 1 5 4


Any explanations would be very helpful.
Thank you
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
beu curt wrote:
Any explanations would be very helpful.


Interesting homework problem ...

Basically, this is an sort problem, except the sorting is done for you. Normally, the initial unordered list is provided, and you have to sort it -- using an algorithm that moves the elements.

Here, the problem is... you don't know the original unordered list, but you do know the moves that it takes to sort them. So, given an unordered (and unmarked) list, and the moves it takes to sort them, find out the ordering of the original list.

Henry
 
beu curt
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:
Interesting homework problem ...

Basically, this is an sort problem, except the sorting is done for you. Normally, the initial unordered list is provided, and you have to sort it -- using an algorithm that moves the elements.

Here, the problem is... you don't know the original unordered list, but you do know the moves that it takes to sort them. So, given an unordered (and unmarked) list, and the moves it takes to sort them, find out the ordering of the original list.

Henry


Thanks, but I still don't get it
 
Steve Harney
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

It is a particularly interesting problem, Henry explained the algorithm, you might be better if someone steps through the input/output.


Take the input
2
3
0 1 0
5
0 1 2 0 1


the 2 means there are two cases ie.
case 1:
3
0 1 0

case 2:
5
0 1 2 0 1

now take case 1.

the three means there are 3 soldiers in the line to start with.

1 2 3

now the 0 1 0 tell them how to move

0 means the first person in the queue will not move..

so after the 0 the line still looks like

1 2 3

next take the 1 .. so the second solder in the line moves one spot to the left.

ie

2 1 3

then finally the last 0 means that the third soldier does not move.

2 1 3.

which is the first part of the output, ( ill leave the second part to you ).

but to help clarify the algorithm if the final digit was say a 2 the third soldier would move two spots to the left ie.

3 2 1



Steve





 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!