TopCoder Statistics - Problem Statement

Problem Statement

There is a shelf with N positions, numbered from 0 to N-1 left to right. On each position there is an item. The item that is currently on position i has weight W[i].

You want to arrange the items by weight, with the lightest ones on the left.

The items are very precious, so they cannot be carried far, only lifted and placed down again. Thus, you are only allowed to swap pairs of adjacent items.

You are not very strong. You can only swap two items if the sum of their weights does not exceed L.

An inversion on the shelf is a pair of (not necessarily adjacent) objects such that the one on the left is strictly heavier than the one on the right.

Clearly, the fewer inversions there are, the closer is the shelf to being sorted in your desired order.

Calculate and return the minimum number of inversions you can have on your shelf.

In order to keep the input small, most of W will be pseudorandom. Please use the pseudocode below to generate it.


state = seed
X = length(Wprefix)

for i = 0 to X-1:
    W[i] = Wprefix[i]

for i = X to N-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    W[i] = 1 + (state modulo M)

Definition

Class:: LimitedSwaps
Method:: minInversions
Parameters:: int, int, int, int[], int
Returns:: long
Method signature:: long minInversions(int N, int L, int M, int[] Wprefix, int seed)
(be sure your method is public)

Notes

The reference solution does not depend on the input being pseudorandom.

Constraints

N will be between 1 and 250,000, inclusive.
L will be between 1 and 2*10^9, inclusive.
M will be between 1 and 10^9, inclusive.
Wprefix will have between 0 and min(N,200) elements, inclusive.
Each element of Wprefix will be between 1 and M, inclusive.
seed will be between 0 and 2^31 - 1, inclusive.

Examples

7

200

1000

{40, 20, 10, 70, 30, 50, 60}

42

Returns: 0

We are given the entire array W. You are very strong: you can lift any two of these items. Thus, you can sort the array completely.
7

29

1000

{40, 20, 10, 70, 30, 50, 60}

47

Returns: 7

The same test case but now you are so weak that you cannot lift any two of these items. The shelf will have to remain in its original state. There are seven inversions.
7

30

1000

{40, 20, 10, 70, 30, 50, 60}

47

Returns: 6

Now you can at least swap the items at (0-based) positions 1 and 2. You should do so, as this decreases the number of inversions to 6.
7

30

1000

{20, 40, 10, 70, 30, 50, 60}

47

Returns: 6

Note that this shelf is no longer the same as in the previous examples: the first two items are now in a different order. Remember that you can only swap adjacent items. You are able to lift the two lightest items at the same time (20+10 <= 30), but on this shelf these two items are not adjacent, so you currently cannot swap them. You are not strong enough to swap any of the pairs of adjacent items on this shelf, so you have to leave it as is. This shelf has six inversions.
10

1234

1000

{500, 470, 923}

47

Returns: 7

You should have the following weights: W = {500, 470, 923, 309, 406, 299, 92, 649, 434, 151}.
7

100

100

{5, 5, 5, 7, 6, 6, 6}

47

Returns: 0

Equal weights do not form an inversion. The initial shelf has three inversions. You can make three swaps to transform it to the shelf on which the weights are in the order {5, 5, 5, 6, 6, 6, 7}. This shelf is sorted. It has no inversions.
250000

900000000

999999937

{}

4747

Returns: 15623064870
250000

12344545

999999937

{}

235235

Returns: 15649389596
250000

1989999937

999999937

{}

32333

Returns: 1350823
1

3525

2304

{1055}

1660249968

Returns: 0
2

6858

4431

{}

440044526

Returns: 0
3

2

1

{}

1355395163

Returns: 0
4

241222

486381

{}

1542245923

Returns: 1
5

2180

24315

{19693, 11204, 18278}

841741944

Returns: 8
6

65

137

{93}

1647457924

Returns: 11
7

25454

98675

{}

1438208187

Returns: 11
8

191

124

{}

1789542187

Returns: 0
9

1415273

894486

{848417, 582239, 274297, 374283}

172270288

Returns: 2
10

73760

53228

{47856, 34040, 52404, 14480, 39738}

489349967

Returns: 13
11

1593279

1482867

{1265674, 1170302, 312900, 930898, 31857}

731414135

Returns: 14
12

39115

152771

{143358, 124915, 114194, 95835, 8699, 69472, 135520, 123683, 82574}

95491659

Returns: 40
13

221632

389556

{362697, 96478, 92630, 246307, 104164, 67045, 51600}

586949650

Returns: 35
14

17696646

14160893

{4477255, 7447753}

1940892

Returns: 3
15

1736736

1305216

{}

1585910533

Returns: 12
71

144

277

{}

2108757054

Returns: 1230
255

70903855

66752839

