Statistics

Problem Statement for "CoolRectangles"

Problem Statement

You're given several rectangles in the cartesian plane with sides parallel to the coordinate axes. A "cool rectangle" is a rectangle in the plane such that each of its edges completely lies on the edges of some input rectangles (these edges may overlap). You want to "compress" the input rectangles by shrinking them into cool rectangles (this will happen instantaneously).

To compress an input rectangle into a cool rectangle, the interior of the cool rectangle must be completely contained within the input rectangle. The interiors of the chosen cool rectangles must not overlap (though their edges may touch), and each cool rectangle may compress at most one input rectangle. Determine the smallest total area of cool rectangles required to shrink all the input rectangles, or return -1 if it is impossible.

The input rectangles will be described by int[]s x1, y1, x2, and y2, where (x1[i],y1[i]) and (x2[i],y2[i]) are opposite corners of the ith rectangle.

Definition

Class:
CoolRectangles
Method:
compress
Parameters:
int[], int[], int[], int[]
Returns:
int
Method signature:
int compress(int[] x1, int[] y1, int[] x2, int[] y2)
(be sure your method is public)

Constraints

  • x1 will contain between 1 and 30 elements, inclusive.
  • x1, y1, x2, and y2 will contain the same number of elements.
  • Each element of x1, y1, x2, and y2 will be between -10000 and 10000, inclusive.
  • For each rectangle, x1[i] < x2[i], and y1[i] < y2[i].

