WEAK TEST CASES IN KILLKTH PROBLEM IN JANUARY LONG

The Killjee and Kth letter problem stated that |S|<=2.10^5 .
But there was no test case containing a string of 2.10^5 same characters . ( Not even > 2*10^4 characters).
Many or maybe most solutions thus had passed the test cases. Even my solution CodeChef: Practical coding for everyone passed with an AC in 0.1s. I had run my solution for a test case, where the string consisted of 'a’s only and its length was 10^5. My solution ran out of time for the same. Also I have run a few more submitted solutions, which too ran out of time or gave Runtime Errors.
I was doubtful of my solution passing the test cases, which surprisingly did when I submitted the final code. Some users might have wasted their time too in thinking over a better solution, and some might not even have submitted their code thinking that it won’t fetch them an AC.

7 Likes

There was a testcase with only 2 characters with probability of 2nd character to appear being 1/10000.

EDIT: The case you are talking about is very easy to get rid of just print the only letter in string. So,it wouldn’t had stopped your solution getting ac

1 Like

This is an AC solution CodeChef: Practical coding for everyone
When I run this soln on array length 2*10^5 with all a’s,and b’s are occuring at every 10000th index, it gives TLE.
KBhk3v - Online C++0x Compiler & Debugging Tool - Ideone.com
P.S. It rather also gives a TLE even when I run it on all a’s and even when length is 10^4 with second character occuring at every 1000th index. The same is with my solution. This could have let to confusion, hence many might not even have submitted their code. I had tried it on few more solutions, hence I had posted this.

1 Like

@killjee the soln also gives a tle on array length of 2*10^5 with alternating ‘a’ and ‘b’.

1 Like

@killjee Also you can do randomly appearing ‘a’ and ‘b’ which will be totally impossible to handle. Or 10^5 ‘a’ then 10^5 ‘b’, and things like that. I find it really unfair to not test for those test cases, as I haven’t coded my solution because I knew it would TL on these tests, so I tried to find a solution which passes these too. But as it turns out there were no test cases for these pretty straight forward corner cases, which seems pretty inconsiderate.

2 Likes

What will you say about building suffix array in O(|S|^2)? It’s amazing :slight_smile:

https://www.codechef.com/viewsolution/16786456

4 Likes

@mgch This is sad :frowning:

1 Like