Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | fateice | 3337 |

3 | Um_nik | 3292 |

4 | OO0OOO00O0OOO0O0…O | 3280 |

5 | Syloviaely | 3274 |

6 | Petr | 3223 |

7 | Swistakk | 3105 |

8 | mnbvmar | 3096 |

9 | yosupo | 3091 |

10 | dotorya | 3081 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 164 |

2 | tourist | 161 |

3 | csacademy | 153 |

4 | Petr | 150 |

5 | Swistakk | 148 |

6 | Um_nik | 144 |

7 | Nickolas | 142 |

7 | Vovuh | 142 |

9 | BledDest | 138 |

9 | PikMike | 138 |

9 | matthew99 | 138 |

9 | Errichto | 138 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round #374 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/20/2018 13:33:00 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

can anybody help me with problem C. how will i come up with such a solution...

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

Can you explain the common idea in more detail ? Please It would be very helpful for us :)

I agree, this is pretty confusing on first look for people that are meeting with DAGs and DP in general but there is also another solution that involves Bellman Ford algorithm..Check this Answer

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

How do I get the idea of using topological sort for dp?

Solve problems!!! If you can't get the solution then read editorial and ask people. Try 645D - Robot Rapping Results Report it's similar idea, but more complicated because it involves some binary search.

DP has a nature that if we want to know the answer of this situation, we must be aware of the situation and answer before it. What amazing is, topological orders have the same nature. I will think about the topological order as soon as I have confirmed that the graph is a DAG.

Problem D.

I missed something or looks like you assume that the optimal sequence doesn't change

aat all, that's not true.Is it about the third part of editorial? If yes:

The sequence we consider doesn't change

abecause we assume that if we changeawhen 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 changeda, our answer will become worse than if we changed it, so our assumption was wrong and changingawill lead us to optimal answer.~~We consider some iteration~~iwhen the elementbwas changed instead ofa. But later operations could changeaseveral times. The proof considers only case whenadidn't change after iterationiat all.Actually I missed line about further operations. Could you explain why we we won't change

alater in more details? If the order does not matter optimal sequence of changes gives us some vector (p_{1},p_{2}, ...,p_{n}), greedy solution (g_{1},g_{2}, ...,g_{n}), wherep_{i},g_{i}is how many times we changed thei-th element, And these two vectors differ inaandb,g[a] =p[a] + 1,g[b] =p[b] - 1.For problem D, I couldn't grasp the editorial too easily. So I understood it on my own in the following fashion.

Let the overall product be

prod=a*b.Consider an operation on element

a.|

prod_{new}| = |a±x|.|b||

prod_{new}| = | |prod| ±x|b| | = |a_{new}|.|b|So the maximum amount by which |

prod| can be changed occurs when |a| is minimum. Why? Becausex|b| is max |b| is max is minimum.Case 1prodis +ve:We can either change the sign of

prodto -veor decreaseprodby max amount.This is so because if

a< 0, then addingxto it will either makea≥ 0 or it will decrease |prod| by max amount. The second condition can be derived in the same way.Case 2prodis -ve:We need to increase |

prod| by max value. This means making |a_{new}| as max as possible.Here is the AC code.

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}. Sayx= 10. Clearly herea= 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, ifx< =athen clearly |prod| should be decreased as per the formula. ifx>a, x — a will make the product most -ve hence we chooseaeven though |prod| may actually increase, prod we definitely decrease the most.if

a< 0 Note that the ifx< = |a| then prod must decrease for which we add toaifx> |a| then changing of sign is possible hence the most new prod can be obtained by choosingaand addingxtoa. We can follow similar arguments for other cases as well.The maximum distance by which |

prod| can be moved right or left on the number line occurs whenais minimum. Ofcourse since it's absolute value, then moving it too much towards left will ultimately cross the origin and then the absolute value will increase.My derivation of the cases is just fine.

Yeah, sure. Just wanted to make it explicit that choosing min |

a| is not just based on reducing |prod|. I gave a justification as to why it should work in cases where |prod| seems to increase.Also, this proves that this is the most optimal way for each individual update. Can you please elaborate how this necessarily implies that the end product(After

kupdates) is optimally small ? . I could not get the editorial in this regard.If your current

prodis -ve, then you will never change the sign. You will just increase the absolute value by making -vemore -veand same for +ve. I have shown that for this you have to operate upon the smallest number in absolute value. This guarantees optimal solution afterkoperations.If your current

prodis +ve, you would try to change the sign to -veor decrease theprodvalue by maximum amount. Fortunately, our solution to decrease theprodvalue by maximum amount is also the exact step we need to change the sign to -ve. If sign changes to -ve, you can proceed as mentioned above. If not, after applying the reqd operation |b_{new}| > |b|. GREEDY works like a charm!Sure. I get that. But this is not mathematically rigorous. e.g. Lets say an algorithm choose some |

b| > |a|, which does not decrease the product as choosing |a| would have done, but it could be possible that this algo takes some step later in the pipeline to compensate for this. How can we definitely say that this cannot happen ?I have two solutions to problem E,one is the solution I used during the contest and its complexity is O(nlogn),the other one is the solution optimised to the first solution,and its complexity is O(n). Their ideas are identical and they both use dp. The O(nlogn) solution uses binary search to identify the position which needs to be transferred,and the O(n) solution takes advantage of the monotonicity.

I'm sorry that I don't know how to make hyperlinks here,so I can only provide the ID of the two codes.

