Lakh's blog

By Lakh, 3 years ago, In English

I was asked this problem in one of the interviews :

Given an undirected graph with N nodes and M edges. Each node is initially having some value A[i]. We are also given a number K.
Now in one operation we can take one of the edges and increment the value of the 2 nodes linked through that edge by K.
I have to find minimum no. of such operations to make value of all nodes in the graph equal or -1 if it is not possible.

Wasn't able to come up with any optimized approach. I was thinking to start with node having minimum value since in order to minimize the operations we should do as less operations as possible on maximum value node. But still not able to reach any correct approach.

Constraints : Not available . Please help if you have some other way to solve this problem.

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Same question with slight variation

1537F - Figure Fixing

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Wow seems interviewer got inspired with this hard problem :) Thanks a lot for sharing the problem.

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

      I don't think the problem in your case is not as difficult as the problem above. as the value of k is fixed. You can uniquely determine how much to increase each node. You just have to make sure it is possible.. If it is possible ,Then the answer is simply half the sum of number of times each node have to be increased.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        But in my case we also don't know the target value that we have to achieve for all nodes in graph

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

          You can think of it like this.. first of all check if every node value % k is same or not, if it is not same, the answer is "NO", otherwise the target value for all node is the max node itself. After this the problem is same as mentioned above.

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

            What if the graph is like a linked list with a node between two nodes having equal values.
            Example
            $$$3$$$ <-> $$$2$$$ <-> $$$3$$$ and k=1 How can we solve a case like this?

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Select 3<->2 do +1 => 4<->3<->3 now select 3<->3 do +1 => 4<->4<->4

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

                I was asking about how to predict the maximum values of a node for such a graph. According to tiasmondal the maximum value of a node after the operations have been performed would be equal to the value of maximum node before performing the operation. But that is not the case here.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                  Rev. 2   Vote: I like it -11 Vote: I do not like it

                  It should be either the max value or the max value+k (you should see which option it is based on the fact that what you need to add in total should be dividable by 2k)

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

                  What if there's an edge between every 2 nodes, $$$n=4$$$, $$$k=1$$$ and the initial values are $$$0,4,5,5$$$? Then clearly you have to make all nodes equal to $$$7$$$(which is not "either the max value or the max value+k").

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

                  ok my bad. Seems like my idea is wrong :(

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Just wondering why I am getting downvotes for discussing the solution for an interview problem :)