The Java Program: C_guards/guards.java

  1 import java.io.*;
  2 import java.util.*;
  3 import java.awt.*;
  4 import java.text.*;
  5 import java.math.*;
  6 
  7 /**
  8  * Solution to Museum Guards
  9  * 
 10  * We'll frame this as a Max Flow problem, but with a twist. We'll start with a brief
 11  * discussion of Max Flow problems.
 12  * 
 13  * Consider a directional, weighted graph that has a special node called the 'Source', 
 14  * and another called the 'Sink'. Consider the weights to be a 'capacity'. Think of
 15  * each edge like a one-way pipe, and the 'capacity' is the most stuff you can push through that pipe.
 16  * (The internet is a series of tubes, right?) Well, the question is... How much stuff can you
 17  * push from the Source to the Sink, given the limited capacities of all the edges?
 18  * 
 19  * The solution technique for a Max Flow problem is called Ford-Fulkerson, and I'll only
 20  * give a brief outline of it here. 
 21  * 
 22  * First, for every edge A->B, create a dual edge, B->A, which starts with 0 capacity.
 23  * The way to think of A->B and its capacity is: How much capacity is available to use.
 24  * The way to think of B->A and its capacity is: How much capacity has been used, that I could give back if I had to.
 25  * That's why B->A starts out as 0 - because, at the beginning of the algorithm, you haven't done anything,
 26  * so you haven't used any capacity.
 27  * 
 28  * Now, find a path from the Source to the Sink, only traversing edges that have some capacity (that is, capacity>0),
 29  * and don't hit any node more than once. You can find this path any way you like, but Breadth-First Search
 30  * has become the standard. This program will use BFS, but DFS or any other method is fine.
 31  * 
 32  * When you've got a path, go back over the edges on the path, and find the one with the smallest
 33  * capacity. That's the most stuff you can push through that path, right? That's the weakest link.
 34  * Then, go back over the path again, and move that amount of capacity from each edge to its dual
 35  * (that is, subtract it from each edge, add it to each edge's dual). 
 36  * 
 37  * Keep doing this (finding paths, finding the min capacity, moving that capacity from each edge 
 38  * to its dual) until you can't find a path with >0 capacity. Then, you're done! The total amount
 39  * of capacity that you moved over all the paths you found is the Max Flow!
 40  * 
 41  * OK, so how do we see Museum Guards as a Max Flow problem? 
 42  * Well, the 'stuff' we'll flow through the system is guard-periods. Build two kinds of nodes,
 43  * for guards, and for time periods. Link the Source to each guard, with the capacity being the 
 44  * number of time periods that guard is able to work. Link a guard to a time period if the guard
 45  * is willing to work that time period, with capacity 1. Finally, link the time periods to the sink. 
 46  * What should the capacity for those edges be? Well, that's tough. We could set them all to n, 
 47  * and see how many guard-periods flow through - but we have no way of forcing the 
 48  * guard-periods to be balanced over the time periods. Some periods could be over-represented,
 49  * and some under-represented. The result wouldn't be meaningful. Hmmm....
 50  * 
 51  * Consider this: If we set the capacity of each of those links to some value x, 0<=x<=n, 
 52  * and we get a total flow of x*48 (48=number of 30 minute periods in a day), 
 53  * then we know we can cover all time periods with x guards. The only way to get
 54  * a total flow of x*48 is to get a full x from each of the 48 time periods. We can't get
 55  * any more from one time period (and less from another), because we've set the 
 56  * max capacity from each time period to the sink to x. That's our hook.
 57  * We just have to do repeated Ford-Fulkersons to find the largest value of x which leads to success.  
 58  */
 59 class guards
 60 {
 61     public Scanner sc;
 62     public PrintStream ps;
 63     
 64     // Program was written with different periods-per-hour possible.
 65     // We settled on 2 periods per hour (by half-hours), but this code
 66     // could have handled other cases.
 67     public static final int PERIODS_PER_HOUR = 2;
 68     public static final int PERIODS_PER_DAY = 24*PERIODS_PER_HOUR;
 69     public static final int MINUTES_PER_PERIOD = 60/PERIODS_PER_HOUR;
 70     public static final int MINUTES_PER_DAY = 24*60;
 71 
 72     public String toString()
 73     {
 74         return "guards";
 75     }
 76     
 77     /**
 78      * A Node in the Max Flow graph
 79      */
 80     public class Node
 81     {
 82         // A list of edges
 83         public LinkedList<Edge> edges;
 84         
 85         // Whether or not this node has been visited by the current search
 86         public boolean visited;
 87         
 88         // A name, for debugging purposes only.
 89         public String name;
 90         
 91         /**
 92          * Create a node.
 93          * 
 94          * @param n The Name of the node
 95          */
 96         public Node( String n )
 97         {
 98                 name = n;
 99                 edges = new LinkedList<Edge>();
100                 visited = false;
101         }
102         
103         /**
104          * Standard toString() method, to help with debugging.
105          * 
106          * @return A pretty string version of the node (which is just the name).
107          */
108         public String toString()
109         {
110                 return name;
111         }
112     }
113     
114     /**
115      * An Edge in the Max Flow graph.
116      */
117     public class Edge
118     {
119         // Each edge has a capacity,
120         public int cap;
121         
122         // A destination,
123         public Node dest;
124         
125         // And a "dual" edge
126         public Edge dual;
127         
128         /**
129          * Create an edge.
130          * 
131          * @param d The destination of this edge.
132          */
133         public Edge( Node d )
134         {
135                 cap = 0;
136                 dest = d;
137                 dual = null;
138         }
139     }
140     
141     /**
142      * A State in the BFS.
143      */
144     public class State
145     {
146         // The node where we are
147         public Node node;
148         
149         // The edge that got us here
150         public Edge edge;
151         
152         // A link to the previous state
153         public State prevstate;
154         
155         /**
156          * Create a State.
157          * 
158          * @param n The Node
159          * @param e The Edge that got us here
160          * @param p The previous State
161          */
162         public State( Node n, Edge e, State p )
163         {
164                 node = n;
165                 edge = e;
166                 prevstate = p;
167         }
168     }
169     
170     /**
171      * Create a link (and its dual) between nodes A and B.
172      * 
173      * @param a Node A
174      * @param b Node B
175      * @param capacity Capacity from A to B (it'll be 0 from B to A)
176      */
177     public void link( Node a, Node b, int capacity )
178     {
179         // Create the edge from A to B, and its dual from B to A.
180         Edge a2b = new Edge( b );       
181         Edge b2a = new Edge( a );
182         
183         // Add them to their respective Nodes
184         a.edges.add( a2b );
185         b.edges.add( b2a );
186         
187         // They are duals of each other
188         a2b.dual = b2a;
189         b2a.dual = a2b;
190         
191         // Set their capacities
192         a2b.cap = capacity;
193         b2a.cap = 0;
194     }
195     
196     /**
197      * Parse a string of the form HH:MM and return the number
198      * of minutes represented.
199      * 
200      * @param time A String time, like 02:34
201      * @return The number of minutes represented by the String time
202      */
203     public int getMinutes( String time )
204     {
205         String tokens[] = time.split( ":" );
206         int h = Integer.parseInt( tokens[0] );
207         int m = Integer.parseInt( tokens[1] );
208         return h*60 + m;
209     }
210     
211     /**
212      * Convert minutes to periods
213      * 
214      * @param minutes Minutes
215      * @return Periods
216      */
217     public int minutesToPeriods( int minutes )
218     {
219         return minutes * PERIODS_PER_HOUR / 60;
220     }
221     
222     // The nodes - source, sink, guards, time periods.
223     public Node source, sink, guards[], periods[];
224     
225     // We'll reuse this same queue for all of our BFS's.
226     public LinkedList<State> queue = new LinkedList<State>();
227     
228     /**
229      * Can we make a schedule such that every time period is covered by x guards?
230      * 
231      * @param x A number of guards to check
232      * @return true if we can cover every time period with x guards, otherwise false.
233      */
234     public boolean cando( int x )
235     {
236         // Start by resetting the system. First, source to guards
237         for( Edge e : source.edges )
238         {
239                 // We never get rid of capacity, we just move it from the edge to its dual.
240                 // So here, we'll just move it back.
241                 e.cap = e.cap+e.dual.cap;
242                 e.dual.cap = 0;
243         }
244         
245         // Now, guards to periods
246         for( Node g : guards )
247         {
248                 for( Edge e : g.edges )
249                 {
250                         // Guards have 2 kinds of edges - those to time periods,
251                         // and those back to the source that are duals of edges from
252                         // the source to the guard. We only want to reset the ones to time
253                         // periods - we already reset the duals back at the source.
254                     if( e.dest != source )
255                     {
256                         e.cap = 1;
257                         e.dual.cap = 0;
258                     }
259                 }
260         }
261         
262         // Finally, periods to sink
263         for( Node p : periods )
264         {
265                 for( Edge e : p.edges )
266                 {
267                         // Periods have 2 kinds of edges - to the sink, and duals
268                         // back to the guards. here, we're only interested in those
269                         // that go to the sink.
270                         if( e.dest == sink )
271                         {
272                                 e.cap = x;
273                                 e.dual.cap = 0;
274                         }
275                 }
276         }
277         
278         // Total capacity
279         int totalcap = 0;
280                 
281         // Now, go through Ford-Fulkerson
282         for(;;)
283         {
284                 // Mark all of the nodes as unvisited - this is a fresh BFS.
285                 // Source is the exception, since we're marking nodes when we put them
286                 // on the queue rather than when we're taking them off.
287                 source.visited = true;
288                 for( Node g : guards )
289                 {
290                         g.visited = false;
291                 }
292                 for( Node p : periods )
293                 {
294                     p.visited = false;  
295                 }
296                 sink.visited = false;
297                 
298                 // Start the BFS. Clear the queue, add the source
299                 queue.clear();
300                 queue.add( new State( source, null, null ) );
301                 
302                 // We want to remember the final state we ended up in.
303                 // That's so we can do the part of Ford-Fulkerson where
304                 // we trace our route, find the smallest capacity along the route,
305                 // and use that capacity along the route.
306                 State finalstate = null;
307                 
308                 // And, off we go with a BFS.
309                 while( queue.size()>0 )
310                 {
311                         // Grab the next state
312                     State s = queue.removeFirst();
313                     
314                     // Did we reach the sink? Then we're done
315                     if( s.node == sink )
316                     {
317                         finalstate = s;
318                         break;
319                     }
320                     
321                     // Otherwise, go through this node's edges
322                         for( Edge e : s.node.edges )
323                         {
324                                 // Look for edges that have capacity>0, that go
325                                 // to nodes we haven't visited yet
326                                 if( e.cap>0 && !e.dest.visited )
327                                 {
328                                         // Mark'em, and queue'em
329                                         e.dest.visited = true;
330                                         queue.add( new State( e.dest, e, s ) );
331                                 }
332                         }
333                 }
334                 
335                 // If we never reached the sink, then we're done.
336                 if( finalstate==null ) break;
337                 
338                 // Figure out how much capacity this route used.
339                 // This is a "weakest link" thing - you can't push through any more
340                 // capacity than the smallest pipe will allow. 
341                 // So, we go back through all of the edges we used, to
342                 // find the smallest capacity.
343                 int capused = Integer.MAX_VALUE;
344                 for( State s=finalstate; s.edge!=null; s=s.prevstate )
345                 {
346                         if( s.edge.cap<capused ) capused = s.edge.cap;
347                 }
348                 
349                 // Total capacity is increased by the capacity used on this route
350                 totalcap += capused;
351                 
352                 // Modify the edges - remove the capacity used from each
353                 // edge in the route, and put it on that edge's dual
354                 for( State s=finalstate; s.edge!=null; s=s.prevstate )
355                 {
356                         s.edge.cap -= capused;
357                         s.edge.dual.cap += capused;
358                 }
359         }
360                 
361         // Did we manage to fill all periods with n guards?
362         return totalcap == x*PERIODS_PER_DAY;
363     }
364            
365     /**
366      * The main method
367      * @throws Exception
368      */
369     public void doit() throws Exception
370     {
371         sc = new Scanner( System.in ); // new Scanner( new File( "guards.judge" ) );
372         ps = System.out; // new PrintStream( new FileOutputStream( "guards.solution" ) );
373         
374         // Create everything we can a priori.
375         // The number of guards will vary, but the source, sink and time periods won't.
376         source = new Node( "source" );
377         sink = new Node( "sink" );
378         periods = new Node[PERIODS_PER_DAY];
379         for( int i=0; i<periods.length; i++ )
380         {
381                 periods[i] = new Node( "period" + i );
382         }
383         
384         // willwork[i] == Is the current guard willing to work this minute of the day?
385         boolean willwork[] = new boolean[MINUTES_PER_DAY];
386         
387         for(;;)
388         {
389                 // Read the number of guards, exit if done.
390                 int n = sc.nextInt();
391                 if( n==0 ) break;
392                 
393                 // Create the guards array
394                 guards = new Node[n];
395                 
396                 // Clear out the last graph - we're going to build a new one
397                 source.edges.clear();
398                 sink.edges.clear();
399                 for( Node p : periods )
400                 {
401                     p.edges.clear();
402                     
403                     // The capacity we use here doesn't really matter.
404                     // We'll reset it with every call to cando().
405                     link( p, sink, 1 );
406                 }
407                 
408                 // Read in info on the guards
409                 for( int i=0; i<n; i++ )
410                 {
411                         // Number of time windows, time limit.
412                         int m = sc.nextInt();
413                         int k = sc.nextInt();
414                         
415                         // Time limit is in minutes - convert it to periods.
416                         k = minutesToPeriods(k);
417                                                 
418                         // Figure out what minutes the guard is willing to work.
419                         Arrays.fill( willwork, false );                 
420                         for( int j=0; j<m; j++ )
421                         {
422                                 // Read start & stop times
423                                 String t1 = sc.next();
424                                 String t2 = sc.next();
425                                 
426                                 // Convert to minutes
427                                 int start = getMinutes(t1);                                                             
428                                 int stop = getMinutes(t2);
429                                 
430                                 // Account for wrap around midnight
431                                 if( stop<=start ) stop += MINUTES_PER_DAY;
432                                                                 
433                                 // Mark those minutes that the guard is willing to work.
434                                 for( int minute=start; minute<stop; minute++ )
435                                 {
436                                         willwork[minute%MINUTES_PER_DAY] = true;
437                                 }
438                         }
439                         
440                         // Create a node for this guard, link it to the source
441                         guards[i] = new Node( "guard" + i );
442                         link( source, guards[i], k );
443                         
444                         // Determine which time periods the guard is willing to work
445                         for( int period=0; period<periods.length; ++period )
446                         {
447                                 // Guard is only willing to work a time period if s/he
448                                 // is willing to work EVERY MINUTE of that time period
449                                 boolean willworkperiod = true;
450                                 for( int minute = period*MINUTES_PER_PERIOD; minute<(period+1)*MINUTES_PER_PERIOD; ++minute )
451                                 {
452                                     if( !willwork[minute] )
453                                     {
454                                         willworkperiod = false;
455                                         break;
456                                     }
457                                 }
458                                 
459                                 // If they're willing, create the link!
460                                 if( willworkperiod )
461                                 {
462                                     link( guards[i], periods[period], 1 );      
463                                 }
464                         }
465                 }
466                 
467                 // Now, it's just a Binary Search 
468                 // to look for the breakpoint where
469                 // cando(x) is true, but cando(x+1) is false.
470                 int lo = 0; // Guaranteed that cando(0) is true.
471                 int hi = n+1; // Since we have only n guards, guaranteed that cando(n+1) is false
472                 while( lo<hi-1 )
473                 {
474                         int mid = (lo+hi)/2;
475                         if( cando(mid) )
476                         {
477                             lo = mid;
478                         }
479                         else
480                         {
481                             hi = mid;   
482                         }
483                 }
484                 
485                 // The Binary Search will end with lo==hi-1,
486                 // cando(lo)==true, cando(hi)==cando(lo+1)==false.
487                 // So, lo is our answer.
488                 ps.println( lo );
489         }
490     }
491 
492         public static void main(String[] args) throws Exception
493         {
494                 long starttime = System.currentTimeMillis();
495                 new guards().doit();
496                 System.out.println( System.currentTimeMillis() - starttime );
497         }
498 }