Electr0's blog

What is the time complexity of this solution??
By Electr0, history, 3 years ago, In English

problem link 339C - Ксюша и гири

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!!

  • Vote: I like it
  • +23
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

You don't need tk "check" all paths. You should use BFS or something that finds just one path.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    But in BFS we have to maintain a queue. And after a few levels of BFS, the length of the queue will become very large.
    For example what i think is that the above graph would be a tree. And the root node or the starting node will be (0,0,1) and then from this node we will have 9 outward edges to nodes like (x1,y1,1), (x2,y2,1)...... And then from each of these nodes we will have 9 outward edges to a total of 81 nodes like (x1,y1,2), (x2,y2,2)..... So after some iterations of BFS to queue size will become very large. But according to the editorial the BFS/DFS solution would give AC. So that means i am wrong somwhere but cant find where?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      In BFS algorithm, each vertex of the graph will be pushed to the queue at most once. Even though each vertex can have up to $$$9$$$ outward edges, most of them will lead to the vertices that represent "bad" states, i. e. states where some of the conditions are not fulfilled. We can just ignore these edges and estimate the number of vertices that represent only "good" states; and this is something like $$$100m$$$ since in each "good" triple $$$(x, y, z)$$$, $$$x$$$ should be from $$$1$$$ to $$$10$$$, $$$y$$$ should be from $$$1$$$ to $$$10$$$, and $$$z$$$ should be from $$$0$$$ to $$$m$$$.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yes i think you are correct. I was overestimating the number of nodes. The actual number of nodes would be a lot less. Thanks everyone for helping!

        → Reply