i_love_sqrt_decomp's blog

Is there any general algorithm?
By i_love_sqrt_decomp, history, 12 months ago, In English

Is there an algorithm that solves this problem for any $$$k$$$? https://mirror.codeforces.com/problemset/gymProblem/101806/X.

Any complexity is allowed, if it solves the problem for $$$k\leq5$$$ with the original constraints.

Spoiler
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
12 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Can't we just check all the simple paths of length K emerging from the vertex 1 and ending at the Vertex n. Since k <= 5, I think this should pass for n and m even going upto 1e6.

Please correct me if I am wrong.

→ Reply
  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Consider a graph where the edges are split into 5 layers, with the first layer being $$$1$$$, second layer $$$2$$$ to $$$\frac{n}{2}-1$$$, third layer $$$\frac{n}{2}$$$, fourth layer $$$\frac{n}{2}+1$$$ to $$$n-1$$$, fifth layer $$$n$$$, and edges between all pairs of vertices in consecutive layers. There would be $$$O(n^2)$$$ possible paths from $$$1$$$ to $$$n$$$, all length $$$4$$$.

    → Reply