TopCoder Statistics - Problem Statement

Problem Statement

An airplane has S seats in each row. There are R rows of seats.

Below, a section will represent any non-empty contiguous sequence of rows, and a column will represent a collection of seats that are at the same position from the left in different rows. (I.e., columns of seats are orthogonal to rows of seats, just as you would expect.)

Each seat of the plane is either empty or occupied.

A section is called left-to-right balanced if within that section each column contains the same number of passengers.

You are given S, R, and the int[] A that encodes the positions of occupied seats. Count all left-to-right balanced sections on this airplane, and return their count.

In the array A, we use bitmasks to encode occupied seats. Each element of A is a S-bit integer that represents one row of seats, from the front to the back. Within each element of A, the individual bits (lowest to highest) represent occupied seats (1) and empty seats (0) from the left of the row to the right.

In order to keep the input size small, A is pseudorandom. Use the following pseudocode to generate it:


L = length(Aprefix)
for i = 0 to L-1:
    A[i] = Aprefix[i]

state = Aprefix[L-1]
for i = L to R-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    A[i] = state &gt;&gt; (31 - S)

Definition

Class:: BalancedAirplane
Method:: count
Parameters:: int, int, int[]
Returns:: long
Method signature:: long count(int S, int R, int[] Aprefix)
(be sure your method is public)

Notes

In your implementation of the pseudocode, watch out for integer overflow. In particular, "state" should be at least a 64-bit integer variable.
In the pseudocode, >> denotes the right shift operator. An equivalent operation is dividing by 2^(31 - S) and rounding down (truncating).
The reference solution does not depend on the input being pseudorandom.

Constraints

S will be between 1 and 30, inclusive.
R will be between 1 and 100,000, inclusive.
Aprefix will have between 1 and min(R, 200) elements, inclusive.
Each element of Aprefix will be between 0 and (2^S)-1, inclusive.

Examples

4

10

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

Returns: 55

This small airplane is empty. All its sections are balanced.
6

11

{1, 0, 2, 0, 4, 0, 8, 0, 16, 0, 32}

Returns: 6

There are six people in this entire airplane: one in each column. The entire airplane is balanced, and each section that consists of a single empty row is also balanced.
6

11

{63, 0, 63, 0, 63, 4, 0, 63, 0, 63, 0}

Returns: 30

This airplane has alternating full and empty rows, except for the middle row with just a single passenger. Any section that does not contain the middle row is balanced.
4

7

{12, 3, 14, 1, 7, 8, 7}

Returns: 7
1

100000

{1}

Returns: 5000050000
6

20

{42}

Returns: 1

A = {42, 37, 33, 29, 49, 27, 2, 26, 51, 39, 45, 11, 33, 35, 15, 58, 7, 42, 21, 11, } The only balanced section consists of two rows close to the end of the airplane (the rows represented by bitmasks 42 and 21).
30

100000

{41,0,0,0,0,42}

Returns: 10
10

100000

{199}

Returns: 364
29

100000

{42}

Returns: 0
1

97882

{1}

Returns: 4790491903
2

99675

{3}

Returns: 27312526
3

98214

{6, 0, 1, 0, 4, 7, 0, 5, 6, 3, 3, 5, 7, 3, 0, 5, 5, 5, 3, 3, 0, 2, 5, 1, 5, 6, 4, 1, 3, 5, 3, 7, 1, 6, 5, 4, 3, 4, 5, 0, 7, 4, 6, 4, 3, 1, 3, 6, 7, 4, 2, 7, 0, 2, 1, 1, 4, 7, 6, 5, 0, 4, 7, 5, 0, 3, 3, 5, 6, 2, 2, 7, 3, 2, 1, 2, 5, 6, 1}

Returns: 377796
4

97186

{3, 13, 2, 11, 0, 8, 1, 4, 5, 15, 6, 15, 14, 0, 2, 5, 4, 10, 1, 7, 1, 12, 3, 0, 2, 9, 1, 9, 7, 4, 8, 2, 15, 10, 1, 3, 13, 13, 11, 9, 15, 4, 2, 3, 14, 14, 0, 13, 2, 9, 15, 3, 7, 11, 10, 5, 14}

Returns: 47744
5

95185

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

Returns: 14917
6

96441

{0}

Returns: 6171
7

96139

