tag:blogger.com,1999:blog-4115025577315673827.post1492767315297024688..comments2020-05-20T14:21:54.596+05:30Comments on CSE Blog - quant, math, computer science puzzles: Snakes and Ladders OptimizationPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-4115025577315673827.post-79081810178854899252013-10-20T21:38:02.263+05:302013-10-20T21:38:02.263+05:30I would say it seems like an application of Djiktr...I would say it seems like an application of Djiktra's algorithm with source as 0 and destination as 100. Considering every move as unit cost, we just have to find the shortest path... And everything needed is given as input hence we have a graph with edges and weights. Kushagrahttps://www.blogger.com/profile/11664824535535246894noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-28285408333977754092013-02-04T17:15:09.443+05:302013-02-04T17:15:09.443+05:30Its not a DAG as graph is not acyclic!Its not a DAG as graph is not acyclic!Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-83177473174933037052012-12-26T20:11:04.926+05:302012-12-26T20:11:04.926+05:30this question also came during flipkart hiring pro...this question also came during flipkart hiring process at other IITs , i also thought it was a DAG, but one can easily form a cycle here using a snake ,plus the edge weights were different so went with dijkstra later , (however wasn't able to code dijkstra during the time limit , so had to contend with BFS code which wasnt giving full score :/ ) dantehttps://www.blogger.com/profile/08618984400645995854noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-36156896568039355642012-12-26T13:24:28.523+05:302012-12-26T13:24:28.523+05:30DAG, with each number as a node. A number x is lin...DAG, with each number as a node. A number x is linked to x + 1, x + 2, .. x + 6 with edge 1. A number with snake's head is linked only to the snakes tail with edge weight 0. A number with ladder's tail is linked only to the number with ladder's head with weight 0. <br />BFS with destination = final point.<br /><br />Maximum number of edges from a vertex = 6. At worse, I travel each edge exactly once. So, at definitely it is O(n). Although, I am reasonably sure, the complexity in this case will come out to be much lesser.Pratyush Rathorehttps://www.blogger.com/profile/14085124243567744668noreply@blogger.com