Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Need help in analyzing this word problem.

  1. #1
    Junior Member
    Join Date
    Nov 2010
    Thanked 0 Times in 0 Posts

    Default Need help in analyzing this word problem.

    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?

    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.

    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.

    0 1 0
    0 1 2 0 1

    2 1 3
    3 2 1 5 4
    Any explanations would be very helpful.
    Thank you

  2. #2
    mmm.. coffee JavaPF's Avatar
    Join Date
    May 2008
    United Kingdom
    My Mood
    Thanked 294 Times in 227 Posts
    Blog Entries

    Default Re: Need help in analyzing this word problem.

    I can understand how this can be quite tricky!

    Have you started to write any code at all?

    Please provide us with your class with as much code as possible. We can take it from there..
    Please use [highlight=Java] code [/highlight] tags when posting your code.
    Forum Tip: Add to peoples reputation by clicking the button on their useful posts.

Similar Threads

  1. removing stopwords from a word list
    By jessie in forum File I/O & Other I/O Streams
    Replies: 1
    Last Post: November 15th, 2010, 12:02 PM
  2. im in a hurry!!Help with a programm..java game of guessing a word
    By mr_doctor in forum What's Wrong With My Code?
    Replies: 3
    Last Post: October 13th, 2010, 08:17 AM
  3. Word filter assignment help
    By normandygahn in forum What's Wrong With My Code?
    Replies: 3
    Last Post: September 15th, 2010, 07:42 AM
  4. [SOLVED] Word Scramble Using Objects & Methods
    By Whitechapel in forum Object Oriented Programming
    Replies: 3
    Last Post: May 23rd, 2010, 12:38 PM
  5. How to invert a word String
    By Truffy in forum Java Programming Tutorials
    Replies: 16
    Last Post: October 3rd, 2009, 02:44 AM