USACO Bronze 2020 January - Photoshoot
Authors: Ananth Kashyap, Ryan Chou, Ben Dodge
We'll start by saying that for each in range , . For all other values of , we are given for , or for . We will then check if these values of produce a valid permutation.
Since , 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:
#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:
Time Complexity
Since the in
operator in Python takes 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:
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!