This year qualification round of Google Code Jam has easy-to-understand problems. I will offer my solution for the second problem with a short solution (20 lines, no 1-liner) in python.
The Lawnmower
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.
Each number in the digit lawn describing the desired height of the grass. The left example pattern result in a NO, the right one in YES:
2 2 2 2 2 3 3 1 3 3
2 1 1 1 2 3 3 1 3 3
2 1 2 1 2 1 1 1 1 1
2 1 1 1 2 3 3 1 3 3
2 2 2 2 2 3 3 1 3 3
the solution
The solution was easy and fast coded. You have only to check for every field of the lawn if there is no greater number in the corresponding vertical OR horicontal line. In the code I reverted this condition to stop the check loop.
For faster solution I generated for every testcase the maximum value per row and column. Then checked all squares for the condition with the max value in the precalculated values.
import sys
def solve(n, m, lines):
#find max value per row
nMax = map(max, lines)
#find max value per column
mMax = [reduce(max, [lines[i][j] for i in range(n)]) for j in range(m)]
#YES, if: A(n,m) >= the colMax or rowMax
for i in range(n):
for j in range(m):
if lines[i][j]<nMax[i] and lines[i][j]<mMax[j]:
return "NO"
return "YES"
#solved
IN = file(sys.argv[1])
for t in range(1, int(IN.readline())+1):
n, m = map(int, IN.readline().split(" "))
lines = [map(int, IN.readline().split(" ")) for x in range(n)]
print "Case #%d: %s" % (t, solve(n, m, lines))
If your solution is correct with the small data set: Check your solution if the range of the limits will work with your code. The large dataset has 100 test cases and 100×100 fields in maximum. This could be 200 max-value-calculation and 10^6 checks – this will fit in the 8 minuts time slot.
The large dataset need 0.2s for the result (with starting python).
other solutions
I found some other Google Code jam solutions with larger programs:
- C++ solution without precalculation (max 200*10^6 checks)
- all solutions for qualification round 2013 commented by vexorian.
- all solutions for qualification round 2013 in java on toughprogramming
The post Google Code Jam 2013 – the lawnmower appeared first on united-coders.com.
