18 of them fail on that simple tree (amazingly none of them even required to rename nodes),
there is 1 alpha-beta search (which I think has the chance to solve small graphs fast),
and there was 1 algorithmic solution that at least works on trees.
AFAIU he takes the BFS tree, forgots the cross edges, and from bottom to top he assigns a danger with v.danger := sum_i ( v.children[i].danger ) - 1
Then he goes down from the top to the bottom, following the greater danger. ( Try it out on my graph: it recognizes that node 0 has 0 danger, and node 2 has 1 danger. )
This works for trees (and for the test cases), but I think I can refute this solution as well.
You again! Oyo o/
You’re a strange guy you know? Reading you here or on the chat, I’m totally unable to say if you’re absolutely boring or extremely funny…
I will not discuss the math problem since I don’t have the knowledge for, but I still can say you’re wrong on the remainder… The ‘public’ part of CG doesn’t have any ‘professional value’, people come here to practice, learn, compete, having fun… Not to have a thing to show to employers.
So perhaps this puzzle is not perfect, but it don’t have to since it’s ONLY FOR FUN. Furthermore the statement doesn’t mention anything about NP-ish things, so I don’t see in which way it lies to anybody…
And yes, most of the users are trying to get a 100% score, and not to write the perfect algorithm considering hypothetical non-existing test-cases, because once more: IT’S A GAME.
CG isn’t a certification authority, nor a school, nor a university or a laboratory which has to publish scientific and exact results. You’re missing the point…
Note that I took the time to write this in the hypothesis that you’re serious. But if you’re a troll, please ignore it and continue, on second thought, I think you make me laugh.
In any case, peace be upon you!
I understand, mistakes happen (well, not with me).
But why on the earth would they teach nonsense for thousands, deliberately? The problem is wrong, people point it out, they delete it, everyone happy (?)
At no point the problem states that you should find a solution that would cover any hypotetical testcase.
You’re given a set of testcases and you must design a solution that you can reasonably expect to solve similar testcases for validation.
And that’s it.
The problem is good as it makes you work on graphs and ask you to be a bit creative instead of just relying on out of the box classical algorithms.
And as for the general problem being NP-hard, there’s nothing wrong with that. There are several NP-hard problems on CG, it’s fine as long as the testcases provided are small enough. NP-hard doesn’t mean unsolvable.
That’s obviously not the case, the problem description is perfectly clear about what should count as a solution.
The official solution, linked by Thibaud, clearly states that DFS solves this problem.
There are no signs or whatever that indicate that you shouldn’t solve this problem, only pass the test cases. This problem is clearly intended and written with the mind that you have to solve it.
It’s a mistake by the creators which happens to teach nonsense to the users.
If there are other NP-hard problems with nonsense official solution, misleading tags, and description that fails to clarify that you don’t have to solve the problem only the test cases (i haven’t seen one tho), then those should be modified as well.
How did you forge a replay with a customized dataset and can I do the same? Otherwise how people are testing custom dataset without the algorithm of the attacker?
I’ve been messing with this for quite some time. I’ve been trying to sort and choose nodes multiple ways, even implemented a quick and dirty custom priority queue since the version of c# on Codingame predates the introduction of PriorityQueue to c#. Tried lots of suggested logic from earlier discussion comments, but mostly I’ve been trying to follow Donotalo’s “DEPTH-FIRST SEARCH ALGORITHM TO OUTMANEUVER SKYNET ROBOTS” example. I was stuck on the final test case for quite some time and this morning I finally realized my silly mistake. I was first entering the DFS algorithm using Node 0 as my current node instead of starting from the agent’s position. Which, as an aside, it’s interesting/amusing to me now that starting from node 0 allowed the first 5 test cases to pass, just not the final one.
i’ll echo the complaints of others, this is essentially just a complex version of a “reverse” clash of code, in that the intended solution is just based on the behavior of specific test cases, not something you can infer from the problem description itself. it’s unsatisfying to be led to work on a problem and then discover that it’s not actually the same problem that the creator intended and that everyone else solved.
Am i the only one that reading datas aren’t correct? For instance, test 1 : the exit nodes should be 4 and 5, where as the reading values are 2 and 6… Have I missed a point?
You may reset to the default code first, and by running it, you will find that the values of ei read are indeed 4 and 5. Then compare the default code with your own code to check what the issue is.
F*%&$ yeah! I finally made it =D
I tried to understand Donotalo’s algorithm for days, but didn’t really get it, but it got me the right ideas I guess.
The rest of this post might contain spoilers…
I don’t precalculate anything except the number of connected gateways per node (not really a calculation ^^)
Then I do three searches:
I bfs through the graph looking for the next node for which the distance to the agent < connected_gws (the distance here is distance[last_node]+1-connected_gws[last_node]) and cut its link to the gateway. (this link has to be cut, otherwise the virus fails). If the seach isn’t successfull continue with 2.
if this stage is reached, we have a joice. bfs to the next node connected to more than 1 gateway and cut the link
bfs to next node connected to any gateway
maybe redundant somewhere or not so elegant, but it seems to work
May not be sufficient just cutting closest 2 link node or 1 link node.
I think the crux of the problem is knowing that bob is looking for 2 link nodes to try to trap the player, and the key to solving some of the problems is maximizing the amount of free turns to cut 2 link nodes.
While this may mean you cut a 2 link node farther away distance wise from bob, but if that farther away path is filled with 1 link exits along the way, it essentially extends the danger of that node because if you cut the 2 link node closer to you, you may be forced to travel along one link path essentially using your turns until you can’t even cut the further 2 link node.
While the path to the closer 2 link may be closer, cutting that first, if along that path is at least 1 additional free turn, you’re giving away a free turn that you could’ve used to cut the further away 2 link node.
If you click on the three dots at the bottom of the replay you can see what’s going on, on second turn you are trying to cut the link 17-1, that link doesn’t exist, that’s why you fail.
I really can’t figure out why only validator 4 isn’t working.
Basically, my code works like this (Javascript):
create array, push N1, N2 onto array.
Cycle through array, push onto graph.
Besides BFS, I have another BFS method in my class called shortestForcedpath (which checks for all paths where each one is connected to a gateway, to avoid all scenarios with forced moves leading up to a double gateway)
I am filtering out undefined, I just can’t figure out why my graph is adding things that didn’t exist.
Any ideas why validator 4 is so different?
Edit: Besides Validator 4, all other validators pass without issue.
Inside the graph, I am using an adjacency graph which just pushes items like
this.adj(u) = v
It’s just causing me to obsess because I can’t figure out what kind of inputs could cause my code to malfunction
I think that Donotalo’s walkthrough: (A Depth-First Search Algorithm to Outmaneuver Skynet Robots – CodinGame Blog) should not be linked on the puzzle main page or only with a warning that it’s here for more advanced users who already solved the puzzle to compare notes because as a noob trying to level up in more advanced algorithms and get past the last hard test cases, you’ll restart from scratch trying to follow it in full, thinking that doing so will introduce you to BFS, DFS and the correct ways to use them for this particular puzzle, but this walkthrough absolutely doesn’t do that. The explanations are pretty messy and even lackadaisical when it comes to the details of the implementations of the algorithms, and it’s extremely frustrating to realize that once you finally get to the very end that the last DFS algorithm is returning some absolute gibberish because some important part is missing from the explanation about it or my implantation is just wrong because I misunderstood what it was supposed to be doing. It’s far from being a tutorial about DFS or BFS.
