TopCoder Statistics - Problem Statement

Problem Statement

You are given the map of a city: an undirected graph on N vertices, numbered from 0 to N-1. Your task is to plan a parade somewhere in the city. The people in the parade want to walk along five consecutive streets, and obviously, the five streets should be distinct. The parade may cross the same intersection multiple times. Formally, the parade is a tour of length 5. Return the number of different parades that can be organized in the given city

Use the following pseudocode to generate the graph:

state = seed

for x = 0 .. N-1:
    for y = x+1 .. N-1:
        state = (state * 1103515245 + 12345) modulo 2^31
        if state &lt; threshold:
            add edge x-y

L = length(toggle) / 2
for i in 0 .. L-1:
    x = toggle[2*i]
    y = toggle[2*i+1]
    if we have the edge x-y:
        remove edge x-y
    else:
        add edge x-y

Definition

Class:: ParadePlanner
Method:: count
Parameters:: int, int, int, int[]
Returns:: long
Method signature:: long count(int N, int seed, int threshold, int[] toggle)
(be sure your method is public)

Notes

The order in which the parade traverses the streets matters. Thus, there can be multiple parades that use the same set of streets.
You should return the actual number of possible parades and NOT its value modulo something.

Constraints

N will be between 1 and 500, inclusive.
seed will be between 0 and 2^31 - 1, inclusive.
threshold will be between 0 and 2^31 - 1, inclusive.
toggle will have between 0 and 200 elements, inclusive.
toggle will have an even number of elements.
Each element of toggle will be between 0 and N-1, inclusive.
For each valid i, toggle[2*i] will be smaller than toggle[2*i+1].

Examples

10

47

0

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

Returns: 2

The generated city has no streets. Then we use toggle[] to add five streets. This creates two possible parades: 0-1-7-2-3-4 and 4-3-2-7-1-0.
4

47

2147483647

{}

Returns: 72

The generated city has four locations, each two of them connected by a street. There's quite a number of possible parades. One of them is 0-1-2-3-0-2.
6

4747

0

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

Returns: 12

Six locations on a circle. We can choose where we start the parade (6 options) and we can choose the direction in which we walk (2 options). Once we make those choices, the route of the parade is fixed.
7

47

1000000000

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

Returns: 46

We generate a random city with 8 streets: 0-1, 0-2, 0-4, 0-6, 1-4, 1-5, 2-3, and 2-4. Then we toggle street 0-1 twice (so that it remains in the city), street 0-2 (to make it disappear) and street 0-3 (to make it appear).
500

4247

0

{}

Returns: 0
500

352352

123456789

{}

Returns: 10337532458
500

3234243

987654321

{}

Returns: 323383201733242
500

0

1987654321

{}

Returns: 10459173413032332
500

47474747

2147483647

{}

Returns: 15345495876753000
2

40007

1234567890

{}

Returns: 0
1

1511168161

268543586

{}

Returns: 0
2

1847635854

1948501517

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

Returns: 0
3

2079845253

940300094

{}

Returns: 0
3

254969676

1369957303

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

Returns: 0
4

1062406038

1724136063

{}

Returns: 12
4

769082629

757526682

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

Returns: 0
5

415291270

377708718

{}

Returns: 4
5

1415570502

1116947460

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

Returns: 86
6

1468955550

518430183

{}

Returns: 0
6

652831561

1935468378

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

Returns: 34
7

1784041460

789865547

{}

Returns: 980
7

1379507973

434504372

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

Returns: 894
499

1301730102

745290886

