Hey Competetive Programmers,
I need help from you guys. I am not very confident in topics like DP and Graph. I wanted to practice good quality questions which actually make my concept stronger and gives confidence to me that I can solve most of the questions on these topics and that's why I need suggestions from you guys.
Please suggest to me, How should I put my steps forward in these topics and what should be my approach.
Auto comment: topic has been updated by mr_cchef (previous revision, new revision, compare).
I've really enjoyed 1472G - Moving to the Capital. This one was my first solved 2100-rated problem. I found an easier solution for this than described in the editorial.
Let's notice that it isn't efficient to do anything after performing the second action.
Compute the distances from the capital to all the other vertices (use BFS). We'll keep answers in ans array. Then do DFS: if answer is already computed, just return it, else set ans[u] to dist[u], iterate through all the edges and compare the distances of u and v. If the distance from the capital to v is lower than from the capital to u, set ans[u] to min(ans[u], dist[v]), else go to v and set ans[u] to min(ans[u], ans[v]). Time complexity: O(n).
Code: 111341664
You can try solving problems in this site. There are some problems about graphs and dp.