USACO Meetings, initial solution

Meetings, initial solution¶

USACO 2019 December Contest, Silver¶

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

In [1]:

# 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(T)        

169439089

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 7min 6s, sys: 32 ms, total: 7min 6s
Wall time: 7min 6s

In [ ]:

# The above code is O(N^2)
# Each rightgoing cow is moved through all other cows, and
# is compared to each leftgoing cow to see if it is within meeting distance.
# However, the code needs to be modified so that only one pass is made 
# through the cowdata.