Strange problem in Google Online Challenge

Revision en2, by pks18, 2020-09-05 12:23:05

I recently (almost a week ago) gave Google's Online Challenge. There was an interesting problem in Graph Theory stated as follows:-

You are given an undirected weighted graph of n vertices and m edges. There are q queries where each query consists of a source, a destination and a weight w. For each query print ‘1’ if there exists a path from source to destination where each edge in the path has a width less than or equal to w.

Constraints:-

n,m,q<=10^5

The constraints were particularly interesting. For a beginner like me, I couldn't think of anything but a brute force solution of BFS with a restriction that the edge weight should be less than w. Clearly, this O(V+E) for each query and quickly goes into a TLE once number of queries becomes large enough. So, how do we solve this problem? Even precomputing looks difficult because each query had a different value of weight w. So, how do we solve it? I have a feeling from the constraints some kind of log factor must come into picture but I am unable to determine what would be helpful.

Any clues, algorithms or ideas will greatly helpful. Thanks in advance.

Tags #graph theory, #bfs, #google

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English pks18 2020-09-05 12:23:05 8
en1 English pks18 2020-09-05 12:15:21 1173 Initial revision (published)