### pks18's blog

By pks18, history, 3 years ago,

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.

• +6

| Write comment?
 » 3 years ago, # |   +6
•  » » 3 years ago, # ^ |   +8 Thanks. This is a new topic for me. I need to learn it first. Thanks for the link.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 This works for offline queries. What about online queries? What concepts / algorithms should I read about to understand that better? Is centroid decomposition or dynamic connectivity applicable here?
•  » » » 3 years ago, # ^ |   +5 You can reduce task to find path from sourse to destinataion with minimal maximum edge on the path and check if this value is less than or equal to w.Minimum spanning tree guarantees you path with minimal maximum edge on path. So,1) Find MST (minimum spanning tree) and build LCA on this tree.2) For each query find maximum on path from source to destination using LCA and check if value is less than or equal to w.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +13 Wow, first time I'm thinking about using MST this way. Always problems ( that I have seen ) that require MST just ask for the min cost of MST.Is there a proof that I can read for Minimum spanning tree guarantees you path with minimal maximum edge on path?I thought, MST just meant that total sum of edge weights will be minimum and it's a tree connecting all vertices.UPD: After thinking about it for a bit, I realise that we use this fact already in Kruskal's algorithm, when we just sort by edge weights and add edges if possible.Good and easy proof for Kruskal's algo, if anyone is interested after reading the comments: Proof
•  » » » » 3 years ago, # ^ |   0 That helped a lot! I got another problem which gives the same feeling as this one but I am not sure how LCA will be helpful here. The problem is as follows:-You are given a undirected tree with v vertices where each node has a specific weight given as an array. We need to answer q queries. Each query consists of source and destination and a number w. For each query we should return the number of nodes having weight of at most w in the path from source to destination.Constraints:- v,q <= 2*10^5Any ideas about this one?
•  » » » » » 3 years ago, # ^ |   0 Again, the offline version is pretty easy, keep adding edges in order of increasing weights, and store answers on the way. To answer the queries, you can flatten the tree using Euler tour, and build a segment tree / Fenwick tree on it. Initially, the value of all edges is $0$, when you add the edge, make the value $1$, and you just need segment tree / Fenwick tree for range sum queries.
•  » » » » » » 3 years ago, # ^ |   0 I just finished reading about segment trees and LCA. But I am still not sure what function are you using for building the segment tree. Because we need the number of nodes having weight less than equal to w. Could you expand a bit on that part?
•  » » » » » » » 3 years ago, # ^ |   0 If you understand the offline algorithm, then it's straightforward. You have $2$ types of events, query events and update events. Each node weight is an update event, and assume initially all nodes have $0$ "value". We will use term "value" for the value you store in the segment tree for a particular node.When you get query events, you just calculate range sum on segment tree you have prepared. You get the indices for the query from euler tour, because you need to split the path in two parts, paths from both vertices to their LCA.When you get update events, you update the segment tree at the index corresponding to the node. Initially the "value" of the node was $0$, and then you update segment tree to make the "value" $1$.
 » 3 years ago, # |   +13 HintPut both the edges and queries into one array and sort them by weight/width.
 » 3 years ago, # |   +1