You are not logged in. Please login at www.codechef.com to post your questions!

×

INLO23 - Editorial

PROBLEM LINK:

Practice
Contest

Author: RAVIT SINGH MALIK
Editorialist: RAVIT SINGH MALIK

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$: A graph Graph and a starting vertex root of Graph.

$Output$: All vertices reachable from root labeled as explored.

A non-recursive implementation of breadth-first search:


 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
 

$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$ :

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])

=>> $maxi$ is the required answer.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.

RELATED PROBLEMS:

asked 12 Oct '16, 23:00

ravit0001's gravatar image

5★ravit0001
346
accept rate: 0%

edited 02 Jan '17, 19:25

admin's gravatar image

0★admin ♦♦
19.7k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,629
×1,238
×505
×185
×17
×1

question asked: 12 Oct '16, 23:00

question was seen: 585 times

last updated: 02 Jan '17, 19:25