Connection Status:
Competition Arena > XorRank

XorRank

2016 TCO Semi 2 · 2016-03-24 · by cgy4ever

2016 TCO Semi 2 · 2016-03-24 · by cgy4ever · Advanced Math
Class Name: XorRank
Return Type: int
Method Name: count
Arg Types: (int, vector<int>, vector<int>)
Problem Statement

Problem Statement

This problem is about sets of non-negative integers.

A set S is called perfect if it has the following properties:
  • it is non-empty
  • whenever a and b are two (not necessarily distinct) elements of S, the number (a xor b) is also an element of S
It can be shown that the size of any perfect set must be a power of two.

You are given an int k, and two equally-long int[]s rank and value. We are interested in perfect sets that have the following properties:
  • The size of the set is 2^k.
  • For each i, the rank[i]-th smallest number in the set (0-based index) must be value[i].
If there are infinitely many such perfect sets, return -1. Otherwise, return the number of such perfect sets, modulo (10^9 + 7).

Constraints

  • k will be between 1 and 30, inclusive.
  • rank will contain between 1 and 50 elements, inclusive.
  • rank and value will contain the same number of elements.
  • Each element in rank will be between 0 and (2^k-1), inclusive.
  • Each element in value will be between 0 and 1,000,000,000, inclusive.
Examples
0)
2
{3}
{13}
Returns: 5

We want perfect sets that have 2^2 = 4 elements. The largest of those elements should be the number 13. We have 5 solutions: {0, 1, 12, 13} {0, 4, 9, 13} {0, 5, 8, 13} {0, 6, 11, 13} {0, 7, 10, 13}

1)
2
{3, 1}
{13, 5}
Returns: 1

This time the only one is: {0, 5, 8, 13}.

2)
6
{58}
{57}
Returns: 0

Since all numbers in the set are nonnegative (and distinct), the number with rank 58 must be at least 58. Thus, there is no solution.

3)
10
{588, 588}
{1748912, 1748913}
Returns: 0

The 588-th number can't be both 1748912 and 1748913 at the same time.

4)
1
{0}
{0}
Returns: -1

There are infinite number of them, like: {0,1}, {0,2}, {0,3}, ...

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

Coding Area

Language: C++17 · define a public class XorRank with a public method int count(int k, vector<int> rank, vector<int> value) · 146 test cases · 2 s / 256 MB per case

Submitting as anonymous