Lifeguards Python

USACO 2018 January Contest, Silver¶

Problem 1: Lifeguards¶

The following python code is based on the official solution:

http://www.usaco.org/current/data/sol_lifeguards_silver_jan18.html

---

In [1]:

class State:
    def __init__(self,a,b):
        self.time = a
        self.index = b

    def __repr__(self):
        return("State({},{})".format(self.time,self.index))

In [2]:

n=3
stateList = [0]*2*n

# Hardcoded Input Data
# Normally this would be read from a file in a loop
i=0
start = 5
end = 9
stateList[2*i] =  State(start, i)
stateList[2*i+1] = State(end, i)
i=1
start = 1
end = 4;
stateList[2*i] = State(start, i);
stateList[2*i+1] = State(end, i);
i=2;
start = 3;
end = 7;
stateList[2*i] = State(start, i);
stateList[2*i+1] = State(end, i);

stateList.sort(key = lambda state:state.time)
print(stateList)

[State(1,1), State(3,2), State(4,1), State(5,0), State(7,2), State(9,0)]

In [3]:

actualCover = 0;
alone = [0]*n
last = 0;
myset = set()

for out in stateList:
    if (len(myset) == 1):
        for loneitem in myset:
            alone[loneitem] += out.time - last
    
    if (len(myset) > 0): 
        actualCover += out.time - last

    if (out.index in myset):
        myset.remove(out.index)
    else:
        myset.add(out.index)

    last = out.time
    
ret = 0;
for outint in alone:
    ret = max(ret, actualCover - outint)

print(ret)

7