I think there is a misunderstanding here. The puzzle is solvable without hard-coding conditions.
It’s possible that some existing solutions don’t pass valid conditions, as highlighted by Jazz a long time ago.
That doesn’t make this puzzle a bad puzzle.
FYI, Mackeyth’s Java solution doesn’t pass your graph:
replay
If you cannot validate the puzzle, I suggest you look at this useful comment
If, say, ~90% (or 100%) of the accepted solutions just doesn’t solve the problem, but only exploit the test system, then why wouldn’t this be a bad puzzle? It clearly lies to these people about this type of problems, and lies to the employers about of the ability of CG users (whatever is CG’s goal, this puzzle is clearly against it).
Also I think that the solution blogpost has nothing to do with the puzzle, but with the test system. They found a heuristic that happened to pass the tests.
Also, if this problem is indeed solvable in P (or even in NP for that matter), then I’d like to hear a reason for it, or a hint for a possible solution. 2 player games with random made up rules tend to not be in NP.
So I checked 20 published python solutions.
AFAIU he takes the BFS tree, forgots the cross edges, and from bottom to top he assigns a danger with v.danger := sum_i ( v.children[i].danger ) - 1
Then he goes down from the top to the bottom, following the greater danger. ( Try it out on my graph: it recognizes that node 0 has 0 danger, and node 2 has 1 danger. )
This works for trees (and for the test cases), but I think I can refute this solution as well.
Anyway this problem clearly fails all the criteria to be here, and should have been deleted at most since Jahz pointed it out 6 years ago, in '16 May 21.
Also the linked official solution makes no sense, and should be removed ASAP.
You again! Oyo o/
You’re a strange guy you know? Reading you here or on the chat, I’m totally unable to say if you’re absolutely boring or extremely funny… 
I will not discuss the math problem since I don’t have the knowledge for, but I still can say you’re wrong on the remainder… The ‘public’ part of CG doesn’t have any ‘professional value’, people come here to practice, learn, compete, having fun… Not to have a thing to show to employers.
So perhaps this puzzle is not perfect, but it don’t have to since it’s ONLY FOR FUN. Furthermore the statement doesn’t mention anything about NP-ish things, so I don’t see in which way it lies to anybody…
And yes, most of the users are trying to get a 100% score, and not to write the perfect algorithm considering hypothetical non-existing test-cases, because once more: IT’S A GAME.
CG isn’t a certification authority, nor a school, nor a university or a laboratory which has to publish scientific and exact results. You’re missing the point…
Note that I took the time to write this in the hypothesis that you’re serious. But if you’re a troll, please ignore it and continue, on second thought, I think you make me laugh. 
In any case, peace be upon you! 
I understand, mistakes happen (well, not with me).
But why on the earth would they teach nonsense for thousands, deliberately? The problem is wrong, people point it out, they delete it, everyone happy (?)
At no point the problem states that you should find a solution that would cover any hypotetical testcase.
You’re given a set of testcases and you must design a solution that you can reasonably expect to solve similar testcases for validation.
And that’s it.
The problem is good as it makes you work on graphs and ask you to be a bit creative instead of just relying on out of the box classical algorithms.
And as for the general problem being NP-hard, there’s nothing wrong with that. There are several NP-hard problems on CG, it’s fine as long as the testcases provided are small enough. NP-hard doesn’t mean unsolvable.
That’s obviously not the case, the problem description is perfectly clear about what should count as a solution.
The official solution, linked by Thibaud, clearly states that DFS solves this problem.
There are no signs or whatever that indicate that you shouldn’t solve this problem, only pass the test cases. This problem is clearly intended and written with the mind that you have to solve it.
It’s a mistake by the creators which happens to teach nonsense to the users.
If there are other NP-hard problems with nonsense official solution, misleading tags, and description that fails to clarify that you don’t have to solve the problem only the test cases (i haven’t seen one tho), then those should be modified as well.
Why can’t you just rate the puzzle 1/5 and move on or make your own contribution with stricter rules, more complex testcases and validators?
How did you forge a replay with a customized dataset and can I do the same? Otherwise how people are testing custom dataset without the algorithm of the attacker?
Will you delete this problem?
I’ve been messing with this for quite some time. I’ve been trying to sort and choose nodes multiple ways, even implemented a quick and dirty custom priority queue since the version of c# on Codingame predates the introduction of PriorityQueue to c#. Tried lots of suggested logic from earlier discussion comments, but mostly I’ve been trying to follow Donotalo’s “DEPTH-FIRST SEARCH ALGORITHM TO OUTMANEUVER SKYNET ROBOTS” example. I was stuck on the final test case for quite some time and this morning I finally realized my silly mistake. I was first entering the DFS algorithm using Node 0 as my current node instead of starting from the agent’s position. Which, as an aside, it’s interesting/amusing to me now that starting from node 0 allowed the first 5 test cases to pass, just not the final one.
i’ll echo the complaints of others, this is essentially just a complex version of a “reverse” clash of code, in that the intended solution is just based on the behavior of specific test cases, not something you can infer from the problem description itself. it’s unsatisfying to be led to work on a problem and then discover that it’s not actually the same problem that the creator intended and that everyone else solved.
Am i the only one that reading datas aren’t correct? For instance, test 1 : the exit nodes should be 4 and 5, where as the reading values are 2 and 6… Have I missed a point?
You may reset to the default code first, and by running it, you will find that the values of ei read are indeed 4 and 5. Then compare the default code with your own code to check what the issue is.
F*%&$ yeah! I finally made it =D
I tried to understand Donotalo’s algorithm for days, but didn’t really get it, but it got me the right ideas I guess.
The rest of this post might contain spoilers… 
I don’t precalculate anything except the number of connected gateways per node (not really a calculation ^^)
Then I do three searches:
maybe redundant somewhere or not so elegant, but it seems to work
May not be sufficient just cutting closest 2 link node or 1 link node.
I think the crux of the problem is knowing that bob is looking for 2 link nodes to try to trap the player, and the key to solving some of the problems is maximizing the amount of free turns to cut 2 link nodes.
While this may mean you cut a 2 link node farther away distance wise from bob, but if that farther away path is filled with 1 link exits along the way, it essentially extends the danger of that node because if you cut the 2 link node closer to you, you may be forced to travel along one link path essentially using your turns until you can’t even cut the further 2 link node.
While the path to the closer 2 link may be closer, cutting that first, if along that path is at least 1 additional free turn, you’re giving away a free turn that you could’ve used to cut the further away 2 link node.
Hope that makes sense.
Trying to figure out why Test 4 - Ordered Gateways isn’t working.
For some reason my code pauses (I think) - but I am not sure how to debug for the submission tests.
I have looked through my code but I thought I covered the edge cases where it was trying to sever something that didn’t exist.
Anyone have any ideas about why this puzzle alone fails the submission ? (All other tests pass without issue)
The one thing I will add is that I seem to sever a different node from what my code does during the tests.
Hi,
If you click on the three dots at the bottom of the replay you can see what’s going on, on second turn you are trying to cut the link 17-1, that link doesn’t exist, that’s why you fail.
Thank you so much!
