USACO Meetings, various better solutions

Meetings, various better solutions¶

USACO 2019 December Contest, Silver¶

http://usaco.org/index.php?page=dec19results

In [1]:

import heapq
import collections

# The 13th dataset is the big one
fin = open ('13.in', 'r')
fout = open ('meetings.out', 'w')
inlist = [int(x) for x in fin.readline().split()]
N = inlist[0]
L = inlist[1]

print("cows, barn position")
print(N,L)

cows, barn position
49931 339897388

In [2]:

rightgoing = 0
leftgoing = 0
cowdata = []
totalweight = 0
left_arrival_times = []
right_arrival_times = []

for i in range(N):
    inlist = [int(x) for x in fin.readline().split()]
    totalweight+=inlist[0]
    if inlist[2] == -1:
        leftgoing+=1
        left_arrival_times.append(inlist[1])
    else:
        rightgoing+=1
        right_arrival_times.append(L-inlist[1])
    
    cowdatum = (inlist[1],inlist[0],inlist[2])
    cowdata.append(cowdatum)

In [3]:

cowdata.sort()
#print(cowdata)
print("rightgoing, leftgoing, totalweight")
print(leftgoing,rightgoing,totalweight)
left_arrival_times.sort()
right_arrival_times.sort()
#print(left_arrival_times)
#print(right_arrival_times)

rightgoing, leftgoing, totalweight
25156 24775 24948664

In [4]:

timedata = []
for i in range(len(left_arrival_times)):
    t=left_arrival_times[i]
    x,w,d =cowdata[i]
    timedatum=(t,w)
    timedata.append(timedatum)

for i in range(len(right_arrival_times)):
    t = right_arrival_times[i]
    x,w,d = cowdata[len(cowdata)-1-i]
    timedatum=(t,w)
    timedata.append(timedatum)
    
timedata.sort()
#print(timedata)

In [5]:

barnweight=0
T=-1
for t,w in timedata:
    barnweight+=w
    #print(t,w,barnweight)
    if barnweight>=(totalweight/2.0):
        T=t
        break
        
print("time that half the weight has reached a barn")
print("T =",T)

time that half the weight has reached a barn
T = 169439089

O(N^2) inital solution¶

In [6]:

%%time
# WARNING: this is very slow
# ANALYSIS MODE: datasets 1-7 pass, datasets 8-13 fail on time
meetings = 0
# cowdata: (X,W,D)
for i in range(len(cowdata)):
    if(cowdata[i][2]==1):
        for j in range(i+1,len(cowdata)):
            if (cowdata[j][0]>cowdata[i][0]+2*T):
                break
            else:
                if cowdata[j][2]==-1:
                    meetings+=1
                    
print("meetings =",meetings)

meetings = 309119583
CPU times: user 6min 50s, sys: 12.4 ms, total: 6min 50s
Wall time: 6min 50s

First attempt at an improved solution¶

Use a Deque to carry all the rightgoing cows forward together, pop off cows as they move past their time T distance¶

In [7]:

%%time
meetings = 0
rgoingdeque = []
rgoingdeque = collections.deque(rgoingdeque)
# cowdata: (X,W,D)
for i in range(len(cowdata)):
    if(cowdata[i][2]==-1):
        while (len(rgoingdeque)>0 and rgoingdeque[0]+2*T<cowdata[i][0]):
            rgoingdeque.popleft()
        meetings+=len(rgoingdeque)
    else:
        rgoingdeque.append(cowdata[i][0])
                    
print("meetings =",meetings)

meetings = 309119583
CPU times: user 56.6 ms, sys: 0 ns, total: 56.6 ms
Wall time: 55.3 ms

Second attempt at an improved solution¶

Use a python list to carry all the rightgoing cows forward together, pop off cows as they move past their time T distance¶

In [8]:

%%time
meetings = 0
rgoinglist = []
# cowdata: (X,W,D)
for i in range(len(cowdata)):
    if(cowdata[i][2]==-1):
        while (len(rgoinglist)>0 and rgoinglist[0]+2*T<cowdata[i][0]):
            rgoinglist.pop(0)
        meetings+=len(rgoinglist)
    else:
        rgoinglist.append(cowdata[i][0])
                    
print("meetings =",meetings)

meetings = 309119583
CPU times: user 57.7 ms, sys: 4 ms, total: 61.7 ms
Wall time: 61.1 ms

Third attempt¶

Use a heapq to carry all the rightgoing cows forward together, pop off cows as they move past their time T distance¶

In [9]:

%%time
meetings = 0
rgoingheap = []
heapq.heapify(rgoingheap)
# cowdata: (X,W,D)
for i in range(len(cowdata)):
    if(cowdata[i][2]==-1):
        while (len(rgoingheap)>0 and rgoingheap[0]+2*T<cowdata[i][0]):
            heapq.heappop(rgoingheap)
        meetings+=len(rgoingheap)
    else:
        heapq.heappush(rgoingheap,cowdata[i][0])
                    
print("meetings =",meetings)

meetings = 309119583
CPU times: user 72.5 ms, sys: 0 ns, total: 72.5 ms
Wall time: 70.8 ms

The moral of the story is this: ANY improvement to this part of the code that changes it from O(N^2) to O(N) will work