During Round 1A I wasn't able to submit correct solution in time.
When round finished, I have submitted solution which shown in Practice
Correct result for 3A and TLE for 3B.
I read Analysis and wrote an "optimized" version but instead of receiving
both Correct results, I received TLE for 3A.
Can anyone help to understand why optimized version written by solution
analysis guideline doesn't work?
This is my code without optimisation
import sys, copy;
debug = False
def pem(a):
for i in range(len(a)):
print >> sys.stderr, ' '.join(map(str, a[i]))
def verify(r,c,i,j,s):
if debug:
print >> sys.stderr, ' i ', i, ' j ', j
k = i-1
comp = []
while k >= 0:
if s[k][j] > 0:
comp.append(s[k][j])
if debug:
print >> sys.stderr, ' k ', k, ' j ', j, ' s[kj]- ', s[k][j
], ' comp ', comp
break
k-=1
k = i+1
while k < r:
if s[k][j] > 0:
comp.append(s[k][j])
if debug:
print >> sys.stderr, ' k ', k, ' j ', j, ' s[kj]+ ', s[k][j
], ' comp ', comp
break
k+=1
l = j-1
while l >= 0:
if s[i][l] > 0:
comp.append(s[i][l])
if debug:
print >> sys.stderr, ' i ', i, ' l ', l, ' s[il]- ', s[i][l
], ' comp ', comp
break
l-=1
l = j+1
while l < c :
if s[i][l] > 0:
comp.append(s[i][l])
if debug:
print >> sys.stderr, ' i ', i, ' l ', l, ' s[il]+ ', s[i][l
], ' comp ', comp
break
l+=1
if debug:
print >> sys.stderr, ' #competitors ', len(comp)
if len(comp) > 0:
print >> sys.stderr, ' average ', float(sum(comp))/len(comp)
return False if len(comp) == 0 else float(sum(comp))/len(comp) > s[i][j]
def solve(r,c,s):
eliminationHappens = True
su = 0
while eliminationHappens:
su += sum([sum(s[i]) for i in range(r)])
eliminationHappens = False
cop = copy.deepcopy(s)
for i in range(r):
for j in range(c):
if s[i][j] > 0:
if verify(r,c,i,j,cop):
s[i][j] = 0
eliminationHappens = True
if debug:
print >> sys.stderr, 's '
pem(s)
return str(su);
t = int(raw_input())
for i in range(1, t + 1):
r,c = map(int,raw_input().split())
s = [map(int,raw_input().split()) for j in range(r)]
print "Case #" + str(i) + ": " + solve(r,c,s)
and this is the optimized version
import sys, copy;
debug = False
def pem(a):
for i in range(len(a)):
print >> sys.stderr, ' '.join(map(str, a[i]))
def buildLinkedList(r,c,s):
return [[buildLLI(r,c,i,j,s) for j in range(c)] for i in range(r)]
def buildLLI(r,c,i,j,s):
upper = None
lower = None
left = None
right = None
k = i-1
while k >= 0:
if s[k][j] > 0:
upper = {'x':k,'y':j,'s':s[k][j]}
break
k-=1
k = i+1
while k < r:
if s[k][j] > 0:
lower = {'x':k,'y':j,'s':s[k][j]}
break
k+=1
l = j-1
while l >= 0:
if s[i][l] > 0:
left = {'x':i,'y':l,'s':s[i][l]}
break
l-=1
l = j+1
while l < c :
if s[i][l] > 0:
right = {'x':i,'y':l,'s':s[i][l]}
break
l+=1
return {'x':i,'y':j,'s':s[i][j],'u':upper,'lo':lower,'le':left,'r':right
}
def ver(item):
dirs = ['u','lo','le','r']
if debug:
print >> sys.stderr, ' item ', item, ' dirs ', [ d for d in dirs if
item[d]!=None]
comps = [item[d]['s'] for d in dirs if item[d]!=None]
return False if len(comps) == 0 else float(sum(comps))/len(comps) > int(
item['s'])
dirs = ['u','lo','le','r']
def opp(d):
return 'lo' if d == 'u' else 'u' if d == 'lo' else 'le' if d == 'r' else
'r'
def solve(r,c,s):
ll = buildLinkedList(r,c,s)
if debug:
print >> sys.stderr, ' ll ', ll
su = sum([sum(s[i]) for i in range(r)])
lost = [ll[i][j] for j in range(c) if ver(ll[i][j]) for i in range(r)]
while len(lost) > 0:
check = []
for l in lost:
if debug:
print >> sys.stderr, ' l ', l
print >> sys.stderr, ' l[x] ', l['x'], ' l[y] ', l['y']
s[l['x']][l['y']] = 0
ll[l['x']][l['y']] == None
for d in dirs:
if l[d]!=None:
actual = ll[l[d]['x']][l[d]['y']]
actual[opp(d)] = l[opp(d)]
check.append(actual)
lost = [ch for ch in check if ver(ch)]
su += sum([sum(s[i]) for i in range(r)])
return str(su);
t = int(raw_input())
for i in range(1, t + 1):
r,c = map(int,raw_input().split())
s = [map(int,raw_input().split()) for j in range(r)]
print "Case #" + str(i) + ": " + solve(r,c,s)
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/c0cb88c4-abc4-4cae-ac9a-389116025188%40googlegroups.com.
