"OverNite 2013" discussion

I have two questions regarding OverNite problems Catch and Recruit.

Catch: I have written the O(n log n) code for finding the longest non-decreasing subsequence:

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int t;
int n;
vector <int> seq;
 
int main()
{
scanf("%d", &t);
while (t--) {
seq.clear();
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int h; scanf("%d", &h);
int ind = upper_bound(seq.begin(), seq.end(), h) - seq.begin();
if (ind == seq.size()) seq.push_back(h);
else seq[ind] = h;
}
printf("%d\n", seq.size());
}
return 0;
} 

Why is it not correct? For example, if there would be longest increasing subsequence the same code with lower_bound would work perfectly, wouldn’t it? Later I wrote a dumb O(n * n) and it works just fine.

Recruit: What is the complexity of this problem? Is O(n * n * k) is supposed to get TLE?

2 Likes

@all i have also submitted in O(n*n) but it get TLE while @karolis_kusas get AC on same approach my submission link ishttp://www.codechef.com/viewsolution/1947177

2 Likes

Try to store the numbers in a different array and then go on with the computation.I got 6 WA because of that.I was taking each height and dynamically computing which was giving the WA just like u.Just a simple change got my answer accepted.This should not have happened.Guess this time I was correct after all.

2 Likes

This is because you havent considered cases with equal heights.Eg on your code 2 3 5 5 gives answer 3 whereas ie should be 4.

1 Like

thanks for clarifying me…

//