O(nlogn):21041800

O(n):21104290

here are the links, thanks for your solution 21041800 21104290

:) Thank you for your help.

Can you please explain the logic behind your

O(n) solution ?The O(n) solution just replace the binary search in the function "query". You need to know the variables that the function returns is the position which needs to be transferred and it is monotonous obviously.

In fact the O(nlogn) solution has got the main idea (greedy+DP) .The O(n) solution just use a trick to optimize the O(nlogn) solution.

Maybe it implies that, for a segment, storing the maximal number of songs to sing in that segment where position as left as possible, is enough. It may require some proof though.

What you said is the meaning of f[i].

As for the proof , for a pair(a,b) (a is the maximal number of songs,b is the position as left as possible),It is clear that (a,b) is not worse than (c,d) (c<=a,d>=b).And for (e,f) (e<a,f<b), it is not better than a certain (c,d),so it is not better than (a,b).

Can someone explain problem E solution? This looks pretty neat.

Can anybody explain the complexity of C-Journey??

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

Could an author's solution be provided for each problem? A link to it would be sufficient. I especially want to see solutions for C and D.

anybody know whats wrong with my D? http://codeforces.com/contest/721/submission/21054178

my solution looks the same as the editorial

Do we really have to use a reversed graph to solve problem C? Can we use the given graph and do the same stuff but starting in point 1?

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

We can also do it without topological sorting, with modified Bellman Ford's. My solution

Why do I need a topological sort? Why can't I do the same DP as in the official solution but starting in the first vertex?

I think you can directly do dp (for example, using dfs) on the given graph as long as you start from vertex 1 and stops at vertex

N.It's somehow similar to doing it on topological sorted vertices — you may find that your dfs won't

go beyond1 andN.yes you can directly do dp , i.e do dfs (starting from 1 ) on each non visited vertex once and then update table, also you need not stop at vertex N . If you don't stop at N , the algo will do unnecessary calculation only and the answer won't change.check 23475069 and 23475056 . But clearly stopping at N is a better approach..

http://codeforces.com/contest/721/submission/21035009 the following submission of the second question i.e. password ,my solution got accepted in the pretests however during the system check it got a wrong answer on pretest 14 ,here the number of unsuccessful password attempts are 5 and one for correct the answer should've been 6 ,since there is a penalty after 6 wrong submissions.Could any one please explain it. Thank you

There are six words whose lengths are less than or equal to the real password, and

k= 5, so there isonepenalty in the worst case.Could anyone give me a test case for C. I am getting wrong answer on test 14

721B — Passwords

Unable to parse markup [type=CF_TEX] what does it mean p1kachu?

I think problem D is simple than C.What do you think？

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

Please explain solution for problem E. Its not at all clear from editorial (specially if p>100).

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) /psongs, now iterate through 1 to (r-l) /p, meaning you want to sing these much songs.Say, you want to sing

jsongs in this segment, then, your last songs must be sung beforer-j*p-t(why notr-j*p?).Then, you want to find maximum

i, wheredp[i] ≤r-j*p-t, meaning that you can sing at mosti+jsongs in this segment if you want to singjsongs in this segment, which should updatedp[i+j]However, there's another problem. Will this affect answers to

dp[k+j] wherek<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 singingjsongs andj- 1 songs, the key to the prove is that for anys,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:

as

jtravel through number of songs, so it won't exceedL/p, and finding theicould takeO(log(L/p)) if you use binary search. So the complexity isThanks a lot! I think there is also a O(n) solution independent of size of p. (n = number of segments)

If you know..can you explain that also ?

Could anybody explain my doubt in problem D?The greedy stategy only proves that in one step we should choose a number with minimal absolute value,but why can it assure that the final answer is optimal?

Can anyone explain D anymore better? Thanks

Can anyone help me with C — Journey ? I keep getting TLE in test case 11 but I don't know how to fix it. Here's my current solution: http://codeforces.com/contest/721/submission/21215115. Thank you very much.

[Problem D]Can somebody help me to understand why this code fails? http://codeforces.com/contest/721/submission/21222485

For problem C. I use dp[i][t] represents the longest path from vertice i with t time. Then dp[i][t] = max{dp[j][t-edge[i][j]] + 1}. my 21225644 is WA. I don't know where is wrong.

`wrong answer Path must end in vertex 1000`

When I first saw Problem C, I thought it can be solved using Dijkstra's. I am not exactly sure why Dijkstra's cannot be used here, since we do not have any negative edges ? Can anyone tell me why we cannot use dijkstra's ? As you can see from my submission here http://codeforces.com/contest/721/submission/21121352. The code fails for 13th test case. I know where it fails but I am not sure why though?? :(

For test 13: the input is basically:

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:

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)?

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.

Can someone help me estimate the complexity of my solution for problem C ( it comes from the DP part )? I know that it isn't the optimal one , but it still managed pretty easily to be accepted. 21407348

This is regarding maxim and array. I have tried to implement exactly what's mentioned here but still not getting AC.

Here is the link to my code in c++

http://ideone.com/ta9Min

Thanks in advance !

Somebody please help me why i am getting Runtime Error in submission 22639657 for problem 721B - Passwords .

I don't understand why my code for C. keeps getting MLE on test 8. When I tweaked it a bit, I got WA on the same testcase.

I did a simple dp+memoization approach with an array

next[i]that stores the next element afteriin the optimal path.Can anyone spot a mistake?

I just solved problem C using 2D Dijkstra :) 36453100