BagsOfNumbers | Topcoder Archive

Problem Statement

Alice and Bob have n bags, each containing some, possibly zero, positive integers: ones, twos, threes, and fours. They play a game using these bags. Alice goes first, and then they alternate turns. In one turn, a player first selects exactly one of the bags. Then she or he removes some non-empty subset of numbers whose sum is divisible by four. Whoever is not able to make a move, loses.

The number of ones, twos, threes and fours in bag number i is a[i], b[i], c[i] and d[i], respectively. For each of the 2^n - 1 non-empty subsets of bags, consider the game played with only these bags. Determine how many of these games are won by Alice if they both play optimally.

Definition

Class:: BagsOfNumbers
Method:: wonByAlice
Parameters:: int, long[], long[], long[], long[]
Returns:: long
Method signature:: long wonByAlice(int n, long[] a, long[] b, long[] c, long[] d)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
The arrays a, b, c and d will have exactly n elements each.
Each element of each array will be an integer between 0 and 1018, inclusive.

Examples

```
2
```
```
{13,13}
```
```
{12,12}
```
```
{25,25}
```
```
{9,9}
```
```
Returns: 2
```
When there is only single bag, Alice can win by removing all integers in it (their sum is 148, which is divisible by four). When playing with both bags, Bob can simply mirror Alice's moves to win.
```
4
```
```
{3,4,1,7}
```
```
{2,2,6,9}
```
```
{1,0,7,7}
```
```
{3,2,1,1}
```
```
Returns: 15
```
Regardless of the choice of bags, Alice always wins.

{0,18,15,16 }

{3,14,8,18 }

{9,12,16,12 }

{0,10,6,7 }

Returns: 14

When bags 0, 1, and 3 are selected, Bob can force win.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.