{38073342, 670240, 46643013, 4955682, 11752257, 56087772, 10104395, 61864774, 36469929, 22705789, 42649356, 58189405, 3133027, 58890719, 41744954, 15737114, 47797816, 4109421, 25416083, 8264322, 1490758, 5945090, 20315753, 3616633, 59005448, 36765974, 20647084, 16046935, 41114357, 60161826, 49258988, 35895681, 10147182, 36905061, 38906925, 51165656, 18331498, 41539536, 57599631, 66413849, 38308069, 5415898, 37779545, 32967497, 22999264, 37347542, 3501907, 63970620, 7690357, 27748030, 28027736, 23739269, 60841442, 20321389, 37870933, 56659457, 50984277, 32833357, 40108335, 9371893, 4263848, 65151353, 34082935, 7856193, 60619125, 30954948, 43818912, 52805090, 30451748, 55275233, 1199757, 29164367, 54336299, 37844690, 35039224, 51231864, 64848541, 4442037, 52453370, 52963983, 19302457, 52596230, 47295405, 32896917, 33715126, 7659036, 50663974, 16449705, 23635006, 53435532, 22220393, 11201653, 31041950, 1516261, 39441428, 6589139, 45025781, 30834519, 63062027, 30905543, 65581631, 18574855, 42817595, 36568993, 46037801, 46659404, 46249760, 61653957, 1596117, 64629581, 37594301, 12702728, 55304579, 45607175, 19263915, 2743826, 51794927, 17667187, 36389984, 32392311, 25749899, 4594678, 48480932, 52747318, 7317196, 59001948, 34954533, 47584290, 39593985, 40192647, 32032306, 36047975, 49951317, 53068783, 24290899, 38819897, 20917633, 27655281, 51673042, 45822366, 60137513, 60284074, 13748582, 49148045, 42447550}

392755518

Returns: 12141
155

106190

105512

{47202, 14261, 12214, 81583, 97515, 55854, 47256, 6586, 45847, 76394, 7403, 51362, 83092, 35116, 33337, 27606, 37975, 27422, 60949, 86681, 39258, 58360, 101673, 57731, 41610, 88408, 7179, 20353, 76060, 62876, 81, 3608, 55410, 59953, 68187, 57394, 80486, 33781, 38531, 13436, 39725, 16234, 22250, 55455, 44127, 65213, 55837, 30738, 65976, 74747, 67271, 34486, 41025, 72718, 3024, 79809, 88221, 49719, 77937, 77242, 91329, 77968, 90421, 81791, 60533, 80869, 73180, 23528, 89461, 92000, 49417, 5610, 23808, 80346, 23785, 81774, 10215, 63564, 53874, 7900, 29416, 60519, 23057, 78373, 52153, 586, 81848, 18231, 97419, 9541, 73426, 51002, 99, 50381, 65448, 97237, 59654, 82547, 48917, 95765, 16055, 67011, 52493, 13384, 11278, 103482, 55089, 53996, 72156, 13666, 80910, 22916, 87179, 65349, 62365, 57574, 78163, 12285, 51840, 68750, 66275, 42913, 56699, 98164, 25775, 41470, 52051, 9777, 17369, 93420, 63914, 43655, 85189, 85106, 13742, 33096, 63631, 103679}

398184188

Returns: 4924
415

1

1

{}

905302894

Returns: 0
569

513

412

{}

268214787

Returns: 46393
343

16383741

11362665

{}

1736740490

Returns: 6624
675

52374

33231

{}

1606747649

Returns: 18439
870

45345460

40715949

{}

674631869

Returns: 147008
654

6

11

{}

608660236

Returns: 101075
577

10

42

{}

540951194

Returns: 80380
653

1996

6949

{4500, 5248, 1799, 5564, 2842, 6297, 739, 5255, 2574, 835, 294, 1654, 6645, 4581, 1110, 2706, 745, 6830, 2616, 6298, 5861, 5435, 3515, 4147, 4473, 4691, 6168, 6307, 5572, 2885, 6534, 4271, 4256, 3486, 5226, 3598, 3573, 5540, 3385, 5962, 4020, 186, 1596, 2675, 402, 4913, 3511, 829, 3598, 6336, 4775, 1017, 789, 6936, 2742, 3582, 6053, 484, 2734, 6454, 6182, 1536, 6662, 5480, 3349, 3841, 6074, 4244, 3892, 5676, 4231, 980, 1880, 1627, 5140, 217}

2119888712

Returns: 105488
383

351800544

689350521

{50425261, 649218199, 320727333, 47475367, 689268660, 662912313, 6766888, 275073123, 370083200, 206399913, 596475438, 230917734, 396613519, 398019724, 143462529, 217322535, 480391205, 661634890, 37085385}

1295401319

Returns: 36195
667

3538115

3353703

{}

1815175106

Returns: 96137
913

24799

13885

