Connection Status:
Competition Arena > ORSolitaireDiv2

ORSolitaireDiv2

SRM 600 · 2013-06-25 · by gojira_tc

SRM 600 · 2013-06-25 · by gojira_tc · Brute Force, Greedy
Class Name: ORSolitaireDiv2
Return Type: int
Method Name: getMinimum
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

Note that the memory limit for all tasks in this SRM is 256 MB.

This problem statement contains subscripts that may not display properly if viewed outside of the applet.

Manao is playing a solitaire game called OR-solitaire. In this game, the player starts with a number X = 0 and should obtain the number goal in one or more moves. The set of valid moves is determined by a int[] numbers. In each move, the player chooses some element of numbers and replaces X with the bitwise OR of X and the chosen element.

Fox Ciel wants Manao to stop playing OR-solitaire and move on with his life. She decided to erase some of the elements from numbers in such a way that it becomes impossible to complete the game. Return the minimum number of elements that need to be removed to achieve this.

Notes

  • If a and b are single bits then a | b is defined as max(a, b). For two integers, A and B, in order to calculate A | B, they need to be represented in binary: A = (an...a1)2, B = (bn...b1)2 (if the lengths of their representations are different, the shorter one is prepended with the necessary number of leading zeroes). Then A | B = C = (cn...c1)2, where ci = ai | bi. For example, 10 | 3 = (1010)2 | (0011)2 = (1011)2 = 11.

Constraints

  • numbers will contain between 1 and 20 elements, inclusive.
  • Each element of numbers will be between 1 and 1,000,000,000.
  • The elements in numbers will be distinct.
  • goal will be between 1 and 1,000,000,000.
Examples
0)
{1, 2, 4}
7
Returns: 1

The goal of the game is to obtain X = 7 from X = 0. The possible moves are to replace X with bitwise OR of X and 1, bitwise OR of X and 2 and bitwise OR of X and 4. X = 7 can be obtained only by using each of the three moves at least once, so removing any single element from numbers will make the game impossible to finish.

1)
{1, 2, 4, 7, 8}
7
Returns: 2

In this example, Fox Ciel should remove the number 7 and one of the numbers 1, 2, 4.

2)
{12571295, 2174218, 2015120}
1
Returns: 0

There is no need to remove elements from numbers, since the game cannot be completed in its initial version.

3)
{5, 2, 4, 52, 62, 9, 8, 3, 1, 11, 6}
11
Returns: 3
4)
{109127425,391193886,77568450,481751837,411889236,488364804,480598915,7490879,95057181,16530444,55580676,92339390,273649157,5737290,144995698,480240667,402927632,95353526,170311435,485081164}
536870911
Returns: 4

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

Coding Area

Language: C++17 · define a public class ORSolitaireDiv2 with a public method int getMinimum(vector<int> numbers, int goal) · 58 test cases · 2 s / 256 MB per case

Submitting as anonymous