Problem Statement
Misof recently had an accident in which he managed to cut his left hand on some broken glass. He is now "all right" - meaning that he can only use his right hand for a while. Help him with some issues he has.
Misof is lying at home and he is bored. He would like to watch a movie in which he can enjoy the sense of a "deja vu" - that is, seeing the same scene for a second time.
For the purpose of this problem, a movie is a sequence of scenes, and we will use nonnegative integers to describe them. Two scenes are different iff they have a different number.
A "deja vu" is a scene that occurs exactly twice in the movie. (A scene that occurs more than two times does not count.)
Misof has already selected a movie to watch, but then he came up with an interesting observation: what if he could increase the number of deja vus by only watching some part of the movie?
Formally, for a sequence X of integers let dejavu(X) be the number of elements that occur in X exactly twice. You are given a sequence M. Find a contiguous subsequence M' of M that maximizes dejavu(M') and return the value dejavu(M').
The sequence M of length N is constructed using the following pseudocode:
A[0] = seed
for i = 1 to N-1:
A[i] = (A[i-1] * 1664525 + 1013904223) modulo 4294967296
for i = 0 to N-1:
M[i] = A[i] modulo R
Definition
- Class:
- DejaVu
- Method:
- mostDejaVus
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int mostDejaVus(int N, int seed, int R)
- (be sure your method is public)
Notes
- The reference solution would correctly solve any sequence of length N, it does not depend on the properties of the pseudorandom generator.
- Watch out for integer overflow when generating M.
Constraints
- N will be between 1 and 200,000, inclusive.
- seed will be between 0 and 10^9, inclusive.
- R will be between 1 and 10^9, inclusive.
Examples
10
47
5
Returns: 2
A = { 47, 1092136898, 2326342713, 3532868, 1750783699, 3040800278, 3282292349, 2587573688, 3003147703, 1792673706 } M = { 2, 3, 3, 3, 4, 3, 4, 3, 3, 1 } The contiguous subsequences {3, 4, 3, 4} and {4, 3, 4, 3} contain two deja vus each, and this is the best Misof can get.
14
474747
7
Returns: 3
M = { 0, 2, 2, 1, 0, 0, 6, 0, 6, 0, 2, 1, 1, 0 } The optimal solutions are the subsequences M[2:12] = {2, 1, 0, 0, 6, 0, 6, 0, 2, 1} and M[6:13] = {6, 0, 6, 0, 2, 1, 1}. Each of these contains three deja vus. Note that for M[2:12] the scene 0 does not count as a deja vu, as it occurs too many times. Only scenes 2, 1, and 6 give Misof one valid deja vu each.
1
47
100
Returns: 0
2
47
1
Returns: 1
2
47
100000
Returns: 0
146117
67135896
694466506
Returns: 14
159463
612881716
43741
Returns: 12131
167167
415062492
760953937
Returns: 18
105361
853713569
807195153
Returns: 3
103101
110011131
9
Returns: 9
163118
777236130
11
Returns: 10
174392
459238762
343
Returns: 130
168585
551852547
67962
Returns: 18456
131725
35717065
56327
Returns: 15250
178771
367127108
344
Returns: 133
195571
982424200
5
Returns: 5
143768
105169864
85805
Returns: 22492
150276
545789166
22726
Returns: 6361
185040
936243973
815
Returns: 278
143890
234670474
899056097
Returns: 11
114437
830082628
749243544
Returns: 5
146274
724619612
41323
Returns: 11354
172779
989998540
56785
Returns: 15581
169820
607076112
16
Returns: 16
140921
604235495
379434604
Returns: 22
195710
557700496
720
Returns: 251
114933
673673332
488
Returns: 174
163622
271805617
554
Returns: 193
101991
182853533
3
Returns: 3
134832
548934239
940026799
Returns: 6
157096
392537040
20
Returns: 17
134735
965501521
860408746
Returns: 8
183666
857357003
12914
Returns: 3629
175618
260940257
454
Returns: 166
156575
930735750
280
Returns: 112
161576
988878479
230
Returns: 93
112899
146737412
79127
Returns: 19318
151427
116055547
68185
Returns: 18713
100059
700751158
14
Returns: 13
108803
396477633
9
Returns: 9
105466
150794607
856
Returns: 288
167064
897188377
315981477
Returns: 38
164840
567230838
705166843
Returns: 16
174361
10723827
6
Returns: 6
119735
989836379
93299
Returns: 21335
106119
942251502
829
Returns: 270
108026
406657323
1
Returns: 1
111611
325052044
18
Returns: 15
140326
256750958
663
Returns: 226
175990
818650486
91131
Returns: 24571
174820
86654360
467988208
Returns: 23
172944
56030499
14
Returns: 13
154741
379828288
83966
Returns: 22639
199578
525333703
165
Returns: 74
166568
125699083
801102584
Returns: 14
159476
884403724
14
Returns: 13
173915
560627570
10
Returns: 10
192373
526350671
8
Returns: 8
146162
854968508
31878
Returns: 8788
160628
24260175
15
Returns: 13
160362
297197665
18
Returns: 14
124810
884873256
15359
Returns: 4281
200000
12331214
2
Returns: 2
200000
10
10000000
Returns: 1920