July 17 Two coins problem

I am not able to find for which test cases my solution for two coins problem is failing from July Challenge 2017. Here is the link to my solution https://www.codechef.com/viewsolution/14585816
If anybody can find out the failing testcases, it’d be great. Thanks in advance.

I will suggest that you generate random trees with SPOJ tree generator and check output of your code vs output of an AC code.

Your code passed all of my “small input” test cases (n<=30).

However, when i used that SPOJ tree generator to make a tree of N=1000, your code printed 1 more than final answer (correct answer=717 , your answer=718).

I am still trying to find a small input test case where your code fails, but i think its hard to come up with one. It will be worthwhile to cross check your algo and algo used by AC codes, as it has more chances of helping in correction of wrong part.

I will edit my answer when i find a suitable test case. Meanwhile you can also try to find cases by using this -

http://spojtoolkit.com/TestCaseGenerator/

EDIT- Finally after getting some parts of your code, i was able to devise a test case against it-

Input
1
24
7 1
13 2
12 3
7 4
15 6
3 7
9 8
14 9
19 10
12 11
5 12
4 13
24 14
5 15
5 16
24 17
12 18
5 19
19 20
15 21
3 22
1 23
12 24
Your Output
16
Correct Output
18
1 Like

Thanks @vijju123

1 Like