1 / 4
Apr 2010

Hi all,

I've bee trying to solve the problem ARMY: spoj.pl/problems/ARMY/2
but I can't beat the time limit. Here is my code.

#!/usr/bin/python
import sys
import psyco
def main():
	file = sys.stdin
	ip = file.read()
	ip = ip.split()
	t = int(ip[0])
	ip = ip[1:]
	while t:
		t -= 1
		ng = int(ip[0])
		nm = int(ip[1])
		ng_list = []
		nm_list = []
		for i in ip[2:2 + ng]:
			ng_list.append(int(i))
		for i in ip[2 + ng:2 + ng + nm]:
			nm_list.append(int(i))
		ip = ip[2 + ng + nm:]
		ng_list.sort()
		nm_list.sort()
		i = 0
		j = 0
		while i < ng and j < nm:
			if ng_list[i] < nm_list[j]:
				i += 1
			else:
				j += 1
		if i < ng:
			print 'Godzilla'
		else:
			print 'MechaGodzilla'
if __name__ == '__main__':
	main()

I've solved the problem using the same algorithm using C++ before. I'm not sure if I have to use a better algorithm or my python implementation is slow. Any help/hint is appreciated.

  • created

    Apr '10
  • last reply

    Apr '10
  • 3

    replies

  • 304

    views

  • 3

    users

  • 1

    link

You don't need psyco. You don't need any sorting.
And you don't need more than one line of python code to solve that problem.
You should learn some more about python. smile

Sorry about that. I just took the C solution I wrote when I was new to SPOJ. Here is a better solution, which still TLEs. I am new to python, please bear with my naive implementation and style of coding blush

#!/usr/bin/python
import sys
import psyco
def main():
	file = sys.stdin
	ip = file.read()
	ip = ip.split()
	t = int(ip[0])
	ip = ip[1:]
	while t:
		t -= 1
		ng = int(ip[0])
		nm = int(ip[1])
		ng_max = 0
		nm_max = 0
		for i in ip[2:2 + ng]:
			if int(i) > ng_max:
				ng_max = int(i)
		for i in ip[2 + ng:2 + ng + nm]:
			if int(i) > nm_max:
				nm_max = int(i)
		ip = ip[2 + ng + nm:]
		if ng_max >= nm_max:
			print 'Godzilla'
		else:
			print 'MechaGodzilla'
if __name__ == '__main__':
	main()

The solution is correct, I verified by writing a C program. Is there an even faster algorithm which I should use or is it my implementation that needs improvement?