D0OMoP's blog

Hidden Edge cases
By D0OMoP, history, 2 weeks ago, In English

Hello everyone, I was giving contest today and I was solving a question, I almost got the logic(atleast I thought that), but I got wrong answer on testcase 2. After contest I went to see what is wrong but I got to know that I can't know the edge case, because it's 120th token and I can't know the 120th input. This has happened to me a lot of time that, my logic is slightly wrong or I made a small mistake in Implementing the code but I can not know what is wrong. Can anyone give me solution for this?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can see the test case if it's small. Just output the input of that testcase.

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Thanks

→ Reply
»
2 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

Here's how you can normally resolve situations like this during the contest.

  • Write a very naive and simple solution to the problem (maybe exponential complexity). One that tries to use no "special" logic, just the barest possible brute force. In this problem, it would be recursively trying to apply the operation on every position.
  • Write a program to generate thousands of small test cases.
  • Using those two, find a test case where your program gives the wrong answer.

By the way, I would be careful about calling counterexamples to your solution "edge cases". I mean, sometimes it's true and your solution is just wrong on some very specific cases like $$$n = 1$$$ or whatever. But it might be that your solution is just wrong.

For example in this problem, all your program does is finds the pair of adjacent elements with the largest difference and applies the operation to that. But for example, this means you do

$$$ [1, 100, 10000] \to [1, 100, 100] \to [1, 1, 100] $$$

while it would be better to do

$$$ [1, 100, 10000] \to [1, 1, 10000] \to [1, 1, 1]. $$$

I don't think it's fair to call this an edge case. Rather, it's an example demonstrating something that your program doesn't take into account: it might sometimes be better to make a not-so-good operation because it opens up very good operations for later.

→ Reply
»
2 weeks ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Your code might be failing on this test case.

3 2

3 2 1

your code will output 4(I wrote a similar solution and got the same verdict) correct output is 3

→ Reply