Editorial for Baltic OI '11 P4 - Treasures and Vikings

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.

$\mathcal O(NM(N+M))$ ~\mathcal O(NM(N+M))~ Solution

With a bread first search (BFS), it is calculated how many rounds the Viking ship uses to get to any sea field. From every field you get to in the BFS you will go horizontally and vertically (from this field) and note that the Viking can see these fields at the time they get to the first field. Since there are $NM$ ~NM~ fields, and there are at most $N+M$ ~N+M~ fields that are horizontal or vertical to a given field the running time is $\mathcal O(NM(N+M))$ ~\mathcal O(NM(N+M))~.

Then make a BFS again, this time starting from the Y-position, so that you will find all fields you can go to before the Viking can see them. Then just check if you can reach the treasure. This takes $\mathcal O(NM)$ ~\mathcal O(NM)~ times since there are $NM$ ~NM~ fields, so the total running time is $\mathcal O(NM(N+M))$ ~\mathcal O(NM(N+M))~.

$\mathcal O(NM)$ ~\mathcal O(NM)~ Solution

The solution is based on the same idea. Initially: Find all "horizontal sea pieces", i.e. every sequence of horizontally aligned sea fields which have island fields (or the end of the map) to the left and to the right. When you do the BFS then every time you go horizontally to note that the Viking can see the fields, just store that the Viking can see this piece. Do the same vertically and you only check each field twice giving a running time of $\mathcal O(NM)$ ~\mathcal O(NM)~.

Comments

There are no comments at the moment.