USACO Gold 2015 December - Fruit Feast

Authors: Danh Ta Chi Thanh, Mark Phan, Arpan Banerjee, Juheon Rhee

Edit This Page

Official Analysis (Java)

Implementation - DP

Time Complexity: O(T)\mathcal{O}(T), where TT is the maximum fullness.

C++

#include <bits/stdc++.h>
using namespace std;


bool dp[2][5000001];


int main() {
	freopen("feast.in", "r", stdin);
	int max_fullness, orange, lemon;
	cin >> max_fullness >> orange >> lemon;

Python

with open("feast.in") as read:
	max_fullness, orange, lemon = map(int, read.readline().split())


dp = [[0] * (max_fullness + 1) for _ in range(2)]
dp[0][0] = True
for i in range(max_fullness + 1):
	if i - orange >= 0:
		dp[0][i] |= dp[0][i - orange]


	if i - lemon >= 0:

Alternative Implementation - BFS/DFS

Instead of a knapsack solution, a BFS/DFS can be done to iterate though all attainable states and simply choose the one with maximum fullness. The scene can be thought of as a graph by defining each edge to be the transition from fullness ii to jj. Each state is defined by fullness and whether Bessie has drank water. Since there are 2T2T states and each state is visited at most once, the time and space complexity of this solution is O(T)\mathcal{O}(T). Below is a BFS implementation.

C++

#include <fstream>
#include <iostream>
#include <queue>
#include <set>
#include <vector>


using std::cout;
using std::endl;
using std::pair;
using std::vector;

Python

from collections import deque


with open("feast.in") as read:
	max_fullness, orange, lemon = map(int, read.readline().split())


poss_fullness = {(0, False)}  # Keep track of which states we visited
to_process = deque([(0, False)])
while to_process:
	fullness, drank_water = to_process.pop()

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum