### Golovanov399's blog

By Golovanov399, history, 16 months ago, translation, ,

We are sorry that you were having troubles with access to Codeforces.

Problem A of elimination/div2
Problem B of elimination/div2
Problem C of elimination/div2
Problem D of elimination/div2 = problem A of div1
Problem E of elimination/div2 = problem B of div1
Problem F of elimination/div2 = problem C of div1
Problem G of elimination/div2 = problem D of div1
Problem E of div1

• +101

 » 16 months ago, # |   0 Auto comment: topic has been updated by Golovanov399 (previous revision, new revision, compare).
 » 16 months ago, # |   +19 Very nice solution for the problem div2 G / div1 D i made exactly the same. 45972559
 » 16 months ago, # | ← Rev. 2 →   0 why can't we choose k = 3 and n = 12 in the second dummy test of problem E? *edit: nevermind i was dumb
 » 16 months ago, # | ← Rev. 2 →   +5 For F, how to prove the "unique if and only if it's perfect" part? Update: got it.
•  » » 16 months ago, # ^ |   +15 Consider a graph G with a maximum matching M. If there exists node V in G where it has at least one edge incident on it in G but has no edges incident on it in M, you can choose any edge E incident on V in G (notice that any edge incident on V in G connects V to nodes which have incident edges on them in M, otherwise M is not a maximum matching). Let E be connecting nodes V and U. Add E to M, and remove the edge incident on U in M. This produces a new maximum matching. This proves that M with at least one unsaturated node is not unique.Now consider a tree T with maximum matching M where all nodes in M are saturated. If you decide to add arbitrary edge E (existing in T but not in M, and connects U and V) to M, you need to delete the edges incident on U and V in M. Now you will have two new unsaturated nodes (which were connected to U and V by the edges removed) in M. Let's call them U' and V'. So you need to add 2 edges from T such that they will be incident on U' and V' in M. Let these 2 edges were connecting U' and V' to U'' and V'' respectively in T. Now you need to delete the 2 edges incident on U'' and V'' in M. Two new unsaturated nodes appear and the process will repeat. The only thing that can stop this process and produce a new maximum matching is adding an edge between the 2 new unsaturated nodes in M, which means that the graph was cyclic (not a tree). This proves that a maximum matching of a tree with all nodes saturated is unique.
•  » » » 16 months ago, # ^ |   0 Thank you!
 » 16 months ago, # |   0 Can anyone explain problem C?
•  » » 16 months ago, # ^ |   +7 Imagine for some i we know all fingers by which we can play this note. Then If ai + 1 > ai and we can play the i-th note by the j-th finger, then we can play ai + 1 by k-th finger for every k > j (after we played the i-th note by the j-th finger). If ai + 1 < ai and we can play the i-th note by the j-th finger, then we can play ai + 1 by k-th finger for every k < j (after we played the i-th note by the j-th finger). If ai + 1 = ai and we can play the i-th note by the j-th finger, then we can play ai + 1 by k-th finger for every k ≠ j (after we played the i-th note by the j-th finger). By storing all these things we can both determine if we can play the whole melody and which fingering we can use for this.
•  » » » 16 months ago, # ^ |   0 Thank you for the answer!
 » 16 months ago, # |   +13 Can someone explain the dp transition for div2E/div1B?
 » 16 months ago, # | ← Rev. 6 →   +29 Hi, I'm confused by the states of div2F, can somebody help and clear my thoughts? ThanksIs it true that: dp[v][0] and dp[v][2] have intersection?Then won't it be repeatedly counting when calculating dp[v][1]?
