-VIBE's blog

CSES Flight Discount

By -VIBE, history, 9 months ago, In English

Was solving this Cses problem from graph section.I came up with a dp approach for this but getting wrong answer on three testcases.Can anyone help me in where i am going wrong. Here is my submission

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Flight discount is a template problem for this algorithm:

algorithm

I can't open Ideone links, could you use another method of sharing such as linking to your submission on cases or posting to Pastebin?

Given that the intended solution is the algorithm above, I'm not sure how you can solve it with a dp approach, but I am really interested to see your approach!

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

    here

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

      Thanks a lot!

      Looking at your program, it seems like you have a 1d DP where you try to find the min cost between using the coupon at that node and not using the coupon at that node.

      One immediate problem I see is how you are managing the visited array. There may be multiple paths to any given airport, but you only allow yourself to visit an airport once. Therefore, your DP solution breaks because, at any given node, you do not know the shortest path to that node, nor the shortest path to the final node.

      There are a few other problems, but we can work on this one first.

      → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your dp fails at this case

0 1 100
1 2 10
2 3 1
3 4 1
4 2 1
1 4 1
3 5 1

do[4][0] will be 1e18 instead of 3. Your dp fails on cycles, such as the example I gave. You need to run Dijkstra's algorithm to solve this problem. CP algorithms has a very good tutorial on it.

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

    His code may be wrong, but the test case you gave is running perfectly fine.

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

      It's numbered from 0 to n-1, but the problem gives numbers from 1 to n. If you add 1 to every element, his code outputs 62, which is incorrect, since there's a path that costs 54. Here's the fixed test case:

      6 7
1 2 100
2 3 10
3 4 1
4 5 1
5 3 1
2 5 1
4 6 1

      Here's an illustration fo the graph. You use the coupon on the edge from 1 to 2, then follow the path 1, 2, 5, 3, 4, 6.

      Image
      → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission getting TLE on Test 18 can someone help me with my code where can I optimize this code submission

mySubmission
→ Reply