#!/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:
- All elements e[i,k], with k != j must be e[i,k] <= e [i, j]
- 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 else 0 elif arminmote > motes: steps = dp(arminmote + motes, 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.