{744, 11863, 9257, 11826, 11296, 8042, 3764, 4434, 6645, 959, 394, 6441, 3126, 12545, 6838, 6011, 8523, 1454, 5655, 11839, 10234, 10283, 5555, 7229, 13704, 1111, 1073, 7753, 4372, 1055, 2659, 3355, 3727, 6916, 7744, 12998, 3236, 4862, 98, 1871, 9905, 9248, 13346, 195, 4115, 8740, 3490, 8722, 6106, 7718, 3511, 5447, 6562, 629, 11027, 10592, 9609, 6795, 5333, 13287, 13179, 8809, 5648, 123, 1791, 337}

1335612918

Returns: 6578
860

1

2

{}

211560378

Returns: 92665
246282

205051664

517563765

{}

1190803699

Returns: 15152704938
246478

9912

111131

{}

1305849986

Returns: 15190823678
249853

872944

6804745

{3412218, 6111296, 6042582, 2790174, 6035474, 754402, 2124073, 3526760, 3133142, 823964, 5941703, 3165794, 3166457, 1479927, 2480446, 249919, 255673, 4824387, 5672012, 4838471, 1605477, 1056817, 4707328, 1869014, 723967, 63891, 3547880, 3587252, 3491872, 5931483, 3548687, 4851239, 6153446, 1070223, 1291753, 6485704, 6053653, 6206553, 6220535, 3151695, 4520543, 5380349, 3859425, 2203189, 5371733, 5380314, 1237851, 629842, 332370, 4948048, 2025630, 6132004, 4930565, 1075984, 591435, 147069, 1149027, 1028778, 4349505, 6541956, 1067727, 5135028, 2450444, 4781075, 5055702, 3509102, 4591643, 6253219, 4094213, 5137743, 4873320, 196797, 1404296, 6558997, 6751923, 5014629, 4546332, 4850818, 5312754, 6074921, 1223555, 1939682, 983843, 1270989, 2391928, 5173537, 4062842, 6768884, 5455937, 4110856, 3863993, 5075290, 2593879, 3436979, 6323658, 3772433, 5079865, 1539156, 107319, 3589880, 6782952, 6610730, 4088232, 4107365, 6140852, 3422875, 2881341, 3145226, 4661760, 2532433, 6708519, 2577817, 3309079, 3158061, 298272, 5232302, 6400564, 4415310, 2254224}

608350938

Returns: 15592950579
247657

1764

4926

{}

1579559189

Returns: 15313354098
245573

9194

2715780

{671061, 2603805, 166830, 1729387, 2017155, 1356772, 618736, 1114286, 1074393, 1387331, 1714408, 467821, 861930, 740722, 2606506, 966851, 1183451, 1030527, 1932148, 2213588, 1429957, 654617, 2214331, 1513925, 467745, 614390, 745400, 2368175, 954213, 2264501, 2396690, 2212436, 1343829, 2679592, 2680913, 2272579, 863801, 2671240, 1045107, 171132, 1532970, 1595438, 721158, 2056087, 2553433, 714228, 810774, 1688761, 225103, 1966748, 1370642, 2300852, 2262823, 313101, 1085740, 399456, 580938, 2161520, 2430660, 873491, 1147957, 2505141, 1633656, 465524, 1071905, 2319041, 1500319, 501738, 1576400, 1561312, 2235783, 943659, 1220283, 1052514, 2552661, 1345605, 2389372, 160760, 2593320, 870141, 1242471, 1870857, 1364003, 479067, 613446, 2483122, 767866, 1092335, 1438847, 1149198}

406616854

Returns: 15069952326
244826

70

68

{}

851928981

Returns: 13904805942
248066

50037

37843

{}

643825690

Returns: 7042599284
241743

323193707

493554361

{}

1778314963

Returns: 14660475931
243109

4

5

{}

1800803545

Returns: 11808119001
245063

487

1789

{}

1349762487

Returns: 14997275887
247448

23

79

{73, 62, 29, 8, 41, 40, 49, 34, 76, 8, 10, 33, 59, 65, 29, 66, 66, 63, 37, 41, 56, 67, 32, 79, 43, 74, 27, 74, 23, 25, 31, 6, 4, 78, 66, 78, 34, 78, 38, 26, 44, 76, 78, 72, 44, 65, 23, 42, 48, 24, 21, 64, 10, 5, 51, 60, 58, 38, 13, 64, 35, 43, 37, 28, 55, 10, 33, 79, 49, 42, 59, 38, 21, 31, 24, 47, 30, 40, 5, 28, 74, 61, 4, 46, 2, 37, 36, 71, 54, 68, 31, 59, 59, 7, 11, 17, 52, 57, 24, 32, 6, 52, 58, 69, 68, 13, 72, 4, 70, 58, 70, 63, 76, 21, 21, 31, 36, 41, 25, 72, 64, 66, 36, 59, 33, 44, 68, 15, 29, 33, 29, 5, 18, 32, 58, 11, 42, 71, 28, 42, 13, 34, 67, 21, 36, 47, 18, 22, 11, 24, 8, 66, 23, 78, 72, 79, 79, 14, 37, 6, 42, 24, 12, 58, 36, 13, 39, 26, 76, 64, 19, 18, 32, 69, 31, 78, 40, 33, 59, 4, 40, 25, 4, 56, 23, 35, 63, 25, 58, 2, 48, 32, 52, 65, 23}

