# INLO23 - Editorial

#PROBLEM LINK:
[Practice][111]
[Contest][222]
**Author:** [RAVIT SINGH MALIK][4444]
**Editorialist:** [RAVIT SINGH MALIK][6666]
#DIFFICULTY:
MEDIUM-HARD
#PREREQUISITES:
BFS , GRAPHS
#PROBLEM:
F(x,y) is a function which determines the performance of the super-computer.
Here (x,y) is that pair of processes (y is always a sub-process of process x) where the difference between the factors of process x and process y is maximum.
You are required to find maximum value of G(x)-G(Y) .
#EXPLANATION:
This problem is completely based on Breadth-first search [BFS], which is used to traversing or searching tree or graph data structures. It starts at the tree root
(or some arbitrary node of a graph, sometimes referred to as a 'search key')
and explores the neighbor nodes first, before moving to the next level neighbors.
$Pseudocode$ : ~~
Input: ~~
$Input$: A graph Graph and a starting vertex root of Graph.
~~Output: ~~$Output$: All vertices reachable from root labeled as explored.
A non-recursive implementation of breadth-first search:
<pre><code>
1. Breadth-First-Search(Graph, root):
2.
3. for each node n in Graph:
4. n.distance = INFINITY
5. n.parent = NIL
6.
7. create empty queue Q
8.
9. root.distance = 0
10. Q.enqueue(root)
11.
12. while Q is not empty:
13.
14. current = Q.dequeue()
15.
16. for each node n that is adjacent to current:
17. if n.distance == INFINITY:
18. n.distance = current.distance + 1
19. n.parent = current
20. Q.e
</code> </pre>
$Time and space complexity$.
The time complexity can be expressed as $O(|V|+|E|)$, since every vertex and every edge will be explored in the worst case.
|V| is the number of vertices and $|E|$ is the number of edges in the graph. Note that $O(|E|)$ may vary between $O(1)$ and $O(|V|^{2})$, depending on how sparse the input graph is.
So,the given question is an improvisation of Breadth-first search [BFS], you have to just store the maximum difference
of parent to its every childern. and store the maximum value between the parent and child at the child node.
$Pseudocode$ :
<code>
while(!q.empty())
int s=q.front()
q.pop()
int size=adj[s].size()
for( i=0 ;i < size ; i++)
int num = adj[s][i]
if(visit[num]!=true)
visit[num]=true
if(maxi < a[s] - a[num])
maxi = a[s] - a[num]
if(a[s] > a[num])
a[num]=a[s]
qu.push(adj[s][i])
</code>
=>> $maxi$ is the required answer.
#AUTHOR'S AND TESTER'S SOLUTIONS:
Author's solution can be found [here][333].
#RELATED PROBLEMS:
[111]: https://www.codechef.com/problems/INLO23
[222]: https://www.codechef.com/INLO2016/problems/INLO23
[333]: https://www.codechef.com/viewsolution/11795581
[4444]: http://www.codechef.com/users/ravit0001
[6666]: http://www.codechef.com/users/ravit0001