USACO Bronze 2020 January - Photoshoot

Authors: Ananth Kashyap, Ryan Chou, Ben Dodge

We'll start by saying that for each $i$ in range $[1, N]$ , $a_1 = i$ . For all other values of $a_i$ , we are given $b_i = a_i + a_{i+1}$ for $[1, N)$ , or $a_i = b_{i -1} - a_{i - 1}$ for $(1, N]$ . We will then check if these values of $a_i$ produce a valid permutation.

Since $N \leq 1000$ , we can simulate this process for every possible starting cow and pick the first valid permutation (since that would be the lexicographical minimum).

Implementation

C++

Time Complexity: $\mathcal{O}(N^2)$

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	freopen("photo.in", "r", stdin);
	freopen("photo.out", "w", stdout);

Python

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

Time Complexity

Since the in operator in Python takes $\mathcal{O}(N)$ time, this solution is slower than the C++ version.

data = open("photo.in").read().strip().split("\n")
n = int(data[0])
b = list(map(int, data[1].split(" ")))

a = []
for i in range(1, n + 1):
	a = []
	a.append(i)
	works = True
	# Check if a valid permutation can be formed given the first number

Java

Time Complexity: $\mathcal{O}(N^2)$

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

public class Photoshoot {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("photo");

		int N = io.nextInt();
		int[] bessieList = new int[N];
		int[] correctList = new int[N];

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