MagicMatchesGame
SRM 526.5 · 2011-12-12 · by cgy4ever
Problem Statement
Today is the Christmas Eve. People around the world celebrate this holiday. The following story takes place in the land of reindeer, where Santa Claus resides.
Instead of placing a boring gift into your stocking or underneath your tree, Santa Claus wants to give you an exciting chance to win some Magic Diamonds!
The game is played with n envelopes, conveniently numbered 0 through n-1. The content of the envelopes is described by three
The game proceeds in several steps:
- You keep some of the envelopes and throw away the others. (You have to keep at least one envelope, you may keep all of them.)
- You collect all Magic Diamonds and numbered cards from the envelopes you kept.
- You go and feed Santa's reindeer. This is explained below.
- Santa throws away some of the envelopes you kept. (He must not throw away all envelopes. He is allowed not to throw away anything.)
- A game of NIM is played using the matches from the envelopes Santa kept. This is explained below.
- If you won the game of NIM, you are allowed to keep all Magic Diamonds you collected in step 2.
Feeding the reindeer works as follows: Let R be the sum of red numbers you collected, and let B be the sum of blue numbers you collected. Santa will mark a rectangular field R meters long and B meters wide. You have to take a shovel and remove all snow from the field so that the reindeer can get to the grass.
The game of NIM is played as follows: Each of the K envelopes Santa kept is emptied on a separate pile, thus creating K piles of matches. You and Santa then take alternating turns removing matches. You take the first turn. In each turn, the current player picks a nonempty pile of matches and removes an arbitrary positive number of matches from the pile. The player who removes the last matches wins. (In other words, the player who cannot make a valid move loses.)
Assume that Santa follows the optimal strategy for the entire game and wins whenever he gets the chance. Your primary goal is to win the game and gain as many Magic Diamonds as possible. If there are multiple ways to do so, you prefer the one that minimizes the work you have to do in step 3. That is, you want to minimize the area of the field you'll have to clear.
Your method must return the smallest possible area of the field, given that you gained as many Magic Diamonds as possible.
Notes
- Note that you can always win the game. In the first turn, you may discard all the envelopes except for one. Santa must keep this envelope. In the game of NIM you then win in the first turn by taking all the matches.
Constraints
- matches will contain between 1 and 50 elements, inclusive.
- red and matches will contain the same number of elements.
- blue and matches will contain the same number of elements.
- Each element in matches will be between 1 and 1,000,000, inclusive.
- Each element in red will be between 1 and 10,000, inclusive.
- Each element in blue will be between 1 and 10,000, inclusive.
{12014, 69122, 89899, 59692, 83775, 96845, 91822, 31930, 39496, 18812}
{42, 20, 363, 143, 429, 417, 78, 128, 94, 257}
{159, 43, 193, 131, 59, 222, 28, 176, 358, 422}
Returns: 3530061
{49729, 18175, 27677, 20032, 82393, 42704, 17759, 99988, 98424, 84088}
{41, 446, 286, 244, 194, 416, 343, 433, 388, 329}
{340, 350, 289, 170, 288, 206, 215, 155, 52, 210}
Returns: 7098000
{78396, 98638, 40124, 42349, 42178, 74869, 43023, 27318, 59620, 65427}
{143, 160, 83, 179, 339, 263, 451, 256, 163, 349}
{15, 154, 111, 398, 88, 256, 120, 132, 7, 124}
Returns: 3352330
{30702, 34863, 18007, 48826, 44632, 28598, 64492, 55737, 88583, 7184}
{154, 236, 164, 36, 43, 59, 241, 438, 176, 220}
{16, 263, 396, 130, 196, 473, 45, 69, 29, 257}
Returns: 3311358
{64245, 56099, 35905, 70419, 87695, 68965, 97342, 1482, 92675, 1356}
{285, 333, 78, 341, 18, 219, 491, 286, 149, 244}
{263, 210, 182, 161, 10, 401, 230, 300, 299, 493}
Returns: 6229756
{1,1}
{5,6}
{5,4}
Returns: 24
Now we have 2 envelopes. Note that we can't keep both envelopes, otherwise we can't win the game of NIM. If we keep envelope 0, the area will be 5 * 5 = 25. If we keep envelope 1, the area will be 4 * 6 = 24. So we should return 24.
{1,2,3}
{4,5,6}
{9,8,7}
Returns: 153
Here the optimal solution is to keep envelopes 0 and 1. The area is (4 + 5) * (9 + 8) = 153.
{10095, 16913, 10198, 12528, 15264, 19224, 16442, 14595, 12060, 11858, 17900, 19304, 10619, 15818, 11670}
{9419, 9448, 9722, 9030, 9591, 9451, 9871, 9124, 9012, 9047, 9024, 9984, 9163, 9852, 9203}
{9706, 9436, 9454, 9585, 9592, 9145, 9356, 9797, 9523, 9032, 9178, 9472, 9594, 9637, 9256}
Returns: 17324432487
Note that the answer can be very large.
Submissions are judged against all 119 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MagicMatchesGame with a public method long long minimumArea(vector<int> matches, vector<int> red, vector<int> blue) · 119 test cases · 2 s / 256 MB per case