•  » » 16 months ago, # ^ | ← Rev. 7 →   +25 I think I have some new thoughts trying out some small examples, let me put it here.I think the confusion can be cleared by distinguishing these two properties: 1. Is it connected to some edges? 2. Is it matched with its parent or children?Suppose we are looking at v. If we are constructing a tree, our decision will be whether to connect v to its children to's or not.dp[v][0] means the answer: number of ways to split the tree such that in the resulting perfect matching v is: a) matched with one of its children, or b) isolated (absolutely no edge connecting it). Also, every component has a perfect matching, for a subtree rooted at v without any constraintdp[v][1] counts: v is matched with its parent and it should not match with any of its children. Note in this case, the edge from v to its children may or may not be present.dp[v][2] counts the way in which v matches one of its children (and thus the edge is there).Let's start with dp[v][1], so in this case we force v to be matched with its parent. For each of its children to, we want either: a) there's no such edge (v, to), or b) there is an edge (v, to), but this edge should be forced non-existant in the perfect matching. For case a) is dp[to][0] and case b) is dp[to][2] because we want to to be matched with to's child instead of v.Then let's come to dp[v][2], so now we want to force v to be matched with one of its child to, and to should not be matched with its children (dp[to][1]), for v's other children to', either we don't want the edge (v, to') (dp[to'][0])or we want the edge but also to' should be matched with its children (dp[to'][2]).And finally, for dp[v][0], either we want to isolate v (dp[to][0]) or we want it to be matched with one of its children (following the logic of dp[v][2]).Interesting problem, thanks.
•  » » 16 months ago, # ^ | ← Rev. 3 →   +11 So to answer this question, do dp[v][0] and dp[v][2] have intersection?Yes.But when you add them in a parent, they account for cases where either you have the parent edge or not.So there won't be double counting.
 » 16 months ago, # | ← Rev. 3 →   0 Hello Golovanov399. I found that my solution 45943852 for problem 1079C - Playing Piano is wrong for test case: 5 5 4 3 2 1 but is ACCEPTED. So, i think if possible such test cases shuld be added and the solutions for the problem shuld be rechecked. As, there may be more solution like mine which is ACCEPTED and should be WRONG. Actually, i don't know what to do from your side to avoid such problems cause a problem may have thausands of way to solve and each way may have such cases. For clearance my next solution 46006405 little diffrence in first line of the call function and is all ok. Thank you.
 » 16 months ago, # |   0 What is the definition of unique maximum matching? I'm confused now..
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 Matching is something for bipartite graphs, trees are bipartite graphs.Supose the graph with 3 nodes and the edges: 1 2 and 2 3In this graph the maximum matching is not unique. The maximum matching is 1 and the chosen edges can be either 2 1 or 2 3
•  » » » 16 months ago, # ^ |   0 I don't understand the "unique" part of it. When the matching is unique?
•  » » » » 16 months ago, # ^ |   0 The matching is unique when there is only one subset of the edges that gives the maximum matching.I just gave you an example of when it is not unique. Here its an example of when it is unique: A graph with 2 nodes and the edge 1 2. The maximum matching is 1 and the only choice is choosing the only edge 1 2.
•  » » » » » 16 months ago, # ^ |   0 So how is it that the anwser is not just 0 or 1?
•  » » » » » » 16 months ago, # ^ |   0 Tree with n + 1 vertices and edges: {1, 2}, {1, 3}, {1, 4} ... {1, n} has n maximal matchings, but no perfect one.
 » 16 months ago, # |   +4 In Div2C, when I first read the problem, I could only think of a greedy approach. Could someone help tell me what observation led them to thinking of a DP approach? How'd the idea of applying DP come? Was there a specific part of the question which made you think "This can be solved with DP."Any help is welcomed! I'm trying to develop the thought pattern and could use some help in doing so.
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 Look, the choice for any finger depending on the previous one as example for fifth one the choice depend on forth one, for forth choice it depend on third one, for third choice it depend on secon done and finally for second choice it depend on first one. Here there is only 5 chice for first number and 4 or less choice for remaining numberes. so u can try by taking all possible way depending upon the condition. for example put 1 in first number and try with putting 2,3,4,5 on second number and if it is not possible to put any number on it then go back to forst one and put 2 on first number and try by putting 3,4,5 on second number if the second number is bigger else try by putting 1 and so on for next numbers.And for more convenience there is only 5 choice for each number and you can try by putting all the possible way whice tend to dp.
•  » » » 16 months ago, # ^ |   0 I see. Thanks for taking the time out to help me. :)
•  » » 16 months ago, # ^ |   +5 Actually the problem has a greedy approach which I used.The main idea is that if ai + 1 > ai, then the next finger should be at least 1 greater. However, if ai + 2 < ai + 1, then it’s better to choose 5, because in the worst case there will be 5 consecutive numbers in decreasing order and 5 will give you a possible answer in the future.You can apply the same idea when ai + 1 < ai and when ai + 1 = ai. The most important part in every case is that checking at the value of ai + 2 allows you to make the optimal choice.The code: 45938901
•  » » » 16 months ago, # ^ |   0 Thank you, I didn't think of looking past the immediate element :)Thanks for making time for my query and linking your code! :)
•  » » » 16 months ago, # ^ |   0 That was really helpful. I was looking for such an answer.
 » 16 months ago, # |   +15 Just wondering, is the machine in Div1E Turing-Complete?