757526682

Returns: 15112018289
242932

451175

576911

{422148, 314454, 280634, 97346, 317477, 241253, 45589, 494159, 320909, 247402, 310155, 478652, 187830, 185400, 317469, 482506, 303201, 305592, 54298, 321571, 39779, 71909, 419104, 530735, 445631, 153475, 396815, 403256, 569206, 235084, 555821, 433649, 466581, 565988, 191262, 264771, 420087, 335882, 351459, 130697, 396454, 456560, 147383, 94139, 454711, 261745, 247128, 3707, 269513, 568360, 26617, 353436, 415888, 557241, 317592, 207635, 265916, 70959, 53086, 254705, 183102, 369712, 363084, 87657, 523431, 273569, 294238, 385884, 214300, 50280, 273097, 510914, 244088, 114673, 553805, 320511, 193548, 416062, 294833, 211414, 553699, 293879, 168239, 169290, 335653, 160678, 291744, 505498, 103508, 299573, 274103, 158344, 410038, 230002, 232579, 186767, 90421, 304157, 541937, 152826, 487727, 309540, 33108, 111767, 231602, 217400, 111465, 206509, 523653, 401873, 317122, 267745, 12762, 351712, 377881, 440374, 101390, 92215, 345599, 272693, 559218, 242996, 144429, 257894, 521425, 210391, 35770, 175858, 24853, 328982, 238596, 384608, 240199, 256568, 512372, 388488, 211579, 445301, 195493, 486124, 233276, 37283, 426454, 488772, 243094, 444109, 19066, 443298, 537553, 69144, 514439, 202760, 409830, 196628, 2160, 251217, 516155}

50410823

Returns: 14798595149
249019

1029412531

854250603

{656135484, 751560231, 713953678, 557338349, 761754041, 743463425, 800394634, 673053409, 542072699, 403219853, 670768203, 238829735, 723897793, 57843449, 233551651, 234624601, 818372069, 527463248, 631265855, 473560129, 535136613, 429421180, 583893765, 431799897, 150271761, 449470263, 383566399, 13877559, 747734428, 562817263, 364707773, 585987425, 798255605, 114938111, 821901445, 654620711, 388544003, 547493939, 414265721, 281294715, 164181215, 56688851, 230979639, 56690751, 604562856, 281029826, 739067792, 277614974, 189250000, 401874114, 658667778, 401158251, 248011407, 612564359, 621495514, 594568372, 143127587, 253225510, 113920547, 144266279, 385963701, 55165533, 155823831, 786789267, 187481096, 418898249, 826599392, 825205549, 744611074, 713352710, 290524756, 560740182, 67494239, 669588349, 785950665, 571590226, 165324554, 258641278, 345948915}

1951970366

Returns: 8877863016
248493

3160894

12795397

{4304353, 158675, 10591218, 9279948, 4682797, 8950513, 4489900, 7800280, 8800314, 10289667, 7834664, 2525951, 6098400, 2263994, 11258513, 3488342, 330636, 1647949, 908428, 6449421, 8286174, 3456640, 11020610, 11317858, 8872236, 11272366, 9662293, 2647851, 10608097, 11753844, 6169299, 973879, 9357373, 12475569, 3049417, 9226230, 3999147, 8078621, 8043833, 7162390, 956892, 11785210, 8340302, 11634270, 11792012, 11554364, 3930690, 8599653, 9664335, 5446841, 8552891, 3691158, 6515334, 12441844, 7652032, 2277111, 10737300, 2848879, 2882480, 3323772, 5578853, 31419, 9932195, 8780105, 12346407, 3355330, 9201076, 7513289, 2744444, 4892248, 8753012, 10771933, 7289619, 10983707, 7924695, 9301025, 7315766, 11518659, 360070, 2798504, 9772657, 7184304, 6691926, 541453, 9353938, 829046, 1016461, 10165279, 11573697, 1708713, 3482076, 8088309, 3158979, 9252787, 537784, 8952985, 2015903, 277225, 5566201, 4341758, 8046461, 4668175, 1653558, 12711778, 12393632, 11059872, 1963003, 6019691, 8108436, 151818, 4671688, 9587257, 7719491, 7482761, 3114418, 2068142, 4340636, 6185186, 7815590, 904377, 8254417, 11614222, 549818, 7144737, 10763084, 1374224, 11558710, 12754846, 11729482, 3523967, 6219370, 3291181, 3866591, 12147451, 9820587, 2402623, 3455020, 8312572, 8624245, 12494071, 1789567, 4875507, 10165634, 10699866, 12399585, 11498944, 9066252, 12746645, 1668291, 8220992, 3257596, 634070, 2520123, 12352163, 8492701, 12685470, 4336699, 2485668, 4705967, 6258187, 2463986, 5581879, 11146750, 8922515, 6212723, 2132075, 2405521, 7184826, 6823828, 9576367, 5328672, 11378261, 3016684, 10148735, 6293063, 317881, 1755035, 7121649, 12502533, 2798455, 11450282, 1090696, 1691044, 2178438, 1732363, 1282527, 3656738, 480796, 3035137, 6487988, 1619092, 1074697, 9368678, 8078680, 12557157, 292794}

