This is essentially CodeChef\'s \'Ordering The Soldiers\' problem: I need an ide

Question

This is essentially CodeChef's 'Ordering The Soldiers' problem:

I need an idea on how to approach the problem given a vector for the input, just a rough outline would be great to start off with

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 decreasing 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 1 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 right, one by one, do: (step forward; go right until there is no superior to the right 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 right, and thus make the sorting process even faster. If you know how many positions each man has to walk to the right, can you try to find out what order of ranks the soldiers initially line up in?

The input will consist of one vector where each number corresponds to how many steps each person took to the right to get into sorted (descending) order.

Explanation / Answer

    import java.io.*;
    import java.util.*;
   
    class CodeChef {
          
       static final int MAX_P=18;
       static final int MAX=(1<<MAX_P);
      
       static int p, tab[]=new int[MAX],cnt[]=new int[2*MAX],ans[]=new int[MAX];
      
       static int find (int k) {
          int s=0;
      
          while (s<p-1) {
            s<<=1;
            s++;
        if (k>=cnt[s]) {
              k-=cnt[s];
              s++;
            }
            cnt[s]--;
          }
      
          return s-(p-1);
       }
      
       public static void main(String args[]) throws Exception {
          int t,n,i;
          BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   
          t=Integer.parseInt(in.readLine());
          while (t-->0) {
            n=Integer.parseInt(in.readLine());
            StringTokenizer token = new StringTokenizer(in.readLine());
            p=1;
            while (p<n)
              p<<=1;
            for (i=p-1; i<2*p-1; i++)
              cnt[i]=1;
            for (i=p-2; i>=0; i--)
              cnt[i]=cnt[(i<<1)+1]+cnt[(i<<1)+2];
            for (i=0; i<n; i++)
              tab[i]=Integer.parseInt(token.nextToken());
            for (i=n-1; i>=0; i--)
              ans[i]=find(i-tab[i])+1;
            StringBuffer out=new StringBuffer();
            for (i=0; i<n; i++)
            {
               out.append(ans[i]);
               out.append(' ');
            }
            System.out.println(out);
          }
       }
      
    }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.