codehacker4689_p's blog

Help needed for an interesting oa problem!
By codehacker4689_p, history, 15 months ago, In English

There is an undirected tree T, with edges of length 1. Initially, each of the nodes(1-indexed) stores a value equal to the node number. Shuffle these values among the nodes in such a way that no node stores a value equal to its node number.

There are two values to determine:

1.The minimum possible sum of the distances between the initial and final positions of all values.

2.The maximum possible sum of the distances between the initial and final positions of all values.

Example

T_nodes = 4

T_from= [1, 2, 3]

T_to= [2, 3, 4]

In the minimum distance shuffle, node values are switched with their neighbours. The distance is 1 +1+1+1=4. In the maximum distance shuffle, the distance is 3+1+1+3=8. Return [3, 8].

Constraints

• 1 ≤ T_nodes ≤ 1e5

• 1 ≤ T_from[i], T_to[i] ≤ T_nodes

• T_from[i] ≠ T_to[i]

Seen this in some recent oa and tried alot but not able to solve. Can anyone help please?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

So this is definitely a trie problem. Let's denote any random node n as the root. For each node that borders the root, you want to store its value in the trie. Make sure you assign proper edge weights in the trie. After this, you want to have a prefix sum s and a suffix sum t to sum up the values of the trie nodes. And then the answer to 1 will be the sum of s and t and the answer to 2 will be the absolute difference of s and t.

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

    Can you be little brief about how we store values in trie and do prefix & suffix sum. Thankyou!

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

      Inside of the trie, make sure the edge weights are assigned correctly according to the ratio of the order of the nodes' values in the original tree. This is important, as the value of our trie's vertex + its edges will be what's in our prefix and suffix sums. The prefix sums optimize our O((V + E)^2) solution to an O(V + E) solution, so neglect them if the constraints permit it. No problem, glad to help.

      → Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Interesting approach! not so clear how you know where to place each number and why it's optimal:/ sounds like the algorithm works for a fixed permutation, but how do we approach the one with maximum or minimum answer?

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

It's a quite hard problem!

→ Reply