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?