Editorial for JDCC '16 Contest 2 P4 - Pokemon Woes


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: atarw

First, calculate the distance between each pair of Pokemon present on the map, as well as Ash's home to each Pokemon, and store this in an array. Distances can be calculated using this formula: \(\lvert x_1 − x_2\rvert + \lvert y_1 − y_2\rvert\), where \((x_1, y_1)\) and \((x_2, y_2)\) are two coordinate locations.

Next, we must try out various orders in which Ash can visit all the points, and choose the one which gives the minimum total distance. This is done using DFS, where the parameters passed in are the current location of Ash, and the Pokemon locations that have already been visited.

To speed this up, use dynamic programming to store results calculated by the DFS. To do so, the Pokemon locations that have already been visited can be represented in binary, with the \(i^{th}\) bit being a \(0\) or \(1\) to represent whether or not the \(i^{th}\) Pokemon has already been visited.

Time Complexity: \(\mathcal{O}(N^2 + M2^M)\), where \(M\) is the number of Pokemon on the map.


Comments

There are no comments at the moment.