527000108

Returns: 15456638603
242831

539

1292

{285, 106, 795, 326, 859, 1135, 60, 149, 500, 1032, 874, 1042, 1286, 1227, 130, 726, 498, 731, 546, 386, 91, 626, 92, 364, 122, 1073, 638, 631, 895, 697, 97, 753, 1232, 516, 375, 1066, 1286, 335, 391, 1269, 50, 1091, 954, 472, 532, 856, 984, 11, 107, 699, 1265, 834, 191, 156, 1273, 701, 428, 532}

1468955550

Returns: 14760293020
241977

1249037

683670

{609610, 352287, 212041, 270300, 287682, 479839, 262109, 505623, 186003, 602135, 429182, 407320, 207921, 36911, 339292, 46628, 246680, 70690, 122140, 287081, 251088, 505542, 462650, 146601, 649382, 100663, 8672, 615133, 349306, 297429, 598012, 41991, 277682, 392482, 390716, 382796, 165703, 92210, 269564, 94196, 505928, 562238, 530567, 489569, 357286, 634795, 405903, 170806, 309360, 126530, 466955, 443721, 612783, 277781, 261293, 252715, 48345, 164469, 34912, 319780, 678203, 439851, 518705, 259555, 222269, 59141, 285694, 608088, 609806, 222993, 540326, 40288, 337219, 287284, 139768, 436457, 125696, 121101, 239367, 556070, 188014, 640140, 190333, 632160, 116713, 410437, 339563, 281329, 7342, 524698, 560993, 286252, 185430, 535021, 8967, 660568, 540168}

1320042049

Returns: 436977077
249403

1180

931

{251, 289, 220, 698, 707, 345, 414, 842, 810, 845, 716, 381, 702, 758, 850, 217, 141, 781, 364, 527, 30, 476, 152, 560, 361, 913, 406, 92, 89, 76, 569, 430, 882, 802, 810, 517, 878, 158, 686, 190, 835, 173, 464, 71, 219, 376, 691, 393, 198, 510, 718, 73, 644, 571, 509, 204, 58, 21, 331, 576, 200, 390, 13, 142, 570, 687, 403, 377, 238, 112, 256, 205, 396, 264, 604, 473, 832, 748, 801, 880, 406, 432, 496, 36, 170}

666471151

Returns: 8270033001
243174

1209

3485

{}

156254224

Returns: 14779879364
242087

753192

1434363

{}

51078785

Returns: 14703770246
245853

49954160

763294249

{}

130852667

Returns: 15098142081
245627

10131520

12632150

{2402318, 7511441, 12142535, 7443495, 2704805, 11136713, 2682107, 8898584, 7153859, 220544, 2155602, 3045967, 8255637, 2125612, 6996974, 6210932, 420559, 143666, 9764382, 7697417, 3419589, 5078156, 2815737, 4683620, 8663682, 12152493, 5133461, 11022277, 10247320, 6968912, 3085413, 5388704, 1697283, 9816211, 6176554, 9285789, 11049637, 3737690, 12125260, 3534237, 10337591, 7675734, 7447263, 3140536, 3785600, 10955042, 4612406, 403248, 10592531, 1606216, 6627554, 804696, 6112451, 9527525, 10620512, 1029377, 7347784, 653484, 1783419, 4290611, 5727592, 11054342, 3539144, 6165729, 169288, 5810210, 3719202, 3544193, 3285348, 3110547, 5664513, 3936301, 6512563, 1005541, 11142433, 1945897, 2167664, 10234216, 8527379, 10403918, 7032077, 5475633, 6100103, 7527303, 8153920, 7743890, 8321952, 9947047, 2838468, 609949, 6996297, 9946224, 8516649, 9157153, 7795328, 5411130, 6217392, 7267738, 2859891, 8722101, 10884350, 9292801, 8968662, 3846796, 8329244, 6900404, 12532100, 778906, 5896509, 5105616, 10473654, 4129591, 7873690, 4103916, 3423277, 1542090, 8365444, 11115651, 6327606, 9741572, 3642717, 8353235, 395942, 5379540, 4170325, 3248640, 5544688, 12253854, 9839942, 8676867, 3759028, 292044, 6623634, 11884704, 681026, 8559756, 9778836, 5609213, 9316913, 9100695, 5488642, 5797725, 10624497, 8571341, 7709236, 10473235, 586650, 9696437, 9990015, 3097921, 1585557, 3472881, 1060007, 4201548, 9676460, 4464879, 6416106, 9840452, 11222496, 467934, 1644991, 8741966, 8522147, 11524679, 6099758, 12118597, 7003375, 4377159, 5927154, 4489025, 11604816, 2452283, 8340519, 9175995, 11230670, 10621650, 2136990, 10267775, 10268569, 9036851, 2555383, 5191898, 4744473, 776056, 10166120, 7299616, 6113308, 9158320, 10351149, 6505403, 11822972}

