google code jam 2013

 https://codingcompetitions.withgoogle.com/profile

Code Jam 2013

You competed in 2 rounds.

View certificate

Code Jam 2011

You competed in 1 round.

View certificate

Code Jam 2009

You competed in 1 round.

View certificate

Analysis

The Small Input

For a problem like this, it can be helpful to think through a few cases. Let's look at the first two examples from the problem statement:

   2 2 2 2 2
   2 1 1 1 2    2 1 2
   2 1 2 1 2    1 1 1
   2 1 1 1 2    2 1 2
   2 2 2 2 2

All the grass needs to be cut to either height 1 or 2. Thus, we can begin by cutting the whole lawn to height 2. The question that remains is which rows and which columns to cut to height 1. Note that if we cut a row (or column) to height 1, all the squares in this row or column will be height 1 in the final pattern since we can't grow grass back.

In the left example, we must at some point do a cut with the lawnmower at height 1. Otherwise, we would never get any grass that low. However, there is nowhere that it is safe to make a cut like that. Every row and every column has at least one square where we want the final grass height to be 2, so we can never run the lawnmower through that row or column while at height 1. This pattern is impossible.

In the second example, we also must do some cuts with the lawnmower at height 1. However, in this case, there are two places where we can safely make that cut: the middle row and the middle column. If we do both, we get the desired pattern.

More generally, there are some rows and columns we cannot cut to height 1. By avoiding those rows and columns, we ensure nothing will be made too low. What remains is to check if it is still possible to get all the grass low enough. Well, if our only goal is to get the grass low, we should do all the cuts we can!

This suggests the following approach:

• Determine which rows and columns it is safe to cut at height 1 (meaning the pattern has no square with height > 1 in that row or column).
• Do a cut on each of these rows and columns at height 1.
• Check if we got every square low enough. If so, the pattern is possible. Otherwise, it is not.

The Large Input

For the large input, we can use almost the exact same strategy. You just have to think through what that means!

We can cut any row or column at a height that is equal to the maximum height appearing in this row (or column). As long as we follow this rule, we will never cut a square too low, and then as above, we just need to try to get everything low enough. For that purpose, we want to use all the cuts we can. The full algorithm is then:

• Iterate over every row and find the largest height that the pattern has in this row. Cut the row at this height.
• Do the same thing for every column.
• Output "YES" if this achieved the desired pattern, and "NO" if not.

Lawnmower (10pts, 30pts)

Attempts

2

Penalties

0

Penalty Time

19:16:13

Points

done

Points

done

Practice Submissions

You have not attempted this problem.

Last updated: Jun 4 2022, 15:27

PROBLEM

ANALYSIS

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 ai,j each, the number ai,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

Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.

Small dataset (Test set 1 - Visible)

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

Large dataset (Test set 2 - Hidden)

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

Sample

Input	Output
3 3 3 2 1 2 1 1 1 2 1 2 5 5 2 2 2 2 2 2 1 1 1 2 2 1 2 1 2 2 1 1 1 2 2 2 2 2 2 1 3 1 2 1	Case #1: YES Case #2: NO Case #3: YES