- Sharing full solutions isn’t encouraged here.
- You have to find good enough solution to pass all testcases and hidden validators within certain amount of time (which is rather huge), not the best possible one! Just be a bit smarter than a bruteforce.
- If you can’t solve the puzzle, it probably means you’re not ready for it yet. Just skip it and try another one.
- Blaming people for hardcoding without substantial proofs just because you think so is unacceptable and might be considered as trolling.
3 Likes
I … don’t agree with anything you just said, but I understand that I am not in the position to argue, and this might not the be the right channel for arguing about semantics and stuff.
What is the right channel for reporting faulty problems? Email? Or an another forum thread. (I’d still like to see a so claimed solution, or an official solution before it.)
I think this is the input for the graph:
16 nodes, 15 links, 8 gates, labeling the nodes from 0 to 15, skynet starting from 1:
16 15 8
0 1
1 2
2 3
0 4
3 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
8
9
10
11
12
13
14
15
1
and the correct answer should be a link on the right side
Please read the statement: “Most of the links have been reinforced: your virus no longer has the possibility to destroy a link between two ordinary nodes, it can now only sever links leading to gateways.”
1 Like
Thx, i corrected it.
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
1 Like
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.
1 Like
So I checked 20 published python solutions.
- 18 of them fail on that simple tree (amazingly none of them even required to rename nodes),
- there is 1 alpha-beta search (which I think has the chance to solve small graphs fast),
- and there was 1 algorithmic solution that at least works on trees.
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! 
2 Likes
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 (?)
2 Likes
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.
4 Likes
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.
2 Likes
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?
7 Likes
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?
1 Like
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:
- I bfs through the graph looking for the next node for which the distance to the agent < connected_gws (the distance here is distance[last_node]+1-connected_gws[last_node]) and cut its link to the gateway. (this link has to be cut, otherwise the virus fails). If the seach isn’t successfull continue with 2.
- if this stage is reached, we have a joice. bfs to the next node connected to more than 1 gateway and cut the link
- bfs to next node connected to any gateway
maybe redundant somewhere or not so elegant, but it seems to work