AGGRCOW Python Solution

AGGRCOW¶

https://www.spoj.com/CLOUD_PL/problems/AGGRCOW.pdf

NOTE: the following code assumes that there is only one test case in the input file (no variable t)

In [1]:

#AGGRCOW

# read input data
# aggrcow.in contains the following test data:
"""
5 3
1
2
8
4
9
"""

fin = open("aggrcow.in", "r")
N,C = map(int,fin.readline().split())

print(N,C)

S = []
for i in range(N):
    S.append(int(fin.readline().strip()))

print(S)

5 3
[1, 2, 8, 4, 9]

In [2]:

# this function returns True if all cows fit into the
# available stalls with the candidate gap
def checkGap(cows,n,stalls,gap):
    
    # put a cow in stalls[0], the first stall
    installed = 1 
    p1 = 0
     
    for p2 in range(1,n):
        if stalls[p2] - stalls[p1] >= gap:
            installed += 1
            p1 = p2
            if installed >= cows:
                # All Cows in Stalls!
                return True
    return False

In [3]:

def binSearchGap(cows,n,stalls):
    lo = 0
    hi = ((stalls[n-1]-stalls[0])//cows)+1 
    # NOTE: the gap can be no larger than highest stall position minus 
    #       lowest stall position divided by the number of cows.
    
    while lo < hi:
        mid = lo + (hi-lo+1)//2

        gapWorks = checkGap(cows,n,stalls,mid)

        if gapWorks:
            lo = mid
        else:
            hi = mid - 1

    return(lo)

In [4]:

S.sort()  # sort before binary search
ans = binSearchGap(C,N,S)
print("Best Gap =",ans)

Best Gap = 3