{99, 0, 98, 127, 116, 95, 31, 102, 26, 22, 107, 105, 26, 44, 127, 121, 112, 23, 101, 83, 110, 50, 80, 101, 19, 33, 124, 85, 26, 64, 124, 23, 91, 7, 101, 20, 57, 53, 65, 78, 29, 15, 73, 45, 124, 61, 103, 121, 1, 102, 60, 95, 27, 86, 16, 40, 27, 61, 46, 20, 36, 43, 42, 19, 23, 32, 100, 89, 31, 106, 75, 56, 88, 23, 80, 26, 9, 51, 34, 84, 23, 81, 109, 90, 108, 112, 111, 105, 125, 5, 49, 83, 12, 109, 25, 112}

Returns: 2834
8

99774

{171, 223, 30, 170, 95, 209, 240, 243, 61, 117, 101, 13, 252, 166, 72, 83}

Returns: 1328
9

97368

{305, 45, 6, 262, 352, 196, 220, 378, 379, 136}

Returns: 618
10

96658

{617, 613, 863, 226, 865, 856, 711, 1019, 525, 92, 1005, 470, 554, 830, 119, 49, 805, 390, 854, 751, 181, 706, 694, 903, 138, 134, 969, 546, 131, 332, 419, 465, 864, 967, 404, 607, 12, 233, 24, 514, 436, 763, 964, 438, 680, 820, 78, 849, 666, 705, 15, 223, 42, 636, 99, 447, 6, 71}

Returns: 358
11

99543

{1570, 1900, 782, 367, 1135, 1619, 1424, 154, 267, 1245, 1274, 213, 1809, 1898, 1666, 1362, 368, 1037, 1722, 1529, 402, 1545, 1546, 722, 1211, 122, 124, 783, 516, 912, 353, 31, 1732, 1751, 1705, 1732, 522, 630, 1538, 1884, 1075, 604, 307, 162, 989, 525, 288, 71, 561, 502, 521, 1196, 1713, 1999, 96, 685, 597, 947, 480, 620, 1167, 1983, 2007, 1886, 1266, 1678, 1842, 751, 52, 1752, 1996, 2005, 1671, 1406, 1535, 1236}

Returns: 174
12

97517

{291}

Returns: 59
13

99311

{7657, 6428, 1660, 1763, 556, 6025, 5573, 2416, 17, 4266, 5754, 2621, 651, 6755, 7879, 5299, 2416, 4352, 4196, 5419, 6696, 1827, 3366, 2893, 3776, 4622, 4025, 7547, 5585, 2557, 5913, 1827, 2399, 2911, 3727}

Returns: 32
14

99422

{6748}

Returns: 20
15

97041

{24928}

Returns: 6
16

96408

{25336, 52773, 7034, 61460, 42832, 9784, 33929, 12482, 18154, 27296, 35873, 51051, 14547, 33497, 46884, 15679, 49262, 48790, 29489, 38133, 32891, 42050, 5023, 27191, 38827, 58464, 42625, 14970, 19170, 23995, 34135, 44963, 35912, 12408, 38609, 27263, 4963, 35461, 28450, 25998, 64533, 64907, 10150, 50036, 3051, 19648, 13949, 54960, 39452, 28878, 54269, 24876, 11292, 28077, 29295, 11701, 54956, 40508, 41335, 49008, 15564, 11937, 41191}

Returns: 3
17

98724

{22712, 89302, 126943, 57391, 15562, 83615, 80847, 99350, 69423, 15562, 19902, 67124, 119858, 57739, 127229, 74289, 83496, 114405, 65220, 86140, 54979, 46522, 49651, 62724, 10880, 7702, 68298, 77253}

Returns: 3
18

96626

{91128}

Returns: 3
19

97685

{164830, 517400, 79202, 36896, 409867, 486767, 471918, 308567, 98506, 516232, 283617, 349998, 295984, 227533, 448251, 79143, 267838, 401136, 339278, 482039, 306114, 168897, 253812, 191245, 380285, 241413, 323999, 38031, 227115, 496673, 25851, 372823, 9678, 298201, 287144, 435995, 247535, 476163, 476318, 55475, 86732, 136451, 421944, 464770, 196285, 259919, 48136, 421240}

Returns: 0
20

98704