Examples

  1. {0,1,2}

    {0,1,2}

    {1,2,3}

    {1,2,3}

    Returns: 3

    We have three non-overlapping squares, so the only cool rectangles are the input rectangles.

  2. {0,1}

    {0,1}

    {2,3}

    {2,3}

    Returns: -1

    The overlapping squares generate 3 cool rectangles. However, there is no way to choose 2 non-overlapping cool rectangles to use.

  3. {1,0}

    {1,2}

    {3,4}

    {4,3}

    Returns: 3

    These rectangles intersect in a way that allows for cool rectangles of area 1 and 2 to be used (although there are 11 available cool rectangles).

  4. {0,1,1}

    {0,1,1}

    {2,3,2}

    {2,3,2}

    Returns: -1

  5. {0,-1,-2,-3}

    {0,1,2,3}

    {1,2,3,4}

    {7,6,5,4}

    Returns: 4

  6. {0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-20,-21,-22,-23,-24,-25,-26,-27,-28,-29}

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29}

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30}

    {59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30}

    Returns: 30

    Computationally, this is the worst case.

  7. {-10000}

    {-10000}

    {10000}

    {10000}

    Returns: 400000000

  8. {0,0}

    {0,0}

    {1,1}

    {1,1}

    Returns: -1

  9. {0,-1}

    {0,1}

    {1,2}

    {59,58}

    Returns: 58

  10. {0,-4,-18,-20,-21,-24,-28,-29}

    {0,4,18,20,21,24,28,29}

    {1,5,19,21,22,25,29,30}

    {59,55,41,39,38,35,31,30}

    Returns: 8

  11. {-2,-3,-5,-6,-8,-11,-13,-15,-16,-19,-20,-21,-24,-25}

    {2,3,5,6,8,11,13,15,16,19,20,21,24,25}

    {3,4,6,7,9,12,14,16,17,20,21,22,25,26}

    {57,56,54,53,51,48,46,44,43,40,39,38,35,34}

    Returns: 26

  12. {0,-2,-3,-6,-10,-12,-15,-19,-20,-21,-22,-23,-24,-26,-27}

    {0,2,3,6,10,12,15,19,20,21,22,23,24,26,27}

    {1,3,4,7,11,13,16,20,21,22,23,24,25,27,28}

    {59,57,56,53,49,47,44,40,39,38,37,36,35,33,32}

    Returns: 19

  13. {-2,-3,-4,-5,-8,-16,-18}

    {2,3,4,5,8,16,18}

    {3,4,5,6,9,17,19}

    {57,56,55,54,51,43,41}

    Returns: 36

  14. {-5,-6,-8,-9,-22}

    {5,6,8,9,22}

    {6,7,9,10,23}

    {54,53,51,50,37}

    Returns: 41

  15. {-2,-7,-11,-15,-28}

    {2,7,11,15,28}

    {3,8,12,16,29}

    {57,52,48,44,31}

    Returns: 66

  16. {-2,-29}

    {2,29}

    {3,30}

    {57,30}

    Returns: 32

  17. {0,-7,-8,-13,-15,-19,-26,-29}

    {0,7,8,13,15,19,26,29}

    {1,8,9,14,16,20,27,30}

    {59,52,51,46,44,40,33,30}

    Returns: 11

  18. {-1,-4,-17,-26}

    {1,4,17,26}

    {2,5,18,27}

    {58,55,42,33}

    Returns: 72

  19. { 0, 2 }

    { 0, 1 }

    { 1, 3 }

    { 1, 2 }

    Returns: 2

  20. { 1, 0 }

    { 1, 0 }

    { 2, 1 }

    { 2, 2 }

    Returns: 3

  21. { 1, 0, 0 }

    { 1, 0, 2 }

    { 3, 3, 2 }

    { 3, 4, 3 }

    Returns: 5

  22. {0,0,0,1}

    {0,0,-1,-1}

    {2,2,1,2}

    {2,2,3,3}

    Returns: 6

  23. {3,0}

    {0,3}

    {6,8}

    {3,9}

    Returns: 57

  24. {0,2}

    {0,0}

    {9,5}

    {9,5}

    Returns: -1

  25. {0,3}

    {0,0}

    {9,5}

    {9,5}

    Returns: -1

  26. {0,0}

    {0,0}

    {9,5}

    {9,5}

    Returns: -1

  27. {0,0,3}

    {0,0,0}

    {9,3,100}

    {9,7,7}

    Returns: 81

  28. {0,0,50}

    {0,0,0}

    {100,50,99}

    {100,99,101}

    Returns: 5049

  29. {0,0,50,50}

    {0,0,0,0}

    {100,50,99,100}

    {100,99,101,99}

    Returns: 5099

  30. {587,221,895,109,907,775}

    {684,147,535,633,843,292}

    {1067,512,1410,626,1414,903}

    {8481,7209,1147,4436,1099,8064}

    Returns: 310138

  31. {933,147,305,929,194,580,460,975,18,244,369}

    {762,137,252,13,234,560,769,820,767,457,497}

    {1242,965,622,1692,308,798,567,1896,810,1035,1117}

    {6768,5753,1752,6727,1626,6426,5746,7480,1392,9711,1587}

    Returns: 39009

  32. {59,253,985,786,329,422,351,197,428,26,380,279,240}

    {57,973,783,562,798,375,776,343,651,339,501,392,879}

    {99,329,1846,1326,578,467,928,742,710,286,1330,322,1057}

    {242,6742,8158,6090,7911,5799,4966,8005,6371,5760,652,9528,2509}

    Returns: 157340

  33. {900}

    {878}

    {1220}

    {5082}

    Returns: 1345280

  34. {-123,-661,195,548,-143,388,-584,-161,-378,-746}

    {-364,-7,53,-287,-154,-105,-127,123,3,465}

    {827,-635,775,1417,434,1271,396,-18,-237,157}

    {9270,6452,2858,5857,2678,8277,4752,5781,985,1763}

    Returns: 171960

  35. {417,-59,-604,-465,178,-454,-146,94,256,-11,-172,-458}

    {-557,519,372,290,336,349,-217,145,-14,-156,-562,86}

    {1313,870,-221,334,323,-15,-93,423,516,163,417,75}

    {7668,5657,2587,8232,7661,4450,256,7317,25,4068,203,1083}

    Returns: 80639

  36. {-65,-7,-339,27,-116,-141,-449,296,-242,452,547,114,200,104}

    {576,-252,-565,215,930,-713,-57,-862,-201,561,-423,341,169,-655}

    {421,820,208,789,118,484,-299,665,751,669,1146,483,329,332}

    {1568,6962,1621,2042,9115,167,6762,-27,53,6469,4875,4024,7238,6372}

    Returns: 135315

  37. {250,-616,-103,-613,-487,31,196,188}

    {387,408,-529,84,-234,-530,-319,745}

    {259,-158,843,-256,-348,355,608,338}

    {2589,6473,3955,1372,1300,646,4216,2260}

    Returns: 216625

  38. {-462,-86,762,-628}

    {71,-129,870,649}

    {434,545,922,306}

    {8336,528,1853,8545}

    Returns: -1

  39. {-653,-2546,1677,374,1951,-289,-1993,86}

    {341,-837,1417,794,-1007,473,-176,-1097}

    {-1,-393,3113,2194,2329,2219,-1890,194}

    {1110,441,2230,1124,562,1421,1141,856}

    Returns: 999195

  40. {-1113,2056,1527,1714,1624,1221,-555,-1659,-1412,302}

    {-1852,339,-265,1370,2483,-425,-265,572,416,-492}

    {-515,2112,2766,1817,3571,1285,622,-1366,-493,1631}

    {-1491,1648,-43,2497,5193,1242,-2,1687,435,922}

    Returns: 963355

  41. {33,1883,-1905,-202,913,-591,1649,-778,-2069,867}

    {315,427,-510,-1116,313,-513,-53,-234,620,85}

    {2081,4298,330,1808,2101,964,3925,-107,-1129,1922}

    {1800,759,1547,488,2228,1379,48,2078,1472,2861}

    Returns: 265680

  42. {1968,95,-961,-611,2054,2193,-2832,575,-972}

    {-845,225,-356,714,-1610,1031,-1235,-844,1042}

    {3725,2866,-51,1813,4081,3366,-2421,3471,1653}

    {485,3094,876,1032,-255,3395,1304,1437,3114}

    Returns: 2988678

  43. {1011,-647,134,-2009,875,819}

    {189,-1504,1830,-1383,-319,825}

    {2530,1930,620,-805,1821,1054}

    {1419,1224,2476,203,1982,2943}

    Returns: 2325650

  44. {-1346,690,1700,115,1523,-117,-740,-364,-517}

    {-616,-1696,95,-2389,-1921,147,-672,2125,-139}

    {894,2815,2639,2972,4417,2753,1757,1567,782}

    {-356,-1624,733,-1744,771,1195,1561,2628,886}

    Returns: 2284917

  45. {-740,584,-662,251,-580,-480,-929,-234,1236,47,1986,462,-1371,-1068,401,168,1570}

    {1644,234,2776,-2716,1682,50,-543,1439,-2533,-312,579,2028,-464,-1289,1210,-2098,9}

    {2183,2980,360,599,-128,1022,1767,1946,1720,2710,3131,1961,889,341,1803,1915,3714}

    {4359,3000,3515,-497,2752,1770,1816,1900,-859,1035,2738,4852,2330,-377,3260,-9,1088}

    Returns: 1210620

  46. {131,-192,35,-340,-15,145,-86,235,248,-202,-134,-435,22,143,25,-163,279,-316,-188,-411,-1,-21,370,-17,-167,366,-295,-50}

    {-94,-274,-64,-156,-53,132,403,-58,76,-23,-395,-147,115,-52,166,-178,99,121,-14,192,-106,184,36,-93,312,3,4,-15}

    {241,-57,226,-288,85,295,8,277,396,-71,-36,-391,59,265,120,-133,289,-131,-41,-279,150,171,456,33,-18,417,-125,1}

    {64,-254,11,-129,24,206,519,20,132,95,-252,-22,253,-51,355,-102,202,221,8,273,-28,295,67,3,507,139,167,111}

    Returns: -1

  47. {29,56,131,-278,94,44,188,252,-381,-23,94,-88,140,-313,291,123,398,245,9,-409,-93,416}

    {263,278,-389,-31,-331,-190,-77,-244,46,75,211,32,-38,250,-198,235,-169,78,98,8,-295,42}

    {30,254,289,-192,158,112,218,412,-357,-11,233,27,250,-267,292,207,549,260,209,-375,93,461}

    {368,285,-307,129,-142,-21,22,-81,155,100,297,93,142,358,-6,350,28,96,149,183,-237,86}

    Returns: -1

  48. {-98,-397,-92,197,-278,-168,-174,191,287,-336,-13,-250,-351,34,-26,318,-206,-107,-346,330,-291,-352,71,81,320}

    {5,183,-336,-132,-45,-167,9,64,97,81,-80,-71,-234,-112,-137,343,200,195,321,16,329,-207,-7,266,94}

    {41,-218,39,328,-207,-94,-93,234,403,-230,69,-81,-243,179,170,464,-204,-52,-252,419,-103,-287,198,162,470}

    {29,269,-304,-88,146,-67,75,198,156,116,-8,-46,-93,-10,-72,495,350,207,521,195,473,-22,131,382,109}

    Returns: -1

  49. {215,3,-60,-404,-86,-267,279,-188,-279,351,46,-395,87,228,-249,-96,140,307,102,185,115,43}

    {-8,209,-289,366,6,75,-14,77,-135,-74,69,86,-112,-54,72,-446,349,-57,145,-421,106,127}

    {299,155,127,-333,45,-150,395,7,-181,391,99,-334,120,423,-145,72,257,373,254,197,261,51}

    {27,218,-201,454,132,129,28,262,-121,-60,215,165,-86,6,79,-398,516,-24,175,-373,135,226}

    Returns: 69412

  50. {-57,-460,71,-118,-21,294,111,170,93,120,70,256,-228,-65,-266,15,56,220,-14,-12,-51,140,127,261,129,39,-109,60,-7,-5}

    {58,42,105,-217,-276,334,480,-21,-406,419,-291,-167,40,-63,-384,-283,38,-291,-154,-31,-193,-21,9,-102,296,-135,-417,54,-29,-246}

    {194,-369,72,102,261,423,402,179,344,167,135,479,-109,250,-193,114,69,461,42,-4,110,476,297,270,210,77,85,118,80,323}

    {109,360,287,-180,-184,462,830,65,-352,434,-19,178,141,66,-227,-220,256,-76,-43,317,-182,245,153,40,497,-9,-167,125,216,-115}

    Returns: 86155

  51. {276,152,66,-238,-136,33,209,-346,25,70,-314,-193}

    {-163,-212,-66,-10,282,-301,-370,55,-250,165,-28,-78}

    {494,438,177,-42,-130,260,549,-280,332,228,-199,129}

    {133,107,184,307,554,-148,-166,276,-228,166,86,-58}

    Returns: 55292

  52. {-370,1,344,-167,-381,-59,133,-152,100,-302,332,-48,52,427,-175,-185,71,-48,-9,361,-107,27,-235,-149,-290,348,-36,36,38,76}

    {56,-95,144,-311,-225,-145,1,-224,-84,179,43,-119,-169,374,-57,124,294,-114,232,-162,289,137,24,-191,5,-213,77,-7,-107,-77}

    {-261,183,376,-118,-288,111,258,153,379,-80,498,296,356,562,-145,-164,182,75,117,631,25,159,-167,145,-239,585,118,144,93,315}

    {181,85,340,-237,-47,73,52,95,84,301,154,93,147,574,-56,431,586,158,482,-86,525,350,122,-144,238,-65,420,319,-41,-56}

    Returns: 63677

  53. {9,-53,-85,-3,61,-86,3,-48,22,-25,30,-19,24,25,-4,0,45,-17,68,74,12,-20,-27,-71,0,-62,42,-11,-12,-5}

    {-57,38,-19,-15,-20,27,-1,-41,-48,25,-57,-36,-34,24,47,56,-50,21,-55,83,-28,-75,-39,3,-25,46,16,-26,-32,-24}

    {27,-24,-45,25,93,-46,15,-44,42,17,78,30,56,38,4,23,89,8,118,84,22,-6,0,-23,6,-25,61,26,-8,16}

    {-18,84,-6,26,-6,34,36,-14,-41,41,-25,-33,-30,31,51,76,-32,66,-38,114,-5,-45,-37,22,-10,71,37,-9,-6,5}

    Returns: -1

  54. {0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-20,-21,-22,-23,-24}

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24}

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}

    {49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25}

    Returns: 25

  55. {0,-1,-2,-3,-4,-8,-6,-7,-8,-9,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-20,-21,-26,-23,-2}

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24}

    {1,2,3,4,5,6,7,8,9,10,15,12,13,14,15,26,17,18,19,20,21,22,23,24,25}

    {49,48,47,96,45,44,13,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,100}

    Returns: 25

  56. {0,-1,-2,-9,-4,-8,-6,-7,-8,-9,-10,-11,-12,-13,-14,-15,-16,-17,-18,-500,-20,-21,-26,-23,-2}

    {0,1,2,3,4,5,6,7,8,9,10,11,11,13,14,15,16,17,18,19,20,21,22,23,24}

    {1,2,3,4,3,6,7,8,9,5,15,12,13,14,15,26,17,18,0,20,21,22,25,24,25}

    {49,48,47,96,45,44,13,42,41,40,39,38,37,36,25,34,33,32,31,30,29,28,99,26,100}

    Returns: 25

  57. {0,-1,-2,-9,-4,-8,-6,-7,-8,-9,-5,-11,-12,-13,-14,-15,-16,-17,-18,-500,-20,-21,-26,-23,-2}

    {0,1,2,3,4,5,2,7,8,9,10,11,11,13,14,15,16,17,18,11,20,21,22,20,23}

    {1,2,3,1,3,6,7,8,9,5,15,12,13,14,15,26,17,18,0,20,21,22,25,24,25}

    {49,48,23,96,45,44,13,42,41,20,39,38,37,36,25,34,33,32,29,30,29,28,99,26,100}

    Returns: 25

  58. {0,-111,-20,9,4,-15,-6,-7,8,-94,-25,-118,-132,-123,-1,15,16,-17,-1815,-500,-20,21,-26,-2}

    {0,1,2,3,-4,5,2,7,8,-9,4,11,211,13,15,15,-10,17,18,11,20,-21,232,20}

    {1,12,13,10,23,566,7,118,19,15,15,1122,135,14,15,26,17,18,0,220,121,232,25,3524}

    {49,348,23,96,45,44,13,242,421,20,39,38,307,36,25,25,133,32,291,30,29,28,999,26}

    Returns: 125

  59. {0,-111,-20,9,4,-15,-6,-7,8,-94,-25,-118,-132,-123,-1,15,16,-17,-1815,-500,-20,21,-26,-2,0}

    {0,1,2,10,-4,5,2,7,8,-9,4,11,211,13,15,15,-10,17,18,11,20,-21,232,20,0}

    {1,12,13,10,23,566,7,118,19,15,15,1122,135,14,15,26,17,18,0,220,121,232,25,3524,1}

    {49,348,23,96,45,44,13,242,421,20,39,38,307,36,25,25,133,32,291,30,29,28,999,26,100}

    Returns: 126

  60. {0,-111,-20,9,4,-15,-6,-7,8,-94,-25,-118,-132,-123,-1,15,16,-17,-1815,-500,-20,21,-26,-2,0,-50}

    {0,1,2,10,-4,5,2,7,8,-9,4,11,211,13,15,15,-10,17,18,11,20,-21,232,20,0,15}

    {1,12,13,10,23,566,7,118,19,15,15,1122,135,14,15,26,17,18,0,220,121,232,25,3524,1,5}

    {49,348,23,96,45,44,13,242,421,20,39,38,307,36,25,25,133,32,291,30,29,28,999,26,100,125}

    Returns: 127

  61. {0,-111,-20,9,4,-15,-6,-7,8,-94,-25,-118,-132,-123,-1,15,16,-17,-1815,-500,-20,21,-26,-2,0,-50,-23}

    {0,1,2,10,-4,5,2,7,8,-9,4,11,211,13,15,15,-10,17,18,11,20,-21,232,20,0,15,-1}

    {1,12,13,10,23,566,7,118,19,15,15,1122,135,14,15,26,17,18,0,220,121,232,25,3524,1,5,2}

    {49,348,23,96,45,44,13,242,421,20,39,38,307,36,25,25,133,32,291,30,29,28,999,26,100,125,200}

    Returns: 128

  62. {0,-111,-20,9,4,-15,-6,-7,8,-94,-25,-118,-132,-123,-1,15,16,-17,-1815,-500,-20,21,-26,-2,0,-50,-23,-1,9,-10}

    {0,1,2,10,-4,5,2,7,8,-9,4,11,211,13,15,15,-10,17,18,11,20,-21,232,20,0,15,-1,-100,3,6}

    {1,12,13,10,23,566,7,118,19,15,15,1122,135,14,15,26,17,18,0,220,121,232,25,3524,1,5,2,200,1000,569}

    {49,348,23,96,45,44,13,242,421,20,39,38,307,36,25,25,133,32,291,30,29,28,999,26,100,125,200,109,109,1001}

    Returns: 130

  63. { 1, 0, 2 }

    { 1, 0, 0 }

    { 3, 4, 3 }

    { 3, 3, 2 }

    Returns: 5

  64. { 1, 0, 2, 2}

    { 1, 0, 0, 2}

    { 3, 4, 3, 3}

    { 3, 3, 2, 3}

    Returns: 5

  65. { 1, 0, 2, 2, 2}

    { 1, 0, 0, 2, 0}

    { 3, 4, 3, 3, 3}

    { 3, 3, 2, 3, 3}

    Returns: 8

  66. { 1, 0, 2, 2, 2, 3}

    { 1, 0, 0, 2, 0, 0}

    { 3, 4, 3, 3, 3, 4}

    { 3, 3, 2, 3, 3, 3}

    Returns: -1

  67. { 1, 0, 0, 2}

    { 1, 0, 2, 2}

    { 3, 3, 2, 3}

    { 3, 4, 3, 3}

    Returns: 5

  68. { 1, 0, 0, 2, 0}

    { 1, 0, 2, 2, 2}

    { 3, 3, 2, 3, 3}

    { 3, 4, 3, 3, 3}

    Returns: 8

  69. { 1, 0, 0, 2, 0, 0}

    { 1, 0, 2, 2, 2, 3}

    { 3, 3, 2, 3, 3, 3}

    { 3, 4, 3, 3, 3, 4}

    Returns: -1

  70. {2,1}

    {-1,2}

    {3,4}

    {6,3}

    Returns: 2

  71. {-1,2}

    {2,1}

    {6,3}

    {3,4}

    Returns: 2

  72. {0,30,60}

    {0,-1,-1}

    {100,31,61}

    {1,2,2}

    Returns: 3

  73. {0,30,60,0}

    {0,-1,-1,0}

    {100,31,61,100}

    {1,2,2,1}

    Returns: 4

  74. {0,30,60,0,30,30}

    {0,-1,-1,0,-1,1}

    {100,31,61,100,61,61}

    {1,2,2,1,0,2}

    Returns: 6

  75. {0,1,0,1}

    {0,0,1,1}

    {1,2,1,2}

    {1,1,2,2}

    Returns: 4

  76. {0,1,0,1,0}

    {0,0,1,1,0}

    {1,2,1,2,2}

    {1,1,2,2,2}

    Returns: -1

  77. {0,1,0,1,0}

    {0,0,1,1,0}

    {1,2,1,2,3}

    {1,1,2,2,2}

    Returns: 6

  78. { 1, 0, 0, 0, 0}

    { 1, 0, 2, 1, 0}

    { 3, 3, 2, 2, 3}

    { 3, 4, 3, 3, 4}

    Returns: 6

  79. { 1, 0, 0, 0, 0, 1}

    { 1, 0, 2, 1, 0, 1}

    { 3, 3, 2, 2, 3, 3}

    { 3, 4, 3, 3, 4, 3}

    Returns: 9

  80. {-37,11,-39,12,-37,74,-6,49,-58}

    {25,-20,-74,36,-5,-13,15,39,18}

    {-15,28,7,46,1,75,0,63,-25}

    {75,0,-51,67,42,7,28,81,50}

    Returns: 3488

  81. {75,12,-55,-37,3,75,47,-26,-25,-68,25,18,24,-40,2,-1,-45,-65,-6,-12,-56,-72,-12,-25,-29,-42,53,-25}

    {64,7,25,36,-52,28,-8,1,-15,-24,72,12,28,-22,63,-18,-71,-85,66,-1,2,11,41,-44,15,-10,33,12}

    {93,50,-53,-12,53,118,88,-11,-9,-21,51,63,33,-10,10,9,-23,-25,-5,32,-29,-63,-9,16,10,-11,67,7}

    {78,50,52,61,-22,52,32,43,22,-2,99,21,39,-17,113,-11,-26,-83,85,3,51,60,43,-29,41,38,47,50}

    Returns: 3114

  82. {28,46,5,9,-9,79,45,-2,-2,6,10,7,3,-29,49}

    {-38,42,-4,79,79,27,-47,-5,0,34,-32,-24,-12,6,79}

    {61,94,27,41,34,121,73,41,30,23,49,51,21,-6,66}

    {11,86,11,101,119,60,-19,24,24,59,13,-21,-3,20,99}

    Returns: 2145

  83. {-12,-5,-63,8,-17,-20,-2,24,-16,-7,-30,61}

    {48,18,43,78,31,-26,30,9,-84,27,17,-19}

    {17,14,-35,30,-14,13,14,69,-2,43,-21,97}

    {61,35,65,94,56,11,35,38,-55,29,37,-12}

    Returns: 3639

  84. {41,-71,-4,6,72,-16,-4,0,-46,18,6,2,-32,-26,-27,-23,-17,-7,8,-76,2}

    {46,1,-35,-30,-37,-79,91,-49,32,-16,-36,-2,69,-11,2,-41,22,17,17,24,5}

    {83,-44,43,35,118,16,-1,25,-14,38,29,36,-29,-10,6,-5,-16,16,52,-64,4}

    {94,19,-25,-17,-4,-33,136,-32,48,-11,2,-1,109,20,34,-10,52,54,62,63,17}

    Returns: 3661

  85. {2,57,4,25,-52,75,-71,38,-87,38,24,-78,-29,-11,24}

    {-52,-36,44,10,27,-53,61,-8,-66,8,71,53,16,-54,-30}

    {51,102,37,65,-16,120,-70,74,-80,86,32,-31,4,-4,55}

    {-14,-10,89,58,38,-24,87,18,-17,46,90,56,34,-29,5}

    Returns: -1

  86. {-80,35,4,72,57,6,-4,-11,-94,6,24,-18,-7,-39,-19,-7,-43,-59,-36,56,29,25,56,47}

    {-49,51,28,-3,-28,-2,-8,26,77,-50,-7,-1,-54,-19,-64,23,69,-16,-65,57,73,61,5,-6}

    {-33,58,38,77,75,29,9,19,-51,40,43,8,28,5,-4,27,-22,-20,-5,58,79,67,67,79}

    {-15,92,52,18,-20,36,39,35,105,-49,2,15,-31,-9,-43,59,74,-2,-23,71,114,101,14,-4}

    Returns: 2381

  87. {-58,-40}

    {3,39}

    {-12,9}

    {33,45}

    Returns: 1674

  88. {-100,50}

    {-100,50}

    {-50,100}

    {-50,100}

    Returns: 5000

  89. {28,-59,-25,-11,27,-20,6,29,-75,73,-40,-81,-7,31,-8,-18,28,-36,67}

    {-71,54,-14,-25,-67,-36,-4,76,51,49,22,-89,14,38,-62,-44,16,46,3}

    {73,-48,7,1,39,25,55,65,-58,92,-36,-33,11,55,4,23,50,-11,101}

    {-25,64,35,-7,-18,5,-1,126,97,52,52,-48,38,44,-19,-12,31,82,52}

    Returns: -1

  90. {-51,-13,-48,63,56,68,-2,16,-6,56,1,-43,54,-22,23,77,24,-40,-39,42,-31,4}

    {18,6,38,74,-29,-18,-19,-17,6,-44,-68,6,-30,76,47,13,-18,15,-25,26,16,10}

    {-19,28,-43,70,75,69,45,36,2,68,50,-39,70,1,32,83,45,-23,-11,86,-16,10}

    {33,45,39,124,-26,3,1,5,53,-30,-53,12,7,126,63,31,0,43,23,55,44,46}

    Returns: 3238

  91. {47,1,36,-72,-24,63,24}

    {78,-74,-9,7,10,15,-12}

    {55,47,39,-36,16,85,71}

    {105,-48,9,45,13,22,3}

    Returns: 3108

  92. {12,1,19,80}

    {17,-47,-9,6}

    {15,18,28,107}

    {58,0,14,38}

    Returns: 1993

  93. {21,-19,-74,0,-7,7,-39,20,-18,-26,-26,-57,-19,-31,-27,-43,39,-31,3,31,-21,20,18,-6,10,26,3,64}

    {-34,14,18,45,26,-17,-65,-41,28,13,-53,34,-28,-35,-4,-14,83,-11,6,-54,54,-33,7,65,-51,2,-33,-51}

    {30,16,-29,38,32,34,-7,43,8,11,8,-28,18,15,-17,-21,52,7,27,79,-19,48,63,6,59,61,42,81}

    {-3,20,26,62,43,29,-43,-13,78,44,-8,40,10,-33,41,30,98,29,31,-28,98,-21,9,103,-12,8,1,-39}

    Returns: 1068

  94. {-48,4,21,-31,-10,-26,63,-14,10,36,3,-65,-22,-6,-18,3,24,-31,-76,24,-73}

    {-29,-73,58,-18,52,11,23,-61,-45,-31,-19,19,-11,-19,14,-8,-43,-23,11,0,-43}

    {2,25,31,-24,8,-7,71,34,31,68,20,-43,-12,26,14,49,50,-13,-58,65,-55}

    {3,-45,90,11,82,43,58,-28,-20,-5,27,49,11,5,25,27,-13,-13,34,41,-8}

    Returns: -1

  95. {-48,-62,-20,13,-23,-22,62,62,-19,-39,-60,24,-42,-45,-19,22,15,17,6,-35,1,30,85,-79,-7,-27,-24,-21,0,-14}

    {-30,-36,-20,74,-17,10,84,-18,21,-74,-72,-17,49,9,30,-49,-21,56,24,31,-77,-4,-18,56,20,41,-62,-58,44,20}

    {-33,-33,9,29,-12,-4,107,88,18,-38,-29,44,-23,-21,23,61,47,21,17,4,51,64,110,-64,2,2,20,11,42,5}

    {-13,-7,2,101,22,49,109,2,33,-47,-57,7,70,40,64,0,17,74,46,32,-54,37,28,79,70,58,-48,-53,59,65}

    Returns: -1

  96. {70,-36,30,-41,-62,-43,-19,-35,-26}

    {21,0,64,-39,29,-40,16,68,-40}

    {82,-29,61,-10,-16,3,-13,-15,-3}

    {34,44,65,10,65,9,62,70,1}

    Returns: 1146

  97. {1,-65}

    {-20,-35}

    {5,-23}

    {-5,-19}

    Returns: 732

  98. {-90,-86,-69,0,59,-33,19,16,9,-35,38,-5,27,-37,-1,36,-26,9,-17,-10,28,-52,-59,-13,-24,24}

    {28,-74,-17,37,18,16,26,-10,-58,-52,-10,18,-58,16,86,21,1,58,47,-34,45,14,51,-42,-13,-19}

    {-79,-76,-37,14,73,17,48,22,49,-24,46,-2,50,2,43,64,-12,11,24,8,40,-48,-37,28,1,69}

    {33,-49,-6,82,46,35,66,6,-10,-35,29,30,-20,49,126,67,27,71,64,6,85,41,54,-35,-10,-12}

    Returns: 3913

  99. {-58,37,26,17,-45,33,-28,34,-15,-71,19,-65,-29,-14,-91,-67,-42,57,4,-16}

    {-18,-9,23,74,-56,-10,14,-29,69,4,-25,2,59,-68,4,79,27,-1,51,-26}

    {-56,83,75,50,-2,75,-23,64,20,-66,61,-20,17,12,-75,-65,-13,89,39,-5}

    {-12,37,60,82,-13,-7,17,-10,92,16,15,38,82,-63,10,115,69,34,65,-20}

    Returns: -1

  100. {21,59,22,-64,-48}

    {41,9,15,58,70}

    {63,90,37,-60,-23}

    {49,29,29,76,76}

    Returns: 1388

  101. {12,-51,-13,-41,4,16,-10,9}

    {-16,-84,-19,1,20,-7,6,-1}

    {27,-21,7,-34,25,35,-7,12}

    {21,-71,-13,29,67,15,20,38}

    Returns: 1054

  102. {1,1,1}

    {0,0,1}

    {2,3,3}

    {2,1,2}

    Returns: 3

  103. {1,1,1,1}

    {0,0,1,0}

    {2,3,3,3}

    {2,1,2,2}

    Returns: 4

  104. {4,32,-25,59,40,-67,63,-45,64,15,10,-50,17,-66}

    {-3,34,-16,45,73,0,1,-72,4,-42,-71,73,51,-77}

    {52,74,8,100,78,-60,111,-1,93,39,29,-40,64,-63}

    {11,55,17,78,120,13,39,-46,7,-15,-27,89,62,-67}

    Returns: -1

  105. {-30,-11,-1,-76,33,2,10,71,-69,15,15,-24,-49,-26,-20,-53,38,-53,43,-11,-40}

    {11,-43,-49,22,-74,32,-74,42,82,-22,-39,18,9,57,35,-29,-28,-22,51,11,12}

    {-23,4,13,-46,83,9,31,116,-62,18,60,-14,-46,5,-19,-45,67,-26,61,36,-30}

    {49,-20,-8,69,-39,33,-59,58,93,24,1,46,20,89,57,8,-8,-16,76,47,54}

    Returns: 6951

  106. {10,57,-12,-32,65,-44,1,-2,42,-26,29,-49,-29,-49,-58,0,20,-23,12,-33,52}

    {-32,0,48,6,-16,37,-77,-32,-4,1,6,-6,59,3,5,26,15,-13,52,-93,-36}

    {50,67,33,-28,91,-32,11,0,51,-19,30,-34,17,-33,-48,24,48,17,57,-14,70}

    {13,2,61,54,3,48,-59,11,27,22,9,5,83,45,27,48,37,34,91,-56,-4}

    Returns: 2138

  107. {-76,-426,-7,-91,-365,-783,-200,76,-78,-137,11,383,-237,717}

    {2,-605,-60,-59,300,28,274,-81,647,-791,-250,-821,301,-185}

    {589,173,383,17,-243,-132,319,188,547,45,659,839,405,1117}

    {29,-179,-15,527,671,361,449,587,1255,-737,164,-268,406,531}

    Returns: 954398

  108. {-597,-156,488,-22,-270,184,-147}

    {-543,361,-719,425,278,-345,662}

    {-341,579,744,508,-267,327,296}

    {-215,810,-447,871,765,324,900}

    Returns: 301558

  109. {215,-254,371,-270,423,-63,-342,114,-916,-286,351,-171,46,83,252,161,-370,1,-204,601,768,-508,79,321,-158,-776}

    {296,35,-524,-224,-671,-399,139,-588,689,609,-120,-778,187,739,-29,68,-270,-374,783,-653,499,-10,-746,-540,598,-80}

    {617,52,483,-252,936,571,39,204,-715,224,800,168,186,571,968,186,217,64,-63,1255,784,-469,183,785,242,-114}

    {388,757,-148,16,-501,-376,152,-367,876,1235,272,-597,660,1184,236,98,369,-300,1328,-495,1020,474,-407,-100,663,31}

    Returns: 208423

  110. {985,223,620,224}

    {199,-26,-189,-288}

    {1536,407,634,309}

    {837,359,68,-223}

    Returns: 431501

  111. {755,348,221,-281,-256,-905,-904,369,-281,-551,-698,44,-54}

    {103,-86,795,352,-181,-297,49,82,-329,-11,73,-190,-351}

    {1103,807,886,269,326,-465,-200,644,-211,-168,-380,337,289}

    {537,315,1331,640,-18,445,155,567,416,643,797,-34,-17}

    Returns: 528019

  112. {1,2,2,3}

    {2,1,3,2}

    {2,3,3,4}

    {3,2,4,3}

    Returns: 4

  113. {1,2,2,3,0}

    {2,1,3,2,0}

    {2,3,3,4,5}

    {3,2,4,3,5}

    Returns: 5

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: