You are not logged in. Please login at www.codechef.com to post your questions!

×

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 https://www.codechef.com/viewsolution/17032732 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.

asked 15 Jan '18, 18:20

kaushal101's gravatar image

5★kaushal101
28016
accept rate: 10%


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

link

answered 15 Jan '18, 18:37

killjee's gravatar image

5★killjee
4769
accept rate: 5%

edited 15 Jan '18, 18:41

1

This is an AC solution https://www.codechef.com/viewsolution/17000927 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. https://www.ideone.com/KBhk3v 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.

(15 Jan '18, 20:43) kaushal1015★
1

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

(15 Jan '18, 20:49) kaushal1015★
2

@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.

(15 Jan '18, 23:08) bazsi7006★
4

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

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

(16 Jan '18, 01:19) mgch6★
1

@mgch This is sad :(

(16 Jan '18, 18:41) kaushal1015★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×191
×161
×62

question asked: 15 Jan '18, 18:20

question was seen: 1,659 times

last updated: 16 Jan '18, 18:41