Connection Status:
Competition Arena > XorSequence

XorSequence

SRM 649 · 2015-01-29 · by tozangezan

SRM 649 · 2015-01-29 · by tozangezan · Dynamic Programming, Math, Sorting
Class Name: XorSequence
Return Type: long
Method Name: getmax
Arg Types: (int, int, int, int, int, int, int)
Problem Statement

Problem Statement

You are given an integer sequence A and an int N that is a power of 2. All elements of A are between 0 and N-1, inclusive.

You can now choose an integer B which is between 0 and N-1, inclusive. This integer determines a new sequence C defined as follows: For each valid i, C[i] = (A[i] xor B).

Given the sequence C, we will count the pairs of indices (i,j) such that both i<j and C[i]<C[j]. Compute and return the largest result we can obtain.

You are given the int N. You are also given ints sz, A0, A1, P, Q, and R. Use the following pseudocode to generate the sequence A:

A[0] = A0;
A[1] = A1;
for (i = 2; i < sz; i++) {
    A[i] = (A[i - 2] * P + A[i - 1] * Q + R) modulo N;
}

Notes

  • Watch out for integer overflow when generating the sequence A.

Constraints

  • N will be between 2 and 1,073,741,824 (2^30), inclusive.
  • N will be a power of 2.
  • sz will be between 2 and 131,072, inclusive.
  • A0 will be between 0 and N-1, inclusive.
  • A1 will be between 0 and N-1, inclusive.
  • P will be between 0 and N-1, inclusive.
  • Q will be between 0 and N-1, inclusive.
  • R will be between 0 and N-1, inclusive.
Examples
0)
4
6
3
2
0
1
3
Returns: 8

Using the provided pseudocode you should compute that A={3,2,1,0,3,2}. For B=3 we then get C={0,1,2,3,0,1}. For this C there are 8 pairs (i,j) such that i<j and C[i]<C[j]. These are the 8 pairs: (0,1), (0,2), (0,3), (0,5), (1,2), (1,3), (2,3), and (4,5). No other choice of B produces more than 8 pairs.

1)
8
8
2
5
3
1
4
Returns: 13

A={2,5,7,2,3,5,2,5}.

2)
8
7
3
0
1
2
4
Returns: 12

A={3,0,7,2,7,4,3}.

3)
32
15
7
9
11
2
1
Returns: 60

A={7,9,0,4,9,31,2,26,11,21,4,16,13,11,6}.

4)
131072
131072
7
7
1
0
0
Returns: 0

All elements of A are equal to 7. Regardless of the value of B you choose, all elements in C will be equal as well. Thus, the number of pairs we seek is always zero.

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

Coding Area

Language: C++17 · define a public class XorSequence with a public method long long getmax(int N, int sz, int A0, int A1, int P, int Q, int R) · 131 test cases · 2 s / 256 MB per case

Submitting as anonymous