Weak Test Cases of MAXNUM3 ( October Lunchtime 17 )

I was going through accepted solutions for problem “Maximum Number” in October Lunchtime 17, and saw that O ( n^2 ) solutions didn’t get TLE for large constraints. Maybe, its due to weak test cases. @admin I request you to please look into this matter. Listed below are some of the solutions which should give TLE :

https://www.codechef.com/viewsolution/15987816 ( substr function works in linear time )

https://www.codechef.com/viewsolution/15994124 ( erase function takes linear time )

5 Likes

But in my case it gives tle:https://www.codechef.com/viewsolution/15995643

Yeah, in my case too. But I was shocked to see the above mentioned solutions being passed :stuck_out_tongue:

Because in your case you are erasing every time. But the code provided in question only erases when it is valid (divisible by 6).

So the test cases must be so weak that there are only few options available for valid deletion of digits.

Exactly, slightly optimised bruteforce solutions got accepted, which should not be the case

OPTSET also has weak test cases. See this solution: 15993038. The solution only considers subsets of length 2, which should give WA. I’m amazed to see this got 40 points.

5 Likes

Subsets of size 2 is an insight mate. I used it to get 40 points…

PS: why are official editorials not out yet??

Not sure what you mean by an insight. It does not give correct answers for certain cases, therefore it is incorrect.
If solutions like this pass then the contest rewards people who code before they think, rather than people who realize that an approach won’t work and try to think of a better one.

About the editorials, I see they’re out now.

1 Like

Mate… I knew that solution was incorrect. But i had an alternative solution in my mind too, which works for 40 points. I just thought to submit the wrong one first. Seems like that was a mistake, seeing someone was keeping an eye on my submissions.

By the way, my correct solution for 40 points is https://www.codechef.com/viewsolution/16013985

Though we are on the subject of my submissions, can you help me understanding the following thing.

The first solution O(N) time complexity, completed 2nd sub-task in 0.13 seconds.

The other solution O(N^2) time complexity, completed 2nd sub-task in 0.15 seconds.

How come this less time difference when N can be up to 1000,

OR My input-output dominates time complexity in this solution??

And Another thing, Why all java submissions show 4284MB memory used.

I don’t see why it would be a mistake, maybe you misunderstand me. Of course it is no way your fault :slight_smile:
My point is simple, test cases should not be so weak that such a solution passes.

And yes, I also think that the I/O dominates the time taken in your solution, since 106 iterations isn’t really much. You can try submitting after removing the processing part to make sure. You’ll get WA but you’ll be able to see the time.

And about the memory, see this question here .

Well, your comment had the air of accusation. @meooow

Although i should have made insight word clear, an insight into weakness of test cases :stuck_out_tongue: (got to know after AC 40 points for wrong solution…)

@taran_1407 - @meooow did not acccuse you. The thing is, when you claim that Subsets of size 2 is an insight mate. then it sounds like you made some observation by which you can prove the correctness of what you did- which was false.

Hence, the reply was natural. Ultimately, its setter’s fault for weak test cases.