TopCoder Statistics - Problem Statement

Problem Statement

You are maintaining a repository that contains N software packages.

Each software package x may have some dependencies: other packages that need to be installed before you can install x.

There are no cyclic dependencies between the packages. You know this, because internally you have given the packages IDs from 0 to N-1 according to one possible way in which all of them can be installed. Hence, whenever package x depends on package y, you can be sure that x > y.

You are now interested in ultimate packages. These are the packages that are related to everything in the whole repository.

Formally, we say that a package x needs package y if either x directly depends on y, or x depends on some package z that needs y.

Then, we say that a package u is an ultimate package if for each other package x either u needs x or x needs u.

You are given the number of packages and all dependencies between them (as specified below). Find all ultimate packages in the repository. Return a int[] with two elements: { the number of ultimate packages, the sum of IDs of ultimate packages }.

The dependencies are given in arrays X and Y, each of length D. For each valid i, package X[i] depends on package Y[i]. Note that the same dependency may be listed multiple times.

In order to keep the input size small, for large inputs X and Y will be generated pseudorandomly. Below we give pseudocode, Java code and C++ code that generates X and Y from the data you are given.


Pseudocode:

X, Y = two empty arrays of length D
XL = length(Xprefix)
for i = 0 to XL-1:
    X[i] = Xprefix[i]
    Y[i] = Yprefix[i]

state = seed
for i = XL to D-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    elen = 1 + (state modulo L)
    state = (state * 1103515245 + 12345) modulo 2^31
    Y[i] = state modulo (N - elen)
    X[i] = Y[i] + elen

-----------------------------------------------------

Java:

int[] X = new int[D];
int[] Y = new int[D];
int XL = Xprefix.length;
for (int i=0; i&lt;XL; ++i) {
    X[i] = Xprefix[i];
    Y[i] = Yprefix[i];
}

long state = seed;
for (int i=XL; i&lt;D; ++i) {
    state = (state * 1103515245 + 12345) % (1L &lt;&lt; 31);
    int elen = (int)(1 + state%L);
    state = (state * 1103515245 + 12345) % (1L &lt;&lt; 31);
    Y[i] = (int)(state % (N - elen));
    X[i] = Y[i] + elen;
}

-----------------------------------------------------

C++:

vector&lt;int&gt; X(D), Y(D);
int XL = Xprefix.size();

for (int i=0; i&lt;XL; ++i) {
    X[i] = Xprefix[i];
    Y[i] = Yprefix[i];
}

long long state = seed;
for (int i=XL; i&lt;D; ++i) {
    state = (state * 1103515245 + 12345) % (1LL &lt;&lt; 31);
    int elen = 1 + state%L;
    state = (state * 1103515245 + 12345) % (1LL &lt;&lt; 31);
    Y[i] = state % (N - elen);
    X[i] = Y[i] + elen;
}

Definition

