I took part in LTime08. Due to school exams, I could only be in the contest for an hour. Upon returning after the end of the contest, I saw the question CHRL3. Now, I don’t understand the purpose of giving such a question. Is this question given to test “Googling” skills of programmers. It is a known fact that the length of the longest increasing sub-sequence in a sequence is the answer to the problem. The fact is available all over the internet. Also, note the solutions submitted. For example, this one:
This solution uses the patience sorting approach which is clearly described on geeksforgeeks and other similar sites, which also provide the code. Other approaches like the dynamic programming one are also available online.
I feel that problems should require certain level of thinking, and not be based on direct facts which are already available all over the internet.
When I suggested this problem, I had no idea for solve this problem(if (n > 1000)). My solution based on modification of Kuhn algorithm and works O(N^2). One more question, when you are writing online contests you use google? When you will seat on IOI you will not have internet connection. As for me, this problem is beautiful for school contests.
It’s a good problem, but not suitable for any contest where you expect the contestants to be seriously good coders. The reason is simple: it’s well known. I literally remembered the solution, I didn’t need to think about the problem at all. (Of course, my solution was the simple BIT one.)
The problem of finding the longest increasing sub-sequence can be solved using binary indexed tree, segment tree, dynamic programming and patience sorting. My point is that the last two approaches are available all over the internet, and once a contestant knows the algo (which can also be found out with minimal googling), the problem is simply a test of copy-paste skills.
This is exactly my point. People can actually copy paste their codes from sites or from previous problems where they required the concept of LIS. So, that really defeats the purpose. Moreover, the fact that LIS is to be computed is available on net. So, this really isnt a good question for a contest.