{296, 458, 82, 157, 15, 21, 276, 329, 97, 101, 112, 283, 2, 496, 449, 461, 125, 362, 45, 263, 389, 394, 308, 402, 85, 339, 147, 175, 153, 417, 204, 254, 45, 152, 158, 252, 306, 417, 163, 413, 168, 175, 20, 312, 2, 12, 461, 493, 147, 218, 171, 325, 66, 489, 330, 486, 35, 348, 142, 463, 147, 307, 188, 368, 434, 461, 96, 109, 439, 461, 95, 437, 106, 245, 190, 305, 300, 437, 215, 467, 12, 102, 345, 360, 121, 338, 10, 107, 39, 431, 353, 444, 101, 113, 296, 421, 70, 242, 81, 456, 40, 339, 147, 438, 73, 349, 111, 181, 279, 341, 443, 448, 41, 127, 187, 234, 368, 445, 226, 310, 82, 360, 20, 74, 243, 402, 158, 414, 208, 236, 256, 466, 441, 469, 117, 259, 89, 218, 308, 476, 57, 60, 371, 392, 204, 355, 189, 437, 180, 333, 11, 450, 365, 368, 20, 53, 279, 455, 57, 455, 7, 277, 154, 447, 42, 426, 256, 306, 278, 317, 409, 495, 111, 413, 238, 350, 21, 255, 383, 393, 60, 296, 408, 465, 377, 443}

Returns: 74095738830320
499

1261824165

1779138580

{}

Returns: 5900605289135400
498

1065391573

1271306823

{171, 413, 197, 270, 313, 386, 168, 226, 1, 76, 156, 404, 41, 387, 139, 276, 376, 406, 29, 157, 64, 311, 255, 404, 50, 254, 57, 186, 237, 408, 94, 142, 17, 301, 297, 350, 16, 451, 149, 174, 12, 251, 355, 472, 197, 489, 274, 391, 284, 339, 260, 276, 79, 124, 180, 408, 327, 397, 216, 484, 92, 105, 254, 487, 182, 277, 215, 432, 202, 409, 27, 304, 141, 453, 63, 150, 63, 274, 315, 362, 58, 366, 320, 331, 189, 195, 476, 480, 86, 334, 214, 362, 360, 394, 14, 129, 177, 353, 30, 365, 288, 372, 51, 440, 159, 343, 286, 387, 36, 219, 249, 282, 270, 472, 261, 421, 99, 325}

Returns: 1099934292818698
473

888051891

1631711390

{174, 461, 126, 199, 143, 280, 119, 140, 22, 413, 58, 229, 170, 237, 220, 409, 143, 227, 170, 457, 132, 209, 16, 414, 146, 377, 400, 422, 304, 466, 88, 202, 41, 138, 76, 146, 299, 410, 87, 241, 267, 349, 262, 337, 127, 457, 253, 370, 161, 219, 271, 291, 114, 115, 150, 154, 60, 77, 248, 346, 35, 100, 264, 460, 204, 247, 129, 461, 23, 195, 144, 409, 270, 348, 337, 400, 362, 442, 7, 211, 36, 92, 213, 437, 107, 396, 404, 457, 221, 431, 150, 333, 237, 255, 2, 223, 9, 53, 87, 226, 148, 234, 162, 211, 227, 388, 57, 311, 250, 449, 29, 331, 49, 389, 70, 308, 18, 292, 163, 239, 186, 376, 35, 340}

Returns: 2790953778900456
496

1906837079

1158129014

{5, 251, 271, 349, 161, 281, 341, 423, 96, 226, 102, 294, 90, 392, 253, 353, 433, 451, 312, 370, 28, 264, 4, 151, 93, 246, 331, 373, 278, 334, 327, 353}

Returns: 679870345711882
457

2134621642

853521546

