Well, folks say they got going by using AXX’s solution. I must not have understood exactly what AXX ment. I did implement what I thought that solution was, and it didn’t help. But I did find something else that worked very well. The way to approach this problem is geometrically. SPOILERS FOLLOW: The basic approach is to compute the distance along the shortest path to interesting nodes and cut the link on that path. For basic exit nodes you simply cut the link to the closest node where distance is the number of edges that are traversed. In fact, if SKYNET is on a node adjacent to an exit it is the only move. if SKYNET is not adjacent to an exit node then you get your choice of things to cut. I call this a free move. But what to cut? A few failures and the obvious answer is that you need to cut a link to a node that connects to two exit nodes. But which one? The answer is to cut the “closest” one. But what metric do you use for distance? I believe that AXX’s solution (which didn’t work for me) was to use the sum of the “rank” of all the nodes on the shortest path to the dual-exit node, where the rank is the number of exit nodes connected to the given node. After looking at the failing boards for a few minute I saw that the key wasn’t the rank, but instead the number of “free moves” that were between SKYNET and the dual-exit node. So, I used BFS to find the shortest path to the dual-exit nodes and then I backtracked along the shortest path and counted the number of nodes that had NO adjacent exits (these are free moves). Then I cut the link along the path that had the fewest “Free” moves. For all the puzzles this seemed to give the correct solution and did it quickly. There are a few more things you need to do to get the “right” shortest path, and things you need to do to reduce the complexity so that it runs fast enough, but defining the distance metric as the number of free moves along the shortest path got the answer for me.
Solved the problem. Yaay
It was my first hard problem, so I am a little too excited about it.
But I am writing this comment to thank all of you who wrote such helpful comments, which helped me think of a feasible algorithm. So I will also do my part:
SPOILERS:
The problem basically requires us to predict the movement of the skynet agent, and pick the most dangerous paths (paths with most urgent nodes) and then act accordingly. I will not write how, but say this: Its a really great problem!
Solved the problem cutting the dual exit nodes ranking them by number of exit nodes between the current position and the exit, divided by the distance between them. The test seems to always favor the closest dual exit node with the most single exit nodes in between.
i cant under stand this game -_-
I had some difficulties understanding AXX solution also. Using the notion of free move helped me solve the problem as well.
Cheers;
There may be an error in the validator test “Ordered Gateways”
The puzzle constraints state that all node numbers are between 0 and 500 inclusive
My solution, which initialized a value to -1 and tested that value for <0 was failing. When changed to a direct test for != -1, the solution passed. In both cases the value is only ever updated with the number assigned to a node or the initialization value. This suggests one of the nodes has been assigned a negative number, in violation of the constraints.
I’ve checked the validators and the node numbers are all at least 0. There must be something else causing the failure. Admittedly, it’s supspicious…
My solution is BFS search with store at end of path variable “FreeMoves”. “FreeMoves” representing how many steps virus can do to analazed direction before I must drop one from links to exit from analized node. If I found at some depth of path negative “FreeMoves”, I stop go deeper, but I still search at that level for more risky node. At end of turn I kill link from badest node to reached exit. Think youself about situation, when wery risky path not found.
There seems to be a bug in the solution-checking-system on this puzzle:
I first failed the 2nd test case, then I succeeded it (until 4th test case included, ie all test cases from 1 to 4 succeeded --see picture1 ).
But when I submit, the system still detect a failure in the 2nd test case (despite trying small changes and restarting the checking) --see picture2.
Did someone already has this kind of bug? Any idea to get past it?
Have you checked the replays in the validators to see what happens?
(You can watch the replays by clicking the REPLAY buttons as shown in your picture 2.)
Yes I did, replays are going valid, but submit indicators remain false.
Could you copy and paste the “REPLAY AND SHARE” link to the failed validator here?
I had success with Minimax. The first four test cases can be solved with a tree of depth four, so I simply enumerated every possible move the agent or the virus could make. Skynet core required a tree of depth 12 and Complex mesh 14, so for those two I had to aggressively narrow the tree to avoid timeouts. Once I watched enough replays to realize the agent only follows two rules, I was able to prune most of the agent moves. It took a little longer to figure out how to limit the number of virus moves.
hey guys, I pass all tests but when I submit, one test fails ( 05 - Complex Mesh). I have no hard code 
. Is there a bug with Complex Mesh? Sadly there are no debug system outs in validation tests.
ok, I solved it: my hashCode method for class Link was not working correctly:
previous version:
@Override
public int hashCode() {
int result = Math.min(node1, node2);
result = 31 * result + Math.max(node1, node2);
return result;
}
correct version:
@Override
public int hashCode() {
int result = Math.max(node1, node2);
result = result + (100 * Math.min(node1, node2));
return result;
}What’s wrong with my code? It works in testcase number 3, but it is bugging in another testcases. It’s returning strange values like 0 0, 0 255, or -136978368 5.
Code:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
/**
* Auto-generated code below aims at helping you parse
* the standard input according to the problem statement.
**/
int main()
{
int N; // the total number of nodes in the level, including the gateways
int L; // the number of links
int E; // the number of exit gateways
cin >> N >> L >> E; cin.ignore();
int nodes[N];
int links1[L];
int links2[L];
int gateways[E];
int linksgateway1[L];
int linksgateway2[L];
int linksneargateway1[L];
int linksneargateway2[L];
for (int i = 0; i < L; i++) {
int N1; // N1 and N2 defines a link between these nodes
int N2;
cin >> N1 >> N2; cin.ignore();
linksgateway1[L] = -100;
linksgateway2[L] = -100;
linksneargateway2[L] = -100;
linksneargateway2[L] = -100;
links1[i] = N1;
links2[i] = N2;
}
for (int i = 0; i < E; i++) {
int EI; // the index of a gateway node
cin >> EI; cin.ignore();
gateways[i] = EI;
}
for (int i = 0; i < L; i++)
{
for (int i2 = 0; i2 < E; i2++)
{
if (links1[i] == gateways[i2] || links2[i] == gateways[i2])
{
linksgateway1[i] = links1[i];
linksgateway2[i] = links2[i];
}
}
}
for (int i = 0; i < L; i++)
{
for (int i2 = 0; i2 < L; i2++)
{
if (links1[i] == linksgateway1[i2] || links2[i] == linksgateway2[i2] || links1[i] == linksgateway2[i2] || links2[i] == linksgateway1[i2])
{
linksneargateway1[i] = links1[i];
linksneargateway2[i] = links2[i];
}
}
}
// game loop
while (1) {
int SI; // The index of the node on which the Skynet agent is positioned this turn
cin >> SI; cin.ignore();
for (int i = 0; i < L; i++)
{
if (SI == linksgateway1[i] || SI == linksgateway2[i])
{
cout << linksgateway1[i] << " " << linksgateway2[i] << endl;
linksgateway1[i] = -100;
linksgateway2[i] = -100;
linksneargateway1[i] = -100;
linksneargateway2[i] = -100;
}
}
for (int i = 0; i < L; i++)
{
if (SI == linksneargateway1[i] || SI == linksneargateway2[i])
{
for (int i2 = 0; i2 < L; i2++)
{
if (linksgateway1[i2] == linksneargateway1[i] || linksgateway2[i2] == linksneargateway2[i] || linksgateway1[i2] == linksneargateway2[i] || linksgateway2[i2] == linksneargateway1[i])
{
cout << linksgateway1[i2] << " " << linksgateway2[i2] << endl;
linksgateway1[i2] = -100;
linksgateway2[i2] = -100;
linksneargateway1[i2] = -100;
linksneargateway2[i2] = -100;
}
}
}
}
}
}I have same question about the last replay. Why it chose 29 instead of 32 on the first turn ? Could you please share your idea?thanks
This blog article should help you understand why:
For me this was the second hardest task, first being " Mars Lander". Mainly because I could see the solution for the puzzles in my mind, and to solve them on paper seemed quite easy, but I had so many troubles implementing my idea. Like, how to implement connections between node, how to apply a connection, how to update connected nodes and many more. I’ve implemented 3 models with the main idea to first apply the certain connections (nodes which could be connected in only one way) and then recursively examine and connect adjacent nodes. Dead end, dead end, dead end. Until I noticed that I could generate all possible connections combinations for a node (all combinations of, needed, links to neighboring nodes) and using DFS to find the correct combinations for all nodes.
which proves that you have succeeded