USACO Bronze 2020 December - Daisy Chains

Authors: Sathvik Chundru, Danh Ta Chi Thanh, Ryan Chou

Edit This Page

Official Analysis (Java)

Due to the low constraints of the problem, we can iterate through every possible photo.

Implementation

Time Complexity: O(N3)\mathcal{O}(N^3)

C++

#include <iostream>
#include <vector>


using namespace std;


int main() {
	int n;
	cin >> n;


	vector<int> flowers(n);

Java

import java.io.*;
import java.util.*;


public class DaisyChains {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(read.readLine());


		int[] flowers = new int[n];
		StringTokenizer flowerST = new StringTokenizer(read.readLine());

Python

n = int(input())
flowers = list(map(int, input().split()))


valid_photos = 0
for i in range(n):
	for j in range(i, n):
		# find the average petal # in the range i - j
		avg_petals = sum(flowers[i : j + 1]) / (j - i + 1)


		for index in range(i, j + 1):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum