Judge's Notes for Fax Regions This problem has both a complicated algorithm and large input. These notes help double check the correctness of the output by comparing to the direct algorithm for small grids and explaining the patterns in the very large datasets that come the end of the input file fax.in. There are three parts to these notes: 1. The first 15 datasets with grids fully graphicaly displayed and with the output calculated by the direct algorithm that fails with large input. This is a slight annotation of the output genrated by fax.java if it is run with any commandlne parameter. The output file generated in this situation matches the output from the general algorithm for the same small grids. 2. The screen output from the normal run of the program is considered in two parts. First the reduced grids generated by the general algorithm corresponding to the grids shown in part 1. 3. An explanation of the pattern in the input for all the large grids. Each was generated with a pattern that allowed the number of components to be calculated by hand. The reduced grid sizes are indicated. ============================================================================== 1. Small faxs generated by the simple algorithm Small Dataset 1: 32 components (sample input) 1.2.3.4. .5.6.7.8 9.A.B.C. .D.E.F.G H.I.J.K. .L.M.N.O P.Q.R.S. .T.U.V.W Small Dataset 2: 2 components (sample input) .11.2 111.. ..111 Small Dataset 3: 3 components (sample input) 1111111 11....1 111.2.1 1.1...1 1.1.3.1 1.1.3.1 1.1...1 1111111 Datasets 4-6 are just datasets 1-3 stretched sideways by a factor of 10, (width and run lengths with 0 appended) allowing simple demonstrations of the general algorithm removing unneeded columns. Small Dataset 4: 32 components 1111111111..........2222222222..........3333333333..........4444444444.......... ..........5555555555..........6666666666..........7777777777..........8888888888 9999999999..........AAAAAAAAAA..........BBBBBBBBBB..........CCCCCCCCCC.......... ..........DDDDDDDDDD..........EEEEEEEEEE..........FFFFFFFFFF..........GGGGGGGGGG HHHHHHHHHH..........IIIIIIIIII..........JJJJJJJJJJ..........KKKKKKKKKK.......... ..........LLLLLLLLLL..........MMMMMMMMMM..........NNNNNNNNNN..........OOOOOOOOOO PPPPPPPPPP..........QQQQQQQQQQ..........RRRRRRRRRR..........SSSSSSSSSS.......... ..........TTTTTTTTTT..........UUUUUUUUUU..........VVVVVVVVVV..........WWWWWWWWWW Small Dataset 5: 2 components ..........11111111111111111111..........2222222222 111111111111111111111111111111.................... ....................111111111111111111111111111111 Small Dataset 6: 3 components 1111111111111111111111111111111111111111111111111111111111111111111111 11111111111111111111........................................1111111111 111111111111111111111111111111..........2222222222..........1111111111 1111111111..........1111111111..............................1111111111 1111111111..........1111111111..........3333333333..........1111111111 1111111111..........1111111111..........3333333333..........1111111111 1111111111..........1111111111..............................1111111111 1111111111111111111111111111111111111111111111111111111111111111111111 Small Dataset 7: 0 components .... .... .... Small Dataset 8: 1 components 1 Small Dataset 9: 2 components 1111111.2 1.......2 1.2222222 1.......2 1111111.2 1.......2 1.2222222 1.......2 1111111.2 Small Dataset 10: 2 components 11111111111111111 1...1...1...1...1 1.2.1.2.1.2.1.2.1 1.2.1.2.1.2.1.2.1 1.2.1.2.1.2.1.2.1 1.2.1.2.1.2.1.2.1 1.2.1.2.1.2.1.2.1 ..2...2...2...2.. 22222222222222222 Small Dataset 11: 7 components 1..22..33..44..55 ..22..33..44..55. .22..33..44..55.. 22..33..44..55..6 2..33..44..55..66 ..33..44..55..66. .33..44..55..66.. 33..44..55..66..7 Small Dataset 12: 5 components 1111111111111111111111111111111111111111111 1.......................................... 1.11111111111111111111111111111111111111111 1.1.......................................1 1.1.2.11111111111111111111111111111111111.1 1.1.2.1.................................1.1 1.1.2.1.2222222222222222222222222222222.1.1 1.1.2.1.2.............................2.1.1 1.1.2.1.2.2222222222222.1111111111111.2.1.1 1.1.2.1.2.2...........2.1...........1.2.1.1 1.1.2.1.2.2.33..444.2.2.1.111111111.1.2.1.1 1.1.2.1.2.2.........2.2.1.........1.1.2.1.1 1.1.2.1.2.22222222222.2.1...55555.1.1.2.1.1 1.1.2.1.2.............2.1.........1.1.2.1.1 1.1.2.1.222222222222222.11111111111.1.2.1.1 1.1.2.1.............................1.2.1.1 1.1.2.1111111111111111111111111111111.2.1.1 1.1.2.................................2.1.1 1.1.22222222222222222222222222222222222.1.1 1.1.....................................1.1 1.111111111111111111111111111111111111111.1 1.........................................1 1111111111111111111111111111111111111111111 Small Dataset 13: 8 components 1111111111111111111111111111111111111111111111111111111 1.....................................................1 1.222222222222222222222222222222222222222222222222222.1 1.2......................22.........................2.1 1.2.3333333333333333333..222........444444444444....2.1 1.2.3..................3.222...4444444.........444..2.1 1.2.3...5555....66.....3.22...44...........77....4..2.1 1.2.33..55............33.222..4.........888.7...444.2.1 1.2..3........3333333.3..222..444..44444..........4.2.1 1.2..3333333333.....333..22.....4444...444444444444.2.1 1.2......................222........................2.1 1.222222222222222222222222222222222222222222222222222.1 1.....................................................1 1111111111111111111111111111111111111111111111111111111 Dataset 14 illustrates a pattern used in the final large dataset: The general formula for 4k << w: width w input consists of the run length w-1 repeated 4k times, followed by the run 4k, for a total of 4k rows The jth set of 4 rows contains one block on left + 2 sets of 2j-1 1-wide blocks For j = 1, ... k this generates k + 2k^2 components In datset 14 you can see it for w = 20, k = 4 In the final dataset w = 1000000000, k = 200 Small Dataset 14: 36 components ........................1 22222222222222222222222.1 2222222222222222222222.3. .....................2.3. ....................4.5.6 7777777777777777777.4.5.6 777777777777777777.8.9.A. .................7.8.9.A. ................B.C.D.E.F GGGGGGGGGGGGGGG.B.C.D.E.F GGGGGGGGGGGGGG.H.I.J.K.L. .............G.H.I.J.K.L. ............M.N.O.P.Q.R.S TTTTTTTTTTT.M.N.O.P.Q.R.S TTTTTTTTTT.U.V.W.X.Y.Z.a. .........T.U.V.W.X.Y.Z.a. Small Dataset 15: 58 components (generated randomly) 1...2222...2.333.44444.2...2222222222..2 1..22.222.22...3.4.4..2222.22..22.222222 .2222.2.2222222.4444.2.2.2222......22..2 222...22.2...22.4...22222..22.2.5.2.2222 22..6.2222.2...7.222.222..22222..222...2 2222..222222.777.222.2.2.22.222..2.2..22 ..2.88.22..2..77.222222.22.22222.2222222 2222...222.2...77.....222.....2222...222 22.22.2222..9....22.2222222.222.22..2..2 ..22222222...2222222222.222222...22.2..2 ..2.2222.22..2...2..222222..22.....222.. .22.2.22222222...222.2..2.22222.A..2.2.. 2...222..222...222..B.2..C.22222....2222 222..2.222..D.E..2....222.22.222222.2222 2.22.22..22....F.222.22.222222222.222.22 222..2.222......222.222..22..22.2..2.2.2 22.G.22222.2..22222222.HH..222.22.22.22. .22..222..222222222....HH.2222.2.2.2222. I.22.2222222222.2.2.H..HH..2222.222222.J I.22.2222..22222.22.HHHHHH.2222.2....22. .2.22...2.K.2.....2..HHHHHH.22222222.2.2 222222222.KK..LLLL..M...HHH.222222..N.22 222....2....LLLLLL..MM.O..HH..22.222.2.2 2.2.22222.LLLLLLL.LL..P.Q...RR.222222222 2..22.2.22..L.LLLLL..PP.QQQQ....22222.22 2..2..2.2...LLL.L..SS..Q.QQ...222222.T.. 2.22.U.V.WW..LLLLLL..QQQ.QQ.222.22..X.Y. .2222.VV.WW..L.L.L....QQQQQ..2..2..Z..Y. 22..2.VVV..V.LL..L.a.QQ.QQ.2222.222.bb.c .22...V.VVVV..LLLL...Q.....2.2.222..bb.. d...VVV.V.VV..LLLLLLL..e.ee.f.2222.bb.gg d.VVVVV.V...hh.LLL..L..eee.ff..2222.bb.g .VV...V....hhhh.LL..L.eeeee..i.....j.bb. VV.hhh.h.hhh.hhh.LL..ee....k.ii.i....b.l .V..hhhh.h.h.hh.LL.k.e.kkkkk.iiii.m.bb.. n..hhhhhhh.h.h..L.kkk.kkk...k....mm.bbbb .o.hhh.h..hh.hh..p..kkkkkkkkkk..mmm.bb.. oo.h.....hh.q.hhh..kkkkkk.kkk...m...b... o.....hhh.h.q.hhhh.kkk.k..kkkkkk.rrr..ss oo...t.hhhh.qq.h..u.kkk.v..k.kkkk.r.ww.s =============================================================================== 2. screen output from fax.java, showing reduced grids and components, where the grid is small enough. For each dataset there is a parenthetical comment indicating whether the grid is the same as the unreduced version above or how it is reduced. Dataset 1: Orig width :8 Sample input checkerboard ( differing rows get removed) Reduced grid: 4 X 8 with 16 components, final total: 32 1.2.3.4. .5.6.7.8 9.A.B.C. .D.E.F.G Dataset 2: Orig width : 5 (no change) Reduced grid: 3 X 5 with 2 components, final total: 2 .11.2 111.. ..111 Dataset 3: Orig width : 7 (omits one equal row) Reduced grid: 7 X 7 with 3 components, final total: 3 1111111 11....1 111.2.1 1.1...1 1.1.3.1 1.1...1 1111111 Again datasets 4-6 are datasets 1-3 stretched by a factor of 10. The reducing algorithm shows them equivalent to datasets 1-3. Dataset 4: Orig width : 80 (columns removed) Reduced grid: 4 X 8 with 16 components, final total: 32 1.2.3.4. .5.6.7.8 9.A.B.C. .D.E.F.G Dataset 5: Orig width : 50 (columns removed) Reduced grid: 3 X 5 with 2 components, final total: 2 .11.2 111.. ..111 Dataset 6: Orig width : 70 (columns removed) Reduced grid: 7 X 7 with 3 components, final total: 3 1111111 11....1 111.2.1 1.1...1 1.1.3.1 1.1...1 1111111 Dataset 7: Orig width : 4 (reduced rows and columns) Reduced grid: 1 X 1 with 0 components, final total: 0 . Dataset 8: Orig width : 1 (same) Reduced grid: 1 X 1 with 1 components, final total: 1 1 Dataset 9: Orig width : 9 (columns removed) Reduced grid: 9 X 5 with 2 components, final total: 2 111.2 1...2 1.222 1...2 111.2 1...2 1.222 1...2 111.2 Dataset 10: Orig width : 17 (matching rows removed) Reduced grid: 5 X 17 with 2 components, final total: 2 11111111111111111 1...1...1...1...1 1.2.1.2.1.2.1.2.1 ..2...2...2...2.. 22222222222222222 Dataset 11: Orig width : 17 (same) Reduced grid: 8 X 17 with 7 components, final total: 7 1..22..33..44..55 ..22..33..44..55. .22..33..44..55.. 22..33..44..55..6 2..33..44..55..66 ..33..44..55..66. .33..44..55..66.. 33..44..55..66..7 Dataset 12: Orig width : 43 (columns removed) Reduced grid: 23 X 34 with 5 components, final total: 5 1111111111111111111111111111111111 1................................. 1.11111111111111111111111111111111 1.1..............................1 1.1.2.11111111111111111111111111.1 1.1.2.1........................1.1 1.1.2.1.2222222222222222222222.1.1 1.1.2.1.2....................2.1.1 1.1.2.1.2.222222222.11111111.2.1.1 1.1.2.1.2.2.......2.1......1.2.1.1 1.1.2.1.2.2.3.4.2.2.1.1111.1.2.1.1 1.1.2.1.2.2.....2.2.1....1.1.2.1.1 1.1.2.1.2.2222222.2.1..5.1.1.2.1.1 1.1.2.1.2.........2.1....1.1.2.1.1 1.1.2.1.22222222222.111111.1.2.1.1 1.1.2.1....................1.2.1.1 1.1.2.1111111111111111111111.2.1.1 1.1.2........................2.1.1 1.1.22222222222222222222222222.1.1 1.1............................1.1 1.111111111111111111111111111111.1 1................................1 1111111111111111111111111111111111 Dataset 13: Orig width : 55 (columns removed) Reduced grid: 14 X 42 with 8 components, final total: 8 111111111111111111111111111111111111111111 1........................................1 1.22222222222222222222222222222222222222.1 1.2................2...................2.1 1.2.3333333333333..22......44444444....2.1 1.2.3............3.22..44444......444..2.1 1.2.3..55...6....3.2..44.......77...4..2.1 1.2.33.5........33.22.4.......8.7..444.2.1 1.2..3....33333.3..22.444.4444.......4.2.1 1.2..333333...333..2....444..444444444.2.1 1.2................22..................2.1 1.22222222222222222222222222222222222222.1 1........................................1 111111111111111111111111111111111111111111 Dataset 14: Orig width : 25 (left columns removed) Reduced grid: 16 X 17 with 36 components, final total: 36 ................1 222222222222222.1 22222222222222.3. .............2.3. ............4.5.6 77777777777.4.5.6 7777777777.8.9.A. .........7.8.9.A. ........B.C.D.E.F GGGGGGG.B.C.D.E.F GGGGGG.H.I.J.K.L. .....G.H.I.J.K.L. ....M.N.O.P.Q.R.S TTT.M.N.O.P.Q.R.S TT.U.V.W.X.Y.Z.a. .T.U.V.W.X.Y.Z.a. Dataset 15: Orig width : 40 (same) Reduced grid: 40 X 40 with 58 components, final total: 58 1...2222...2.333.44444.2...2222222222..2 1..22.222.22...3.4.4..2222.22..22.222222 .2222.2.2222222.4444.2.2.2222......22..2 222...22.2...22.4...22222..22.2.5.2.2222 22..6.2222.2...7.222.222..22222..222...2 2222..222222.777.222.2.2.22.222..2.2..22 ..2.88.22..2..77.222222.22.22222.2222222 2222...222.2...77.....222.....2222...222 22.22.2222..9....22.2222222.222.22..2..2 ..22222222...2222222222.222222...22.2..2 ..2.2222.22..2...2..222222..22.....222.. .22.2.22222222...222.2..2.22222.A..2.2.. 2...222..222...222..B.2..C.22222....2222 222..2.222..D.E..2....222.22.222222.2222 2.22.22..22....F.222.22.222222222.222.22 222..2.222......222.222..22..22.2..2.2.2 22.G.22222.2..22222222.HH..222.22.22.22. .22..222..222222222....HH.2222.2.2.2222. I.22.2222222222.2.2.H..HH..2222.222222.J I.22.2222..22222.22.HHHHHH.2222.2....22. .2.22...2.K.2.....2..HHHHHH.22222222.2.2 222222222.KK..LLLL..M...HHH.222222..N.22 222....2....LLLLLL..MM.O..HH..22.222.2.2 2.2.22222.LLLLLLL.LL..P.Q...RR.222222222 2..22.2.22..L.LLLLL..PP.QQQQ....22222.22 2..2..2.2...LLL.L..SS..Q.QQ...222222.T.. 2.22.U.V.WW..LLLLLL..QQQ.QQ.222.22..X.Y. .2222.VV.WW..L.L.L....QQQQQ..2..2..Z..Y. 22..2.VVV..V.LL..L.a.QQ.QQ.2222.222.bb.c .22...V.VVVV..LLLL...Q.....2.2.222..bb.. d...VVV.V.VV..LLLLLLL..e.ee.f.2222.bb.gg d.VVVVV.V...hh.LLL..L..eee.ff..2222.bb.g .VV...V....hhhh.LL..L.eeeee..i.....j.bb. VV.hhh.h.hhh.hhh.LL..ee....k.ii.i....b.l .V..hhhh.h.h.hh.LL.k.e.kkkkk.iiii.m.bb.. n..hhhhhhh.h.h..L.kkk.kkk...k....mm.bbbb .o.hhh.h..hh.hh..p..kkkkkkkkkk..mmm.bb.. oo.h.....hh.q.hhh..kkkkkk.kkk...m...b... o.....hhh.h.q.hhhh.kkk.k..kkkkkk.rrr..ss oo...t.hhhh.qq.h..u.kkk.v..k.kkkk.r.ww.s ============================================================================== 3. The remaining input generated large original grids. All were reduced by the general algorithm, though all but one stayed too large to print. In each case the pattern in the input as explained after the screen output lines from the program. When input is described, the notation (#x: ...) is used to indicate the number of repetitions of a single number or group: (4x: 1000) means 1000 1000 1000 1000 (3x: 1 1000) means 1 1000 1 1000 1 1000 When the number of repetitions is large I give an input layout, indicating the number of identical lines in the input. Dataset 16: Orig width : 1000000000 Reduced grid: 500 X 2 with 250 components, final total: 250 width 1000000000 (x1000: 500000000) left half blank 500 alternations on right -> 250 comps Input layout: 125 lines of (8x: 500000) Dataset 17: Orig width : 1000000000 Reduced grid: 500 X 2 with 1 components, final total: 1 width 1000000000 0 1000000000 first line black (x998: 500000000) left half solid, 500 alternations on right -> 1 comp Input layout: row 1: 0 1000000000 (6x: 500000000) 124 rows of (8x: 500000000) Dataset 18: Orig width : 1 Reduced grid: 6 X 1 with 2 components, final total: 1000000000 width 1 (x4: 1000000000) Two 1000000000 sames generate 2*billion blanks, Each billion differents generate .5 billion dots->billion comps way reduced grid: . 1 . . 2 . Dataset 19: Orig width : 1000000000 Reduced grid: 1000 X 1 with 250 components, final total: 250 width 1000000000 (x1000: 1000000000) 500 same runs only increas heights, 500 different runs alternate full black and white lines -> 250 (maximum trillion pixels) input layout: 142 lines of (7x: 1000000000) last line (6x: 1000000000) Dataset 20: Orig width : 1 Reduced grid: 998 X 1 with 250 components, final total: 250 width 1 0 switch to black (x499: 1 1000000000) 499 alternating black and blank vertical lines more than 500 billion rows -> 250 comps input layout: first line: 0 1 (4x: 1000000000 1) 98 lines of (5x: 1000000000 1) last line (4x: 1000000000 1) 1000000000 Dataset 21: Orig width : 998000 Reduced grid: 3 X 998 with 1497 components, final total: 499499 width 998000 0 switch to black (x998: 1000) first row 499 black segments alternating with 499 blank segments 998000000 checkerboard for 1000 more rows -> 499*1001 = 499499 comps input layout: row 1: 0 (15x: 1000) 61 rows: (16x: 1000) last row: (7x: 1000) 998000000 Dataset 22: Orig width : 999000 Reduced grid: 3 X 999 with 1498 components, final total: 499999 width 999000 x999: 1000 first row 500 blank segments around 499 black segments 999000000 checkerboard for 1000 more rows, alternate 500 and 499 black segments -> 501*499 + 500*500 = 499999 input layout: 62 rows: (16x: 1000) last row: (7x: 1000) 999000000 Dataset 23: Orig width : 1000000000 Reduced grid: 800 X 801 with 80200 components, final total: 80200 width 1000000000 See the pattern in dataset 14. (800x: 999999999) jth set of 4 rows contains 1 long block on left 800 + 2 sets of 2j-1 1-wide blocks for j = 1 ... k -> k + 2k^2 comps Here k = 200, 200 + 2*200^2 = 80200 comps