Hi,
I tried to solve this question: Problem using a DFS procedure with an extra variable recording the number of consecutive cats we have seen till now.
This code returned Wrong answer on test case 9. I cannot find test cases for which this solution returns wrong answer. I also tried converting variables to long long in case int was overflowing, but no luck. After some thought I realized there could be a scenario in the problem where visiting a node "cleanses" us of all cats seen. Then we could go back through the parent to the other leaves, with a reduced m.
I implemented it this way: Code
I basically record the best cats_seen that has been obtained till now and if we can beat that we visit the node again. However this too returns WA on test case 9.
Please help me debug this.
Also, general question, till what constraint (of n) is recursive DFS feasible? Meaning it won't cause a stack overflow? I'm not sure where to find help debugging my solutions, so I'm posting it on my blog. Please do give me a link if there's a dedicated place for this, because it would be really nice to have one.
In your first code, the basic idea is correct but the graph construction is incorrect. It won't work on test cases like
4 21 1 1 11 21 43 4because you're changing the adjacency list of only one vertex.
Here's an AC version of your code with the graph construction fixed and minor modifications to DFS: http://codeforces.net/contest/580/submission/22137984