Please help me with this question!!

[kimchiboy03]

Problem link: https://train.nzoi.org.nz/problems/642

Currently, I am working on this problem and I cannot find a way to solve it.

The current method that I have tried was:

1) Find the distances from the initial point to the other points
2) Jump to the peg with the smallest distance which is smaller than the maximum distance
3) Set the new peg as the initial peg
4) Repeat until no more pegs can be reached

Can someone please tell me how you would have solved this problem?

Thanks in advance.

[dhayden]

This is basically the "shortest path" problem in graph theory. Each node is a peg. Edges lead from each peg to the other pegs that can be jumped to. The cost of each edge is 1.
- Construct the graph. You'll want to do some optimization to avoid having to check whether each peg can be reached from each other peg.
- Run the shortest path algorithm. See https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
- Find the highest node and use the shortest path to that node to answer the problem.

[ne555]

given that all the costs are the same, you may use https://en.wikipedia.org/wiki/Breadth-first_search instead of dijkstra.

computing all the distances is O(n^2), not a problem until subtask 5. but as d=1, there you may simply check if the neighbour peg exists

peg(x-1, y)
peg(x+1, y)
peg(x, y-1)
peg(x, y+1)

> Jump to the peg with the smallest distance
¿why the smallest? you are trying to minimize the jumps
however, a greedy algorithm will not work

[kimchiboy03]

@dhayden @ne555 Thank you for your replies! I will try both methods and see which one works the best.