USACO 2020 January Contest, Bronze Problem 2. Photoshoot

USACO 2020 January Contest, Bronze Problem 2. Photoshoot

Farmer John is lining up his NN cows (2N1032≤N≤103), numbered 1N1…N, for a photoshoot. FJ initially planned for the ii-th cow from the left to be the cow numbered ai,ai, and wrote down the permutation a1,a2,,aNa1,a2,…,aN on a sheet of paper. Unfortunately, that paper was recently stolen by Farmer Nhoj!

Luckily, it might still be possible for FJ to recover the permutation that he originally wrote down. Before the sheet was stolen, Bessie recorded the sequence b1,b2,,bN1b1,b2,…,bN−1 that satisfies bi=ai+ai+1bi=ai+ai+1 for each 1i<N.1≤i<N.

Based on Bessie's information, help FJ restore the "lexicographically minimum" permutation aa that could have produced bb. A permutation xx is lexicographically smaller than a permutation yy if for some jjxi=yixi=yi for all i<ji<j and xj<yjxj<yj (in other words, the two permutations are identical up to a certain point, at which xx is smaller than yy). It is guaranteed that at least one such aa exists.




  • Test cases 2-4 satisfy N8.N≤8.
  • Test cases 5-10 satisfy no additional constraints.




The first line of input contains a single integer N.N.The second line contains N1N−1 space-separated integers b1,b2,,bN1.b1,b2,…,bN−1.


OUTPUT FORMAT (file photo.out):

A single line with NN space-separated integers a1,a2,,aN.a1,a2,…,aN.



4 6 7 6


3 1 5 2 4

aa produces bb because 3+1=43+1=41+5=61+5=65+2=75+2=7, and 2+4=6.2+4=6.


Problem credits: Benjamin Qi and Chris Zhang

USACO 2020 January Contest, Bronze Problem 2. Photoshoot 题解(翰林国际教育提供,仅供参考)



(Analysis by Benjamin Qi)

For each ii from 11 to N,N, try setting a1=i.a1=i. Then we can determine the rest of the elements of aa by setting ai=bi1ai1ai=bi−1−ai−1 for each 2iN.2≤i≤N. If this indeed produces a valid permutation (all elements of aa are in [1,N][1,N] and none repeat), then return the result. This runs in O(N2)O(N2) time.

Dhruv Rohatgi's code:


#include <iostream>
#include <algorithm>
using namespace std;
int N;
int b[100000], d[100000], ans[100000];
bool used[100000];
int main() {
	cin >> N;
	for(int i=0;i<N-1;i++)
		cin >> b[i];
	for(int i=2;i<N;i++)
		d[i] = b[i-1]-b[i-2];
	for(int a=1;a<=N;a++)
		ans[0] = a, ans[1] = b[0] - a;
		for(int i=2;i<N;i++)
			ans[i] = ans[i-2] + d[i];
		for(int i=1;i<=N;i++)
			used[i] = 0;
		bool bad = 0;
		for(int i=0;i<N;i++)
			if(used[ans[i]] || ans[i] <= 0 || ans[i] > N)
				bad = 1;
			used[ans[i]] = 1;
			for(int i=0;i<N;i++)
				cout << ans[i];
				if(i<N-1) cout << ' ';
			cout << '\n';
			return 0;

Bonus: Solve the problem in O(N).