1889970991

Returns: 15088230568
249033

69716429

67220891

{34154827, 51667624, 21335764, 26277505, 53085907, 55020871, 62911092, 7724956, 39346784, 66472884, 12943114, 40330380, 49124246, 32992507, 11429803, 9400816, 4265608, 17252778, 35706073, 42405803, 54708455, 11981157, 28985322, 38445865, 27045458, 45582987, 13548003, 28918379, 64803766, 24656066, 9345035, 66073992, 6729954, 27178974, 8409385, 48508913, 4731151, 59159080, 8995649, 8518609, 64598725, 28423322, 21455741, 8760098, 22940570, 8915425, 25661119, 28318160, 24707673, 28895525, 53043204, 63010365, 54096627, 5129418, 22772859, 26210216, 7163467, 45695830, 12432685, 36323286, 62033617, 59586666, 54573832, 30215435, 65191510, 28007822, 34806744, 22889748, 52019034, 40679066, 23290341, 21507829, 41316998, 4170329, 5663721, 25596421, 26568850, 11076462, 58570648, 29572225, 623222, 20542590, 32857694, 62911272, 58681734, 11904463, 7019426, 22532122, 51383386, 38638063, 46064788, 40291878, 53687057, 66620881, 11902426, 39879409, 38183899, 41494331, 66154657, 16038721, 42931347, 44114236, 46125771, 59827106, 26941453, 5434685, 580807, 3324441, 66209133, 62288469, 38791429, 57206378, 44858914, 17460034, 9208739, 13673640, 49346912, 28498927, 37445068, 65140986, 38670696, 49325990, 42354543}

900330333

Returns: 14372495359
243080

42

87

{}

2063188795

Returns: 14550178965
246082

330352

842841

{335347, 616202, 401610, 120710, 123855, 441253, 754830, 7371, 25452, 209419, 407741, 179047, 707773, 738030, 707658, 707667, 688393, 506452, 128889, 40766, 248728, 693480, 21201, 219221, 81910, 446786, 431182, 724581, 208432, 231932, 607893, 144126, 496419, 587973, 471185, 816637, 81206, 167365, 827269, 325105, 82508, 696123, 453581, 713345, 612126, 820152, 421124, 302198, 548187, 187015, 151522, 716526, 229282, 370956, 543247, 388619, 268010, 81083, 146292, 573167, 700412, 85693, 261567, 631364, 320847, 384984, 480612, 754772, 662990, 172097, 677205, 531700, 463171, 635750, 457514, 103050, 168016, 739293, 784038, 578101, 41813, 153442, 499522, 824241, 623319, 324660, 641390, 712935, 427336, 485155, 531426, 429788, 692481, 547683, 531490, 434252, 525901, 241281, 532238, 282604, 184038, 446709, 632754, 117367, 123265, 761251, 804164, 794224, 329664, 395188, 198044, 234359, 417949, 727887, 826377, 840012, 43679, 156007, 68924, 807106, 638802, 188830, 387101, 370201, 682599, 451430, 295051, 751282, 631298, 62216, 475086, 455709, 751256, 24143, 749316, 755486, 810757, 579621, 38159, 16515, 732854, 53480, 635630, 123667, 42612, 109070, 572290, 117335, 562595, 255553, 15049, 568841, 150380, 316300, 530439, 502382, 2949, 86389, 525106, 627785, 570892, 649405, 838216, 601456, 278414, 811951, 497513, 195048, 225816, 229053, 349261}

363472480

Returns: 15115546034
249759

116097

523298

{}

2003191710

Returns: 15594980955
247288

2

1

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

1228137489

Returns: 0
240553

254052

412690

{}

1251129581

Returns: 14427757524
245569

2

1

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

814586981

Returns: 0
243443

29002445

29698198

{29638654, 9482949, 9892978, 21830965, 15554775, 16755542, 2052785, 928535, 27652090, 6809862, 136598, 14636374, 619905, 3483559, 18033721, 14032751, 25175864, 21995827, 5702011, 14871654, 9720058, 15376239, 24538033, 10676535, 13892666, 26901568, 15364927, 14899535, 25477885, 3794415, 20400507, 16439333}

944518017

Returns: 14817882386
244279

4

2

{}

122593667

Returns: 0
248224

