xagofes's blog

By xagofes, history, 5 years ago, translation, In English

There is a grid of size N * N. Each cell of the grid contains a magic positive integer. The distance between two cells is equal to the sum of the magic numbers in these cells and the Euclidean distance between these cells. Among all these cells, the R cells are painted red and the G cells are painted green. For each green cell, we need to find such a red one that there is no other red cell, the distance to which is less.

512 <= N <= 4096

1 <= R + G <= N * N

Is it possible to make it better than O(G * R)?

If there were no magic number in the cells, it would be Nearest neighbor search problem.

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by xagofes (previous revision, new revision, compare).

»
5 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

It seems like some structures for finding the nearest neighbor allow using custom metrics to calculate the distance. For example, Ball tree .

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Unless I'm misunderstanding the problem, a simple BFS should be sufficient, finding the shortest path on an unweighted graph from multiple sources. Run BFS using every red cell as a source. To account for the "magic numbers", only add each red cell to the queue once the smallest distance currently in the queue equals its "magic number". Runs in O(N*N) which appears to be the expected running time for N <= 4096.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    In this problem distance between two sells is equal to Euclidean distance ( +  smth). not Manhattan distance. So usual BFS does not work