Can anyone explain me the bfs logic behind the problem Problem - B - Codeforces.
I can’t figure out why we should perform bfs here. Plz elaborate in detail.
Think about it this manner, you are given a graph with node0(initial value of this node is n), the graph contains edges from this node to two other nodes, lets say node1(with value as 2*n) and node2(with value as n-1). Now, these two nodes, each, have edges to two other nodes with cost assigned as twice and one less than that of their immediate parent. Now, you are supposed to find the shortest path (each edge costs you 1 unit to traverse it) from initial node to the final node whose value is m. Isn’t this the shortest path problem? That’s why we are applying BFS here.
Explaining first example, Create a queue of pairs as <int,int> where the first int corresponds to the value of the node and sec corresponds to the cost.
Initial Configuration of queue: (4,0)
then pop this, and push two other nodes, (8,1) and (3,1)
Pop (8,1) and push (16,2) and (7,2)
Pop (3,1) and push (6,2) and (2,2)
We get the node with our desired value :6 , so we stop here and return 2 as the answer.
PS: I assumed you know the basics of graph theory, that is why BFS gives the shortest distance in a graph whose all edges have cost as 1. In case, you don’t know, let me know in comments.
Thanks a lot for ur help.