Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

deepak_097's blog

By deepak_097, history, 4 months ago, In English,

What is the logic behind this to solve this problem ?

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

 
 
 
 

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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