{55565, 940257, 1018147, 338163, 332464, 499923, 577998, 667954, 406140, 1034051, 576172, 964226, 535575, 706761, 244376, 463167, 533168, 473943, 68548, 289190, 512834, 939315, 177778, 679723, 453112, 678460, 197305, 545775, 329410, 582986, 756745, 292601, 345249, 165117, 386416, 117009, 376557, 215321, 599986, 88018, 672271, 388960, 181250, 942957, 578383, 206854, 625883, 409692, 1037953, 301980, 285754, 510227, 504309, 655323, 538643, 952873, 55135, 648151, 395305, 53338, 903397, 365491, 563526, 1021132, 395723, 940610, 26955, 774971, 518752}

Returns: 1
21

98288

{739772, 750818, 210495, 902349, 1321853, 1688591, 1257815, 1122533, 389382, 1269905, 965011, 182352, 1976632, 1283634, 989607, 1240616, 1914606, 751319, 741599, 1269872, 1930020, 1212801, 1222365, 217189, 1286280, 159115, 287632, 1676415, 1782522, 613899, 1587257, 1613023, 940335, 1734593, 1866321, 765045, 1059082, 1680346, 1343526, 1405835, 522784, 1585814, 1826237, 589529, 376554, 1818842, 1046977, 988511, 14827, 1078050, 106466, 1413741, 1663551, 1270367, 830536, 1063661, 283834, 212342, 1018817, 732406, 1478844, 1452332, 350625, 2093723, 1094275}

Returns: 0
22

97298

{1714396}

Returns: 0
23

95392

{3905407}

Returns: 0
24

95895

{6193515}

Returns: 0
25

98250

{18808217, 10767247, 10834516, 21481765, 10283385, 18671564, 32351856, 6624490, 19172626, 17542585, 10133992, 26242412, 14720083, 14884997, 11953050, 5786909, 19466043, 9780835, 31214479, 19810534, 2118851, 7153065, 14822484, 13913559, 7133730, 13216541, 33513761, 25719808, 20295782, 17135623, 816738, 22509538, 24184348, 28183886, 6488926, 5901698}

Returns: 0
26

97699

{18486861, 33010336, 66742301, 26930039, 4578539, 22509785, 3181086, 42109692, 30540260, 49229747, 30745467, 32840645, 65583565, 49726459, 27082090, 56998457, 25023093, 62223855, 29859217, 4772120, 54586008, 62562693, 31115966, 56845853, 2440352, 56742088, 8850366, 65848079, 25953203, 52458205, 25168310, 276398, 32155664, 66067715}

Returns: 0
27

99258

{128676566}

Returns: 0
28

97574

{119414867}

Returns: 0
29

95441

{527463247, 473560128, 535136612, 429421179, 431799896, 150271760, 449470262, 383566398, 13877558, 364707772, 114938110, 388544002, 414265720, 281294714, 164181214, 56688850, 230979638, 56690750, 281029825, 277614973, 189249999, 401874113, 401158250, 248011406, 143127586, 253225509, 113920546, 144266278}

Returns: 0
30

97944

{374962191, 837796497, 581049511, 134988476, 330649106, 517282554, 691897828}

Returns: 0
7

95512

{87}

Returns: 2813
6

99197

{5}

Returns: 6458
8

95193

{135, 246, 4, 161, 218, 117, 121, 183, 226, 123, 17, 191, 180, 175}

Returns: 1276
10

99711

{488, 72, 257, 683, 200, 743, 785, 517, 198, 464, 685, 447, 964, 225, 853, 723, 586, 489, 535, 731, 82, 991, 639, 809, 532, 452, 233, 424, 777, 994, 518, 305, 909, 31, 348, 169, 152, 544, 975, 892, 748, 67, 542, 966, 645, 45, 497, 432, 708, 883, 376, 361, 962, 406, 261, 201, 279, 704, 803, 221, 546, 909, 0, 250, 848, 137, 756, 42, 541, 85, 287, 371, 1005, 411, 1013, 928, 20, 151, 358, 308, 692, 95, 480, 125, 775, 252, 45, 181, 619, 110, 630, 489, 309, 559, 165, 1006, 701, 106}

Returns: 329
3

98387

{4}

Returns: 400835
9

99896

{119, 472, 464, 18, 445, 67, 294, 501, 116, 251, 360, 339, 170, 473, 23, 100, 470, 471}

Returns: 657
6

99463