Class:: TheUltimatePackages
Method:: count
Parameters:: int, int, int[], int[], int, int
Returns:: int[]
Method signature:: int[] count(int N, int D, int[] Xprefix, int[] Yprefix, int L, 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 2 and 65,000, inclusive.
D will be between 0 and 300,000, inclusive.
Xprefix will contain between 0 and min(500,D) elements, inclusive.
Yprefix will contain the same number of elements as Xprefix.
For each i, N-1 >= Xprefix[i] > Yprefix[i] >= 0.
L will be between 1 and N-1, inclusive.
seed will be between 0 and 2^31 - 1, inclusive.

Examples

5

4

{1, 3, 2, 4}

{0, 2, 1, 3}

1

47

Returns: {5, 10 }

There are five packages and four dependencies: 4 depends on 3, 3 depends on 2, 2 depends on 1, and 1 depends on 0. Each of these five packages is ultimate.
5

6

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

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

1

64

Returns: {2, 4 }

There are five packages: 1, 2, and 3 each depend on 0 and 4 depends on 1, 2, and 3. Ultimate packages are packages 0 and 4.
5

4

{2, 2, 3, 4}

{0, 1, 2, 2}

1

32532

Returns: {1, 2 }

The only ultimate package here is package 2.
4

3

{3, 3, 2}

{0, 2, 1}

1

2555

Returns: {1, 3 }

The only ultimate package here is package 3, because it needs all other packages.
7

0

{}

{}

1

0

Returns: {0, 0 }

No ultimate packages here.
2

4

{1, 1, 1, 1}

{0, 0, 0, 0}

1

0

Returns: {2, 1 }

A dependence listed four times is the same thing as a dependence listed once.
15000

300000

{}

{}

20

47

Returns: {7623, 56693287 }
5000

300000

{}

{}

3

1255

Returns: {5000, 12497500 }
10000

210000

{}

{}

11

124

Returns: {3226, 8856614 }
15000

300000

{}

{}

123

1254215

Returns: {0, 0 }
7

8

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

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

1

1

Returns: {1, 0 }
7

8

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

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

1

1

Returns: {1, 0 }
7

12

{2, 3, 4}

{1, 2, 3}

5

4747

Returns: {0, 0 }

The generated arrays X and Y look as follows: X = { 2, 3, 4, 5, 6, 4, 4, 5, 4, 4, 5, 6 } Y = { 1, 2, 3, 1, 1, 1, 0, 1, 0, 1, 1, 1 }
500

100000

{}

{}

497

215366

Returns: {1, 442 }
280

30480

{}

{}

256

1475191316

Returns: {0, 0 }
231

233941

{}

{}

193

175701600

Returns: {1, 0 }
314

19741

{}

{}

157

1133040875

Returns: {0, 0 }
346

26724

{}

{}

318

1836955051

Returns: {0, 0 }
217

56300

{}

{}

164

1039591800

Returns: {0, 0 }
117

111863

{}

{}

96

1468508435

Returns: {0, 0 }
385

48406

{}

{}

378

151521850

Returns: {0, 0 }
164

78374

{}

{}

128

1647457924

Returns: {0, 0 }
360

78262

{}

{}

346

974776318

Returns: {0, 0 }
457

94182

{}

{}

348

473072173

Returns: {0, 0 }
495

223621

{}

{}

419

1229727803

Returns: {0, 0 }
495

49911

{}

{}

338

172270288

Returns: {0, 0 }
347

117372

{}

{}

239

948917258

Returns: {1, 0 }
410

23169

{}

{}

302

2084771948

Returns: {0, 0 }
229

61858

{}

{}

115

731414135

Returns: {1, 228 }
380

18828

{}

{}

258

2046595582

Returns: {0, 0 }
500

226906

{}

{}

485

142514072

Returns: {66, 17444 }
411

127377

{}

{}

386

1352884873

Returns: {0, 0 }
111

46619

{}

{}

77

1853868645

Returns: {1, 110 }
454

44346

{}

{}

347

853308887

Returns: {0, 0 }
165

20862

{}

{}

154

1477705088

Returns: {0, 0 }
370

159405

{}

{}

253

1906624755

Returns: {196, 36038 }
100

29952

{}

{}

54

1585910533

Returns: {100, 4950 }
110

71002

{}

{}

63

778158833

Returns: {110, 5995 }
478

183801

{}

{}

439

2124698091

Returns: {50, 11936 }
370

133690

{}

{}

362

317163642

Returns: {0, 0 }
189

54941

{}

{}

175

200513682

Returns: {1, 0 }
418

36781

{}

{}

305

528916607

Returns: {0, 0 }
111

26303

{}

{}

58

1321413367

Returns: {0, 0 }
222

50669

{}

{}

190

346617440

Returns: {0, 0 }
388

220912

{}

{}

336

224121999

Returns: {305, 58131 }
158

240555

{}

{}

124

1300568894

Returns: {0, 0 }
388

167680

{}

{}

210

502796335

Returns: {368, 71412 }
336

135758

{}

{}

279

284290351

Returns: {150, 25036 }
500

129787

{}

{}

378

490178290

Returns: {0, 0 }
486

55849

{}

{}

446

1422105126

Returns: {0, 0 }
185

136994

{}

{}

167

421704849

Returns: {1, 184 }
443

251796

{}

{}

291

102151484

Returns: {1, 0 }
386

51580

{}

{}

203

1130699910

Returns: {22, 4977 }
377

231657

{}

{}

205

468300517

Returns: {1, 376 }
366

225958

{}

{}

331

1338728498

Returns: {178, 34523 }
310

38760

{}

{}

181

1309953612

Returns: {5, 1089 }
307

112737

{}

{}

180

400206914

Returns: {0, 0 }
418

225582

{}

{}

221

1502298833

Returns: {318, 65859 }
398

29224

{}

{}

361

1150680127

Returns: {0, 0 }
230

51755

{}

{}

141

1997165977

Returns: {109, 11513 }
438

123895

{}

{}

417

1891726748

Returns: {15, 4071 }
262

21472

{}

{}

253

2642986

Returns: {1, 16 }
114

250977

{}

{}

90

1880671616

Returns: {0, 0 }
414

104066

{}

{}

233

1301697396

Returns: {77, 15328 }
10764

243842

{}

{}

30

1475191316

Returns: {0, 0 }
9217

233941

{}

{}

17

1797583853

Returns: {0, 0 }
5387

131236

{}

{}

7

39237771

Returns: {0, 0 }
10170

191377

{}

{}

3

1899324723

Returns: {10138, 51557114 }
8965

229157

{}

{}

54

1468508435

Returns: {0, 0 }
14138

193624

{}

{}

68

539016619

Returns: {2, 27459 }
10471

226187

{}

{}

28

1085916001

Returns: {0, 0 }
6590

218853

{}

{}

3

473072173

Returns: {6590, 21710755 }
11826

206128

{}

{}

94

1123519141

Returns: {0, 0 }
10848

257935

{}

{}

7

1117738417

Returns: {9811, 53064818 }
13509

160939

{}

{}

45

1631517495

Returns: {0, 0 }
12952

170184

{}

{}

8

731414135

Returns: {10743, 67050711 }
13961

150629

{}

{}

7

1870943262

Returns: {0, 0 }
10989

200543

{}

{}

62

1352884873

Returns: {0, 0 }
5364

186479

{}

{}

7

790342737

Returns: {5223, 14016609 }
7894

183153

{}

{}

2

586949650

Returns: {0, 0 }
14332

233926

{}

{}

1

1906624755

Returns: {14332, 102695946 }
5007

239617

{}

{}

1

88998632

Returns: {0, 0 }
9329

167887

{}

{}

3

863925910

Returns: {0, 0 }
13105

133690

{}

{}

36

752144434

Returns: {0, 0 }
7466

143310

{}

{}

23

263002937

Returns: {475, 1199822 }
11205

136895

{}

{}

1

231464469

Returns: {0, 0 }
13976

193755

{}

{}

20

1173215853

Returns: {3276, 23015686 }
14352

259851

{}

{}

4

492182829

Returns: {14348, 102929694 }
11774

223803

{}

{}

7

599801112

Returns: {9393, 54991132 }
6040

251989

{}

{}

61

76784397

Returns: {223, 702628 }
12120

206472

{}

{}

126

490178290

Returns: {0, 0 }
9016

217870

{}

{}

3

97040700

Returns: {9004, 40567206 }
14629

251519

{}

{}

12

102151484

Returns: {0, 0 }
14178

206321

{}

{}

1

2073107849

Returns: {14178, 100500753 }
17968

300000

{}

{}

1

42

Returns: {17968, 161415528 }
1500

300000

{ }

{ }

1499

2345

Returns: {0, 0 }
65000

300000

{ }

{ }

10000

123

Returns: {0, 0 }
20000

300000

{2, 2, 3, 4 }

{0, 1, 2, 2 }

1

32532

Returns: {20000, 199990000 }
4488

132597

{2765, 4352, 4321, 1186, 3684, 4339, 2836, 1963, 2322, 4017, 2620, 3025, 3599, 4347, 384, 3498, 974, 2751, 4139, 4127, 3657, 2011, 3416, 1816, 3265, 4120, 3947, 3992 }

{1826, 2743, 1031, 910, 1120, 1874, 2404, 43, 1320, 1910, 1580, 2028, 2834, 1730, 282, 740, 249, 1391, 3663, 2739, 975, 1916, 2574, 1145, 1126, 2900, 52, 2221 }

89

93900083

Returns: {0, 0 }
60000

300000

{189, 316, 339, 634, 1199, 1383, 1585, 1632, 1827, 1897, 1919, 2100, 2113, 2293, 2728, 3058, 3119, 3167, 3453, 3665, 3711, 3792, 3800, 3816, 3911, 3939, 4055, 4083, 4089, 4119, 4779, 4980, 5342, 5495, 5511, 5564, 5565, 5589, 5684, 5935, 6564, 6866, 6925, 7131, 7363, 7391, 7805, 7811, 7915, 7947, 7955, 8077, 8495, 8919, 8985, 9242, 9285, 9304, 9375, 9427, 9478, 9930, 10449, 10503, 10566, 10618, 10630, 10647, 10659, 10674, 10751, 10850, 11033, 11384, 11429, 11495, 11516, 11529, 11793, 11978, 12583, 12716, 12798, 12815, 13012, 13022, 13100, 13357, 13489, 13568, 13599, 13675, 13705, 13710, 13886, 14251, 14329, 14407, 14482, 14517, 14865, 15106, 15197, 15484, 15922, 16178, 16253, 16354, 16364, 16423, 16446, 16580, 16621, 16655, 16657, 16755, 17299, 17331, 17338, 17373, 17382, 17612, 17885, 19030, 19139, 19293, 19583, 19770, 19835, 20053, 20280, 20344, 20380, 20683, 21318, 21390, 21391, 21644, 21930, 22041, 22283, 22294, 22401, 22822, 22877, 22949, 23024, 23239, 23510, 23769, 24178, 24246, 24452, 24678, 24807, 24849, 24898, 24902, 24927, 25012, 25129, 25373, 25496, 25508, 25554, 25587, 25823, 26036, 26065, 26165, 26219, 26241, 26312, 26457, 26617, 26723, 26976, 27172, 27210, 27256, 27285, 27689, 27835, 27958, 27971, 28097, 28105, 28297, 28330, 28576, 28834, 29200, 29348, 29489, 29494, 29777, 29912, 29984, 30094, 30131, 30227, 30325, 30349, 30383, 30514, 30530, 30674, 30779, 30817, 30860, 30872, 31915, 32046, 32147, 32305, 32520, 32626, 32668, 32821, 32872, 32885, 32909, 33087, 33260, 33386, 33514, 33556, 33730, 33732, 33902, 34002, 34215, 34251, 34541, 34598, 35104, 35111, 35305, 35515, 35629, 36216, 36378, 36488, 36492, 36573, 36685, 36987, 37017, 37032, 37634, 37681, 37694, 37857, 37864, 37972, 38012, 38680, 38682, 39098, 39213, 39284, 39570, 39796, 39888, 40231, 40282, 40480, 40610, 41068, 41177, 41596, 41657, 41794, 41922, 41927, 42052, 42104, 42149, 42278, 42592, 43017, 43435, 43685, 43712, 43942, 43952, 44129, 44465, 44567, 44821, 44855, 44867, 45075, 45087, 45187, 45240, 45271, 45856, 45978, 46217, 46322, 46400, 46512, 46598, 46683, 46710, 46790, 47057, 47109, 47149, 47277, 47436, 47731, 48038, 48581, 48671, 48766, 48852, 49017, 49207, 49216, 49261, 49290, 49433, 49905, 49911, 50992, 51042, 51082, 51222, 51305, 51416, 52056, 52220, 52319, 52667, 52925, 53094, 53180, 53192, 53414, 53798, 53964, 53982, 54182, 54282, 54284, 54339, 54652, 54742, 54884, 54893, 55291, 55354, 55463, 55470, 55505, 55535, 55652, 55906, 56172, 56230, 56341, 56410, 56458, 56574, 56592, 56686, 56687, 56840, 57041, 57119, 57148, 57153, 57424, 57500, 58021, 58069, 58204, 58540, 58570, 58984, 59095, 59408, 59480, 59817, 59962 }

{188, 315, 338, 633, 1198, 1382, 1584, 1631, 1826, 1896, 1918, 2099, 2112, 2292, 2727, 3057, 3118, 3166, 3452, 3664, 3710, 3791, 3799, 3815, 3910, 3938, 4054, 4082, 4088, 4118, 4778, 4979, 5341, 5494, 5510, 5563, 5564, 5588, 5683, 5934, 6563, 6865, 6924, 7130, 7362, 7390, 7804, 7810, 7914, 7946, 7954, 8076, 8494, 8918, 8984, 9241, 9284, 9303, 9374, 9426, 9477, 9929, 10448, 10502, 10565, 10617, 10629, 10646, 10658, 10673, 10750, 10849, 11032, 11383, 11428, 11494, 11515, 11528, 11792, 11977, 12582, 12715, 12797, 12814, 13011, 13021, 13099, 13356, 13488, 13567, 13598, 13674, 13704, 13709, 13885, 14250, 14328, 14406, 14481, 14516, 14864, 15105, 15196, 15483, 15921, 16177, 16252, 16353, 16363, 16422, 16445, 16579, 16620, 16654, 16656, 16754, 17298, 17330, 17337, 17372, 17381, 17611, 17884, 19029, 19138, 19292, 19582, 19769, 19834, 20052, 20279, 20343, 20379, 20682, 21317, 21389, 21390, 21643, 21929, 22040, 22282, 22293, 22400, 22821, 22876, 22948, 23023, 23238, 23509, 23768, 24177, 24245, 24451, 24677, 24806, 24848, 24897, 24901, 24926, 25011, 25128, 25372, 25495, 25507, 25553, 25586, 25822, 26035, 26064, 26164, 26218, 26240, 26311, 26456, 26616, 26722, 26975, 27171, 27209, 27255, 27284, 27688, 27834, 27957, 27970, 28096, 28104, 28296, 28329, 28575, 28833, 29199, 29347, 29488, 29493, 29776, 29911, 29983, 30093, 30130, 30226, 30324, 30348, 30382, 30513, 30529, 30673, 30778, 30816, 30859, 30871, 31914, 32045, 32146, 32304, 32519, 32625, 32667, 32820, 32871, 32884, 32908, 33086, 33259, 33385, 33513, 33555, 33729, 33731, 33901, 34001, 34214, 34250, 34540, 34597, 35103, 35110, 35304, 35514, 35628, 36215, 36377, 36487, 36491, 36572, 36684, 36986, 37016, 37031, 37633, 37680, 37693, 37856, 37863, 37971, 38011, 38679, 38681, 39097, 39212, 39283, 39569, 39795, 39887, 40230, 40281, 40479, 40609, 41067, 41176, 41595, 41656, 41793, 41921, 41926, 42051, 42103, 42148, 42277, 42591, 43016, 43434, 43684, 43711, 43941, 43951, 44128, 44464, 44566, 44820, 44854, 44866, 45074, 45086, 45186, 45239, 45270, 45855, 45977, 46216, 46321, 46399, 46511, 46597, 46682, 46709, 46789, 47056, 47108, 47148, 47276, 47435, 47730, 48037, 48580, 48670, 48765, 48851, 49016, 49206, 49215, 49260, 49289, 49432, 49904, 49910, 50991, 51041, 51081, 51221, 51304, 51415, 52055, 52219, 52318, 52666, 52924, 53093, 53179, 53191, 53413, 53797, 53963, 53981, 54181, 54281, 54283, 54338, 54651, 54741, 54883, 54892, 55290, 55353, 55462, 55469, 55504, 55534, 55651, 55905, 56171, 56229, 56340, 56409, 56457, 56573, 56591, 56685, 56686, 56839, 57040, 57118, 57147, 57152, 57423, 57499, 58020, 58068, 58203, 58539, 58569, 58983, 59094, 59407, 59479, 59816, 59961 }

1

1

Returns: {0, 0 }
65000

300000

{ }

{ }

100

1234

Returns: {0, 0 }
65000

300000

{1, 3, 2, 4 }

{0, 2, 1, 3 }

1

23

Returns: {0, 0 }
65000

300000

{1, 1, 1, 1 }

{0, 0, 0, 0 }

12345

123457

Returns: {0, 0 }
3

3

{1, 2, 2 }

{0, 0, 1 }

1

1

Returns: {3, 3 }
65000

300000

{1 }

{0 }

1234

123456

Returns: {0, 0 }
50000

100000

{ }

{ }

13

12422

Returns: {0, 0 }
65000

300000

{1000 }

{656 }

4545

90909

Returns: {0, 0 }
64543

203030

{ }

{ }

123

532617

Returns: {0, 0 }
65000

300000

{1, 1, 1, 1 }

{0, 0, 0, 0 }

64000

15487

Returns: {0, 0 }
5

4

{1, 3, 2, 4 }

{0, 2, 1, 3 }

1

47

Returns: {5, 10 }
65000

300000

{2, 1 }

{1, 0 }

64999

1242124214

Returns: {0, 0 }
5

10

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

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

4

0

Returns: {5, 10 }
65000

300000

{ }

{ }

30000

123141

Returns: {0, 0 }
3

3

{2, 1, 2 }

{1, 0, 0 }

2

123

Returns: {3, 3 }
200

100000

{100 }

{99 }

85

10109

Returns: {200, 19900 }
65000

300000

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

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

1

233

Returns: {0, 0 }
4

6

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

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

1

1

Returns: {4, 6 }
20000

300000

{2, 3, 4 }

{1, 2, 3 }

5

4747

Returns: {12284, 158660708 }
4

3

{3, 2, 3 }

{0, 1, 2 }

2

12

Returns: {1, 3 }
65000

300000

{2, 3, 4 }

{1, 2, 3 }

50

4747

Returns: {0, 0 }
3

3

{2, 2, 1 }

{0, 1, 0 }

1

0

Returns: {3, 3 }
65000

300000

{ }

{ }

1

87

Returns: {0, 0 }
3

3

{1, 2, 2 }

{0, 1, 0 }

1

1

Returns: {3, 3 }
65000

300000

{ }

{ }

64999

1432

Returns: {0, 0 }
65000

300000

{1 }

{0 }

32000

123456789

Returns: {0, 0 }
65000

300000

{ }

{ }

1

123

Returns: {0, 0 }
26000

300000

{1, 2, 3, 4, 5 }

{0, 1, 2, 3, 4 }

1

57

Returns: {26000, 337987000 }
186

20806

{ }

{ }

122

915

Returns: {72, 8758 }
3

1

{2 }

{1 }

1

1

Returns: {0, 0 }
4

1

{3 }

{2 }

1

1234

Returns: {0, 0 }
3

3

{1, 2 }

{0, 0 }

2

0

Returns: {1, 0 }
3

3

{1, 2, 2 }

{0, 0, 1 }

1

1432

Returns: {3, 3 }
7

6

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

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

2

12

Returns: {1, 4 }
65000

300000

{2, 3, 4 }

{1, 2, 3 }

5

4747

Returns: {0, 0 }

Statistics

Problem Statement for "TheUltimatePackages"

Problem Statement

Definition

Notes

Constraints

Examples