20

10

{}

1992328053

Returns: 0
244030

1495

1980

{141, 1362, 1542, 1828, 1802, 852, 910, 1109, 553, 253, 1437, 671, 24, 1007, 1168, 1064, 1088, 1398, 648, 1125, 959, 228, 1368, 1696, 385, 905, 1721, 1699, 1947, 141, 1930, 507, 410, 1178, 1302, 576, 362, 1572, 1016, 1415, 907, 442, 1736, 1808, 1850, 932, 644, 559, 1251, 1484, 1056, 362, 1901, 1671, 1427, 919, 755, 467, 114, 1057, 19, 605, 376, 988, 1720, 380, 1002, 596, 1046, 316, 1326, 1494, 1115, 1340, 1311, 1414, 916, 1915, 1411, 1455, 754, 1018, 1286, 1564, 407, 1506, 1617, 188, 1415, 1342, 496, 850, 1067, 217, 1453, 496}

1359661468

Returns: 14878462792
240141

1

3

{}

203855037

Returns: 9584542741
247413

2988

2043

{1715, 249, 490, 279, 105, 154, 481, 1982, 518, 1922, 1267, 268, 271, 493, 234, 749, 664, 1969, 812, 844, 1233, 828, 825, 414, 499, 822, 847, 538, 1430, 1580, 1162, 287, 844, 1307}

751930650

Returns: 4424170700
247977

226

172

{}

594311353

Returns: 7170491801
240345

2

2

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

703597589

Returns: 7220715138
244379

12917

9598

{4820, 1750, 1238, 412, 3278, 9059, 2958, 8330, 8001, 5876, 9212, 5787, 5309, 7101, 30, 4201, 1006, 5561, 543, 665, 1690, 6737, 4966, 8192, 6693, 6477, 6345, 4172, 9050, 4625, 2533, 4822, 3736, 3941, 6464, 5933, 7551, 7580, 7389, 7570, 5244, 9435, 3279, 5263, 292, 5154, 747, 8234, 4512, 1488, 1586, 6311, 9183, 7726, 7780, 8238, 8910, 4180, 6147, 7362, 5790, 9004, 9048, 1202, 6021, 6533, 4433, 1568, 9209, 8925, 7308, 2209, 7711, 2548, 9117, 5770, 822, 4798, 8069, 8059, 2638, 9516, 2199, 7703, 585, 3973, 8706, 6432, 4657, 4440, 722, 7335, 847, 4578, 1683, 8897, 2617, 9074, 368, 5622, 7480, 7497, 3357, 7324, 648, 6752, 7044, 344, 4419, 3774, 5572, 5145, 2583, 8004, 8630, 6919, 9508, 4896, 5264, 5700, 8565, 732, 7909, 8097, 4640, 1198, 7297, 2655, 3326, 4246, 936, 8294, 8438, 5692, 5709, 4988, 2868, 2005, 3427, 5135, 2250, 9583, 6575, 2654, 6278, 6997, 8856, 7958, 3661, 5031, 1598, 2610, 5190, 1830, 7296, 4313, 2511, 4339, 4192, 1661, 7054, 5253, 3016, 1232, 3799, 2060, 2607, 3763, 522, 8593, 76, 5407, 9438, 914, 2121, 1438, 4482, 508, 881, 5986, 107, 9464, 4379, 4807, 62, 2843, 7525, 3433, 3932, 5174, 6302, 5068}

522170821

Returns: 6390371723
241702

967378923

622498546

{}

756152175

Returns: 2190536284
244799

70

37

{32, 29, 16, 32, 17, 36, 21, 20, 3, 2, 25, 21, 13, 37, 11, 11, 8, 27, 32, 11, 7}

355112072

Returns: 128953492
241616

182116

246337

{}

1206275013

Returns: 14575358840
249366

261600

178954

{}

1980423188

Returns: 4505101580
241116

1129619

1561184

{}

1570733817

Returns: 14539714646
245585

5386905

3306985

{451489, 2089974, 1021859, 140488, 57443, 2613102, 2035587, 1834437, 348203, 110422, 699394, 1756186, 2995390, 2354843, 1216035, 3023770, 239056, 1173480, 1051197, 249229, 1064619, 517478, 442578, 2205792, 3007398, 2696379, 3268900, 1146918, 1845476, 734662, 2356561, 765456, 679261, 1944593, 344308, 3180518, 2161575, 202715, 2135516, 1497180, 2881624, 1616570, 213977, 481678, 2308324, 1573032, 1271264, 2368040, 2035141, 2859950, 1340085, 2660595, 335535, 1073147, 1539658, 724361, 2586656, 375750, 1319325, 1130988, 771579, 2441264, 1862269, 126947, 1711840, 2824466, 1696836, 1783608, 2051834, 2245762, 1723130, 2091612, 890509, 2135910, 1827599, 3143764, 141795, 2665362, 1781354, 2666228, 891940, 4823, 1612647, 1888447, 2819175, 1241428, 1165543, 1485377, 709154, 2653375, 305781, 1206517, 416185, 1219202, 1763893, 2729026, 3122466, 254385, 2033077, 511374, 2171603, 1756546, 152428, 102322, 2924526, 2935780, 659915, 893260, 487508, 688578, 2289968, 1675190, 455600, 1421472, 70512, 994994, 806927, 2815475, 1968851, 686538, 2009678, 776666, 1077477, 226910, 165668, 775356, 3127347, 2295262, 695467, 665888, 2169375, 833823, 694358, 2117498, 1977260, 3187299}

