What is the time complexity of this solution??

Revision en1, by Electr0, 2021-11-17 11:57:47

problem link 339C - Xenia and Weights

The editorial of this problem tells us to make a graph of nodes where each node is a tuple (i,j,k). And after making this node we have to find a path from (0,0,1) to some node (x,y,m). Now according to the question, this graph is acyclic and directed. And each node can have 9 outdegree (there are 10 weights to select from but we cant select the previous weight). And the length of the path is m<=1000. Now i cant find a way to find the path from (0,0,1) to (x,y,m). Because i think there can be 9^(1000) possible paths. How to prove that the number of paths we have to check will actually be less so that we dont get a TLE. Please Help!!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Electr0 2021-11-17 11:57:47 718 Initial revision (published)