{24, 36, 5, 33, 61, 49, 8, 13, 61, 46, 39, 52, 26, 11, 13, 39, 51, 42, 46, 13, 11, 54, 46, 6, 44, 7, 50, 34, 32, 26, 37, 26, 59, 38, 56, 56, 40, 7, 19, 61, 0, 3, 54, 58, 56, 32, 37, 13, 38, 15, 21, 54, 43, 63, 54, 30, 33, 40, 2, 48, 59, 22, 48, 5, 23, 23, 9, 62, 52, 7, 28, 59, 22, 50, 0, 17, 9, 49, 0, 49, 63, 58, 47, 15, 51, 13, 11, 53}

Returns: 6673
8

99509

{255, 243, 224, 47, 202, 167, 221, 100, 161, 203, 38, 67, 249, 170}

Returns: 1345
3

97068

{5, 0, 6, 1, 3, 3, 4, 4, 1, 0, 4, 2, 7, 3, 6, 7, 0, 6, 3, 5, 1, 5, 1, 2, 1, 3, 2, 1, 2, 2, 2, 1, 1, 2, 6, 5, 1, 6, 4, 3, 5, 1, 5, 1, 0, 3, 2, 5, 1, 5, 6, 5, 6, 7, 6, 6, 7, 0, 3, 5, 0, 6, 1}

Returns: 374646
9

99774

{342, 447, 60, 341, 191, 418, 480, 486, 122, 234, 203, 27, 505, 333, 145, 167}

Returns: 645
6

95594

{5}

Returns: 6224
2

97098

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

Returns: 20380005
2

97057

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

Returns: 18854921
6

99669

{62}

Returns: 6450
2

96371

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

Returns: 20191206
4

99221

{8, 12, 3, 8, 11, 3, 12, 11, 7, 9, 8, 10, 1, 6, 9, 14, 10, 3, 4, 5, 8, 10, 8, 3, 9, 6, 1, 8, 6, 6, 15, 15, 2, 12, 0, 4, 3, 13, 9, 7, 13, 6, 2, 6, 7, 2, 13, 9, 10, 11, 3, 2, 10, 14, 6, 3, 2, 10, 15, 7, 1, 10, 9, 12, 8, 1, 2, 8, 14, 7, 15, 9, 10, 13, 7, 10, 6, 5, 6, 7, 1, 0, 8, 9, 6, 10, 10, 5, 10, 11, 5, 5, 15, 2, 1, 12}

Returns: 48703
9

98686

{504, 276, 341, 289, 222, 437, 77, 261, 391, 331, 470, 298, 164, 247, 186, 371, 235, 316, 37, 221, 485, 25, 364, 9, 291, 280, 425, 241, 465, 465, 54, 84, 133, 412, 453, 191, 253, 47}

Returns: 641
8

98704

{13, 229, 248, 82, 81, 122, 141, 163, 99, 252, 140, 235, 130, 172, 59, 113, 130, 115, 16, 70, 125, 229, 43, 165, 110, 165, 48, 133, 80, 142, 184, 71, 84, 40, 94, 28, 91, 52, 146, 21, 164, 94, 44, 230, 141, 50, 152, 100, 253, 73, 69, 124, 123, 159, 131, 232, 13, 158, 96, 13, 220, 89, 137, 249, 96, 229, 6, 189, 126}

Returns: 1351
8

99155

{91, 25, 110, 161, 206, 153, 137, 47, 155, 117, 22, 241, 156, 120, 151, 233, 91, 90, 155, 235, 148, 149, 26}

Returns: 1390
6

95310

{51, 54, 18, 48, 49, 28, 52, 56, 23, 32, 51, 41, 42, 15, 48, 55, 17, 11, 55, 31, 30, 0, 32, 3, 43, 50, 38, 25, 32, 8, 6, 31, 22, 45, 44, 10, 63, 33, 35, 47, 26, 6, 33, 62, 29, 13, 39, 23, 50, 35, 25, 35, 20, 20, 40, 19, 35, 61, 12, 36, 33, 19, 50, 28, 28, 22, 11, 37, 18, 59, 37, 4, 13, 28, 26, 13, 25, 63, 49, 38, 32, 1, 42, 46, 53}

Returns: 6386
3

95720

{3}

Returns: 328196
4

97014

{6}

Returns: 47142
2

96373

{1}

Returns: 18691100
7

96876

{94}

Returns: 2780
5

98478

{14}

Returns: 15546
2

98331

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

Returns: 27117707
10

97151

{525}

Returns: 309
2

99531

{3}

Returns: 27286958
10

98825

{276}

Returns: 326
5

95161

{24, 31, 13, 10, 23, 3, 11, 15, 30, 30, 27, 3, 31}

