Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

sumantopal07's blog

By sumantopal07, 8 days ago, In English,

https://cses.fi/problemset/task/1195 to solve this problem i implemented dijkstra's and Dynamic Programming to decide whether to opt for coupon or not for each state transiton.But I'am getting TLE and not able to optimize my code. I think my approach is slow. Any suggestion please help. Here is william lin's code https://youtu.be/dZ_6MS14Mg4?t=13603 but i did't get his approach. If any one could explain what he did will be helpful

My Code
 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
8 days ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

Here's my approach...

-Firstly find shortest path from 1 to every node. (answers in array A)

-Then find shortest path from N to every node (on Inverted graph) which means finding shortest path from every node to N.(answers in array B)

-Then consdier each edge in graph , suppose you are applying discount on that edge... then if we can reach 1 to u and N to v (in short v to N) then ans=min( ans , A[u] + weight/2 + B[v] )...

  • »
    »
    7 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    @Kartik_Bhanderi

    Thanks for your input. I tried following your approach and wrote the following code:

    My code

    However, I still seem to get TLE on the majority of test cases. Is this only because I've implemented Bellman-Ford instead of Dijkstra or would you refactor my current code to be more efficient?

    • »
      »
      »
      7 days ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

      Brother , firstly put your code in spoiler properly. (for that choose spoiler and inside that choose block and place your code there...)

      like this

      And as you said you have implemented bellmen ford , whose time complexity is O(V.E) , so obviously it will result into TLE.

      And in our case we only need single source shortest path , hence no need to use bellman ford instead we can use dijkstra's algo.

      Hope it helps ;)

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Sorry about that; I've fixed the formatting now.

        And yes, I thought so too. Thanks for the confirmation. I'll try to learn Dijkstra's and implement it now!

»
8 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I got same aproach as yours, but use priority_queue instead of set. And I do not erase any extra element from the queue at any time. Just put new vertex on the queue whenever one of the dp-values becomes smaller.

Spoiler
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By adding negative values of DP you are priority queue work as min_heap?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, this is just to make the priority_queue.top() work like set.begin(), ie return the smallest element.

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is it safe to assume that set operations are more expensive than operations on priority queue?

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, of course, especially write access is more expensive. Same O(logn), but bigger constant factor.