{123, 212, 162, 336, 4, 24, 268, 451, 24, 231, 172, 270, 254, 373, 26, 38, 120, 129, 67, 123, 58, 187, 165, 202, 210, 308, 103, 124, 205, 211, 134, 357, 71, 210, 351, 363, 225, 360, 18, 335, 96, 160, 353, 411, 183, 356, 57, 219, 45, 160, 422, 443, 363, 443, 53, 382, 157, 280, 139, 275, 84, 316, 176, 329, 2, 142, 6, 309, 153, 208, 74, 140, 168, 216, 230, 247, 271, 389, 51, 60, 93, 380, 356, 380, 200, 325, 37, 436, 306, 374, 15, 306, 243, 268, 87, 200, 290, 375, 206, 405, 407, 455, 33, 296, 36, 117, 5, 266, 167, 218, 145, 401, 193, 319, 301, 430, 51, 158, 58, 228, 301, 320, 87, 176, 31, 58, 40, 135, 121, 246, 155, 265, 77, 146, 163, 388, 220, 325, 132, 415, 34, 292, 90, 384, 27, 185, 331, 439, 3, 119, 297, 351, 139, 345, 377, 388, 53, 349, 10, 441, 103, 270, 233, 394, 121, 197, 215, 334, 179, 270, 143, 229, 130, 158, 129, 294, 118, 277, 261, 453, 164, 400, 20, 228, 4, 288, 33, 148, 123, 341}

Returns: 87804953424774
495

998407301

488040624

{}

Returns: 8716414099204
490

1445064648

770022622

{}

Returns: 81824132160190
465

703597589

1148143693

{43, 201, 12, 102, 283, 311, 92, 443, 183, 287, 173, 311, 52, 210, 155, 433, 202, 402, 79, 150, 116, 123, 235, 236, 230, 414, 294, 405, 102, 164, 9, 407, 23, 402, 49, 378, 197, 286, 241, 243, 257, 278, 130, 192, 204, 440, 48, 287, 69, 302, 149, 252, 82, 388, 240, 372, 124, 272, 306, 391, 22, 229, 26, 143, 81, 344, 11, 175, 233, 234, 104, 228, 20, 210, 220, 457, 10, 138, 117, 174, 216, 297, 164, 310, 178, 416, 267, 300, 22, 247, 37, 440, 82, 103, 259, 263, 177, 178, 62, 107, 160, 394, 82, 196, 114, 157, 49, 81}

Returns: 428573757516356
440

1912378370

1130412453

{}

Returns: 289671906238438
419

1098788664

435384246

{81, 374, 268, 384, 2, 168, 294, 394, 28, 66, 44, 140, 15, 323, 27, 187, 3, 372, 88, 235, 107, 122, 161, 196, 391, 418, 90, 149, 41, 360, 126, 251, 133, 385, 282, 298, 14, 196, 97, 294, 209, 248, 42, 50, 272, 298, 268, 371, 143, 292, 281, 394, 263, 285, 93, 255, 7, 236, 34, 331, 125, 137, 57, 187, 174, 348, 147, 328, 13, 85, 214, 365, 30, 129, 269, 367, 329, 399, 140, 225, 89, 287, 24, 260, 182, 351, 58, 281, 289, 417, 130, 187, 88, 315, 45, 161, 208, 344, 217, 250, 0, 196, 230, 404, 142, 181, 86, 323, 37, 147, 50, 148}

Returns: 1852671314780
453

2081869854

523646929

{}

Returns: 7202984144920
466

156085843

104777245

{80, 109, 59, 84, 55, 455, 98, 343, 94, 381, 81, 264, 100, 282, 118, 276, 65, 268, 114, 392, 66, 103, 228, 322, 51, 168, 145, 463, 27, 35, 106, 227, 96, 340, 309, 316, 342, 359, 80, 261, 132, 268, 62, 315, 146, 158, 162, 413, 194, 377, 12, 68, 45, 230, 309, 388, 307, 460, 15, 98, 23, 248, 69, 240, 325, 392, 329, 381, 46, 313, 3, 402, 51, 236, 155, 452, 438, 443, 61, 208, 268, 290, 118, 416, 397, 461, 82, 205, 267, 398, 109, 215, 195, 305, 346, 431, 77, 378, 99, 146, 340, 421, 110, 358, 385, 445, 134, 147, 254, 279, 126, 356, 141, 393, 57, 295, 246, 259, 110, 298, 260, 336, 169, 351, 195, 243, 42, 390, 49, 299, 269, 333, 40, 226, 198, 321, 11, 242, 219, 407, 93, 99, 32, 209, 134, 198, 132, 414, 51, 249, 108, 464, 121, 395, 29, 193, 37, 255, 308, 434, 338, 395, 112, 443, 104, 260, 109, 351, 33, 191, 146, 224, 287, 354, 81, 280, 196, 238, 184, 360}

