Statistics

Problem Statement for "RoadWork"

Problem Statement

Federal repaving contracts have been awarded to various contractors to fix a number of sections of the nation's highway system. Each contract specifies a single section, giving its starting and ending location. The number of feet of highway in that section is the ending location minus the starting location. For example, a section whose start is 2000 and whose end is 2001 is just one foot long. We need software to protect the public from the possibility that contracts might be granted for overlapping sections, leaving the government to pay multiple times for fixing that part.

We want a program that will examine the contracts and will tell us how many feet of highway have been included in more than one contract. Create a class RoadWork that contains a method fraudFeet that takes int[] start and int[] end as input and returns the number of feet of highway that are included in more than one contract. Corresponding elements of start and end give the starting and ending location of a contract.

Definition

Class:
RoadWork
Method:
fraudFeet
Parameters:
int[], int[]
Returns:
int
Method signature:
int fraudFeet(int[] start, int[] end)
(be sure your method is public)

Notes

  • Keep in mind that the highways can potentially be very long (2,000,000,000 feet) and that your program must run in 8 seconds, and use less than 64 MB of memory.

Constraints

  • start contains between 1 and 50 elements inclusive
  • end contains the same number of elements as start
  • each element of end is greater than the corresponding element of start
  • each element of start and end is between 0 and 2,000,000,000 inclusive

