USACO Bronze 2020 January - Photoshoot

Authors: Ananth Kashyap, Ryan Chou, Ben Dodge


Official Analysis (C++)

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

Since N1000N \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: O(N2)\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: O(N3)\mathcal{O}(N^3)

Time Complexity

Since the in operator in Python takes O(N)\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: O(N2)\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!