Army

[raga]

Hi all,

I've bee trying to solve the problem ARMY: spoj.pl/problems/ARMY/
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.

[numerix]

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.

[gorlum0_sof]

Algorithm. Re-read problem, you do much excessive work.

[raga]

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

#!/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?