I’ve got the same question as aryan141994
I have the same algorithm 
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 
1 Like
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 ? 
2 Likes
Solved it using axx’s method. It’s a good habit to browse the forums
I don’t understand why on the last replay, your algorithm chose 29 instead of 34 on the first turn. Could you please help me ? thanks
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.
1 Like
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.
1 Like
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:
This is what I get in Complex mesh validator
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.
That’s why I’m crazy looking for the error. May I write some code in this forum???
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???
I test my code with following inputs and works fine:
37
81
4
36
8
36
13
36
7
22
21
8
19
0
7
19
18
15
23
1
3
18
22
27
28
0
11
27
23
9
0
16
15
32
21
20
21
3
20
17
19
6
0
6
12
10
14
2
33
6
11
7
9
2
34
10
9
15
24
4
6
27
30
27
29
11
10
17
32
2
4
8
17
3
19
25
27
32
31
4
5
2
3
24
25
30
16
3
33
25
23
26
27
16
27
34
33
35
34
7
1
26
25
18
32
13
9
14
15
28
29
1
6
17
18
13
15
19
20
23
24
26
28
22
32
29
30
16
17
9
14
4
1
2
1
11
12
22
19
17
31
1
0
16
23
3
8
0
10
35
2
5
35
8
16
7
13
21
19
13
16
13
14
5
2
16
18
0
26
2
I saw now what was done for Indiana, and maybe instead of “redesigning” the hard version, Skynet should just have its very hard version as well, with same rules but harder use cases
1 Like
Pessimistic N^3 does the job. In my case I use bfs from agent node at every step of the way to determine most threatening gateway link. With good conditions for enqueueing nodes this has complexity far below N^2. But still, worst case scenario is N^3. Also keep in mind I’m using ordinary 2D table with no degree sorting etc. I reckon you could improve overall pessimistic complexity to N^2 log N using better structures - with realistic results closer to N log N.
The thing you must keep in mind here is that super complex examples would mean that they are unsolvable (agent always wins). For example 2 or more equally demanding paths possible for agent, and enough time to start making proper cuts only on one of them.
Sooo from what I gather, your algorithm fails on this test:
15 14 6
0 1
1 2
1 3
0 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
10 12
10 13
10 14
2 3 11 12 13 14
and you start from node 0; basically, you have 1 node connected to two gateways which is really close and 1 node connected to 4 gateways which is really far. Since the far node will have a higher “rank” according to your definition, you’ll try to cover that node up and the bot will just escape through the close node.
edit : I figured it out
I’m not understanding this at all.
So you rank all the nodes by the number of exit edges connected to them… So would you ignore the gate nodes? Or do those get ranked really well? How does that work?
Then you use Dijkstra… starting where? Starting at the agent? Starting at the gates?
Then you “summed the rank on the shortest path to gate nodes, ones that still has exit edge.” I’m so lost. What are you adding together? And for which nodes? All of them? Or just the ones connected to gates? Or just the nodes connected to 2 or more gates?
1 Like
If you have 2 urgent nodes connected to the same gate, one is closer to the agent than the other, which do you choose? This question also applies when the gates are different but have the same number of links.
Hi everyone, I really need your help on this one
I did a simple algorithm to try to pass tests 1 to 6, it’s meant to work, but it doesn’t
I have an error output and a normal output just after that both print the same vars, and both don’t print the same thing ;- ;is this a bug or something ?