SpecialClique
2016 TCO Semi 2 · 2016-03-24 · by cgy4ever
2016 TCO Semi 2 · 2016-03-24 · by cgy4ever · Brute Force
Problem Statement
Problem Statement
In this problem we use "AND" to denote the bitwise-and operator. For example, (6 AND 5) = 4.
A collection C is called a clique if and only if it has the following properties:
A clique is called trivial if the bitwise-and of all its elements is non-zero. A clique that is not trivial is called special.
For example, the cliques {3}, {1,1,1} and {16,17,18,19} are trivial, and the cliques {3,6,5} and {3,3,6,5,6} are special.
You are given along[] s that contains a collection of positive integers.
We want to change s into a special clique by erasing some (possibly none, but not all) of its elements.
Return "Possible" if this can be done, or "Impossible" if it cannot be done.
A collection C is called a clique if and only if it has the following properties:
- C is non-empty.
- The elements of C are positive integers. (They are not required to be distinct.)
- Whenever x and y are two (not necessarily distinct) elements of C, the value (x AND y) is non-zero.
A clique is called trivial if the bitwise-and of all its elements is non-zero. A clique that is not trivial is called special.
For example, the cliques {3}, {1,1,1} and {16,17,18,19} are trivial, and the cliques {3,6,5} and {3,3,6,5,6} are special.
You are given a
Constraints
- s will contain between 1 and 1,000 elements, inclusive.
- Each element in s will be between 1 and 1,000,000,000,000,000,000 (10^18) inclusive.
Examples
0)
{3,6,5,8,24,56}
Returns: "Possible"
We can erase the last three elements of s, producing the special clique {3,6,5}.
1)
{6, 5, 8, 24, 56}
Returns: "Impossible"
Each clique we can produce from this s is a trivial clique.
2)
{585858585858585858, 585858585858585858, 585858585858585858, 585858585858585858}
Returns: "Impossible"
Note that s may contain duplicates.
3)
{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}
Returns: "Impossible"
4)
{1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597}
Returns: "Possible"
Submissions are judged against all 139 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SpecialClique with a public method string exist(vector<long long> s) · 139 test cases · 2 s / 256 MB per case