# 2020 January Problem 2: Photoshoot

I keep timing out for cases 5-10. My algorithm doesn’t try all N! permutations; instead, it constructs possibilities for a based on the starting value. Then, I check whether a is indeed a permutation in linear time, for a total TC of O(N^2).

My code is below:

``````int n, a[1005];

bool valid(){
///check if a is a valid permutation of 1..n
int cnt[n];
//initialize cnt since it's declared within func
trav(val,cnt) val=0;
FOR(i,0,n){
if(a[i]<1 || a[i]>n) return 0;
//cow values are 1-indexed
cnt[a[i]-1]++;
}
trav(val,cnt) if(val!=1) return 0;
return 1;
}

int main(){
setIO("photo");
cin >> n;
int b[n-1]; trav(in,b) cin >> in;
//cows are labled 1..n, indexes 0..n-1
FOR(start,1,n+1){
a[0]=start;
//fill out remaining
FOR(i,1,n){
a[i]=b[i-1]-a[i-1];
}
FOR(i,0,n) cerr << a[i] << " ";
cerr << endl;
if(valid()){
FOR(i,0,n){
cout << a[i];
if(i!=n-1) cout << " ";
}
}
}
}
``````

Comment out the lines with `cerr`.
Thank you. I removed the `cerr` lines, and the submission succeeded.
I wonder why this would make the program time out, though. Doesn’t `std:err` not interfere with the regular output stream?
Within the outer loop of my code, I already have other O(N) algorithms running (finding `a[i]` and checking if it’s valid). So when I write an additional line to dump the contents of the array, it only increases the time complexity by a minor constant factor. Why would this make the program time out?