Notes for judges. The key to this problem is the longest chain of 'disjoint' garbage locations. Two locations are disjoint if one is Southwest of another. The algorithm used for this problem determines the longest chain by having each robot 'peel' the leftmost garbage locations still on the map. This is something like taking an onion apart layer by layer. The following diagrams represent the fields in input file if drawn on a 24 X 24 grid. In these diagrams, an X marks a garbage location and a '+' marks an empty location. Field 1 Garbage count 7 Robot count 2 This is the example field shown in the diagram and in the sample input. +X+X++++++++++++++++++++ +++X+X++++++++++++++++++ ++++++++++++++++++++++++ +++X++X+++++++++++++++++ ++++++++++++++++++++++++ +++++X++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ Field 2 Garbage count 184 Robot count 16 This is a large and sparsely populated field. A+++A++A+AAA+A+AAA+++A++ B+++++B+++++++BB++++B+++ +CC+C+C+C+C++++C++++++AA D+D++DD++D+DDD++CC++++++ ++E+E+E++++++D+++CC++B++ F+++FF+E+E+++D+D+D+C++++ ++++G++F+EE++E++ED+++BB+ +++H+G++++++F++F++++++BA I+IHH++++G+++++++D+++++A J+++H++++++G+GG+++D+++BA J+I++++H+++HH+++++D++CB+ ++I++I++++++HH++E+DD++B+ J+++++++++++I++++++DDC++ JJ+++++++J++++G++E++D++A KKK++KK+++J++H++F+++++++ +L++LL++++J+++++++E+++B+ MM+MML+++++J+++G++EEDC++ +N++M+++KK++I++++F++++BA O+++M+++++K+I+HG++++++B+ +N+N++++LL++++++GF+++++A +O+N++++M++++IH+G+FED+++ +OO+++NN+++++++++GF+D++A ++O++++N+++J+IH++G++++++ PP++O+++++++JI++++++++++ Field 3 Garbage count 8 Robot count 1 This field has garbage on a diagonal allowing 1 robot to grab all of the garbage. This is a best case with not 'disjoint' locations. ++++++++++++++++++++++++ +X++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ +++++++X++++++++++++++++ ++++++++++++++++++++++++ +++++++++X++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++X+++++++++++ +++++++++++++X++++++++++ ++++++++++++++++++++++++ +++++++++++++++X++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++X+++ ++++++++++++++++++++++++ ++++++++++++++++++++++X+ ++++++++++++++++++++++++ Field 4 Garbage count 8 Robot count 8 This is a worst case diagonal where each location is disjoint. It requires 1 robot per garbage location. ++++++++++++++++++++++++ ++++++++++++++++++++++X+ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ +++++++++++++++X++++++++ ++++++++++++++++++++++++ +++++++++++++X++++++++++ ++++++++++++++++++++++++ +++++++++++X++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ +++++++X++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ +++X++++++++++++++++++++ ++X+++++++++++++++++++++ +X++++++++++++++++++++++ ++++++++++++++++++++++++ Field 5 Garbage count 63 Robot count 3. Here the number of rows limits the number of robots. XXXXXXXXXXXXXXXXXXXXX+++ XXXXXXXXXXXXXXXXXXXXX+++ XXXXXXXXXXXXXXXXXXXXX+++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ Field 6 Garbage count 126 Robot count 6. Here the number of columns limits the number of robots. XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ XXXXXX++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ Field 7 Garbage count 21 Robot count 4 Just a smallish random field. X+X+++++++++++++++++++++ ++++XX+X++++X+++++++++++ X+++++X+++++++++++++++++ X++++++++XXXX+++++++++++ X+++++++++++++++++++++++ +++++X+++X++++++++++++++ ++++++++++++++++++++++++ +X++++++++++++++++++++++ ++++++++++++++++++++++++ ++X+XX+++X++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ Field 8 Garbage count 18 Robot count 2 The pattern here, something like a '+', only needs 2 robots. ++++++++++++X+++++++++++ ++++++++++++X+++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++X+++++++++++ ++++++++++++X+++++++++++ ++++++++++++X+++++++++++ ++++++++++++X+++++++++++ ++++++++++++X+++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++X+++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++X+++++++++++ ++++++++++++X+++++++++++ ++++++++++++X+++++++++++ +XX++++++++X+X++++X++++X ++++++++++++X+++++++++++ Field 9 Garbage count 11 Robot count 2. A 'greedy' approach will fail on this map. This is because the first greedy pass will divide the field into two disjoint clumps requiring two additional robots. ++++++++++++++++++++++++ ++X++X++++++++++++++++++ XX+X++XX++++++++++++++++ +++++++X++++++++++++++++ +++XX+++++++++++++++++++ +++++++X++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ Field 10 Garbage count 1 Robot count 1 One piece only needs one robot wherever it is located. ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++X+++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ ++++++++++++++++++++++++ Field 11 Garbage count 576 24 robots. The number of disjoint locations is exactly the number of items on the longest diagonal. XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXX Field 12 Garbage count 31 2 Robots. Only perimeter locations. 1 robot strips left column and bottom row, the other strips the top row, right column. X+++X++++X++++X++++X+++X X+++++++++++++++++++++++ X++++++++++++++++++++++X ++++++++++++++++++++++++ +++++++++++++++++++++++X +++++++++++++++++++++++X X++++++++++++++++++++++X ++++++++++++++++++++++++ ++++++++++++++++++++++++ X+++++++++++++++++++++++ ++++++++++++++++++++++++ +++++++++++++++++++++++X ++++++++++++++++++++++++ ++++++++++++++++++++++++ X++++++++++++++++++++++X X+++++++++++++++++++++++ X+++++++++++++++++++++++ +++++++++++++++++++++++X +++++++++++++++++++++++X ++++++++++++++++++++++++ ++++++++++++++++++++++++ X+++++++++++++++++++++++ +++++++++++++++++++++++X X+X++XXX++++XX+++++++++X