USACO 2016 January Contest, Silver, Problem 2

Problems and Contests
#1


Subsequences Summing to Sevens

import sys
sys.stdin = open("div7.in")
sys.stdout = open("div7.out", "w")
n = int(input())
cow_ids = []
printed = False
for i in range(n):
  cow_ids.append(int(input()))
pref_sums = [0]
for cow_id in cow_ids: 
  pref_sums.append(pref_sums[-1] + cow_id)
for i in range(n, 0, -1):
  starts_max = n - i
  for j in range(0, starts_max + 1):
    sum_of_ids = pref_sums[j + i] - pref_sums[j]
    if sum_of_ids % 7 == 0: 
      print(i)
      printed = True
  if printed == True: 
    break
if not printed: 
  print(0)

The following code is O(n^2) and only passes half of the tc. Any suggestions on how to improve this?

#2

Use a map instead of looping back. Also, take the mod 7 while summing the prefix sums.

1 Like
#3

thank you, I will try that!