Lawnmower Solution: Google codejam 2013 Qual Round

Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the second problem from Qualification Round 2013.

Problem

Alice and Bob have a lawn in front of their house, shaped like an N metre by M metre rectangle. Each year, they try to cut the lawn in some interesting pattern. They used to do their cutting with shears, which was very time-consuming; but now they have a new automatic lawnmower with multiple settings, and they want to try it out.

The new lawnmower has a height setting – you can set it to any height h between 1 and 100 millimetres, and it will cut all the grass higher than h it encounters to height h. You run it by entering the lawn at any part of the edge of the lawn; then the lawnmower goes in a straight line, perpendicular to the edge of the lawn it entered, cutting grass in a swath 1m wide, until it exits the lawn on the other side. The lawnmower’s height can be set only when it is not on the lawn.

Alice and Bob have a number of various patterns of grass that they could have on their lawn. For each of those, they want to know whether it’s possible to cut the grass into this pattern with their new lawnmower. Each pattern is described by specifying the height of the grass on each 1m x 1m square of the lawn.

The grass is initially 100mm high on the whole lawn.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing two integers: N and M. Next follow N lines, with the ith line containing M integers a_i,j each, the number a_i,j describing the desired height of the grass in the jth square of the ith row.

Output

For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is either the word “YES” if it’s possible to get the x-th pattern using the lawnmower, or “NO”, if it’s impossible (quotes for clarity only).

Limits

1 ≤ T ≤ 100.

Small dataset

1 ≤ N, M ≤ 10.
1 ≤ a_i,j ≤ 2.

Large dataset

1 ≤ N, M ≤ 100.
1 ≤ a_i,j ≤ 100.

Sample

Solution

This problem is exactly opposite to the first problem, it required thinking rather than coding. The idea to to this problem is to understand that for any square of height x in the pattern > all heights in one of row or column must be smaller or equal to x.

Here is the Java code for Lawnmover problem in Google codejam Qualification round 2013

package googlecodejam2013;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Reader;
import java.util.ArrayList;

public class LawnMover {

	public boolean isPossible(int[][] pattern, int n, int m){
		for(int i=0; i < n; i++){
			for(int j=0; j < m; j++){
				if(!isNumberPossible(pattern, i, j, n, m, pattern[i][j])){
					return false;
				}
			}
		}
		return true;
	}
	//Check if all heights in row or column is smaller or equal to the current height
	private boolean isNumberPossible(int[][] pattern, int row, int col, int n, int m, int num){
		boolean isColPossible = true;
		boolean isRowPossible = true;
		for(int j=0; j < m; j++){
			if(pattern[row][j] > num){
				isRowPossible = false;
				break;
			}
		}
		
		for(int i= 0; i < n; i++){
			if(pattern[i][col] > num){
				isColPossible =  false;
				break;
			}
		}
		return isColPossible || isRowPossible;
	}
	
	public static void main(String[] argv) {
		try {
			long startTime = System.currentTimeMillis();
			Reader reader = new FileReader("large.in");
			BufferedReader bufReader = new BufferedReader(reader);
			String x = bufReader.readLine();
			int numOfTestCases = Integer.parseInt(x);
			int count = 0;
	
			File file = new File("large.out");
			FileWriter writer = new FileWriter(file);
			for(count =1; count<= numOfTestCases; count++) {
				ArrayList<Integer> nAndM = getIntegerList(bufReader.readLine());
				;
				String output = (new LawnMover().isPossible(getLawnPattern(bufReader, nAndM.get(0), nAndM.get(1)), nAndM.get(0), nAndM.get(1)) ? "YES":"NO");
				writer.write("Case #" + count + ": " + output+"\n");
				System.out.println("Case #" + count + ": " + output);
			}
			writer.close();
			System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private static int[][] getLawnPattern(BufferedReader bufReader, int n, int m) throws IOException{
		int[][] pattern = new int[n][m];
		
		for(int i =0; i <n; i++){
			ArrayList<Integer> rowList = getIntegerList(bufReader.readLine());
			
			for(int j=0; j<m;j++){
				pattern[i][j] = rowList.get(j);
			}
		}
		return pattern;
	}
	
	private static ArrayList<Integer> getIntegerList(String s) {
		ArrayList<Integer> intList = new ArrayList<Integer>();
		String[] strArr = s.split(" ");
		for (String str : strArr) {
			intList.add(Integer.parseInt(str.trim()));
		}
		return intList;
	}
	
}

Facebook Comments