Returns: 14727
5

99199

{14}

Returns: 15655
8

98736

{87, 101, 170, 0, 102, 229, 83, 149, 222, 241, 223, 10, 85, 219, 204, 16, 25, 31}

Returns: 1300
3

96700

{0, 1, 0, 5, 4, 7, 4, 1, 1, 5, 7, 0, 4, 7, 7, 2, 1, 4, 5, 7, 0, 7, 0, 6, 1, 3, 5, 3, 3, 2, 3, 7, 1, 4, 1, 7, 3, 0, 2, 4, 2, 4, 5, 2, 5, 5, 2, 2, 6, 6, 5, 2, 6, 0, 1, 6, 2, 1, 1, 2, 1, 1}

Returns: 373942
5

95234

{6}

Returns: 14935
3

99574

{1, 2, 5, 2, 2, 4, 3, 2, 0, 6, 2, 6, 0, 1, 3, 6, 1, 5, 3, 5, 4, 3, 0, 4, 0, 2, 0, 4, 4, 6, 5, 0, 5, 4, 2, 2, 3, 0, 7, 3, 4, 6, 7, 0, 0, 5, 6, 1, 1, 5, 3, 4, 5, 1, 2, 7, 6, 5, 3, 4, 4, 7}

Returns: 340512
5

98950

{24}

Returns: 15340
5

95288

{15, 4, 7, 17, 15, 30, 28, 8, 6, 0, 21, 18, 2, 16, 23, 23, 23, 10, 5, 16, 5, 30, 29, 21, 24, 10, 18, 7, 28, 27, 16, 15, 15, 2, 10, 2, 19, 26, 31, 15, 13, 3}

Returns: 15083
6

99750

{4, 41, 35, 17, 53, 15, 14, 29, 22, 23, 14, 50, 41, 34, 0, 34, 22, 1, 39, 38, 52, 47, 42, 31, 36, 27, 43, 51, 47, 27, 17, 45, 3, 59, 18, 45, 50, 11, 11, 9, 53, 19, 23, 21, 57, 8, 27, 46, 49, 24, 63, 9, 63, 25, 7, 2, 41, 24, 48, 1, 17, 50, 47, 29, 13, 31, 25, 49, 32, 59, 50, 53, 61, 4, 21}

Returns: 6275
4

96587

{4}

Returns: 48988
2

95298

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

Returns: 18299050
30

100000

{512430803, 420870972, 734254217, 759033630, 803518015, 71434131, 519795900, 949662361, 771122961, 510546714, 494022072, 918477525, 677697581, 19618885, 1034126712, 566520437, 1345417, 220022263, 50809160, 898791926, 87850800, 842705655, 830124984, 552822147, 737595658, 974250758, 923817927, 134271793, 755584080, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 804257791, 787480575, 787480575, 787480575, 787480575, 787480575, 787480575, 787480575, 787480575, 787480575, 787480575, 787480575, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653262847, 653131775, 653131775, 653131775, 586014719, 586014719, 586014719, 586014719, 586014719, 552460287, 552460287, 551935999, 551935999, 551935999, 551935999, 551935999, 551935999, 551870463, 551870463, 549773311, 549773311, 549773311, 549773055, 549510911, 549510911, 549510911, 549510911, 549510911, 549510911, 549510911, 549510911, 549510907, 549510907, 549510888, 549510760, 549510728, 549510656, 549510656, 549510656, 549510656, 549510656, 549509632, 549509632, 549509632, 549509120, 549509120, 545314816, 545314816, 545314816, 545314816, 545314816, 545314816, 545314816, 545314816, 545314816, 545314816, 545314816, 545314816, 545282048, 545282048, 545282048, 545282048, 545282048, 545277952, 545277952, 545277952, 545277952, 545277952, 545277952, 545277952, 545277952, 545277952, 545277952, 545277952, 545277952, 545277952, 545275904, 545275904, 545275904, 545275904, 545275904, 545275904, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 8404992, 16384, 16384, 16384, 16384, 16384, 16384, 16384, 16384, 16384, 16384, 16384, 16384, 16384, 4247}

Returns: 1
30

100000

{42 }

Returns: 0
30

100000

{1 }

Returns: 0
30

100000

{494374691 }

Returns: 0

Statistics

Problem Statement for "BalancedAirplane"

Problem Statement

Definition

Notes

Constraints

Examples