I beat this with some little scheme to catch how nodes were moving and a greedy algorithm. Both my movement catching scheme and the greedy algorithm broke down on the last test but I patched them up with some hacks. I tried to bruteforce this in a more proper way but couldnt so had to resort to hacks in the end. Would be interested to hear about other people’s solutions’.
I also had to resort to some hacks for the last test.
There are two problems with the last test:
- Some moves would destroy more nodes in the short term, but force you to use more bombs in the long run (placing bombs between cross shaped static nodes)
- Some moves could destroy more nodes if you are able to plan 15 turns ahead. (half cross shaped static nodes + 1 moving node in the bottom)
I think it’s doable if you split the terrain between smaller areas surrounded by indestructible blocks, and try to plan ahead deeper for these zones.
Salut à tous,
Il y a une erreur dans l’énoncé au niveau des contraintes sur les variables :
Il est écrit 3 < rounds < 20 alors que la valeur limite dans les tests semble être <100
Je n’ai pas encore fini le puzzle, mais je reviendrai poster ici quand ça sera fait…
Here i got 90%. I managed to clean my code before begin to think about that last test. Like in the last difficult Vox Codei puzzle, i think the good way is eliminate max kill option if future win is impossible due to lack of bombs. But i’ll take some days to think about that because maybe there is a scheme to detect those situations… I’ll come back when finished.
This puzzle is very interesting
So, i tried a simple trick… and did 100%. Perhaps some tests are missing to disable this possibility…
Solved it using backtracking.
I started by discerning nodes’ movements, then built a parameter space. Then I reduced it to a manageable size by discarding points that I deem strictly worse than others. Then used backtracking to find the first valid solution that covers all nodes within available amount of bombs.
The trick is, of course, to reduce set of candidate solutions to a size solvable in 100ms.
The relatively clean way that I have found to handle this,
is to use the moving range of the node as a priority sorting weight.