Author: | Bohdan Feysa |
Task preparation: | Bohdan Feysa |
Editorial: | Bohdan Feysa |
Block : n,m\le 100:
For the first block of our task we will be iterating through every possible answer (1\le k\le n), create a matrix n\times n and check whether there is a path from to which does not contain any cells closer than to any tourist traps. This results in O(n\cdot(n^2+m)) time complexity.
Block : n,m\le 10^3:
For the second block of this task we will preserve the technique of constructing the matrix, but instead of iterating through every possible answer we will use binary search to find the biggest possible s.t. there is a path from to which does not contain any cells closer than to any tourist traps. This results in O(\log{n} \cdot(n^2+m)) time complexity.
Block : n\le 10^3:
This block has the same solution, but here we need to use BFS from all tourist traps to mark all cells that are closer than to any tourist trap. This results in O(\log{n} \cdot(n^2)) time complexity.
Block : either x_1=x_2=\dots=x_m or y_1=y_2=\dots=y_m:
This is a block in which we could use a formula to try and pass from to between each pair of closest tourist traps. Time complexity is either O(m\log{m}+m\log{n}) or O(m\log{m}+m).
Block : full solution:
We will create a graph out of m+4 vertices. Each of the first vertices denotes a tourist trap. Other vertices denote borders of the matrix.(m+1 - top,m+2 - left,m+3 - bottom,m+4 - right)
We will create an edge between a pair of first vertices if there is no path from to which passes between these two tourist traps while not passing through any cell which has distance from it to a tourist trap less than . Also, we will try to connect the first vertices to the other : if that tourist trap is closer to the border than , then we add an edge. Now, if there is a path from m+1 to m+2 or from m+1 to m+3 or from m+2 to m+4 or from m+3 to m+4, then there is no way to go from to with given .
Total time complexity O(m^2\log{n}) which passes nicely.