why this problem is in beginner section??
5 Likes
Can someone help me and tell me what’s wrong with any of the answers for this solution? I tried with my own random test cases against the solved ones but it shows WA everytime.
why this problem is in beginner section??
why this problem is in beginner section??
i thought you can visit y from x if the difference between their special numbers were <=k ,and found a soln , and got wa on all cases. Now,that i read the question properly its the y-x<=k condition -_- . Spent more than 2 hours for nothing .
The problem states that “you can move from the X-th street to the Y-th street if and only if 1 <= Y - X <= K” but the Editorialist’s Solution (Java code) accepts the follow instance: N=4, K=2, A = {3, 9, 11, 13} and gives the result 351. If I understood the problem well, this instance should not produce results. Is there something I’m misunderstanding?
/* Shotest path in DAG problem, with order O(E) solution. /
/ Weights are in product, but log() linearizes it. /
/ MinCost(i, j) = MinCost(i, k) + MinCost(k + 1, j); k <= K upto j.
/* Edges are in the order of N * K since, the number of edges from a given Node say ‘a’ is atmost K. N nodes, K per node. */
/* Shortest path in DAG problem, with order O(E) solution. /
/ Weights are in product, but log() linearizes it. /
/ MinCost(i, j) = MinCost(i, k) + MinCost(k + 1, j); k <= K upto j.
/* Edges are in the order of N * K since, the number of edges from a given Node say ‘a’ is atmost K. N nodes, K per node. */