PROBLEM LINK:
Contest link
Problem link
Practice link
Author: HITK Chapter
Tester: Ankur Kayal
Editorialist: HITK Chapter
DIFFICULTY:
Medium
PREREQUISITES:
Maths, DFS, Trees.
PROBLEM:
Given n nodes and each node having an electron and a node energy. Each node will have a change in energy and you have to find the final node position of each electron so that it will have the least energy possible.
QUICK EXPLANATION:
Run a dfs from the root node and keep storing the most optimal node energy-node number pair for each node.
EXPLANATION:
First, we will calculate the final energy of each node. This can easily be done using the Sieve of Eratosthenes and we will pre-calculate the nearest prime number less than or equal to every number.
Now, we will run a dfs from node 1. After the dfs call, we will store the minimum energy value encountered so far for each node. Also, we will store the node number having that minimum energy. We will store both of these variables in a list of pairs. Now, sort the list of pairs and the first element of the list will contain the information of the most optimal node.
Now, we can calculate the final answer for each electron by storing the final node position and the absolute energy difference for each node in an ans array, that electron will finally jump to the most optimal node in its subtree.
Also during returning, we will return the minimum value and that node number to its parent. This way, each node will transfer the pair to each of its ancestors and each node will have the information of the most optimal node present in its subtree with minimum energy.
Note that there can be a scenario when the electron is already present in the most optimal node, so in that case, the node position will remain same and the final energy may or may not change(depending on the initial energy of that node is already prime or not).
Time Complexity : O( Alog(log(A)) + nlog(n) )