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.
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.
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.
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 =)
So like other people here, got 100% but unsatisfied with my solution since I’m quite sure it can’t solve all cases.
Did someone understood how the custom tests are working ? I’d like to build one I can’t solve, and check if other people solutions are havings problems as well or not.
Custom test look like this (example for test 01) :
LOCKED
8 <— ok, number of nodes
159 361 <— ???
285 277 <— ???
285 450 <— ???
681 361 <— ???
780 216 <— ???
780 513 <— ???
540 450 <— ???
540 277 <— ???
13 <— ok, number of links
6 2 <— ok, a link…
7 3
6 3
5 3
3 4
7 1
2 0
0 1
0 3
1 3
2 3
7 4
6 5
0 <— ok, starting position for the agent
2 <— ok, number of gateways
4 <— ok, gateway id
5 <— ok, gateway id
I guess that the ??? lines (there are as much as nodes) implement the agent logic, to determine when you’re at a node N where the agent is going next, obviously depending on what links are remaining on the map, but I’v not been able to understand the logic. There are even some negative numbers (test 06).
Anybody ?
Edit: ok, looks like it’s actually just the coordinates for the UI
Too bad, won’t be able to push this nice problem further
All right, that was finally easy, I don’t know how the agent is implemented, but it handles very well this very simple custom test:
LOCKED
12
85 328
625 297
625 427
800 325
800 250
800 400
800 475
313 197
625 100
313 400
800 100
800 150
11
2 6
0 7
9 2
3 1
2 5
4 1
9 1
0 9
7 8
8 10
8 11
0
6
3
4
5
6
10
11
Facts:
This test is compliant with the rules
This test is “solvable”, it has a least one solution
This test is even easy ! Takes 10 seconds to solve on “paper”, it’s a very simple and obvious graph
And nows comes the fun part: out of the 24 Java published solutions, only 10 are able to solve it !!!
Yes, I did spent 10 minutes copy/pasting the Java solutions and evaluating them against my custom test.
It’s a bit disturbing to see 60% of the published Java solutions not able to solve this easy case, although they can solve quite complex ones such as IDE test 4/5/6. While I said earlier that I’m not satisfied with my own solution, at least it solves this test.
I don’t know about the other languages (I only have access to Java solutions since I only solved it using Java), but my guess is that we would have the same kind of ratios.
And I’m quite sure I could easily raise this ratio even further with a little more complex test.
So, open questions:
a) am I wrong somewhere on my facts ?
b) should this puzzle be “redesigned” ?
c) is your solution solving this test ?
I think this puzzle is not a good puzzle. The tests can be passed by implementing simple linear algorithm, but the problem is actually NP complete, so in order to solve it correctly an exponential algorithm is required.
Hello! The logic behind my solution is pretty simple:
I find the nearest node with two gateways’ links and severe one of the links.
If the one-gateway node is closer than two-gateways then I severe this one link.
This logic allows me to pass all tests except for the last one: https://www.codingame.com/replay/solo/128353757
I saw @derbov’s solution posted above but I still don’t understand how to determine the right link.
Finally solved it after some thinking. The logic is a little tricky. You need to tweak bfs a bit. This is the algorithm I followed:
If there’s an immediate gateway node adjacent to the current node, obviously you need to break it.
If not then you need to sever one of the links that lead to multiple gateways(urgent nodes).
Now the challenge is to write an evaluating function that determines which ‘urgent’ node you need to sever.
In my approach, my evaluation function considered the number of nodes that immediately lead to a gateway and the distance of the urgent node from Skynet. Do remember to not consider gateway nodes in the distance.
My algorithm is like yours but I have a problem with Complex mesh validator. My code pass all test cases but when I submit my code doesn’t work like I want.
This is the first link I want to sever ( based in the distance from agent to the nodes with multiple adyacent gateways and the adyacents gateways in the closest way nodes ), in test cases works fine, but in validators doesn’t work like I want:
The only thing that changes between the test and validator are nodes id I guess, and so your program may not compute links in the same order. And it may explain the difference in outputs.
I changed the inputs order and always the output is the correct “27 16”. I think my code is correct. I need the inputs of Complex mesh validator to debug my code. Does anyone have the Complex mesh validator inputs???
