http://www.usaco.org/index.php?page=viewproblem2&cpid=1156
I figured out how to create a program that runs in O(N) time to get 10/10 testcases, but I don’t understand why it works. From what I can tell, I think it is different than the official solution.
Python 3 code:
# USACO 2021 Dec. Contest, Bronze
# Problem 2. Air Cownditioning
def main():
from sys import stdin as fin, stdout as fout
n = int(fin.readline().strip())
start = list(map(int, fin.readline().strip().split()))
target = list(map(int, fin.readline().strip().split()))
l = target[0]-start[0]
count = 0
cur = []
a = target[1] - start[1]
difs = [l]
for i in range(n): # the list of differences between initial and target temperatures
if target[i]-start[i] != difs[-1]:
difs.append(target[i]-start[i])
for i in range(len(difs)):
dif = difs[i]
if i == 0: # handles the start of list
Next = difs[i+1]
if Next < dif and dif > 0:
count += dif
elif Next > dif and dif < 0:
count -= dif
elif i == len(difs)-1: # handles the end
last = difs[i-1]
if last < dif and dif > 0:
count += dif
elif last > dif and dif < 0:
count -= dif
else:
last = difs[i-1]
Next = difs[i+1]
if dif > 0: # positive
if dif > last and dif > Next: # if it is a peak
count += dif
elif dif < last and dif < Next: # if it is a valley
count -= dif
elif dif < 0: # negative
if dif < last and dif < Next: # if it is a peak
count -= dif
elif dif > last and dif > Next: # if it is a valley
count += dif
print(count)
main()
Program Explanation:
It first gets the difference between initial and target temperatures.
EDIT: I also compressed the list - a sequence of equal values is equal to one of those values
Then, for each sequence of positive values, the sum of all the peaks is added to the count, and each valley is subtracted from count.
For each sequence of negative values, it does the same - each negative peak’s absolute value is added to count, and each negative valley’s absolute value is subtracted from count.