What is the logic behind this to solve this problem ?

problem link (https://www.spoj.com/problems/PPATH/)

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | OO0OOO00O0OOO0O0…O | 3280 |

3 | Syloviaely | 3274 |

4 | Um_nik | 3248 |

5 | Petr | 3233 |

6 | fateice | 3230 |

7 | mnbvmar | 3096 |

8 | anta | 3053 |

9 | FizzyDavid | 3050 |

10 | LHiC | 3047 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 161 |

2 | tourist | 160 |

3 | Radewoosh | 159 |

4 | Petr | 153 |

5 | csacademy | 151 |

6 | Swistakk | 148 |

7 | Vovuh | 145 |

7 | Um_nik | 145 |

9 | Nickolas | 142 |

10 | PikMike | 140 |

What is the logic behind this to solve this problem ?

problem link (https://www.spoj.com/problems/PPATH/)

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/16/2018 11:49:50 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

There are only 1061 4-digit primes. Generate a graph with each vertex representing one of these primes. Add edges between two vertices if we can move from one vertex(prime) to another with a cost of 1.

Notice that there can be atmost 39 edges per vertex so the number edges is O(n). Then, since the number of test cases are small and the cost for each edge is same, a simple bfs from the initial prime as the root should do the trick for each test case.

Yes i did in this way and got AC. Thnaks for the reply. Sorry for the downvote it was done by mistake.