621692263

Returns: 2068066955
246792

139

93

{}

962268816

Returns: 3815653850
244518

13

20

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

1453597035

Returns: 14195195498
243947

132

70

{}

612725387

Returns: 172381500
244290

56

737

{271, 16, 374, 509, 559, 671, 557, 253, 713, 284, 116, 591, 494, 519, 630, 175, 127, 478, 52, 222, 597, 534, 337, 522, 674, 714, 44, 340, 704, 391, 488, 86, 448, 281, 577, 75, 351, 187, 655, 426, 100, 599, 540, 667, 651, 81, 453, 149, 398, 643, 607, 553, 363, 647, 438, 24, 486, 440, 187, 200, 428, 373, 236, 64, 574, 43, 66, 419, 607, 202, 270, 397, 379, 335, 282, 265, 550, 269, 397, 103, 499, 217, 476, 262, 243, 375, 470, 210, 59, 388, 75, 511, 397, 217, 636, 49, 618, 677, 311, 118, 229, 28, 438, 222, 225, 209, 522, 566, 219, 704, 86, 84, 201, 82, 67, 383, 702, 297, 293, 449, 576}

681689179

Returns: 14880829596
248989

5901

7914

{2887, 7838, 2177, 7824}

2062978491

Returns: 15524314179
241065

1072

2029

{1728, 1457, 1070, 1454, 834, 2012, 1353, 1186, 591, 1187, 107, 955, 2013, 1714, 712, 773, 1304, 1921, 1159, 1357, 2023, 28, 842, 1719, 1217, 1158, 1002, 138, 1866, 592, 1895, 1528, 1818, 1497, 1500, 700, 1081, 1673, 1792, 384, 1400, 387, 614, 803, 1517, 206, 1847, 228, 1665, 269, 714, 1417, 1687, 686, 689, 1392, 1866, 378, 387, 1279, 7, 120, 221, 1259, 204, 1391, 936, 1168, 1891, 25, 187, 1782, 70, 1577, 1477, 141, 958, 1833, 425, 442, 546, 505, 947, 1915, 1941, 1461, 529, 418, 414, 1714, 1080, 1295, 1443, 454, 788, 403, 1241, 1865, 1387, 1662, 1787, 1398, 1807, 1355, 215, 1909, 2015, 1468, 517, 885, 802, 365, 403, 286, 1148, 897, 1815, 1612, 1670, 201, 560, 1266, 974, 1079}

247812231

Returns: 14531005949
241848

62276

80814

{79387, 70243, 6922, 20519, 36871, 75356, 7257, 80660, 69677, 44391, 52848, 22916, 22981, 45893, 10585, 40379, 65133, 75363, 169, 12967, 66780, 51946, 4578, 28701, 78238, 74059, 55257, 28620, 35413, 53335, 58658, 8995, 6597, 33207, 56079, 1186, 43772, 18143, 25447, 10541, 38665, 80560, 50913, 59255, 55451, 42585, 30645, 64749, 38896, 30675, 10114, 45371, 36344, 1901, 68384, 40815, 49628, 66508, 47362, 22046, 16260, 77827, 61007, 67019, 60183, 73377, 34248, 47137, 38475, 75109, 74558, 32744, 69024, 40852, 31009, 51781, 41644, 53351, 51922, 73750, 32051, 28591, 7320, 26912, 32863, 39400, 31016, 17782, 49098, 37684, 73322, 72205, 47736, 61926, 24291, 9619, 5022, 39415, 67158, 38341, 75147, 15541, 66655, 31739, 33090, 14103, 9820, 37810, 65477, 49951, 26729, 19854, 25725, 19293, 13724, 403, 30784, 74897, 78463, 43425, 30372, 20050, 45308, 14424, 17204, 75971, 56065, 44674, 34559, 66043, 62961, 57367, 55580, 57470, 60138, 66902, 34295, 74450, 22022, 29305, 17933, 51375, 65887, 17354, 16927}

1305618260

Returns: 14620282981
250000

5000000

5000000

{1 }

42

Returns: 15657523462
250000

10000000

10000000

{1 }

42

Returns: 15628856862

Statistics

Problem Statement for "LimitedSwaps"

Problem Statement

Definition

Notes

Constraints

Examples