2015 Open Bronze Problem 2 Bessie Gets Even

Official Problem Statement

Bessie Gets Even

Problem

In the problem "Bessie Gets Even" (USACO 2015 Open Bronze, Problem 2), Bessie the cow is given a list of numbers and is trying to count the number of ways she can select a subset of those numbers such that the sum of the numbers in the subset is even.

The list of numbers Bessie has been given are guaranteed to be between 1 and 10, inclusive. The list may have up to 20 numbers, and each number in the list can appear multiple times.

Solution

This problem can be solved using a technique known as dynamic programming.

Firstly, for each number between 1 to 10, we count the frequency of its occurrence in the list. Let's denote this frequency as freq[i].

We can then create a 2D dynamic programming table, dp[i][j], where dp[i][j] represents the number of ways to make a sum of j using the first i numbers. We initially set dp[0][0] to 1 since there is only one way to create a sum of 0, that is by taking no numbers at all.

Then, for each number i from 1 to 10, we perform the following steps:

• We create a temporary copy of the DP table.
• We then iterate through all possible sums j from 0 to 20. For each sum, we consider adding k copies of the current number i, where k can range from 0 to freq[i]. For each valid k, we add the number of ways to form the sum j - k * i (from the previous set of numbers) to dp[i][j].
• After we've finished processing the current number i, we copy the temporary DP table back to the original one.

Finally, the answer to the problem is dp[10][0], since we want to count the number of ways to form an even sum (which is 0 modulo 2).

Code

C++

#include <iostream>
#include <cstdio>

using namespace std;

int num[256][2];

bool is_even(int x) {
  return x % 2 == 0;
}

int main() {
  freopen("geteven.in", "r", stdin);
  freopen("geteven.out", "w", stdout);

  int N;
  cin >> N;

  for (int i = 0; i < N; i++) {
    char letter;
    int val;
    cin >> letter >> val;

    num[letter][val % 2]++;
  }

  int result = 0;

  for(int B = 0; B < 2; B++)
  for(int E = 0; E < 2; E++)
  for(int S = 0; S < 2; S++)
  for(int I = 0; I < 2; I++)
  for(int G = 0; G < 2; G++)
  for(int O = 0; O < 2; O++)
  for(int M = 0; M < 2; M++) {
    int expression = (B + E + S + S + I + E) * (G + O + E + S) * (M + O + O);

    if (is_even(expression)) {
      result += num['B'][B] * num['E'][E] * num['S'][S] * num['I'][I] *
                num['G'][G] * num['O'][O] * num['M'][M];
    }
  }
  
  cout << result << endl;

  return 0;
}

Java

import java.util.*;
import java.io.*;

public class BessieGetsEven {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new FileReader("geteven.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("geteven.out")));
        
        int N = Integer.parseInt(in.readLine());
        int[][] num = new int[256][2];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            char letter = st.nextToken().charAt(0);
            int val = Integer.parseInt(st.nextToken());

            num[letter][val % 2]++;
        }

        int result = 0;

        for(int B = 0; B < 2; B++)
            for(int E = 0; E < 2; E++)
                for(int S = 0; S < 2; S++)
                    for(int I = 0; I < 2; I++)
                        for(int G = 0; G < 2; G++)
                            for(int O = 0; O < 2; O++)
                                for(int M = 0; M < 2; M++) {
                                    int expression = (B + E + S + S + I + E) * (G + O + E + S) * (M + O + O);
                                    if (expression % 2 == 0) {
                                        result += num['B'][B] * num['E'][E] * num['S'][S] * num['I'][I] *
                                                num['G'][G] * num['O'][O] * num['M'][M];
                                    }
                                }
        out.println(result);
        out.close();
    }
}

Python

def is_even(x):
    return x % 2 == 0

num = {c: [0, 0] for c in 'BESIGOM'}

with open('geteven.in', 'r') as fin, open('geteven.out', 'w') as fout:
    N = int(fin.readline().strip())
    for _ in range(N):
        letter, val = fin.readline().strip().split()
        val = int(val)
        if is_even(val):
            num[letter][0] += 1
        else:
            num[letter][1] += 1

    result = 0

    for B in range(2):
        for E in range(2):
            for S in range(2):
                for I in range(2):
                    for G in range(2):
                        for O in range(2):
                            for M in range(2):
                                if is_even((B + E + S + S + I + E) * (G + O + E + S) * (M + O + O)):
                                    result += num['B'][B] * num['E'][E] * num['S'][S] * num['I'][I] * num['G'][G] * num['O'][O] * num['M'][M]

    fout.write(f"{result}\n")