Connection Status:
Competition Arena > EllysAndor

EllysAndor

2016 TCO NYC Regional · 2016-03-24 · by espr1t

2016 TCO NYC Regional · 2016-03-24 · by espr1t · Greedy
Class Name: EllysAndor
Return Type: String
Method Name: canGet
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

Elly has given you the following riddle:


"At the beginning, the variable X is set to zero. I will show you a sequence of cards. Each card will contain a positive integer. Each time I show you a card, you will have to choose exactly one of three possible actions. Let C be the number shown on the card. The three actions are:


  • Leave X unchanged.
  • Change X to (X OR C).
  • Change X to (X AND C).


Can you find a sequence of actions such that at the end the variable X will contain the value goal?"


You are given the int[] numbers and the int goal. The elements of numbers are the positive integers on Elly's cards, in the order in which she'll show them to you. Return "Possible" (quotes for clarity) if there is a sequence of actions after which X equals goal. Otherwise, return "Impossible".

Notes

  • Given two integers X and Y, the result of the bitwise operation X AND Y has 1-bits on all positions where both X and Y have 1-bit in their binary representation. For example 1337(10) AND 4213(10) = 49(10), since 0000010100111001(2) AND 0001000001110101(2) = 0000000000110001(2).
  • Given two integers X and Y, the result of the bitwise operation X OR Y has 1-bits on all positions where at least one of X and Y has 1-bit in its binary representation. For example 1337(10) OR 4213(10) = 5501(10), since 0000010100111001(2) OR 0001000001110101(2) = 0001010101111101(2).

Constraints

  • numbers will contain between 1 and 100 elements, inclusive.
  • Each element of numbers will be between 1 and 1,000,000,000, inclusive.
  • goal will be between 1 and 1,000,000,000, inclusive.
Examples
0)
{42, 13, 29, 17}
25
Returns: "Possible"

You should choose the following sequence of actions: Start with X = 0. Change X to (X OR 42) = 42. Change X to (X AND 13) = 42 AND 13 = 8. Change X to (X AND 29) = 8 AND 29 = 8. Change X to (X OR 17) = 8 OR 17 = 25. Alternately, when processing the number 29, you could have left the variable X unchanged.

1)
{13, 13, 42, 13, 13}
42
Returns: "Possible"

We can simply skip all the 13s, and use OR on the 42.

2)
{1337, 666, 511, 4242, 666, 1234, 4321, 717}
193
Returns: "Possible"

A possible solution here would be to use AND, OR, OR, OR, AND, AND, OR, AND.

3)
{1337, 666, 511, 4242, 666, 1234, 4321, 717}
2016
Returns: "Impossible"

This example has the same sequence of numbers as Example 2, but the goal is different. This new goal cannot be achieved.

4)
{2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
13
Returns: "Impossible"

Since all numbers are even, we are unable to reach an odd goal.

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

Coding Area

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

Submitting as anonymous