Connection Status:
Competition Arena > FlippingCoinSum

FlippingCoinSum

SRM 838 · 2022-09-19 · by misof

SRM 838 · 2022-09-19 · by misof · Dynamic Programming
Class Name: FlippingCoinSum
Return Type: int[]
Method Name: flip
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

There are some coins on your table. Some of them are face-up (i.e., you can see their numerical value), the rest is face-down.

The values on the face-up coins are given in the int[] faceUp, and the values of the other coins are in faceDown.


You are allowed to flip some of the coins. You want to reach a state in which the sum of the numbers visible on the coins is exactly equal to goal. Your goal is to reach that state by performing as few flips as possible.


If the goal cannot be reached, return {-123456789}. Otherwise, return a int[] describing the shortest possible solution. Each element of the return value should be either +x (representing an action where you flip a face-down coin worth x face-up) or -x (representing the opposite action).

If there are multiple optimal solutions, you may return any one of them.

Notes

  • If the goal cannot be reached, the correct return value is an array with one element: the negative integer -123456789.

Constraints

  • faceUp will contain between 0 and 50 elements, inclusive.
  • faceDown will contain between 0 and 50 elements, inclusive.
  • Each element of faceUp will be between 1 and 1000, inclusive.
  • Each element of faceDown will be between 1 and 1000, inclusive.
  • goal will be between 0 and 100,000, inclusive.
Examples
0)
{2, 2, 5}
{1, 10}
9
Returns: { }

The sum of visible numbers is already exactly 9, so the only optimal solution is to do nothing.

1)
{2, 2, 5}
{1, 10}
14
Returns: {-5, 10 }

The only optimal solution here is to flip the 5 face-down and the 10 face-up.

2)
{2, 2, 5}
{2, 10}
3
Returns: {-123456789 }

There is no way to produce the sum 3. In particular, note that we cannot flip a coin worth 2 face-down three times in a row, as there are currently only two face-up coins worth 2 each.

3)
{2, 2, 5}
{100, 10}
5
Returns: {-2, -2 }
4)
{1, 1, 1, 1, 1, 1, 1}
{1, 1, 1, 1, 1, 1, 1}
10
Returns: {1, 1, 1 }

Any three of the seven face-down coins need to be turned face-up.

5)
{1, 1, 2, 2, 2, 3, 3, 3, 3}
{1, 2, 3, 4, 5, 6, 7}
0
Returns: {-1, -1, -2, -2, -2, -3, -3, -3, -3 }

All coins need to end face-down.

6)
{5, 5, 5, 5, 47, 100}
{42, 80, 174}
147
Returns: {-100, 80 }

One valid but not optimal solution is to flip all coins worth 5 face-down. The returned solution (flip the 100 face-down and the 80 face-up) needs fewer flips.

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

Coding Area

Language: C++17 · define a public class FlippingCoinSum with a public method vector<int> flip(vector<int> faceUp, vector<int> faceDown, int goal) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous