Boring_Day's blog

How to solve this easy problem? Easy problem Discussion blog [easy but interesting problem]
By Boring_Day, 23 months ago, In English

You are given a tree. Each node has a value. You need to choose three distinct paths in the tree. Let's suppose that

P1= sum of path 1, p2 = sum of path 2, P3 = sum of path 3

Print minimum and maximum possible value of

|P1-P2| + |P2-P3| + |P3-P1|

Constraints 3<= n <= 2e5

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

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

I'm sorry, I'm not qualified to solve this easy of a problem. Please show me how to solve it.

→ Reply
»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I'd say that because we compare all 3 paths, that we can assume that P1 >= P2 >= P3. Now if we work out the absolute values we get P1 — P2 + P2 — P3 + P1 — P3 = 2*P1 — 2*P3.

In order to solve this, we need to "block" each edge (one at a time, this edge is the path with minimum sum) and find the maximum path in the 2 created trees. With DP this should be doable in O(n). As for path number 2 I guess it's allowed to have an empty path?

Or if it's not, we can then use an unused edge in the trees for that path or take one greedily from the maximum sum one (with an extra check for both ones)

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    p1 is maximum sum path, and p3 is minimum, which means we can take any other path since its sum will always be less than p1 and greater than p3 (or equal)

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Will this work for minimum possible value?

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It won't work for the minimum possible value, and I still have no idea how to properly do it. I will let you know if I have an idea

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

    I just cant wrap my head around how you made the P2 just disappear into thin air.

    If your approach is indeed correct, Maths make me feel WTF

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      The most important part is that we compare each pair of paths (you can check it easily for all possibilities, for example take P2 >= P1 >= P3). And when you work out the absolute values (which is possible since we now know the relative sums of the paths).

      Also when we do the second part, it should be clear that when we take the minimum edge for P3 that this will remain the minimum. Now to see that P2 can't be bigger than P1: Let's say that there is an edge left with a weight C. Now, if this edge is bigger than P1, then we didn't take the maximum path for P1 and thus this is a contradiction, so P2 will indeed be smaller ( or equal, but that's ok).

      In many problems where you want to minimize or maximize a certain equation this "technique" is used to reduce the problem to easier subproblems.

      → Reply