MojisBag

TCO19 SRM 753 · 2019-03-06 · by minimario

TCO19 SRM 753 · 2019-03-06 · by minimario · Brute Force

Show categories

Class Name: MojisBag

Return Type: int

Method Name: maximumXor

Arg Types: (int, int, int, int)

Problem Statement

Moji has a set S. Initially, this set is empty.

The set S is a multiset: it may contain multiple copies of the same value.

Arpa has Q queries. In each query Arpa either inserts a value into S or erases a value from S.

The queries are generated using a pseudorandom sequence. You are given the numbers base, add, and rate. The sequence is defined as follows:

X[0] = add
for all i, X[i+1] = (X[i] * base + add) modulo (10^9 + 7)

For each i from 0 to Q-1, inclusive:

If X[i] modulo rate is nonzero, Arpa's query number i is to add X[i] to S.
If X[i] modulo rate is zero, Arpa's query number i is to remove an element from S. If S is currently empty, nothing happens. Otherwise, let idx = (X[i] modulo the number of inserts into S so far). Arpa's query is to remove the idx-th element (0-based index) inserted to S. If this element has already been removed from S, S remains unchanged.

Note that when erasing we only erase each specific idx at most once, even if the value has been inserted at other times as well. For example, if the first four queries are "insert 47", "insert 47", "erase 0-th inserted value", and "erase 0-th inserted value", the set S will contain one copy of the value 47 because the second erase didn't do anything.

After each query, Moji wants to know the maximum value that can be obtained by computing the bitwise xor between two elements of S. By definition, if S contains fewer than two elements, this value is 0. Let Y[i] be the largest bitwise xor after processing the query number i. Then, let:

Z[0] = Y[0]
for all i, Z[i+1] = (Z[i] * base + Y[i+1]) modulo (10^9 + 7)

You are given the ints Q, base, add, and rate. Compute and return the value Z[Q-1].

Constraints

Q will be between 1 and 100,000, inclusive.
base will be between 2 and 10^9 + 5, inclusive.
add will be between 1 and 10^9 + 6, inclusive.
rate will be between 1 and 10^9 + 7, inclusive.

Examples

100000
104
515530019
2
Returns: 840517545

100000
91
943327677
3
Returns: 128776079

100000
169
294702567
6
Returns: 726995689

100000
85
86086317
4
Returns: 572169721

100000
83
188213258
6
Returns: 398850553

10
4747
7
3
Returns: 871911884

X = {7, 33236, 157771299, 940351124, 846754394, 543080192, 1653385, 848618553, 392242902, 977042774}. This describes the following sequence of actions: insert 7 insert 33236 attempt erase of value with idx=1 (value 33236, succeeds) insert 940351124 insert 846754394 insert 543080192 insert 1653385 attempt erase of value with idx=3 (value 846754394, succeeds) attempt erase of value with idx=0 (value 7, succeeds) insert 977042774 The maximum xor evolves as follows: Y = {0, 33235, 0, 940351123, 940351123, 940351123, 940942365, 940942365, 940942365, 975521759}.

5
47
7
3
Returns: 34911440

Here, we do the following: insert 7 attempt erase of value with idx=0 (value 7, succeeds) insert 15799 attempt erase of value with idx=0 (value 7, fails -- it was erased before) insert 34900327 Y = {0, 0, 0, 0, 34911440}.

3
429
3558
2
Returns: 0

Each of the first three operations does nothing, as you cannot erase from an empty set.

Submissions are judged against all 31 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class MojisBag with a public method int maximumXor(int Q, int base, int add, int rate) · 31 test cases · 2 s / 256 MB per case