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

×

what to do in case if I think my solution is right(I am close to AC) but it shows WA?

There are many situations where I think the solution I wrote is correct and I am close to AC but due to some corner cases or some bugs I failed. Previously I used give hours and even days on that solution for debugging and after a day even it doesn't ACed I asked for help here. But now I think it's waste of time as number of problems I could solve due to this is less. So, I want to know from you mates what you people do in such a situation.

Apart from this even today I stuck on a problem which I think is correct (I'd already test my code for several random test cases but i got no error). If someone can then please look into this. (problem link)

asked 11 Oct, 18:02

pk301's gravatar image

3★pk301
5819
accept rate: 17%


When facing problems it's often a good idea to write a brute force solver and a test case generator (if it's feasible for the problem you're looking at). That way you can find cases where your algorithm fail, and from that hopefully deduce what you're doing wrong. On top of that you can always write some cases you know the answer to by hand, which is especially useful if you want to check corner cases you know of.

In this case you should be able to write a brute force solution that tries to pick all combinations of 1 segment, 2 segments, 3 segments and so on and greedily try to see if they can be put down in a way that fulfills the constraints. The complexity for such a solution is worse than exponential, but it's guaranteed to be correct! Now generate test cases and see if you can find cases where the correct brute force code and your solution differs.

This kind of approach is also useful if you're working on optimizing code. Continuously check that the optimization/changes you've done doesn't break your solution. For harder problems it's not uncommon for me to have either a test script running whenever I save my file, or just have a while loop running in s shell that throws random test cases at my code continuously. When you think you have found a solution that should perform well enough you can use your generator to stress test your solution as well!

link

answered 12 Oct, 05:09

algmyr's gravatar image

7★algmyr
1.0k12
accept rate: 32%

I'd recommend the FastOlympicCoding plugin for stress testing.

(12 Oct, 12:48) abdullah7686★
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:

×216
×125
×91
×55

question asked: 11 Oct, 18:02

question was seen: 145 times

last updated: 12 Oct, 12:48