Please give advice on my solution

general
, ,
1

Hi Guys,

I am quite new here and have been trying to have a go at the Draughts problem and have been stuck on getting a correct solution and I can’t seem to figure out what is wrong with my solution:

http://www.codechef.com/viewsolution/3482076

The problem: http://www.codechef.com/problems/DRGHTS

I ran several test cases of various different trees and I can get it to work locally, I must be missing a case that I’m not seeing. I would greatly appreciate advice on where my solution is wrong.

What I am doing is first pruning the trees to remove all 0-label nodes that are leaves or root nodes, leaving a new tree with all 1-label nodes and 0-label nodes in between. Though I still get wrong answer.

Thank You.

2

Edit : Sorry, Mistake on my part. Output 7 6 is correct.

After trying more then 5-6 test cases , i finally found one:

8 6
1 1 1 1 0 1 1 0
1 2
2 3
2 4
2 5
6 7
7 8

Your code gives answer as 7 6 but i think the answer should be 7 4. Ideone link

3

Now I feel a little confused, I thought the answer should be 7 6, so maybe I’ve misunderstood the 2nd question.

Could anyone explain please what it is 7 4? After pruning I get left with these two trees:

1)–> 2)–>3) 2)—>4)

Second tree:

6)–>7)

All leaf 0-label have been removed.

1 Like
4

7 6 is correct

1 Like
5

@iqdot @junior94 Sorry for the mistake on my part. Misinterpreted the question. 7 6 is correct. I will try to see if there is some other case where it might be failing.

1 Like
6

Thanks, i’m really scratching my head here trying to figure out where I am going wrong.