Hint to get 100 points.

contest

#1

I am not discussing the algorithm for any problem and this is a general hint for all problems you are getting a partial score and striving to get 100 points, except Chanllenge problem.

I want to tell everyone a secret which helped me to score 100 points.

I code around 4-5 programs for a problem and i noticed that one of my code was giving CA for last set in second subtask and some other sets from first subtask, and other was giving WA in only last set in second subtask.

Then i just wrote a code that generated random test cases about 100 in each output and tested my both code on same test cases and compared the output (Use ideone for testing be keeping visibility as private), Now thanks for the luck there i got a test case for which m code failed.

I made some corrections and got 100 points.

So i think if i was able to do that then you guys can also do, just write a code to generate random test cases and test your code on these cases and believe me if you dedicate your time wisely you will definitely find the bug…!!

Update:


If you don’t know about random functions then check these links or just google :P:

For C : http://stackoverflow.com/questions/822323/how-to-generate-a-random-number-in-c

For Java : http://stackoverflow.com/questions/363681/generating-random-integers-in-a-range-with-java

For Python : (Check Standard Modules tab in this link) http://www.codeskulptor.org/docs.html#tabs-Python

EDIT: While searching more about test case generation i found this link, This has really good explanation: http://www.codechef.com/wiki/test-generation-plan.

Best of Luck… :slight_smile:


#2

yeah it sure will help in finding the bug!
But what if a person’s code is not efficient enough to pass full constraints for those 100 pts :stuck_out_tongue:


#3

I usually follow the method you mentioned.I write two solutions : one is real solution and other one is bruteforce(to check the correctness of the real solution), but in case of SANSKAR, the judge says my bruteforce solution is Wrong :frowning: :frowning: :frowning: :frowning: Now the only option is to wait till the end of contest and check my solution with the accepted one … !!


#4

There are situations where this doesn’t work.

For example, your random cases may not be random enough. Maybe you assumed something silly that’s actually where your code is failing. Maybe a good random generator is slow and you wrote a bad one. Etc.

Also, if your code is actually failing on some special case, it’s very unlikely that you’d catch it with random cases. A good example of this is geometrical problems - those have a lot of special cases.

Then, there are critical errors like misunderstanding the problem / some case of it and writing a wrong bruteforce or random cases’ generator. Or maybe, as has been mentioned already, you’re getting TLE.

And, of course, if you don’t have enough time to do all of this, it might be a better idea to just read your code and try to figure out a mistake.

This is a very good method, but you need to remember that it’s bug-prone like any other :smiley:


#5

Change the Algorithm…


#6

indeed :wink:


#7

But @gvaibhav21 really i find this method very helpful because many times random test case generators output such cases which we are unable to think and helps to get ACed…! :slight_smile:


#8

Bro problem sanskar has a lot of tricky test cases.

Re-Read the constraints, there is a case where my code was failing because i didn’t read the constraints carefully and as far i believe problem Sanskar is judged on corner test cases i think except set 2 in subtask 1 each set has corner cases that is making the problem harder!!

Because there is a lot of complaint on forum for ACed codes failing on a particular test case.


#9

SANSKAR is a troll problem. There’s a trick that has nothing to do with algorithms, but it’s possible to figure it out on your own.


#10

thats true…