ThreeWaySplit
2022 TCO Parallel 2A · 2022-04-14 · by misof
Problem Statement
Time limit: 4 seconds.
Pirates Alice, Bob and their captain Cindy are dividing some loot. The loot consists of N items, numbered from 0 to N-1. Item i has the value loot[i] dubloons.
Cindy has two goals: She wants to reward her crew as much as possible, but at the same time she wants to prevent disputes among them.
There is only one way to prevent disputes: Alice and Bob must get items with the exact same value.
Return a
Notes
- Any optimal solution will be accepted.
Constraints
- loot will contain between 1 and 24 elements, inclusive.
- Each element of loot will be between 1 and 10^9, inclusive.
{4, 7, 53}
Returns: "CCC"
The only way to give Alice and Bob items with the same value is to give them nothing at all.
{1, 1, 1, 4, 1}
Returns: "BBBAB"
Alice and Bob may get a different number of items, only their total value must be equal. Here, Cindy can split all the loot between her two crew members. The example return value is the only optimal solution for this test case.
{47, 47, 47}
Returns: "CBA"
In the optimal solution each pirate gets one of these three items. As order does not matter, there are six optimal return values: all permutations of the string "ABC".
{1, 2, 3, 4, 5, 6}
Returns: "CBBABA"
There are several ways how to give 10 to Alice, 10 to Bob and 1 to Cindy. This is clearly optimal.
{1}
Returns: "C"
Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ThreeWaySplit with a public method string split(vector<int> loot) · 128 test cases · 2 s / 256 MB per case