Its actually a pretty common idea for directed acyclic graphs to run some dp on them via dfs.

You can solve Problem C using dp on this DAG. Every DAG has Topological Orders,and we can use an order for our dp.

Is it about the third part of editorial? If yes:

The sequence we consider doesn't change a because we assume that if we change a when it's minimum, we won't come to the optimal answer (and we can't change it at all after that moment because the order of operations doesn't matter). So we show that if we hadn't changed a, our answer will become worse than if we changed it, so our assumption was wrong and changing a will lead us to optimal answer.

Its a good proof but needs a few clarifications to make it technically right. It's not true that the maximum decrease in |prod| occurs for min |a|. Say our set is {2, 5, 10}. Say x = 10. Clearly here a = 2 and if we decrease 2 by 10 we get the |prod| as 400 where as we would have got |prod| = 0 by choosing to decrease 10.
Lets build on your proof to justify why your algo works correctly. If prod is +ve: If a >  = 0, if x <  = a then clearly |prod| should be decreased as per the formula. if x > a , x — a will make the product most -ve hence we choose a even though |prod| may actually increase, prod we definitely decrease the most.
if a < 0 Note that the if x <  = |a| then prod must decrease for which we add to a if x > |a| then changing of sign is possible hence the most new prod can be obtained by choosing a and adding x to a. We can follow similar arguments for other cases as well.

Brilliant solution

here are the links, thanks for your solution 21041800 21104290

The complexity is O(M*N) where N is vertices and M is edges. The Idea was to run dp on DAG , which can be done with dfs in general. Here is Code

No, you can do topological sorting first. See solution http://mirror.codeforces.com/contest/721/submission/21117607

There are six words whose lengths are less than or equal to the real password, and k = 5, so there is one penalty in the worst case.

I don't think so. D requires more proving and is easier to write bugs. C is fairly straightforward DP, if you know what the solution might look like, although it took me 10 or more submissions ;D

for p ≥ 100 , let's denote dp[i] as the minimum distance it can sing up to i songs and you are now dealing with some of the segment, let's see how it can affect the answer.

For the right point of the current segment — r, you can sing at most (r - l) / p songs, now iterate through 1 to (r - l) / p, meaning you want to sing these much songs.

Say, you want to sing j songs in this segment, then, your last songs must be sung before r - j * p - t(why not r - j * p ?).

Then, you want to find maximum i, where dp[i] ≤ r - j * p - t, meaning that you can sing at most i + j songs in this segment if you want to sing j songs in this segment, which should update dp[i + j]

However, there's another problem. Will this affect answers to dp[k + j] where k < i ? The answer is no. To illustrate this may require some efforts, but I suggest that you may compare the two cases when you are singing j songs and j - 1 songs, the key to the prove is that for any s, dp[s] - dp[s - 1] ≥ p.(This part will be tough, and I don't think I can convince you by typing here, drawing a picture may help)

Then finally, you may get code like this:

for segment s
  (l, r) = s
  for j from 1 to (r - l) / p
    find maximal i where dp[i] <= r - j * p - t
    update(dp[i + j])

as j travel through number of songs, so it won't exceed L / p, and finding the i could take O(log(L / p)) if you use binary search. So the complexity is

wrong answer Path must end in vertex 1000

For test 13: the input is basically:

10 10 8
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
1 9 2
9 10 1

Since (1,9) is longer than (1,2), you go through path 1-9-10 first, with total distance of 3. now par[10] = 9, par[9] = 1.

Then you try (1,2). You go all the way through 1-2-3-4-5-6-7-8-9, but you can't reach 10 because total distance from 1 to 9 is already 8. So, supposedly, you discard the path.

But what really happens is that this failed try set par[9] = 8, par[8] = 7, ..., breaking the once-correct path 1-9-10. So now we have 1-2-3-4-5-6-7-8-9 + 9-10, whose total distance is 9.

To fix this, just store par[] in the pq instead of using a global array. This way you can have a path tree instead of everybody sharing a global path record.

At first I thought your algorithm was wrong, but after some rethinking, I wonder if it's actually correct. Correct me if I'm wrong: we try longer path before shorter path, so that we don't have to layer the graph. What I'm still confused about is:

1. can you / how do you make sure a longer path like a-b-c-d-e-f-g-h (weight of each edge is 1 => total 7) is not "pruned" by a shorter path like a-i-h (weight of each edge is 2 => total 4)?

2. you may need to change len[v] <= len[u] to len[v] <= len[u] + 1 so that if there is a new path with same hops but takes less time, we take that path instead.

Your state of DP is exceeding the array bounds. You have taken (node, time) taken as state and rather it should be (node, no.ofedges). Because Time is very large here  <  = 10⁹, so it cannot be a parameter for the state.

I was looking for something like this. Thanks a lot :)

In C, why am i getting TLE on test case 7?? https://mirror.codeforces.com/contest/721/submission/87456309 Please Help!!!

If you understood plz explain Cant understand why my code is giving MLE on test case 8 238429202 <-my code