What is the USA Computing Olympiad (USACO)?

This Friday is the first 2014-2015 contest.

The contest format

The USA Computing Olympiad is an online individual competition, where the top 4 US high school students represent the United States in the International Olympiad of Informatics (IOI). Approximately 4 to 6 times per year, anybody in the world can make an account on usaco.org and participate in the competition (post-high-school individuals can participate as ‘observers’). New accounts begin in the ‘bronze’ division, where the top scorers are promoted to the ‘silver’, then ‘gold’, and then finally the ‘USACO camp top 16’. Once promoted to a level, the student stays in that level. Only US high school students are permitted to enter the top 16.

The competition consists of 3 to 5 programming problems, which the individual has 3 to 5 hours to complete. Each problem is an “input output matching” problem, where the student’s program must read an input file and write an output file. Problems can be written in either C, C++, Java, Pascal, or Python, but the USACO recommends not using Python. Programs must also run within a small time frame (1 second for C,C++,and Pascal. 2 seconds for Java and Python), and programs must use limited memory.

Try a bronze problem on a piece of paper

Problem 3 of the 2014 March Contest is called “Cow Art”. Students are given an input file which contains a grid (up to 100 x 100 in size, although this example is 5 x 5):

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

The question asks you to print two numbers.

Part 1: Print how many different patches of R, G, or B there are. In the example, there are 4 regions:

Part 2: Print how many different patches of R, G, and B there are if you treat R and G as the same color. In the example, there are 3 regions:

Thus, the output file should be formatted as: “4 3”

Here’s the code that solves the problem:

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
public class CowArtSolution  {
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(new File("cowart.in"));
		PrintWriter pw = new PrintWriter(new File("cowart.out"));
		int n = sc.nextInt();
		char[][] board = new char[n][n];
		for(int r = 0; r < n; r++) {
			String line = sc.next();
			for(int c = 0; c < n; c++) board[r][c] = line.charAt(c);
		}
		pw.print(countRegions(board));
		for(int j = 0 ; j < n; j++) for(int i = 0; i < n; i++) if(board[j][i]=='R') board[j][i]= 'G';
		pw.println(" "+countRegions(board));
		sc.close();
		pw.close();
	}
	public static int countRegions(char[][] board) {
		boolean[][] humanVisit = new boolean[board.length][board[0].length];
		int count = 0;
		for(int j = 0 ; j < board.length; j++) for(int i = 0; i < board[0].length; i++) 
			if(fill(board,j,i,board[j][i],humanVisit)) count++;
		return count;
	}
	public static boolean fill(char[][] board, int r, int c, char start, boolean[][] visited) {
		if(r<0 || c < 0 || r >= board.length || c >= board[r].length || board[r][c] != start || visited[r][c]) return false;
		visited[r][c] = true;
		fill(board,r-1,c,start,visited);
		fill(board,r+1,c,start,visited);
		fill(board,r,c-1,start,visited);
		fill(board,r,c+1,start,visited);
		return true;
	}
}

import java.io.File;

import java.io.IOException;

import java.io.PrintWriter;

import java.util.Scanner;