Examples

  1. {50,50,50}

    {58,58,60}

    Returns: 8

    All three contracts cover the section from 50 to 58

  2. {171234,12,20,30}

    {171236,20,30,40}

    Returns: 0

  3. {12,32,92}

    {991,161,1093}

    Returns: 959

    32 to 92 is covered by the first 2 contracts, 92 to 161 is covered by all the contracts, and 161 to 991 is covered by the first and last contract. The answer is (92-32) + (161-92) + (991-161)

  4. {2,1,3}

    {3,3,7}

    Returns: 1

  5. {75,175,275}

    {180,178,1000}

    Returns: 3

  6. {0, 1923000111}

    {1923222111,2000000000}

    Returns: 222000

  7. {2000,1000,7}

    {1000000000,2003,908}

    Returns: 3

  8. {29, 290, 2}

    {29212,3000,35}

    Returns: 2716

  9. { 1000000005, 1000000001, 1000000000}

    { 1000000011, 1000000004, 1000000019 }

    Returns: 9

  10. {1709552293,387021492,649905243,683525168,21709014,166707373}

    {1796097038,609009555,1263730672,888365412,1059572095,1270280624}

    Returns: 1097023299

  11. {1007329316,62249131,366912071,814912262,522097146,1161070548,85411943,636883235,516991041,880035067,89755303,894987862,427532972,366202782,1122739784,233095489,1119449206,90253616,303771747,351026505,586390879,227402426,1382869108,272847461,47738039,1290533356,34373292,182142632,215823336,889875693,342355173,298483519,90320700,929071626,1014814526,625959471,120116728,92248544,1066219079,688417460,1483697437,624806546,899733488,629908341,751224104,960654762,849291703,1586488084,1460817897,931570225}

    {1886858647,1187528001,1410293004,1985820179,808673292,1964499171,1299618767,1055353233,849566357,1632626461,973617117,1813143931,701677784,1490290777,1741965241,1741458813,1544656745,1234921945,1000415311,1338990491,1356392465,1751921909,1549860377,797558624,1860446917,1800924436,166908401,1936273036,1069806583,1565215929,575061625,445057568,964419734,1006516600,1552554992,962470085,1750680325,620444469,1373300359,1822163585,1713146900,1642390868,1826759997,1038239433,1902297928,1540601842,1711840071,1845434150,1631018142,1768585719}

    Returns: 1916761132

  12. {1000000007,1000000001,1000000001,1000000003,1000000009,1000000005}

    {1000000008,1000000015,1000000012,1000000017,1000000018,1000000012}

    Returns: 16

  13. {6}

    {195}

    Returns: 0

  14. {13,16,1,6,6,20,39,3}

    {38,48000000,22,17,7,34,42,21}

    Returns: 38

  15. {1,2,3,4,5,6,7,8}

    {2,3,4,5,6,7,8,9}

    Returns: 0

  16. {1718493625,1582535148,722330455,572829729,1138357336,54238927,30420105,1752770750,26021204,199749176,1657209031,1402077089,25259875,137980945,447692329,497862542,59945468,330562249,153871582,112356626,1259761854,167153941,541033686,589058120,86572261,477146570,83415932,1345824859,230559775,587423914,1794910545,543278968,995000886,364894916,428483104,886069823,1217551079,128767224,476633818,384598431,1751646010,651761881,331295496,139020139,689204031,14707864,6337731,272894105,223442602,475330795}

    {1833857279,1868353920,1167101544,1116252118,1640331853,1730597915,773757557,1915826320,620827014,1639048324,1711078253,1719809623,1637424654,1697948149,1349655764,1739885580,153230762,911540621,1492973032,1081420131,1923204399,1712313100,1427724791,685531208,1413461610,584365474,1083872043,1957310646,1630876330,591040062,1921444925,568620690,1529073148,1473198451,1643084577,1764352194,1515794329,1103388646,1127963231,758272590,1923618060,1247564340,1233112937,721243864,1258870826,985218855,564448292,542734355,1711287799,1200691945}

    Returns: 1908910196

  17. {227130708, 632067356, 1481760506, 1755018689, 564180258, 191573561, 1255452275, 873509538, 233951664, 662832089, 1250106745}

    {231912158, 1076051137, 1659154729, 1945390791, 1623645173, 1205227354, 1825923466, 1309785876, 1047072002, 1838768858, 1879387104}

    Returns: 1650216890

  18. {464293638, 1840284986, 539410942, 1165428111, 1156971219, 585944469, 385101957, 1771674842, 256041599, 620722497, 1830487933, 975428873, 323029182, 411425693}

    {906422999, 1903057967, 1202289049, 1373109565, 1683612203, 1291967424, 1358737953, 1839102116, 1645287192, 1612452589, 1940876983, 1496883988, 1117790506, 664710958}

    Returns: 1393645174

  19. {993032259, 144292128, 1764838712, 1627201254, 1050878313}

    {1274383466, 1932728057, 1775221894, 1709965643, 1635369959}

    Returns: 727316566

  20. {566452864, 504149087, 1722407479, 1158898451, 1661022289, 825697966, 1441294187, 774297883, 138209565, 1290255719, 52894329, 763093042, 1605550584, 260248241, 1545030332, 596651633, 626474840, 1208578616, 1488525023, 1501762642, 104188324, 1767579494, 884524176, 247442614, 281888812, 1474375824, 569558256, 632059223, 367126878, 1345472158, 1436155738, 53584409, 288125085, 913375481, 226821093}

    {1871571261, 1685468739, 1725244670, 1462018032, 1721666370, 1876875174, 1590581113, 1481165295, 1506178428, 1856187022, 758261462, 1153369454, 1714885680, 669238610, 1726274979, 1161094862, 733053394, 1209879086, 1831374428, 1554041732, 110048756, 1924173051, 1132107244, 341702754, 803586092, 1636253461, 1414807896, 1771392046, 486634466, 1723613081, 1873711178, 1694279738, 1220643760, 993199892, 1490658740}

    Returns: 1823290765

  21. {564199412, 1259437085, 1477116774, 1582942672, 685460084, 723351254, 1327585932, 408096162, 1943216311, 308902589, 1425670784, 307474203, 1582834313, 70141538, 1403113736, 427138740, 62088386, 522878503, 207513166, 736797670, 1124786478, 1970049172, 1011947521, 1051520209, 782721059, 1737357616, 568081001}

    {987665483, 1577163325, 1780177010, 1616974536, 1328120353, 1914550126, 1374711493, 1281736943, 1957888058, 1027938976, 1663123581, 1499828087, 1790067018, 227141993, 1490335014, 1019708070, 1466927837, 1950607171, 703084279, 1363192862, 1297510742, 1972559499, 1366469461, 1554021082, 1210621083, 1965574964, 1293501428}

    Returns: 1887746520

  22. {1984635708, 709042858, 1895217239, 447078283, 1931319568, 1501585786, 442426422, 362784750, 1657107018, 929860846, 1195167017, 647446512, 1262799901, 1326841443, 1866737419, 1848323196, 1619725854, 458476154, 8482896, 956545337, 356617676, 1706399252, 1138825760, 1115764813, 788997335, 1991974434, 1693706663}

    {1987718225, 1767311898, 1918691870, 1952934708, 1985710075, 1625530343, 536296285, 852203376, 1837289545, 1478966929, 1318326237, 758273624, 1339536904, 1635100601, 1970498232, 1904721853, 1733769125, 783774142, 1511085349, 1502639839, 1130680183, 1895857648, 1459213756, 1973246530, 1958918775, 1993313000, 1957001431}

    Returns: 1617703221

  23. {1499496653}

    {1668135693}

    Returns: 0

  24. {449483869, 1931249777, 213301285, 172594326, 1356275515, 423463718, 1184608996, 904578703, 1327680720, 267791374, 1289684005, 474887570, 1284514911, 1651320854, 483855553, 1358298860, 200973792, 1900469984, 987839765, 1522787744, 140737521, 648956894, 1689627528, 675194941, 589095527, 256869363, 533799087, 511900254, 588904038, 113645332, 1656077988, 1857312980, 1688189518, 1957776747, 520936793, 72992679, 1207209778, 1846049940, 820066881}

    {1595746015, 1989602604, 1678004027, 1903997642, 1552839785, 1315608614, 1540525718, 1841864931, 1337254645, 1519013727, 1392596307, 501141721, 1940221973, 1764770683, 721929412, 1491797232, 264799987, 1988343380, 1146493117, 1633988857, 1956560346, 1627398437, 1942646575, 1045211174, 1270899553, 971567678, 1344168008, 1908308404, 1435928479, 969383575, 1770156661, 1892271968, 1799078489, 1992690107, 1284797639, 709382323, 1301812078, 1995746403, 919320669}

    Returns: 1879044775

  25. {1073351662, 100867735, 591677887, 1445518284, 186166547, 584545488, 720667266, 1202398831, 1393068524, 1651676462, 510863655, 1692048129, 1198694335, 283256548, 1727875524, 21615002}

    {1922525580, 960352710, 1570127507, 1766777888, 229441084, 1644956347, 1938189426, 1627081457, 1515391861, 1989603226, 958796230, 1961658282, 1655957067, 1478602605, 1974175915, 1673647196}

    Returns: 1873308180

  26. {1177573465, 1072642900, 1511139557}

    {1292762375, 1998852200, 1546704117}

    Returns: 150753470

  27. {352721775, 1841232503, 1265274695, 1483749131, 1373320687, 739767744, 1386642089, 235885209, 1879186449, 1417267867}

    {1133433800, 1873740589, 1897158388, 1639843137, 1414339020, 1545304327, 1671716180, 1569205167, 1985022124, 1984719705}

    Returns: 1631997930

  28. {375829203, 1360915328, 677164046, 869886160, 386483456, 1636864448, 1003888403, 952209843}

    {1967908485, 1538245493, 1217021551, 1256603427, 782443692, 1888280951, 1139011231, 1830121618}

    Returns: 1501797495

  29. {756808823, 363898675, 1279763600, 373353437, 1583845205, 783727104, 1471015877, 795384560, 1038340369, 783080158, 1595961032, 100614061, 1390799740, 1363609810, 856262972, 564477294, 1266428404, 1563079822, 393895771, 248575886, 1053687004, 1982360591, 1261283866, 1808983466, 141094884, 361373912, 1692346024, 1388657670, 1052592802, 1399300783, 994754886, 39271593, 51777343, 1514363808, 1883724869, 617776087, 285320519, 1738498183, 1577640903, 1603006327}

    {1817920348, 1475114049, 1796551264, 443242029, 1862389692, 1759905434, 1739653759, 1283224193, 1500627983, 1378366248, 1666110989, 630225999, 1409447094, 1408471732, 1168999353, 721601827, 1481311263, 1602814963, 1072788763, 1127781998, 1407103653, 1982857288, 1634966731, 1864234693, 1163433781, 753995996, 1797630655, 1798797837, 1661595160, 1633092415, 1117259282, 1614581952, 359091990, 1930981695, 1904427790, 1267291951, 1814911675, 1971765844, 1963042609, 1884081546}

    Returns: 1911265266

  30. {1891222483}

    {1915274390}

    Returns: 0

  31. {475840473, 1777644955, 1154854320, 85019804, 1738861544, 220853768, 1245172565, 686551053, 1591468705, 556887236, 1664635098, 1213996411, 668770336, 904999699, 1919914214, 580854415, 1225738650, 1475959174, 1521648866, 452500281, 1530446177, 260480085, 870906302, 553820523, 1261330110}

    {1908532462, 1894553272, 1432139279, 671484101, 1939589826, 369569856, 1701045729, 686805354, 1829415897, 1958873906, 1753965881, 1930576227, 1922708300, 1409463175, 1982524294, 1913391898, 1589884893, 1925620194, 1758998010, 1922667315, 1925092738, 856728915, 1824676015, 850618622, 1726669009}

    Returns: 1738020138

  32. {1827396649, 1112161564, 1098575040, 1720167871, 653531151, 1585700774, 752254427, 570854900, 301731680, 838904293, 1241387683, 1501020620, 642990411, 1677925347, 563167429, 359349467, 1641758002, 180503217, 456805408, 33584142, 727069633, 293682735, 595520306, 362271004, 432348027, 1217788130, 1863608675, 1711666083, 1061695748, 459464602, 1726411623, 1350615124, 1640488977, 1936599574, 1200989220, 256219295, 908085807, 1017936535, 1435315484, 483100018, 610461193, 880193513, 403806562, 1729074587}

    {1935043107, 1855386620, 1201696939, 1743859053, 969460238, 1599252247, 1526782549, 1331029708, 1402432429, 1667367979, 1407325969, 1964450295, 740745567, 1867274352, 1210334981, 487629633, 1674488807, 356261861, 1910200181, 1355736540, 1610332455, 1784200976, 914335499, 1497093682, 914425117, 1914961173, 1924327529, 1895765211, 1657239414, 1443623991, 1951042969, 1384434676, 1755108087, 1995515580, 1271792275, 379984382, 1702860289, 1199614341, 1586934856, 1957278863, 1153192224, 1214313847, 1136670347, 1982011442}

    Returns: 1801508225

  33. {1740082973, 830234626, 1103316742, 981812868, 220141622, 476678555, 58043914, 801247714, 1078945143, 1401588312, 518368011, 1788476682, 938590809, 206023862, 1885441580, 1077311742, 1136585812, 129932638, 1249865005, 356277808, 903446052, 1777874648, 865245071, 1360024522, 1337292139, 362447839, 891406515, 913593578, 1245755077, 1660726313, 727569892, 1974855347, 425503948, 1379023397, 755807172, 1620427083, 449707957, 1121292651, 815088609, 1420384815, 1533746014, 656479143, 226232695, 147081725, 549475334, 680133062, 688072096}

    {1878553664, 1255440867, 1206460220, 1874930442, 1663570034, 570482221, 1628102017, 926993699, 1405994177, 1551108259, 1901934331, 1887653980, 969608618, 378473344, 1941918292, 1839023241, 1632931780, 465448480, 1453256020, 817390085, 1738314517, 1893115933, 1265854666, 1676253602, 1691939010, 1079315587, 1393400433, 1095979341, 1516519201, 1836404025, 1202285798, 1977153308, 712901626, 1469418314, 954648440, 1763944242, 1590391287, 1479012220, 1727111019, 1866127749, 1574186001, 1104182691, 786664172, 394141784, 1499030102, 1670116682, 962772559}

    Returns: 1772001693

  34. {1089222657, 240593176, 476666769, 1521653088, 1123735831, 1849776770, 1911366225, 123045576, 1188079610, 596948036, 651330459, 415615402, 953938256, 19783620, 1694844528, 372948672, 1283513658, 558510677, 1059874776, 1974530581, 1006779485, 1089050775, 1409528561, 1517759323, 1897099604, 47106429, 442284239, 149808103, 103023173, 526002244, 554804485, 1252148606}

    {1889965631, 914093227, 1897287523, 1554096430, 1270010334, 1977473464, 1999434684, 514123590, 1692738748, 1930532939, 840869801, 1638999359, 1246185509, 126273911, 1779440640, 1837313496, 1559539816, 1310735287, 1883975979, 1998400756, 1089930212, 1656801773, 1944235571, 1610172260, 1941394745, 785985451, 1699058804, 1334388805, 594932599, 1163807733, 839936100, 1855304827}

    Returns: 1951294327

  35. {1379792318, 613278804, 387780460, 562887634, 622408292, 1236905789, 1052189671, 1221720073, 652187927, 257955352, 1692290963, 1043361340, 383948100, 1410304278, 1793143732, 1419428733, 1085587830, 1100507548, 890804430, 1323451460}

    {1451455329, 1157667355, 1847280959, 1481426356, 1775146134, 1444532612, 1717245641, 1357756358, 979950137, 1253529162, 1837047773, 1101761200, 582136349, 1889209551, 1978140960, 1741736209, 1395410560, 1957267508, 1116826488, 1936359275}

    Returns: 1573319408

  36. {641840823, 739083227, 143182962, 551341052, 1760136658, 506858549, 297953041, 1842726760, 1087829021, 1339808862, 1118015383, 28373275, 1701441692, 1588232612, 1828355169, 1452238394, 588801704, 139559748, 1348602331, 925252498, 1723809445, 595203087}

    {1047184855, 927165837, 578408006, 768822846, 1957143778, 1632436850, 1936716148, 1881516064, 1857752427, 1533836186, 1401353568, 784964476, 1916049352, 1670451556, 1898500601, 1569881446, 1933957425, 1019663866, 1857918214, 1438798201, 1818051495, 1075444112}

    Returns: 1797156400

  37. {817676768, 1742646522, 1589047949, 105614447, 1929445666, 984144202, 443136704, 1427102801, 1887156414, 1742254895, 104697646, 687228982, 616125574, 1784936157, 512697564, 1089186088, 1300023051, 259448043, 1902749367, 899407695, 168913995, 772173782, 1901855870, 1725691849, 699532423, 945124959, 1695541184, 1494665590, 1673098709, 1019443835, 962682291, 948903146, 1035993322, 576215065, 1773353490, 984009620, 8599886, 944899834, 144995769, 645983123, 387629357, 1369704118, 452224092, 109167787, 487238269, 1504194308}

    {1255496870, 1833841449, 1961728555, 1614964783, 1964609907, 1932294460, 1866308265, 1644885934, 1914587832, 1892730093, 716503229, 1306468833, 1935619192, 1878453268, 1952025839, 1725590237, 1879690008, 485500847, 1908443525, 954737575, 1049893805, 1616627271, 1992695886, 1856612175, 1748443788, 1520959687, 1915531287, 1678683135, 1679727794, 1732241586, 1055787112, 1935425727, 1043539317, 1032880330, 1780488084, 1934582538, 720725140, 1707131658, 1094734081, 758175897, 1529079742, 1570402020, 1262597560, 530187031, 921653152, 1782679293}

    Returns: 1859912261

  38. {1261605945, 276323380, 1551080360, 1255135757, 489591569, 798681358, 1735655874, 183412168, 262893396, 1591188282}

    {1798828246, 1710640784, 1843882019, 1498920670, 922044581, 1923605548, 1985622767, 301708992, 1999500616, 1835198725}

    Returns: 1722729371

  39. {1450946240, 1622654721, 1025504959, 784008019, 746683752, 1988604645, 1878792566, 1191397069, 1308560338}

    {1627373539, 1965098390, 1192312158, 1122318260, 1400226334, 1994626248, 1967266065, 1402315601, 1742290563}

    Returns: 995957729

  40. {43705618, 251596571, 1538839771, 968683609, 1941438405, 1810623642, 1120952646, 15132408, 999592110, 237472802, 430588045, 521935340, 1539273436, 332112266, 434266356, 1298230632, 463623298, 388635146, 1520905759, 1323842145}

    {1328189897, 671275365, 1971048973, 979938119, 1982998778, 1915910487, 1626859616, 644768775, 1989400960, 1144608273, 1580746996, 1011937126, 1811334257, 1069754980, 731334665, 1312999929, 482520197, 1887728268, 1959536038, 1415331022}

    Returns: 1939293160

  41. {222417478, 1030481145, 883209984, 299946602, 1930910183, 1697301343, 640248896, 314322872}

    {1311553939, 1923439433, 1848241639, 531546761, 1968340822, 1717249026, 736517800, 1528045928}

    Returns: 1548295037

  42. {526348132, 1263943937, 1801094807, 362492334}

    {1015464195, 1414332259, 1960160180, 1126537308}

    Returns: 489116063

  43. {874191461, 669716870, 1194176424, 1769712499, 374592909, 935598569, 521412735, 1556649845, 1037495521, 1058186090, 1692181651, 1883588340, 995117148, 1061826968, 1679546453, 408903303, 1227264279, 1069807950, 1056868361, 328303246, 1248910241, 1395040311, 495992697, 230223898, 1342817137, 1365241524, 720635182, 1158376277, 1282514717, 1952926908, 110280850, 201759854, 1990947678, 1780523281, 649908362, 432454576, 1080104828, 570916974, 1420851808, 1511503427, 1716941890, 613749213, 1328112869, 1783198411, 760910818, 1317770901, 1259435555, 1178082343, 618408435, 419569460}

    {1608578014, 865744166, 1334167121, 1884640061, 1445653792, 1641252667, 1821931147, 1785535490, 1846989019, 1708814455, 1908529135, 1976384496, 1585423533, 1853005581, 1921727322, 954959732, 1839717931, 1221771026, 1661656869, 739496865, 1665254843, 1977060906, 926330807, 230277528, 1436806001, 1602461053, 1780125110, 1451030632, 1548327294, 1991497997, 1643803983, 1950047713, 1997626559, 1960701751, 912370695, 1380951066, 1991752574, 1794808169, 1955055662, 1689760194, 1989640061, 888797305, 1376373191, 1868481797, 1793392857, 1950136760, 1864446659, 1264465674, 862201602, 1301201580}

    Returns: 1789992720

  44. {1449626310, 1235598697, 884247582, 1957677004, 263253338, 358007588, 1461505146, 1267185536, 1209624945, 1311773441}

    {1654634730, 1908063844, 1954801007, 1993614329, 1246568027, 1459720560, 1814621876, 1552076087, 1541340996, 1961667480}

    Returns: 1600783895

  45. {1187981103}

    {1306717681}

    Returns: 0

  46. {1488670893, 809049428, 203395092, 1654083968, 1654825853, 170045558, 410239188, 1502265462, 100887422, 477815650, 1217102512, 702324748, 744144809, 1390393089, 1889835935, 1431620181, 422590345, 243087763, 468540575, 70468026, 1009026836, 573756326, 774802475, 1769954337, 1750882385, 1703858915, 86041312, 579439438, 1843546341, 1508114454, 1734786137, 1516567115, 1745037806, 1005566708, 1390690092, 1462591167, 239819848, 1904874708}

    {1886707830, 1084444298, 896901659, 1966565640, 1727064733, 1346182395, 1574881976, 1661683696, 1509092886, 1425957779, 1597021476, 1673204980, 1539303548, 1463506540, 1948486834, 1748492364, 1720898061, 939910968, 919661630, 1814658025, 1978745726, 1933143151, 1834287017, 1847653597, 1825408848, 1788260804, 235402232, 1578560676, 1919640757, 1728856685, 1747102365, 1722750328, 1882611407, 1659694177, 1965640322, 1751314908, 747650786, 1941140555}

    Returns: 1880524328

  47. {149746244, 51026955, 1644150389, 1337312087, 1035194430, 755303473, 448082253, 1345554372}

    {395674531, 791219187, 1775216647, 1709070902, 1969162552, 1358191414, 1771537561, 1664600274}

    Returns: 1573062681

  48. {312726204, 122620191, 895349298, 1858733939, 89530067, 1205967608, 958893364, 301386344, 578673540, 1359636185, 1926992469, 1635451548, 97078164, 603373305, 267984036, 1277590081, 1357698539, 1362393913, 831362257, 1753818609, 748637988, 1805608328, 808107108, 727740700, 882894212, 503308683, 1340549480, 1789641622, 301547071, 412125635, 914585069, 264260268, 713201598, 695068088, 1167049283, 795049815, 652498078, 1384458374, 241065828, 1962740549, 940502180, 395575689, 1322181546, 1696016900}

    {973069594, 639814957, 1550851504, 1982087131, 1267562869, 1233203362, 1494871418, 306020104, 607452993, 1648975181, 1989742740, 1713059958, 1470880372, 1213566279, 1014132153, 1617752320, 1935270168, 1379769642, 1143500545, 1951931787, 1010256360, 1918094592, 1738183626, 1899265053, 1244709280, 700651409, 1934947745, 1931138628, 1030940667, 995461395, 1136883247, 1855522146, 1720037818, 1750118049, 1363864522, 1446219820, 1562490344, 1496842232, 1145746013, 1988685654, 1370796098, 556859562, 1952506735, 1857072031}

    Returns: 1891607490

  49. {201749215, 930362269, 1032416055, 1866247209, 972350162, 536427848, 1621918357, 225060716, 1919681064, 1371950866, 569340450, 6069940, 1113999030, 1268797485, 1113355367, 1631927910, 1318918761, 386186771, 744275399, 509204536, 1091893491, 1117598941, 1124906971, 366019465, 261771175, 876711554, 923636369, 1566360153, 978738509, 82676883, 1005059862, 971396348, 31964854, 165052147, 1923470008, 418104541, 630259393, 908696120, 164511156, 1385514448, 341052751, 958943548, 80316051, 1918889879, 383017000, 1807370690}

    {1009900878, 1191407115, 1870402283, 1880760898, 1772996046, 905850996, 1978297307, 1827721129, 1945544399, 1906429397, 1556623994, 1604256599, 1790629616, 1839302631, 1561139857, 1747919239, 1851752670, 1309437147, 979306893, 1429749463, 1491204373, 1563442316, 1543372109, 1904146420, 305021390, 1848587782, 1083889506, 1742764211, 1085373210, 707815283, 1515957683, 1201060281, 1573408280, 1120038247, 1961767042, 1140108525, 1219001174, 1033028446, 1372111596, 1877989190, 954342296, 1948079678, 1470008136, 1923295942, 870042956, 1823398982}

    Returns: 1929802188

  50. {1277422493, 444302474, 874837172, 1528090384, 259027508, 928325163, 1256169272, 1392877260, 491505283, 609539607, 1930902586, 259655651, 948031282, 1620104365, 1256093040, 1209797176, 623105353, 1338169453, 1932326534, 836977665, 854483562, 743041863, 166043818, 248399658, 1577849387}

    {1415491451, 1974825223, 918979565, 1812387989, 1224301936, 1938397467, 1790799478, 1994405849, 1639604075, 629975619, 1997926487, 1494019109, 1365482396, 1631356874, 1681179482, 1474950931, 1044477700, 1632002279, 1993162304, 1925897747, 1502601383, 1497036803, 1493609118, 592042713, 1930406379}

    Returns: 1746006191

  51. {1686466284, 1744322730, 350386597, 229138541, 200758075, 1810693780, 832411846, 401525421, 1520227041, 466242497, 752348736, 744053165, 1918772801, 635478324, 806237676, 178605667, 1239815944, 1760941297, 1463551966, 1496119355, 1666945067, 540432552, 441030575, 1532350977, 887264083, 808897733, 1604368050, 1085955048, 1842752108, 1885276408, 1743072620, 149183470, 1764948633, 1204630213, 163806350, 521519629, 1688276188, 1555860951, 547519027, 376559446, 137313668, 1745332788, 1015688160, 1852452332, 1183331852, 6709865, 850978723}

    {1816741260, 1906708287, 987167458, 1625682985, 323779153, 1951738749, 1330163924, 416542845, 1954835710, 672898173, 921817024, 1594590645, 1971942261, 880060643, 1451761430, 571342686, 1636308852, 1790417222, 1924966011, 1573883077, 1694110665, 1183552972, 1046736003, 1691286753, 1373648872, 1337577375, 1998929915, 1793274744, 1985176657, 1938215144, 1905829598, 1111755860, 1938389753, 1322250909, 981398267, 1071649942, 1881419195, 1886173770, 1147227844, 737292142, 1932542266, 1834908879, 1619855836, 1900240294, 1382688750, 1094550573, 1426814112}

    Returns: 1847862989

  52. {1777135268, 1750534257, 1756633362, 1648828460, 1416886509, 787270355, 207802729, 142027907, 1493106646, 1884376231, 367647426, 1115974951, 1771354165, 627142161, 778806680, 1104944466, 554717329, 110499369, 139446588, 99966103, 1965005051, 781276611, 1800820712, 178739820, 1689880129, 1920227146, 1359679120, 1466727790, 1578747277, 1271638930, 1978338648}

    {1951571976, 1997171361, 1856125703, 1967029063, 1437705446, 1734032346, 679963795, 1949107880, 1714672929, 1971111371, 1014760873, 1764891898, 1887781860, 1293387002, 1648182339, 1975317448, 1098747912, 138294312, 1436992362, 934941480, 1998324570, 1529750406, 1885100925, 576927270, 1998053980, 1968696457, 1633256906, 1936179063, 1630810824, 1870840061, 1993704903}

    Returns: 1886402335

  53. {430020611, 327088659, 1221124469, 610912662, 1159862968}

    {1976614228, 1856414104, 1441245194, 651401056, 1636178617}

    Returns: 1426393493

  54. {1279912516, 448712336, 794161939, 1709516500, 131925900, 677032524, 1969239838, 525847929, 1004004944, 577134439, 1002243198, 682626864, 114541925, 705237668, 518412565, 1278009423, 459867219, 1821934001, 847593886, 664497409}

    {1705192850, 706479701, 968011729, 1852179431, 1121380099, 1089719146, 1986694489, 1296256704, 1020574462, 1270044547, 1897874142, 1839461808, 1701871843, 1721651995, 1588739858, 1425104021, 832756411, 1994566706, 1838451740, 1872876637}

    Returns: 1783402893

  55. {841379429, 921483696, 246477837, 819549571, 6962850, 425996334, 1891650463, 1056857299, 681108463, 1907246202, 1798852281, 1005666617, 1627478794, 1014910714, 786655485, 1196504145, 1120583949, 357604892}

    {855651081, 1954699358, 1663425028, 954489690, 674813950, 1440778975, 1961517272, 1776289501, 826473206, 1982648731, 1935914592, 1576921885, 1933621035, 1652797272, 927372122, 1809312954, 1782052356, 705196697}

    Returns: 1715039435

  56. {1652516778, 1955176408, 1374886063, 1120352426, 704600716}

    {1767832329, 1967403405, 1633540946, 1831272695, 1594359581}

    Returns: 628504071

  57. {1970730315, 431191600, 1986028406, 1819363066, 13246014, 71190780, 1928131170, 1475761836, 818145387, 224916722, 1101596952, 312893737, 1471117401, 964936618, 1711834222, 60258173, 1665298153, 266706184, 393423577, 418931295, 1942407516, 48808656, 1014791736, 1916319474, 1328538959, 1891050808, 1475195369, 1598925492, 1684915219, 875727469, 64326914, 258439856, 593922366, 497367878, 1454854959, 386470049, 1100734576, 86275783, 898211361, 553219609, 1130842320, 691175803, 1693938819, 405430184, 1903796299, 1866279169, 1502909349}

    {1980988166, 1331565898, 1989288900, 1987323934, 762303239, 828374761, 1974148488, 1588625096, 1884386221, 1247243887, 1546072195, 1225478262, 1509593125, 1350176237, 1860720796, 668974876, 1682935869, 1518061747, 1825836499, 673191201, 1961847201, 1760383788, 1506263025, 1990587665, 1626912709, 1974274563, 1943541775, 1634715720, 1777486010, 1400975034, 985008517, 1856750649, 1789516441, 1201088190, 1760803101, 1609229891, 1853689403, 1065501711, 1182500179, 1735706940, 1646597482, 994065012, 1808988910, 1816517422, 1940955433, 1988796100, 1895685616}

    Returns: 1940480244

  58. {1518449590, 1500823612, 82447765, 1913634279, 206338975, 1331011675, 892150323, 1040872045, 1455733065, 1282596925, 575638833, 410915154, 1118898424, 51806956, 295523073, 865724565, 1586124051, 207253987, 1842127187, 706668014, 1975633906, 1597651996, 736061364, 476809191, 213270488}

    {1798586692, 1577716888, 1592259706, 1979310339, 1592141145, 1928819327, 1700678447, 1289144120, 1700670470, 1397587811, 771640222, 1303081147, 1954398627, 1054481829, 379231899, 1819086155, 1735107373, 1666237552, 1964625948, 1057778399, 1990136797, 1997557586, 836422226, 1137333838, 1212471497}

    Returns: 1907689032

  59. {1727226489, 530234663, 1603619426}

    {1851607104, 1148970958, 1902839388}

    Returns: 124380615

  60. {371717731, 1741268665, 453254540, 243379060, 1647527739, 651684599}

    {584708538, 1994996078, 1499586327, 1481535670, 1695353504, 1665170767}

    Returns: 1145511624

  61. {300433266, 1794742166, 24788499, 1082796559, 1915854596, 186912941, 504377149, 1737879302, 617066686, 455639910, 1781356631, 542495874, 91802483, 540906934, 1583593999, 288280387, 1473103585, 1446834863, 1502349333, 494830944, 1063702716, 1036162927, 783125057, 818509720, 1804668850, 1945945642, 145934897, 430115119, 1183627368, 1444778420}

    {942712126, 1832433622, 1112546334, 1337258736, 1960833052, 1650097800, 628272910, 1991605340, 638610402, 523283284, 1835316872, 1319296864, 949074578, 1792179258, 1977719260, 813477501, 1700404606, 1871783571, 1577287343, 840538448, 1311803789, 1998312839, 1026090256, 905411975, 1986278324, 1953469826, 728518259, 729253356, 1825081314, 1946946357}

    Returns: 1899802857

  62. {1864468002, 948991836, 1529292746, 1570049450, 1510683137, 954883280, 106049894, 1349314581, 1264903995, 1744762950, 1042138322, 1561066592, 1319484053, 1407323084, 802039475}

    {1961491203, 1357764795, 1894529484, 1690502658, 1726745571, 1544148382, 331648139, 1877994950, 1451546298, 1761996702, 1535638044, 1729927566, 1880718672, 1906216288, 1303354779}

    Returns: 957224452

  63. {591708165, 1548482981, 1673824985, 317862366, 641432728, 1509680267, 1171117501, 1617697744, 1914518655, 30583130, 859033096, 782150699, 940138267, 461452746, 1495728196, 678781514, 404807676, 1266841843, 1567344557, 742057030}

    {769044406, 1601057766, 1989898972, 793727376, 888271450, 1758087253, 1365433182, 1975529544, 1945485370, 587278063, 1874789826, 1637736517, 1302519574, 1508737492, 1510363661, 1559628276, 1281215737, 1504572573, 1730688216, 1885844843}

    Returns: 1657667178

  64. {1046463879, 940431159, 109580350, 555468010, 271137209, 264296926, 213428514, 1946818548, 127701142, 1045240483, 643575653, 1043410403, 277740276, 1011595845, 162722464, 1884740736, 896618198, 3556257, 497239656, 371632686, 649217840, 1068085522, 700176528, 304079135, 1192171216, 722897277, 1107164945, 1717060088, 1460390958, 1772313420, 393031267, 1147145878, 1495715836, 557815753, 1736928965, 1962699652, 75483332, 1026101763, 603804190, 1390490406, 898841357, 497458324, 1150006695, 1371529649}

    {1742152095, 1912145414, 452735528, 1820740700, 508544967, 1101605792, 1324751097, 1982404900, 747149160, 1500506347, 1008934224, 1955028622, 839652890, 1761374220, 1170647381, 1899988054, 1551878927, 1165118720, 1727989750, 652644337, 1638374018, 1595974910, 807639040, 349465671, 1749207728, 1297653906, 1309637251, 1748683746, 1765937474, 1822335153, 1934008246, 1622715139, 1639883627, 1237914530, 1959589658, 1970225774, 1360662427, 1119291973, 769664350, 1726467026, 1655765376, 1449371111, 1273189491, 1487904442}

    Returns: 1891632448

  65. {1918644096, 1812729368, 1486850583, 641517164, 1456843622, 1523276039, 1475577036, 1029333681, 1807371467, 70759661, 831284627, 1446296584, 1840913019, 156131922, 1605181236}

    {1939685376, 1883972635, 1712365612, 822547138, 1639735145, 1696802516, 1955607817, 1495054231, 1977138791, 1589348014, 1550034276, 1888028895, 1935412942, 187619182, 1736665934}

    Returns: 1336840424

  66. {845041661, 1971425649, 1197098458, 808386883, 568377345, 1262645660, 1822248221, 1026931010, 1124834378, 728843235}

    {1383183136, 1984047071, 1928307982, 1889632552, 1074058958, 1687190519, 1888348489, 1567350410, 1193921438, 1529200509}

    Returns: 1160789317

  67. { 1 }

    { 2000000000 }

    Returns: 0

  68. { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    { 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000 }

    Returns: 2000000000

  69. { 1, 2, 3, 4, 5, 6, 7, 8 }

    { 1900000001, 1900000002, 1900000003, 1900000004, 1900000005, 1900000006, 1900000007, 1900000008 }

    Returns: 1900000005

  70. { 0, 0, 0, 0, 0 }

    { 2000000000, 2000000000, 2000000000, 2000000000, 2000000000 }

    Returns: 2000000000

  71. { 12, 32, 92 }

    { 991, 161, 1093 }

    Returns: 959

  72. { 0, 0 }

    { 1999999999, 1999999999 }

    Returns: 1999999999

  73. { 1, 5, 8, 9, 13 }

    { 2000000000, 2000000000, 1000000000, 500000000, 80 }

    Returns: 1999999995

  74. { 10, 50 }

    { 1000, 500 }

    Returns: 450

  75. { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    { 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000 }

    Returns: 2000000000

  76. { 50, 50, 50 }

    { 60, 58, 60 }

    Returns: 10

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

    { 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000, 2000000000 }

    Returns: 2000000000

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

    { 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999, 1999999999 }

    Returns: 1999999999

  79. { 1, 1, 2, 3, 5, 65, 23, 548, 56, 43, 2, 35, 56, 65, 56, 323, 756, 876, 8768, 678, 8767, 8078, 5787, 567567, 65756, 55, 676, 3454, 3, 54, 5, 7, 8, 86, 7, 67, 67, 67, 67, 67, 67, 9, 78, 999, 99, 7575, 775, 67 }

    { 1234324343, 1999999999, 132432434, 343242432, 324343434, 3333333, 4444444, 44444444, 666666666, 77777777, 88888888, 99999999, 222222222, 454444444, 1999999999, 1888888888, 1777777777, 1666666666, 2000000000, 1555555555, 223423534, 43545454, 45455555, 65475765, 345345345, 7474466, 345343443, 345345345, 2234324, 345344343, 543566664, 4654646, 903903096, 689683658, 65356356, 636636363, 36363636, 363636363, 36363636, 363636363, 36363636, 36363636, 363636364, 36363636, 36363636, 36363636, 36363636, 155555555 }

    Returns: 1999999998

  80. { 1, 2, 20 }

    { 100, 10, 30 }

    Returns: 18

  81. { 1, 1999999999 }

    { 2000000000, 2000000000 }

    Returns: 1

  82. { 1, 2, 3 }

    { 4, 5, 6 }

    Returns: 3

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: