Dashboard - Qualification Round 2013 - Google Code Jam
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.
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
codejam 2013 prob b
Therefore, we start by calculating the max elements for each row and maximum element in each column, then we loop on the array elements, if we found an element that is not maximum in its row and not maximum in its column we mark the pattern as impossible.
http://www.vexorian.com/2013/04/google-codejam-2013-qualification-round.html
O(N^2)
O(N^3)
Read full article from Dashboard - Qualification Round 2013 - Google Code Jam
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).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
Official Analysis: https://code.google.com/codejam/contest/2270488/dashboard#s=a&a=1
http://toughprogramming.blogspot.com/2013/04/code-jam-2013-qualification-round.html
http://toughprogramming.blogspot.com/2013/04/code-jam-2013-qualification-round.html
First we map the desired pattern into a two dimensional array.
The idea is to find an element in the pattern which will make it an impossible pattern. Such element will be the one that you cant cut it vertically or horizontally, because if you do you will mess up another element.
Therefore, we start by calculating the max elements for each row and maximum element in each column, then we loop on the array elements, if we found an element that is not maximum in its row and not maximum in its column we mark the pattern as impossible.
http://www.vexorian.com/2013/04/google-codejam-2013-qualification-round.html
For each row, find the maximum height in that row. We can clearly just run the mower on that row with that maximum height as setting. The heights of all grass squares in that row will either become exactly what the pattern wants them to be, or a larger height (which we can cut by using another mower run).
Then we can do the same about columns, run the mower using a height setting equal to the maximum height in that column.
If we did any different kind of move. If we ever used a setting smaller than the maximum of a row or column, we would definitely have a wrong pattern. Some grass squares (the ones that are supposed to be equal to the maximum height of the column/row) would become smaller than what you wanted.
If after doing these moves for each row/column, the pattern is not equal to what we wanted, it should be impossible to do it.
The solution is then to verify. Each cell must be either equal to the maximum height of the column that contains the cell, or the maximum height of the row that contains the cell. Else it would not be possible to do it.
http://www.vexorian.com/2013/04/google-codejam-2013-qualification-round.htmlO(N^2)
string solve( ) {
int rowMax[N];
int colMax[M];
// Find the maximum for each row:
for (int i=0; i<N;i++) {
int mx = 0;
for (int j=0; j<M; j++) {
mx = std::max(mx, a[i][j] );
}
rowMax[i] = mx;
}
// Find the maximum for each column:
for (int j=0; j<M; j++) {
int mx = 0;
for (int i=0; i<N; i++) {
mx = std::max(mx, a[i][j] );
}
colMax[j] = mx;
}
//Verify:
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if ( (a[i][j] < rowMax[i]) && (a[i][j] < colMax[j]) ) {
return "NO";
}
}
}
return "YES";
}
http://toughprogramming.blogspot.com/2013/04/code-jam-2013-qualification-round.html int[] maxRows = new int[N];
int[] maxCols = new int[M];
// calculating the max of each row
for (int row = 0; row < N; ++row) {
int max = -1;
for (int col = 0; col < M; ++col) {
if (lawn[row][col] > max)
max = lawn[row][col];
}
maxRows[row] = max;
}
// calculating the max of each column
for (int col = 0; col < M; ++col) {
int max = -1;
for (int row = 0; row < N; ++row) {
if (lawn[row][col] > max)
max = lawn[row][col];
}
maxCols[col] = max;
}
// checking each element
for (int row = 0; row < N; ++row) {
if (impossible)
break;
for (int col = 0; col < M; ++col) {
if (lawn[row][col] < maxRows[row]
&& lawn[row][col] < maxCols[col]) {
// pattern is impossible
impossible = true;
break;
}
}
} O(N^3)
def grassShorterOrEqualInColumn(lawnState, lawnColumns, row, value):
for column in range(lawnColumns):
if lawnState[row][column] > value:
return False
return True
def grassShorterOrEqualInRow(lawnState, lawnRows, column, value):
for row in range(lawnRows):
if lawnState[row][column] > value:
return False
return True
def lawnMower(lawnState, lawnRows, lawnColumns):
for row in range(lawnRows):
for column in range(lawnColumns):
value = lawnState[row][column]
if grassShorterOrEqualInColumn(lawnState, lawnColumns, row, value)or grassShorterOrEqualInRow(lawnState, lawnRows, column, value):
continue
else:
print "This cell doesn't work!" + str(row) + str(column)
return "NO"
return "YES"
Read full article from Dashboard - Qualification Round 2013 - Google Code Jam
