DejaVu
TCO19 SRM 755 · 2019-04-14 · by misof
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
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.
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
Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DejaVu with a public method int mostDejaVus(int N, int seed, int R) · 64 test cases · 2 s / 256 MB per case