Hello everyone,
I need help with the following problem E. Paired Payment.
I have read the tutorial but honestly I did not understand it much (maybe I am to blame for that), later I found a video by galen_colin on his youtube channel, the video link, He did an excellent job explaining problem E. However, he did not go into implementation details.
My question is:
- Is this some common technique used, if yes where can I read about it.
- How to plug these fake vertices into the graph and how to identify fake from original vertices? (I need the answer from implementation perspective)
- I also need similar problems to solve to strengthen my understanding with these kind of problems
I am looking for an answer, or maybe some blog where I can read about this technique more in details.
thanks in advance
You can just think of it as a form of dynamic programming, where the state is both the current node and previous edge weight. As far as implementation, just look at any submissions here. For example in my submission, dp[c][x] corresponds to the state of vertex c with previous edge weight x, and since all the edge weight is positive, the state when x is 0 corresponds to when an even number of edges have been taken, so you don't have to worry about the previous one. You can see you easily can then alternate between setting x as the previous edge weight and 0. Here is a similar problem.
1473E - Minimum Path is a recent problem which involves creating multiple copies of the same vertex to represent some additional states and finally using a single source shortest path algorithm to get shortest distances.