MANYCHEF Python solution TLE

general
, , ,
1

http://www.codechef.com/COOK30/problems/MANYCHEF I have verified that my algorithm is correct, and optimal O(N). It is also the same as one mentioned in editorial. Please help me figure out why it TLE’s on the judge. I am aware that Python is significantly slower than C/C++ but there are many C++ solutions which got AC with 0.0x time, and time limit for Python is also 4*Time Limit for C++. Pasting my Python code here.

t = int(raw_input())
chs = 'CHEF'
while t > 0:
	t -= 1
	s = raw_input()
	i = len(s) - 4
	r = ['?'] * len(s)
	while i >= 0:
		chef = True
		for j in xrange(4):
			if chs[j] != s[i+j] and s[i+j]!='?':
				chef = False
		if not chef:
			r[i+3] =   ('A' if s[i+3] == '?' else s[i+3])
			i -= 1
		else:
			r[i+3] = 'F'
			r[i+2] = 'E'
			r[i+1] = 'H'
			r[i]   = 'C'
			i -= 4
	for j in xrange(3+i, -1, -1):
		r[j]= ('A' if s[j] == '?' else s[j])
	print ''.join(r)

Thanks.

2

I just placed break below the if statement i.e
if chs[j] != s[i+j] and s[i+j]!=’?’:
chef = False
break
and got AC from your code i guess it was increasing the worst case complexity of the algorithm
my code submission http://www.codechef.com/viewsolution/1951480

1 Like