# Always learning !

As i wrote before, i did participate on Google Code Jam Qualification Round. I just did 3 problems and got 50 points.I’ll talk about one of the problems: Lawnmower.

```#!/usr/bin/python
# -*- coding: utf-8 -*-

from sys import stdin

if __name__ == "__main__":
ncases = int(stdin.readline())

for ncase in xrange(ncases):
n, m = map(int, stdin.readline().split(' '))

lawn = [[] for j in xrange(n)]

for row in xrange(n):
lawn[row] = map(int, stdin.readline().split(' '))

allle = True

for row in xrange(n):
for column in xrange(m):

hle = True
vle = True
for frow in xrange(n):
if lawn[frow][column] > lawn[row][column]:
vle = False
for fcolumn in xrange(m):
if lawn[row][fcolumn] > lawn[row][column]:
hle = False

allle = hle or vle

if not allle:
break
if not allle:
break

result = 'YES' if allle else 'NO'
print 'Case #' + str(ncase + 1) + ': ' + result
```

I got stuck for sometime, but in the end i found and coded quite elegant solution in python. We have a matrix and every element e[i,j] on it had to satisfy the following constraints:

1. All elements e[i,k], with k != j must be e[i,k] <= e [i, j]
2. All elements e[k,j], with k !=i must be e[k,j] <= e [i, j]

If both constraints are satisfied, then the answer is yes, else we can’t cut the lawn.

The interesting part is the next round i’ll like to talk about. I didn’t participate on Round A, but i did try round B. As i told before, i never practice for this, and after trying quite a bit the first problem i got frustrated and decided to stop. In like 30 minutes, there were already a lot of people with 2 or more problems completed.

I want to talk about the first problem: Osmos. The problem was easy to understand, my mistake was getting so stuck in thinking “efficiently” and trying to find the best solution. In the end i made a bad assumption and never passed the runs. I stopped and reminded to view the solution later.

I viewed the solution found my error and learned a lot from the code i saw.

I’ll show my fixed code:

```#!/usr/bin/python
# -*- coding: utf-8 -*-

from sys import stdin

def dp(arminmote, motes):
if len(motes) == 1:
return 1 if arminmote <= motes[0] else 0
elif arminmote > motes[0]:
steps = dp(arminmote + motes[0], motes[1:])
else:
steps = 1 + min(dp(2*arminmote - 1, motes), dp(arminmote, motes[1:]))
return steps

if __name__ == "__main__":
ncases = int(stdin.readline())

for ncase in xrange(ncases):
case = stdin.readline()
arminmote, leftmotes = map(int, case.split(' '))

case = stdin.readline()
motes = map(int, case.split(' '))
motes.sort()

if arminmote > 1:
steps = dp(arminmote, motes)
else:
steps = len(motes)

print 'Case #' + str(ncase + 1) + ': ' + str(steps)
```

The Round B winner code:

```# dolphinigle
# GCJ 2013 1B
# 4 May 2013

ntest = int(raw_input())
for itc in range(ntest):
print 'Case #%d:' % (itc+1),
my_mote, n = map(int, raw_input().split())
motes = sorted(map(int, raw_input().split()))
if my_mote == 1:
print n
continue
best_answer = n
my_answer = 0
for index, i in enumerate(motes):
if i < my_mote:
my_mote += i
continue
# maybe stop here?
best_answer = min([best_answer, my_answer + n - index])
while my_mote <= i:
my_mote += my_mote - 1
my_answer += 1
my_mote += i
best_answer = min([best_answer, my_answer])
print best_answer
```

Quite the difference? Yes. First i didn’t see any polynomial way of solving, i just though that it was needed in some cases to choose between 2 possibilities and didn’t use any memorization or dynamic programming technique. I did fail quite hard, but it is important to learn from mistakes.

I saw why the first place on round B is this guys. In just 7 minutes he came with this brilliant solution. With one cycle and using two variables: one to count the motes needed to eat and the other the best solution so far, starting with removing all the motes. I was amazed and learned a lot seeing this code. I had never use raw_input and enumerate. They are so useful.

Learning and sharing is so important, specially all regarding computers. One of the reason i made this post is that. Hope it is useful to someone.

Advertisement