USACO Bronze 2017 January - Cow Tipping

Authors: Maggie Liu, Kevin Sheng, Melody Yu

Edit This Page

Official Analysis (Java)

Video Solution

By Melody Yu

Video Solution Code

Alternate Explanation

While the official solution processes the cells in a standard right to left order starting from the bottom right square, there's another way to process them as well.

Like in the official solution, we start at the lower right. However, we process the edges of the square simultaneously and "close in" on the top left square.

Implementation

Time Complexity: O(N2)\mathcal{O}(N^2)

C++

#include <cstdio>
#include <iostream>
#include <vector>


using namespace std;


const char TIPPED = '0';


bool flip(int r, int c, vector<vector<bool>> &cows) {
	if (cows[r][c]) {

Java

import java.io.*;


public class CowTip {
	static final char FLIPPED = '0';


	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("cowtip.in"));
		int width = Integer.parseInt(read.readLine());
		boolean[][] cows = new boolean[width][width];
		for (int r = 0; r < width; r++) {

Python

from typing import List




TIPPED = "0"




def flip(r: int, c: int, cows: List[List[int]]) -> bool:
	if cows[r][c]:
		for ri in range(r + 1):
			for ci in range(c + 1):

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