pks18's blog

Strange problem in Google Online Challenge
By pks18, history, 4 years ago, In English

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.

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

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

https://codeforces.me/blog/entry/82071#comment-688118

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks. This is a new topic for me. I need to learn it first. Thanks for the link.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +13 Vote: I do not like it

        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

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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^5

        Any ideas about this one?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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$$$.

              → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it
Hint
→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Found a similar problem

→ Reply