•  » » 16 months ago, # ^ |   +10 No loops
 » 16 months ago, # |   0 Can any suggest more problems like C. Playing Piano for further practice ?
•  » » 16 months ago, # ^ |   0 Here is how I recommend you practice DP: Go HERE, start from the top and work your way down. You will become good at DP very quick
 » 16 months ago, # | ← Rev. 2 →   0 can someone explain the solution for problem D/div2.thanks in advance.
•  » » 16 months ago, # ^ | ← Rev. 2 →   +3 I had a pretty simple approach.To get from point A to point B, there are countable number of ways - Go the manhattan route -- completely ignoring the given line. Go from A to the given line parallel to the Y-axis, then traverse along the given line, and then go to B from the line vertically, when you're at the same X-coordinate as B. Go from A to the given line parallel to the Y-axis, then traverse the given line and move horizontally when you're at the same Y-coordinate as B. you'll go from A to the line parallel to the X-axis, traverse along given line, exit line and travel along Y-direction when you're at same X-coordinate as B. You'll go from A to the line parallel to the X-axis, traverse along the line, exit line and travel along the X-direction when you're at the same Y-coordinate as B. So overall, 5 cases to check — manhattan, X-line-X, X-line-Y, Y-line-X, Y-line-Y.Your answer is the minimum of them!Here's my accepted solution — https://codeforces.com/contest/1079/submission/45935081Corner case is to just check if either 'a' or 'b' in the line equals zero and if so, return infinity as the result along that direction. :)
 » 16 months ago, # |   0 For Div1D, the editorial mentions using a sparse table, but I was only able to make the sparse table approach fast enough after many submissions. Did the writers actually expect people to use this approach? And did anyone else use this approach?46016077
•  » » 16 months ago, # ^ |   +5 For sparse tables it is generally a good idea to flip the array dimensions around, because of caching. Just flipping the dimensions around in your solution makes it significantly faster — 46857851
•  » » » 16 months ago, # ^ |   0 thanks
 » 16 months ago, # |   0 Can someone please explain to me one case in problem G?The third input contains 100 entries in total and entries 48-52 look like: ... 5 37 2 53 28 ... The judge answer for 50th entry is 2, and I am curious why.I think the parrot on entry 2 will spread the message to the shown subarray of five elements in the first second. In the next second we have at most 3+37+53 parrots talking. What am I missing?
•  » » 16 months ago, # ^ |   0 Nevermind, I didn't see that message will spread from 53 to both sides ...
 » 12 months ago, # |   0 Can anyone provide the recursive solution for Div2 C.
 » 10 months ago, # |   0 I tried implementing the editorial solution for Div 1 D, but I keep getting WA on Test Case 9. Can someone please provide a break case or find a bug in my code?https://codeforces.com/contest/1078/submission/55229631