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 }