The Java Program: F_ninja/ninjawayYiu.java

  1 /*
  2 ACM ICPC Southeast Regional 2009
  3 
  4 The Ninja Way
  5 
  6 Author: Yiu Yu Ho
  7 */
  8 
  9 import java.io.*;
 10 import java.util.*;
 11 
 12 public class ninjawayYiu
 13 {
 14         public final int oo = 1000000000 + 1000;
 15 
 16         public Scanner in = new Scanner(System.in);
 17         public PrintStream out = System.out;
 18 
 19         public int n, D;
 20         public Tree[] v;
 21         public int[] L, R;
 22 
 23         private class Tree implements Comparable<Tree>
 24         {
 25                 //i: index of the tree with respect to input order
 26                 //h: height of the tree
 27                 public int i, h;
 28                 public Tree(int ii, int hh) { i = ii; h = hh; }
 29                 public int compareTo(Tree u) { return h - u.h; }
 30         }
 31 
 32         public void main()
 33         {
 34                 int i, j, k, x;
 35 
 36                 n = in.nextInt();
 37                 while(n > 0)
 38                 {
 39                         D = in.nextInt();
 40 
 41                         v = new Tree[n];
 42 
 43                         //(L[i], R[i]) are the leftmost and rightmost location tree i can be at
 44                         L = new int[n];
 45                         R = new int[n];
 46                         
 47                         for(i=0;i<n;++i)
 48                         {
 49                                 v[i] = new Tree(i, in.nextInt());
 50                                 L[i] = -oo;
 51                                 R[i] = oo;
 52                         }
 53                         
 54                         //sort by height
 55                         Arrays.sort(v);
 56 
 57                         //The shortest tree is fixed at position 0
 58                         L[v[0].i] = R[v[0].i] = 0;
 59 
 60                         boolean done, poss;
 61                         
 62                         done = false;
 63                         poss = true;
 64 
 65                         while(!done && poss)
 66                         {
 67                                 done = true;
 68 
 69                                 //update base on input order
 70                                 for(i=0;i+1<n;++i) if(L[i]+1 > L[i+1])
 71                                 {
 72                                         L[i+1] = L[i]+1;
 73                                         done = false;
 74                                 }
 75                                 
 76 
 77                                 for(i=n-1;i-1>=0;--i) if(R[i]-1 < R[i-1])
 78                                 {
 79                                         R[i-1] = R[i]-1;
 80                                         done = false;
 81                                 }
 82 
 83                                 //update base on sorted order
 84                                 for(x=0;x+1<n;++x)
 85                                 {
 86                                         i = v[x].i;
 87                                         j = v[x+1].i;
 88                                         if(L[i] - D > L[j])
 89                                         {
 90                                                 L[j] = L[i] - D;
 91                                                 done = false;
 92                                         }
 93 
 94                                         if(R[i] + D < R[j])
 95                                         {
 96                                                 R[j] = R[i] + D;
 97                                                 done = false;
 98                                         }
 99                                 }
100                                 
101                                 //I am doing this in both directions to make sure propagation in both directions 
102                                 //are handled quickly, in the hope to reduce the number of iterations of the while-loop.
103                                 //It works ;)
104                                 for(x=n-1;x-1>=0;--x)
105                                 {
106                                         i = v[x].i;
107                                         j = v[x-1].i;
108 
109                                         if(L[i] - D > L[j])
110                                         {
111                                                 L[j] = L[i] - D;
112                                                 done = false;
113                                         }
114 
115                                         if(R[i] + D < R[j])
116                                         {
117                                                 R[j] = R[i] + D;
118                                                 done = false;
119                                         }
120                                 }
121 
122                                 for(i=0;i<n;++i) if(L[i] > R[i]) poss = false;
123                         }//end while !done and poss
124                         
125                         if(poss)
126                         {
127                                 i = v[n-1].i;
128                                 //Note that because of input order constraint, L[i] and R[i] are either both negative 
129                                 //or both positive
130                                 out.println(Math.max(Math.abs(L[i]), Math.abs(R[i])));
131                         }
132                         else
133                         {
134                                 out.println(-1);
135                         }
136 
137                         n = in.nextInt();
138                 }//while n > 0
139         }//end public void main()
140 
141 
142 
143         public static void main(String[] args)
144         {
145                 long startTime = System.currentTimeMillis();
146                 (new ninjawayYiu()).main();
147                 long endTime = System.currentTimeMillis();
148 
149                 System.err.println("Time = "+(endTime - startTime)+"(ms)");
150         }
151 }