DejaVu | Topcoder Archive

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.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.