Feel free to send your feedback or ask some help here!
Test 5 for this task seems to be buggy.
There are 2 different paths in the graph which should be severed on the first move. Itâs just a Skynet agentâs âwrongâ behavior which helped me to pass the test â my solution uses the fact that Skynet agent tends to choose the longest of those paths.
Is it ok to use behavioral patterns like that? Or is this a bug?
Iâm leaning to the latter.
Thanks for your reply.
2 Likes
I assume that the agent goes to the path down, and slightly to the left, for you too. It is the best thing to do, because this path is really dangerous: it can jump from âurgentâ nodes to âurgentâ nodes until it reaches a point where it has two exit choices. Therefore, if you donât sever a link in that path on your first move, you lose. So even if it is a long path, the behavior of the agent is right
2 Likes
Thank you for your reply, lilian_cartellier.
You are right, taking a look at test 5 with a clear head Iâve realized that longest path is the only correct one. So the agent behavior is correct.
I solved this problem and want to give my feedback. It is a great problem, but the tests for it are too simple, you can produce much much more complex tests within boundaries of the conditions of the problem.
Following text contains the ideas of the solution, SPOILERS.
I managed to come up with algorithm, which firstly analyzes the graph and simplifies it by removing leaves, merging adjacent dangerous nodes and special removing of nodes with low, but non-zero danger, then if it is not enought to determine our move, it uses dynamics for quick full enumeration of all graphs with the same structure as obtained graph, but lower danger at least in one node. The complexity of the first stage is O(N^3), which is OK. But complexity of the second stage is about O(3^(#2) * N^2) where #2 is the number of nodes with measure of danger at least 2, which can be around 100 in some graphs within conditions of the problem. So 2nd phase can spoil the whole algorithm. But what do we see in the tests?
In every test my programm determine every move before reaching second phase, so I got 100% in this problem.
Admins, make the hard tests (at least one) for the problem or add more specifications in the text of it, please. I hope you will improve your content because it is unique and very enjoyable. If you want more details about how to construct a complex graph, I may share them.
5 Likes
Actually tests for this puzzle canât be harder (only larger) when you know there is a simple O(N log N) solution 
1 Like
That is the point! Tests need to separate weak solutions from the best one. Here is an example of graph with #2 = 3, which forces my algorithm to fall into the second phase:
Start node is 0. But I see your issue: if to add new test then people will lose their 100% on this problem which is unfair. I have no idea how to deal with this situation except consider me as a lucker with weak solution which passed all tests.
And one more note. The restriction
is excessive. I can emulate any graph satisfying other conditions on such in maximum 3x nodes, 3x links and 2x exits.
The graph youâre proposing canât be solved with puzzle constraints as you canât cut a link between two nodes, only a link between a node and a gateway. It cannot exist neither within level 1 constraints because it has nodes connected to 2 gateways.
So thereâs no luck and no weak solutions as long as you look carefully at constraints. You also have to consider these puzzles are done during constest, thus have to be solved within a limited timespan. There were 3 hours for both levels and even if top coders finished it after 1 hour, others deserve a chance to get as far as they can. There are coders here who donât know graph theory because they never learned it (or at least not yet).
Anyway, I agree there could have been a bonus level (as for Indiana and Vox Codei) with different constraints where you solution wouldnât be overkill.
1 Like
[quote=âNewboO, post:8, topic:61, full:trueâ]
The graph youâre proposing canât be solved with puzzle constraints as you canât cut a link between two nodes, only a link between a node and a gateway. It cannot exist neither within level 1 constraints because it has nodes connected to 2 gateways.[/quote]
Actually that graph can be solved and yes, I know, that I canât cut a link between two non-exit nodes. It is the topic about level 2. The strategy:
Lets draw this graph on paper on such way: 1-2-3-4-5-6 cycle is a regular hexagon, 1 is its only left node. Start node 0 locates more left and connects with 1. On the right side node 4 connects with 7 and 8 exit nodes. Bunch of nodex 9, 10, 11, 12, 13, 14, 15, 16 locates on top and hangs from node 2. Symmetric bunch 17-24 swings from 6 on bottom. Firstly about the virus. It never comes in earlier visited nodes, because in that case it would fall in situation like the former one but with few more severed links. Hence after 2 moves virus will be in node 2 or 6. The whole graph has the axis of symmetry throught 0, 1, 4, so without loss of generality it will be in node 2. In the first two moves we sever 10-13(E) and 21(E)-18 links indepently from virus behavior.
In the third move we sever 11-14(E) if the virus is in node 2 (symmetric if in node 6). Then we have 2 cases:
Case 1: virus moved to 9. In that case we sever 12-15(E). Then virus moves to any of node from 10, 11, 12. In all cases our moves are trivial and we force virus to turn back to node 9, which means, as I said, that we won in that case.
Case 2: virus moved to 3. We sever 4-7(E). Virus moves to 4. We sever 4-8(E). Virus moves to 5. We sever 19-22(E). Virus moves to 6. Here we can sever no links and fall directly into case symmetric to case 1. Just node 2 is replaced by node 6 and bunch 9-16 by bunch 17-24. In the symmetric way here we force the virus to visit some formerly visited node by symmetric strategy. So we win here too.
Oops, indeed, I made the virus play first when solving on paper so I was always 1 turn short 
Rest of my message still applies though.
It seems there is a problem with âskynet core networkâ test. It gets passed when I run the test manually but it donât when I hit submit. Therefore I only get 83% not 100%. I use Python3. Am I missing something?
1 Like
The test cases used on submission are different from the tests that you can see on ide window.
The difference are minor, but still present to avoid hard coded solutions.
Thanks, cup_of_tea. I managed to pass the tests.
Though it is a very interesting task - to fix a bug that you canât see. 
Well, despite not using a hardcoded solution (can provide pastebin if wanted, but I figure linking that here would be frowned upon) I fail at 3/6 cases during submit after succeeding all test cases. I guess it must have to do with the test cases using smaller indices consistently so I get away with errors, but it kinda makes the test cases a bit poorly constructed.
EDIT: Yeah, as suspected in all the test cases, using the smaller index is better than (aka more âdangerousâ) a larger, I think it would save people a lot of headache if that was fixed so people realize their algorithm is buggy. Or maybe the admins love to watch us suffer, who knows.
I have a struct containing a list of integers (represent the graph as an array of linked lists). When I push_back an int into a list in the begining of my code I get this wonderful error:
Aborted.
at raise.c. function __GI_raise (sig=sig@entry=6) on line 56 at abort.c. function __GI_abort () on line 89 at malloc.c.
function __malloc_assert ( assertion=assertion@entry=0x7ffff6b1c198
"(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2]))
- __builtin_offsetof (struct malloc_chunk, fd)))) && old_size
== 0) || ((unsigned long) (old_size) >= (unsigned
long)((((__builtin_offs"âŚ, file=file@entry=0x7ffff6b17c85 âmalloc.câ,
line=line@entry=2372, function=function@entry=0x7ffff6b18003
<func.11292> âsysmallocâ) on line 293 at malloc.c. function sysmalloc (av=0x7ffff6d59620 <main_arena>, nb=32) on line 2369 at malloc.c. function __GI___libc_malloc (bytes=24) on line 2891 at new_allocator.h. function __gnu_cxx::new_allocator<std::_List_node >::allocate (this=0x6030b0, __n=1) on line 104 at stl_list.h. function std::_List_base<int, std::allocator >::_M_get_node (this=0x6030b0) on line 343 at stl_list.h. function std::list<int, std::allocator >::_M_create_node<int const&> (this=0x6030b0) on line 511
I tried adding something like graph[0].links.push_back(3), not only does that line not crash but it removes this crash further on in the code where the links are read and added. However, it causes a bug later on cause I have no reason to add a link there like that.
I use the exact same type of thing in other problems and had no issues, what is going on? I googled around for this type of error, didnât find anything exactly like mine but the solution to the problem revoled around updating the compilerâŚ
Language: C++
Edit: Found a mistake in my code, fixing it removed the problem, but I donât understand why because that bug had not much to do with the line on which the program was crashing.
Edit2: Solved using BFS (=shortest path in unweighted undirected graph). Using BFS to find closest edge of a certain criteria to the agent. I run it about 3 times to look in priority for this type of thingâŚin second priority for that type of thingâŚetcâŚ
Seems more like a ripple effect, you had a bug that was probably leaking, and then the rest started to leak as well and a line which has nothing to do with the main problem fail.
This topic was not helpful, but I did solved it.
I ranked nodes by the number of exit edges connecting to them. Then I used Dijkstra, and then summed the rank on the shortest path to gate nodes, ones that still has exit edge.
Finally Iâve removed an exit edge connecting to maximum ranked gate node and updated itâs rank.
To pass the core network, I had to exclude exit nodes from Dijkstra, since there was short-cuts through them.
6 Likes
Graphs in this puzzle can be solved if there are some nodes without connections to gateways. If you remove node (3) or node (5), then puzzle will become unsolvable.
In my solution i determine nodes with gateways (âhotâ nodes) and lengths of a ways to get from problem nodes to Skynet. Itâs like a sonar from a Skynet node (SI).
After that trace recursively from all âhotâ nodes to SI, it is eaysy because we know lengths, calculate weight only for âhotâ nodes while tracing back. My weight calculation doesn`t leave any data for other weight calculation, because there is only one float for one hot node.
My replays:
For your simmetrical graph i suggest to check if top hot points is doubled by weight and recheck their weight by adding some N first passed nodes. If top âhotâ nodes still doubled by weight after M (M=length of some âhotâ point) calculations, then do not care, take 1st.
1 Like
Hi there !
Warning, the following post contains hints to help solving this puzzle.
- If Skynet is on a node without any connections to gateways, it cannot beat you this turn, so use this kind of turn (I will call them KIND1) wisely
- If Skynet is on a node with exactly one connection to a gateway, you have no choice for this turn, you must severe this connection. (KIND2)
- Notice that Skynet will beat you if it reaches any node with connections to 2 gateways (KIND3). This kind of situation must be avoided, so as soon as possible, you must try to severe one of those. Of course, ASAP = KIND1
The challenge in this puzzle is to determine which KIND3 nodes Skynet will reach the most fast and turn it into a KIND2 node before it happens. This must be repeated until there are only KIND2 nodes left. Then the rest is easy =)
28 Likes
Can you please tell how to use tree in this kind of problem