Summary of Test Data Characteristics for Rivers (IOI 2005, Day 2) ======= == ==== ==== =============== === ====== # n k wL wH iH i0 eH dL dH rdH Answer Remarks --- --- -- -- ---- -- -- --- --- ---- ----- ------- ------- 0 4 2 1 10 2 2 3 1 10 16 4 Example --- --- -- -- ---- -- -- --- --- ---- ----- ------- ------- 1 10 5 5 39 2 3 7 4 49 239 1422 random 2 15 6 15 85 3 6 5 4 96 368 21535 random 3 20 9 31 951 4 12 5 1 895 3173 853242 random 4 10 7 15 98 4 6 3 4 96 191 3260 indegree(0) = 4 5 15 4 89 998 4 8 4 133 895 1842 2337134 indegree(0) = 4 6 20 15 0 10 6 10 4 321 9854 22706 13837 indegree(0) = 6 7 7 3 0 10 2 4 3 302 8839 26332 15855 balanced iH-ary tree 8 10 6 92 9550 2 6 3 2 10 18 50254 balanced iH-ary tree 9 20 4 72 981 1 1 20 180 952 10741 6586110 one river 10 20 11 64 988 3 14 3 3 96 167 71823 balanced iH-ary tree --- --- -- -- ---- -- -- --- --- ---- ----- ------- ------- 50% boundary 11 40 10 0 98 5 23 6 5 99 344 58513 random 12 50 30 1 98 6 24 6 2 100 294 16472 random 13 60 40 2 100 7 28 6 6 99 409 15377 random 14 100 50 0 10 7 51 8 1 1000 5276 52817 random 15 70 34 2 995 10 37 6 1 100 304 382375 indegree(0) = 10 16 80 44 2 995 10 40 7 1 100 346 328796 indegree(0) = 10 17 100 50 2 100 30 53 5 23 979 2856 534900 indegree(0) = 30 18 80 39 1 98 7 69 3 1 1000 2679 583120 balanced iH-ary tree 19 100 50 92 9698 8 88 3 1 10 20 560117 balanced iH-ary tree 20 100 50 1 100 1 1 100 1 100 4859 53769 one river --- --- -- -- ---- -- -- --- --- ---- ----- ------- ------- # n k wL wH iH i0 eH dL dH rdH Answer Remarks where # = case/run identifier n = number of villages in addition to Bytetown (input) k = number of sawmills to be built (input) wL = minimum (highest) number of trees cut near a village wH = maximum (lowest) number of trees cut near a village iH = maximum (highest) indegree of the villages (incl. Bytetown) i0 = number of villages with indegree 0 (leaves) eH = maximum (highest) number of edges to Bytetown (root) dL = minimum (lowest) distance between adjacent villages dH = maximum (highest) distance between adjacent villages rdH = maximum (highest) distance to Bytetown (root) Max. score per case: 5 points