Can anyone suggest anything here?
понеділок, 13 квітня 2020 р. 19:07:56 UTC+3 користувач Bohdan Dovhan
написав:
>
> 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 google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/869ceedf-ec38-4d7d-a225-4179eae647b6%40googlegroups.com.
