My Last Chance! problem

general
1

how to use bfs in this LSCN Problem - CodeChef question?

2

That question is simply based on graph traversal! In this you can either implement BFS of DFS.

So at initial just store all the numbers reachable from that particular vertices i.e., all the prime divisor of number. for example. Suppose if we want to get connect all vertices(reachable numbers) from 60 then it will look like this 60-> 2, 3, 5.

But question ask for adding the divisor so we have to add then prime factors like 60-> 62, 63, 65

At last you have to perform all these operations for all values upto 1000. If you feel any difficult to know how to find all such numbers then you can refer this LINK or you can simply see this modified code.

const int SIZE = 1001;
vector<int>divisor[1001];
void factor() {
    for(int i=4;i<SIZE;++i) {
        int n=i;
        for(int j=2;j*j<=n;++j)
            {
            if(n%j==0)
            divisor[i].pb(i+j);
            while(n%j==0)
                n/=j;
        }
        if(n>1 && i!=n)divisor[i].pb(i+n);
    }
}

Now the question boils down to find a minimum path from A to B. Why?

As you can simply relate this as a graph which contain vertices number from 1 to 1000, connecting the path that are reachable from single vertex.

For this you can perform simply BFS or DFS. And get the final answer!

You can simply see my solution HERE
If you still feel any difficulty then feel free to ask again!

3 Likes
3

anno i have properly commented my code for your better understanding , if you still find any problem feel free to ask . My Solution
link text

1 Like
4

At last you have to perform all these operations for all values upto 1000? i am not able to understand this line.

5

I am talking about storing all divisor from 1 to 1000. See this for loop

 for(int i=4;i<size;++i)