Returns: 2932293286
456

1513561887

1141345700

{}

Returns: 376299000086362
471

279403726

1470829300

{133, 320, 134, 246, 267, 363, 208, 338, 238, 428, 177, 193, 210, 429, 381, 454, 174, 270, 418, 447, 95, 349, 96, 153, 200, 379, 51, 461, 56, 416, 67, 178, 354, 421, 171, 172, 347, 466, 94, 96, 29, 55, 46, 445, 17, 394, 239, 458, 106, 110, 236, 365, 103, 428, 269, 323, 310, 466, 346, 415, 53, 366, 129, 221, 139, 316, 243, 269, 29, 429, 57, 261, 59, 121, 287, 382, 198, 289, 27, 80, 144, 294, 28, 315, 272, 360, 173, 206, 157, 254, 50, 330, 112, 396, 111, 138, 25, 318, 331, 422, 129, 219, 4, 398, 70, 329, 151, 314, 166, 380, 119, 391, 39, 177, 193, 259, 63, 304, 238, 261, 184, 451, 291, 468, 127, 269}

Returns: 1660889901468910
439

1696735254

1364578531

{}

Returns: 739695530584316
500

1701364534

1050239372

{28, 105, 489, 495, 128, 153, 121, 347, 69, 459, 153, 349, 60, 260, 123, 449, 147, 418, 120, 292, 306, 388, 176, 427, 411, 489, 56, 67, 296, 366, 134, 257, 245, 387, 224, 234, 290, 440, 86, 380, 70, 320, 66, 303, 272, 345, 390, 399, 167, 460, 66, 234, 9, 445, 203, 259}

Returns: 436916477074728
499

1641300512

1783027596

{}

Returns: 6001455306428850
496

197907777

969365078

{207, 382, 35, 341, 105, 481, 296, 465, 292, 482, 242, 307, 50, 384, 226, 479, 97, 290, 7, 177, 73, 145, 380, 389, 242, 365, 304, 408, 113, 314, 108, 289, 164, 239, 10, 257, 93, 309, 205, 471, 69, 150, 232, 404, 124, 422, 83, 126, 212, 392, 248, 281, 418, 437, 65, 87, 377, 458, 163, 380, 129, 201, 238, 472, 40, 74, 192, 206, 64, 235, 342, 380, 207, 394, 67, 424, 66, 119, 18, 193}

Returns: 274987673404024
412

2133781351

1570497132

{}

Returns: 1008172937252782
478

1812286614

768760599

{}

Returns: 66355932181548
413

778528433

1456221142

{161, 207, 62, 281, 116, 384, 35, 334, 128, 170, 232, 349, 34, 91, 10, 230, 16, 378, 146, 388, 83, 199, 289, 405, 161, 324, 176, 370, 344, 378, 65, 141, 269, 392, 170, 355, 25, 88, 149, 167, 210, 290, 269, 381, 32, 408, 163, 398, 82, 240, 14, 226, 125, 210, 278, 349, 135, 389, 126, 379, 359, 379, 320, 340, 64, 279, 186, 378, 271, 326, 254, 389, 281, 405, 141, 319, 231, 334, 156, 392, 82, 92, 39, 353, 198, 215, 114, 404, 31, 249, 169, 212, 114, 292, 62, 348, 19, 345, 194, 218, 166, 212}

Returns: 697011093455918
475

1537355483

66895135

{}

Returns: 310436660
489

96818796

1491367119

