ScienceGuy's blog

Help in easy problem
By ScienceGuy, history, 7 years ago, In English

Hi, can you please tell me the solution for this problem? http://codeforces.net/gym/101147/problem/E

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can build graph where edge (i, j) exists if |i - j| = d[i] or |i - j| = d[j].
This graph contains only O(N) vertices and edges.
Now you have problem 'find distances from every vertex to N in undirected unweighted graph'.
It can be solved by bfs from N to all other vertices of graph in O(V + E) = O(N).

→ Reply