Connection Status:
Competition Arena > BitwiseAnd

BitwiseAnd

SRM 596 · 2013-06-25 · by ir5

SRM 596 · 2013-06-25 · by ir5 · Graph Theory, Greedy
Class Name: BitwiseAnd
Return Type: long[]
Method Name: lexSmallest
Arg Types: (vector<long long>, int)
Problem Statement

Problem Statement

For non-negative integers A and B, let A&B denote the bitwise AND operation. That is, for each i, the i-th bit of A&B in binary representation is 1 if and only if the i-th bits of A and B are 1.

We call a set of non-negative integers S cool if the following conditions are satisfied.

  • For any two distinct elements A, B in S, A&B > 0.
  • For any three distinct elements A, B, C in S, A&B&C = 0.

You are given a long[] subset and an int N. All elements in subset are distinct. Compute a cool set with N distinct elements such that the cool set contains each element of subset and each element is between 1 and 2^60 - 1, inclusive. Return one such cool set as a long[] with elements in increasing order. If there are multiple solutions, return the lexicographically smallest one. If there are no such cool sets, return an empty long[] instead.

Constraints

  • N will be between 3 and 50, inclusive.
  • subset will contain between 0 and N elements, inclusive.
  • Each element of subset will be between 1 and 2^60 - 1, inclusive.
  • All the elements in subset will be distinct.
  • Elements in subset will be sorted in increasing order.
Examples
0)
{14, 20}
3
Returns: {14, 18, 20 }

There are several possible cool sets. For example, the following sets are cool and each of them contains all the elements of subset. {14, 18, 20} {14, 20, 26} {14, 20, 50} ... Among these sets, the first one is the lexicographically smallest one.

1)
{11, 17, 20}
4
Returns: { }

There is no cool set because (11&20) equals 0.

2)
{99, 157}
4
Returns: {99, 157, 262, 296 }
3)
{1152921504606846975}
3
Returns: { }

The element in subset equals to 2^60-1. Note that each element of your cool set should be less than or equal to 2^60-1.

4)
{}
5
Returns: {15, 113, 402, 676, 840 }

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

Coding Area

Language: C++17 · define a public class BitwiseAnd with a public method vector<long long> lexSmallest(vector<long long> subset, int N) · 132 test cases · 2 s / 256 MB per case

Submitting as anonymous