{142, 337, 166, 405, 175, 461, 215, 375, 73, 337, 365, 390, 305, 356, 219, 315, 228, 290, 255, 338, 256, 402, 19, 434, 159, 342, 241, 382, 100, 185, 131, 213, 22, 485, 265, 316, 157, 434, 1, 387, 14, 60, 320, 335, 414, 462, 26, 376, 108, 222, 86, 275, 75, 325, 204, 429, 236, 469, 163, 289, 337, 480, 299, 320, 382, 390, 296, 347, 110, 251, 187, 188, 92, 428, 262, 351, 326, 373, 210, 314, 356, 449, 222, 348, 274, 393, 143, 149, 195, 283, 128, 281, 148, 486, 197, 437, 47, 467, 84, 403, 155, 318, 161, 280, 314, 322, 185, 481, 222, 460, 162, 320, 258, 331, 144, 386}

Returns: 2161188860591410
480

1587052320

1513494549

{}

Returns: 2090287746058778
400

1366146383

1976373037

{23, 162, 374, 390, 133, 377, 45, 58, 51, 368, 54, 296, 19, 206, 12, 365, 114, 267, 120, 150, 33, 386, 97, 249, 260, 304, 56, 219, 240, 389, 41, 295, 196, 204, 86, 88, 137, 181, 99, 202, 289, 356, 106, 346, 47, 136, 247, 352, 18, 315, 39, 340, 150, 344, 159, 384, 141, 330, 0, 367, 317, 326, 303, 321, 256, 278, 225, 234, 155, 156, 25, 122, 136, 224, 269, 342, 127, 349, 22, 26, 126, 207, 265, 267}

Returns: 2626163520218016
445

938133512

1257698550

{61, 125, 131, 321, 15, 21, 22, 78, 231, 361, 328, 332, 257, 302, 29, 392, 309, 396, 128, 255, 22, 365, 238, 331, 79, 139, 218, 273, 91, 288, 79, 406, 12, 92, 58, 167, 16, 377, 205, 325, 39, 47, 155, 323, 237, 327, 31, 41, 118, 198, 120, 148, 37, 252, 240, 374, 198, 309, 150, 197}

Returns: 515986229116420
495

1401184248

507246461

{42, 401, 38, 196, 81, 341, 43, 122, 121, 441, 383, 432, 251, 328, 18, 366, 131, 157, 300, 490, 116, 142, 259, 410, 38, 469, 24, 69, 158, 280, 133, 371, 165, 458, 33, 441, 58, 114, 104, 216, 128, 465, 263, 381, 117, 346, 217, 435, 110, 139, 69, 159, 214, 263, 69, 387, 76, 206, 13, 187, 110, 356, 262, 272, 149, 462, 27, 424, 351, 453, 175, 308, 217, 252, 236, 277, 77, 256, 61, 269, 73, 276, 158, 209, 38, 389, 214, 229, 47, 230, 101, 348, 71, 145, 285, 287, 159, 170, 321, 452, 49, 411, 65, 454, 480, 483, 270, 385, 106, 155, 249, 273, 198, 493, 189, 459, 117, 269, 271, 418, 56, 85, 2, 280, 379, 419, 362, 476, 138, 291, 5, 110, 362, 422, 13, 320, 267, 301, 44, 53, 48, 436, 247, 466, 54, 388, 295, 334, 238, 326, 155, 478, 91, 338, 373, 423, 80, 441, 242, 263, 455, 459, 26, 221, 124, 271, 256, 363, 162, 269, 35, 299, 148, 176, 424, 479, 148, 445, 359, 484, 222, 427, 112, 166, 10, 212, 22, 192, 41, 87, 346, 472, 302, 458, 186, 405, 189, 294}

Returns: 10987746047552
500

1432

1000000000

{ }

Returns: 340762868427858

Statistics

Problem Statement for "ParadePlanner"

Problem Statement

Definition

Notes

Constraints

Examples