2020 January Problem 2: Photoshoot

Problems and Contests
#1

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 << " ";
      }
    }
  }
}

Thanks, in advance, for your help.

#2

Comment out the lines with cerr.

#3

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?

#4

Input / output generally has a high constant factor.