Statistics

Problem Statement for "MojisBag"

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].

Definition

Class:
MojisBag
Method:
maximumXor
Parameters:
int, int, int, int
Returns:
int
Method signature:
int maximumXor(int Q, int base, int add, int rate)
(be sure your method is public)

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

  1. 100000

    104

    515530019

    2

    Returns: 840517545

  2. 100000

    91

    943327677

    3

    Returns: 128776079

  3. 100000

    169

    294702567

    6

    Returns: 726995689

  4. 100000

    85

    86086317

    4

    Returns: 572169721

  5. 100000

    83

    188213258

    6

    Returns: 398850553

  6. 100000

    172

    2416949

    11

    Returns: 358066850

  7. 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}.

  8. 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}.

  9. 3

    429

    3558

    2

    Returns: 0

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

  10. 100000

    866335531

    708017183

    925153796

    Returns: 241997070

  11. 100000

    712085426

    849195462

    174530381

    Returns: 186907799

  12. 100000

    423897348

    911912779

    743630977

    Returns: 728728808

  13. 100000

    869704435

    834354869

    740600103

    Returns: 130394781

  14. 100000

    394664783

    692929830

    443095625

    Returns: 522941780

  15. 100000

    351952445

    108058582

    466862768

    Returns: 105578825

  16. 100000

    601395241

    823120705

    359616375

    Returns: 670915544

  17. 100000

    936031892

    784443218

    801953417

    Returns: 974755814

  18. 100000

    977841364

    552382976

    50665378

    Returns: 697862532

  19. 100000

    767260589

    368627318

    902194004

    Returns: 201268532

  20. 99990

    734990268

    405591419

    631163983

    Returns: 714140639

  21. 99999

    47139479

    827823889

    758616188

    Returns: 953224701

  22. 99999

    508405125

    773684271

    559783360

    Returns: 658559006

  23. 99996

    196269801

    191082356

    836000803

    Returns: 680766925

  24. 99999

    237007553

    876861872

    394358531

    Returns: 423976999

  25. 99999

    3383124

    210876941

    981563290

    Returns: 946531585

  26. 99999

    872290241

    646921925

    742552752

    Returns: 423640425

  27. 99995

    963736073

    400304407

    304458899

    Returns: 6572013

  28. 99999

    494095977

    236040827

    677829809

    Returns: 863474174

  29. 99998

    171036958

    242053402

    681190434

    Returns: 20037518

  30. 100000

    32

    32131

    2

    Returns: 834174922

  31. 100000

    123

    456

    10

    Returns: 628364853

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.
This problem was used for: