Hoof, Paper, Scissors

USACO 2017 January Contest, Silver - Problem 2

Algorithm

We want to find x such that the number of similar gestures from 1 -> x and x -> N is maximal. The naive solution would be:

for gesture i in [H,P,S]:
    for gesture j in [H,P,S]:
        for x in range(0,N):
            count_i = number of is from 1 to x
            count_j = number of js from x to N
            record = max(record, count_i+count_j)

However, this runs in O(N^2) time, since the counting operation runs in linear time. We can improve this algorithm so it runs in linear time:

for gesture i in [H,P,S]:
    for gesture j in [H,P,S]:
        count_i = 0
        count_j = count number of js from 0 to N
        for x in range(0,N):
            if gestures[x] is i:
                count_i += 1
            if gestures[x] is j:
                count_j -= 1
            record = max(record, count_i+count_j)

Python

def run(gestures):
    record = 0
    for i in "HPS":
        for j in "HPS":
            count_i = 0
            count_j = gestures.count(j)
            for x in range(0,len(gestures)):
                if gestures[x] == i: count_i += 1
                if gestures[x] == j: count_j -= 1
                record = max(record, count_i+count_j)
    return record

def main():
    gestures = "".join(open("hps.in","r").read().split("\n")[1:])
    res = run(gestures)
    open("hps.out","w").write(str(res)+"\n")

if __name__ == '__main__': main()