USACO Social Distancing

USACO 2020 US Open Contest, Silver¶

Problem 1. Social Distancing¶

http://usaco.org/index.php?page=viewproblem2&cpid=1038

In [ ]:

# SAMPLE INPUT:
#
#5 3
#0 2
#4 7
#9 9

In [1]:

fin = open ('socdist.in', 'r')
fout = open ('socdist.out', 'w')
# N = COWS
# M = INTERVALS (Mutually Disjoint!  Non-Overlapping!)
N,M = map(int, fin.readline().split())
print("cows",N,"intervals",M)
ENDPOINT = 0
STARTPOINT = (10**18)
INTERVALS = []
# read in the intervals, and determine the smallest and largest endpoints
for i in range(M):
    a,b = map(int,fin.readline().split())
    if a<STARTPOINT:
        STARTPOINT=a
    if b>ENDPOINT:
        ENDPOINT=b
    INTERVALS.append((a,b))

INTERVALS.sort()
print(INTERVALS)
print("STARTPOINT",STARTPOINT,"ENDPOINT",ENDPOINT)

cows 5 intervals 3
[(0, 2), (4, 7), (9, 9)]
STARTPOINT 0 ENDPOINT 9

In [2]:

# function to check if distance d can be achieved
def goodD(d):
    print("Considering distance",d)
    print("    first cow placed at",STARTPOINT)
    cowQ = N-1 # first cow placed at STARTPOINT
    pointer = STARTPOINT+d
    for a,b in INTERVALS:
        if pointer < a:
            pointer = a
        if pointer > b:
            continue
        # if we get here, we can place at least one cow in the interval
        while cowQ > 0 and pointer <=b:
            print("    cow placed at",pointer)
            cowQ -= 1
            pointer += d
        if (cowQ==0):
            print("    SUCCESS: all cows placed with distance", d,"\n")
            return True
    print("    FAIL: ran out of intervals to place cows\n")
    return False

In [3]:

# binary search
# min distance is 1
# max distance possible is length between STARTPOINT and ENDPOINT
# divided by (N-1)
p1 = 1
p2 = int((ENDPOINT-STARTPOINT)/(N-1))+1
while(p1 < p2):

    mid = (p1+p2+1)//2
    if( goodD(mid) ):
        p1 = mid    
    else:
        p2 = mid-1
        
print("answer",p1)
fout.write(str(p1)+"\n")
fout.close()

Considering distance 2
    first cow placed at 0
    cow placed at 2
    cow placed at 4
    cow placed at 6
    cow placed at 9
    SUCCESS: all cows placed with distance 2 

Considering distance 3
    first cow placed at 0
    cow placed at 4
    cow placed at 7
    FAIL: ran out of intervals to place cows

answer 2