Connection Status:
Competition Arena > XorOrderDiv1

XorOrderDiv1

SRM 697 · 2016-07-09 · by Arterm

SRM 697 · 2016-07-09 · by Arterm · Dynamic Programming, Math, Sorting
Class Name: XorOrderDiv1
Return Type: int
Method Name: get
Arg Types: (int, int, int, int)
Problem Statement

Problem Statement

Welcome to the Festival of Binary Numbers! The festival will last for 2^m days. The days are numbered 0 through 2^m - 1. On each day of the festival there is a single race. There are n contestants, numbered 0 through n-1. Each contestant takes part in all 2^m races. The skill level of contestant i is a[i]. All a[i] are integers between 0 and 2^m - 1, inclusive. Additionally, all a[i] are distinct.


For each i and j, the time needed by contestant i to finish the race on day j can be computed as (a[i] xor j). Note that on each day the contestants' times will all be distinct. After each race the contestants are ordered according to the time they needed, starting with the fastest one. Contestant who places x-th (counting from zero) will get x^2 penalty points. (I.e., starting from the winner of the race, the contestants get 0, 1, 4, 9, 16, ... penalty points.) For each i, let p[i] be the total number of penalty points contestant i receives in the 2^m races. Then, let q[i] = p[i] modulo (10^9 + 7).


You are given the ints m and n. You are also given ints a0 and b. These are used to generate the sequence a, as follows: For each i, a[i] = (a0 + i * b) modulo 2^m. Constraints guarantee that the elements of a will be distinct.


Compute each of the values q[i], and return the bitwise xor of all these values.

Notes

  • The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of the allowed size within the given limits.
  • The author's solution does actually compute each of the values q[i].

Constraints

  • m will be between 1 and 30, inclusive.
  • n will be between 1 and 200,000, inclusive.
  • a0 will be between 0 and 2 ^ m - 1, inclusive.
  • b will be between 0 and 2 ^ m - 1, inclusive.
  • The values a0 and b will be such that all values of the sequence a are distinct.
Examples
0)
2
3
0
1
Returns: 8

There are 2^2 = 4 days and 3 contestants. Their skill levels are a = {0, 1, 2}. The individual races are described below: day 0: finishing times are {0, 1, 2}, penalty points are {0, 1, 4}. day 1: finishing times are {1, 0, 3}, penalty points are {1, 0, 4}. day 2: finishing times are {2, 3, 0}, penalty points are {1, 4, 0}. day 3: finishing times are {3, 2, 1}, penalty points are {4, 1, 0}. Hence, the penalty point totals are {6, 6, 8}, and the correct return value is (6 xor 6 xor 8) = 8.

1)
3
5
1
3
Returns: 48

The skill levels in this example are a = {1, 4, 7, 2, 5}.

2)
16
100
41
5
Returns: 523436032
3)
30
200000
399
18082016
Returns: 408585698

Watch out for integer overflow.

4)
4
4
13
4
Returns: 0

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

Coding Area

Language: C++17 · define a public class XorOrderDiv1 with a public method int get(int m, int n, int a0, int b) · 66 test cases · 2 s / 256 MB per case

Submitting as anonymous