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;
    if(a[i]<1 || a[i]>n) return 0;
    //cow values are 1-indexed
  trav(val,cnt) if(val!=1) return 0;
  return 1;

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

Thanks, in advance, for your help.

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?

Input / output generally has a high constant factor.