Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Help needed for an interesting oa problem!

Revision en5, by codehacker4689_p, 2023-09-30 11:01:33

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English codehacker4689_p 2023-09-30 11:01:33 2 Tiny change: '_nodes ≤ 105\n\n• 1 ≤' -> '_nodes ≤ 1e5\n\n• 1 ≤'
en4 English codehacker4689_p 2023-09-30 09:23:27 358
en3 English codehacker4689_p 2023-09-30 09:02:39 22 Tiny change: ' values.\nSeen th' -> ' values.\nConstraints: n<=1e5.\nSeen th'
en2 English codehacker4689_p 2023-09-30 08:13:43 57
en1 English codehacker4689_p 2023-09-30 06:31:29 576 Initial revision (published)