public class CowArtSolution {

public static void main(String[] args) throws IOException{

Scanner sc = new Scanner(new File("cowart.in"));

PrintWriter pw = new PrintWriter(new File("cowart.out"));

int n = sc.nextInt();

char[][] board = new char[n][n];

for(int r = 0; r < n; r++) {

String line = sc.next();

for(int c = 0; c < n; c++) board[r][c] = line.charAt(c);

}

pw.print(countRegions(board));

for(int j = 0 ; j < n; j++) for(int i = 0; i < n; i++) if(board[j][i]=='R') board[j][i]= 'G';

pw.println(" "+countRegions(board));

sc.close();

pw.close();

}

public static int countRegions(char[][] board) {

boolean[][] humanVisit = new boolean[board.length][board[0].length];

int count = 0;

for(int j = 0 ; j < board.length; j++) for(int i = 0; i < board[0].length; i++)

if(fill(board,j,i,board[j][i],humanVisit)) count++;

return count;

}

public static boolean fill(char[][] board, int r, int c, char start, boolean[][] visited) {

if(r<0 || c < 0 || r >= board.length || c >= board[r].length || board[r][c] != start || visited[r][c]) return false;

visited[r][c] = true;

fill(board,r-1,c,start,visited);

fill(board,r+1,c,start,visited);

fill(board,r,c-1,start,visited);

fill(board,r,c+1,start,visited);

return true;

}

Try a silver problem:

Problem 3 of the 2011 December Contest was called “Umbrellas for Cows”. Students were given an input file representing the positions of cows (in stalls) and the cost of various sized umbrellas. Here is a sample positions of cows:

And the umbrellas:

Size 1 umbrella: $2
Size 2 umbrella: $3
Size 3 umbrella: $4
Size 4 umbrella: $4
Size 5 umbrella: $8
Size 6 umbrella: $9
Size 7 umbrella: $15
Size 8 umbrella: $16
Size 9 umbrella: $17
Size 10 umbrella: $18
Size 11 umbrella: $19
Size 12 umbrella: $19

The goal is the decide which umbrellas to buy in order to cover all the cows for the total lowest price.

View post on imgur.com

The solution, above, shows that you can cover all the cows with one size 4 umbrella, one size 1 umbrella, and one size 2 umbrella. The cost is 4 + 2 + 3 = $9.

import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class UmbrellasSolution {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("umbrella.in"));
		PrintWriter pw = new PrintWriter(new File("umbrella.out"));
		dp = new HashMap<Integer,Integer>();
		int n = sc.nextInt(), m = sc.nextInt();
		int[] cows = new int[n], costs = new int[m];
		for(int i=0;i<n;i++) cows[i] = sc.nextInt();
		for(int i=0;i<m;i++) costs[i] = sc.nextInt();
		Arrays.sort(cows);
		for(int i=m-2;i>=0;i--) costs[i] = Math.min(costs[i], costs[i+1]);
		pw.println(minCost(cows, costs, n));
		pw.close();
		sc.close();
	}

	static Map<Integer,Integer> dp;
	public static int minCost(int[] cows, int[] costs, int pos) {
		if(pos == 0) return 0;
		if(dp.containsKey(pos)) return dp.get(pos);
		int result = costs[costs.length-1]; //assume we have to take longest umbrella (or could just use null / MAX_VALUE)
		for(int i=0;i<pos;i++) result = Math.min(result, minCost(cows,costs,i) + costs[cows[pos-1]-cows[i]]);
		dp.put(pos, result); //Try using the umbrella of the length that goes from i to pos
		return result;
	}
}

import java.io.File;

import java.io.IOException;

import java.io.PrintWriter;

import java.util.Arrays;

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

public class UmbrellasSolution {

public static void main(String[] args) throws IOException {

Scanner sc = new Scanner(new File("umbrella.in"));

PrintWriter pw = new PrintWriter(new File("umbrella.out"));

dp = new HashMap<Integer,Integer>();

int n = sc.nextInt(), m = sc.nextInt();

int[] cows = new int[n], costs = new int[m];

for(int i=0;i<n;i++) cows[i] = sc.nextInt();

for(int i=0;i<m;i++) costs[i] = sc.nextInt();

Arrays.sort(cows);

for(int i=m-2;i>=0;i--) costs[i] = Math.min(costs[i], costs[i+1]);

pw.println(minCost(cows, costs, n));

pw.close();

sc.close();

}

static Map<Integer,Integer> dp;

public static int minCost(int[] cows, int[] costs, int pos) {

if(pos == 0) return 0;

if(dp.containsKey(pos)) return dp.get(pos);

int result = costs[costs.length-1]; //assume we have to take longest umbrella (or could just use null / MAX_VALUE)

for(int i=0;i<pos;i++) result = Math.min(result, minCost(cows,costs,i) + costs[cows[pos-1]-cows[i]]);

dp.put(pos, result); //Try using the umbrella of the length that goes from i to pos

return result;

}

Leave a Reply Cancel reply