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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s