I would guess that all of the published solutions are polynomial or better. A slower complexity class would probably time out.
The primary challenge is identifying the closest node to the agent with multiple gate connections. The ruling time complexity for most solutions should be determined by their graph navigation algorithm, most likely O(n^2) or faster.
Can you give me one?
So there is a semi-official solution, A Depth-First Search Algorithm to Outmaneuver Skynet Robots
AFAIU it only focuses on the case when Skynet follows a particular greedy algorithm, and we will work against it (it doesnāt even work on trees). (Thatās not how 2 player games usually work.)
If you read back, some people claiming, that half of the submitted (and published) solutions donāt work, some claiming this problem NP complete, some claiming O(n^3) algorithms, anyhow, I couldnāt find one myself.
edit: ig i just have to pass the tests in all languages, and check the published solutions
Also canāt you just delete faulty problems? The ones that contain a lot of wrong solutions. (I donāt know if you can mass-test the solutions with different test cases.)
They have no benefit whatsoever, but are rather harmful (and annoying).
I thought you could only submit a solution with a 100% success rate?
The article you found is an excellent description of how to solve the puzzle. If I understand correctly, the DFS + priority queue approach it describes would be O(n^2 log n).
For finding the agentās distance from multi-gate nodes I used Dijkstra, conditionally assigning weight 0 to all edges from a node that is connected to a gate. My solution simulates cutting each edge from a multi-gate node, then finds for each simulation the agentās distance from each remaining multi-gate node and chooses the cut that is most favorable.
That puts my solution at something like Ļ“(m(v+e)log(v)), with m the number of edges from a multi-gate node to a gate, v the number of nodes, and e the number of edges. That would be O(n^2 log n). I would not be surprised if there are published O(n log n) solutions, maybe even O(n).
the structure of the graph is the same but the nodes ids are different. So I believe your program logic is not independent from the nodes ids
My solution simulates cutting each edge from a multi-gate node, then finds for each simulation the agentās distance from each remaining multi-gate node and chooses the cut that is most favorable.
Sounds logical. How do you determine the āmost favorableā?
The cut that leaves me with the most choices. Any time the agent is adjacent to a gate, your only option is to cut that link. My solution looks for the number nodes not adjacent to a gate that the agent will have to pass through in order to get to a node that is linked to more than one gate.
So you cut the link of a multi-gate node that is reachable the shortest way through nodes not adjacent to gates?
Or something like that, right?
Well, this is a wrong solution, it fails even on trees. Consider the following example, where the leaves, denoted by g are the gateways:
If I understand correctly your solution cuts one of the links on the left, but then Skynet goes right, and eventually escapes. However, if you cut one link on the right first, you can stop Skynet.
I still think that this problem is not even in NP (that is, not solvable with nondeterministic computers, or, there are no polynomial-time checkable witnesses) and all the accepted solutions just hardcoded the public and non-public tests.
Also Iād really like to a see a solution, if there are any.
I still think that this problem is not even in NP (that is, not solvable with nondeterministic computers, or, there are no polynomial-time checkable witnesses) and all the accepted solutions just hardcoded the public and non-public tests.
Sorry about that but you are absolutely wrong. My solution is based on a BFS algorithm and has no hardcoded parts. Iād suggest that you look at how your solution fails, figure out what you (as a human) would do instead (in other words, solve it by hand) and translate that reasoning into code.
You are claiming that your solution has no hardcoded parts, and you suggest that I should check the test cases where my solution fails, and solve them by hand.
Fortunately, none of the validators are so complex.
In order to solve a case like the one you propose, you would need to search for an entire sequence of cuts from multi-node gates that prevents the agent from winning. That would add a degree or two, but it would still be a polynomial solution.
you would need to search for an entire sequence of cuts from multi-node gates that prevents the agent from winning. That would add a degree or two, but it would still be a polynomial solution.
There are n! such sequences.
edit: as always, Iād like to see a good solution, if there are any.
5425 people have solved the puzzle but this troll still claims there is no solution. Enough for me.
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.ā
Thx, i corrected it.
