My python is a bit rusty, so bear with me. I feel as if there is a problem
with this line:
{s[l['x']][l['y']] = 0}
in the solve() method. Consider the following case on a 2x3 floor where
each digit represents the competitor's skill level:
3 2 3
5 1 2
after Round 1, the floor should look like this:
- - 3
5 - 2
However, your algorithm sets to the board to this:
- 2 3
5 - -
Here's why. When you set the skill level of a competitor to 0 and remove
them from the linked list, they are no longer being considered when they
should be. For example, the competitor in the top left gets eliminated, but
their skill level should still be taken into account when evaluating the
remaining competitors in that round. More specifically, for the competitor
in the top middle, the average (if we look at the full board) skill level
of surrounding competitors is 2.33 which is, of course, greater than 2, so
this person gets eliminated. But, if we set our first competitor's skill to
0 before we evaluate the second, then the average drops from 2.33 to 2, and
top-middle competitor lives to fight another day. In a nutshell, this may
cause competitors *to last longer than they should be*, which could be
resulting in your TLE. Hope this helps.
Best,
Matt
On Monday, April 13, 2020 at 12:07:56 PM UTC-4, Bohdan Dovhan wrote:
>
> 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/b6ef0837-a0cc-416f-8349-0b2bb193ef7f%40googlegroups.com.
