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
Auto comment: topic has been updated by Golovanov399 (previous revision, new revision, compare).
Very nice solution for the problem div2 G / div1 D i made exactly the same. 45972559
why can't we choose k = 3 and n = 12 in the second dummy test of problem E? *edit: nevermind i was dumb
For F, how to prove the "unique if and only if it's perfect" part? Update: got it.
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.
Thank you!
Can anyone explain problem C?
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.
Thank you for the answer!
Can someone explain the dp transition for div2E/div1B?
Hi, I'm confused by the states of div2F, can somebody help and clear my thoughts? Thanks
Is it true that:
dp[v][0]
anddp[v][2]
have intersection?Then won't it be repeatedly counting when calculating
dp[v][1]
?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 connectv
to its childrento
's or not.dp[v][0]
means the answer: number of ways to split the tree such that in the resulting perfect matchingv
is: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 fromv
to its children may or may not be present.dp[v][2]
counts the way in whichv
matches one of its children (and thus the edge is there).Let's start with
dp[v][1]
, so in this case we forcev
to be matched with its parent. For each of its childrento
, we want either:(v, to)
, or(v, to)
, but this edge should be forced non-existant in the perfect matching.For case a) is
dp[to][0]
and case b) isdp[to][2]
because we wantto
to be matched withto
's child instead ofv
.Then let's come to
dp[v][2]
, so now we want to forcev
to be matched with one of its childto
, andto
should not be matched with its children (dp[to][1]
), forv
's other childrento'
, either we don't want the edge(v, to')
(dp[to'][0]
)or we want the edge but alsoto'
should be matched with its children (dp[to'][2]
).And finally, for
dp[v][0]
, either we want to isolatev
(dp[to][0]
) or we want it to be matched with one of its children (following the logic ofdp[v][2]
).Interesting problem, thanks.
So to answer this question, do
dp[v][0]
anddp[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.
What is the definition of unique maximum matching? I'm confused now..
Matching is something for bipartite graphs, trees are bipartite graphs.
Supose the graph with 3 nodes and the edges: 1 2 and 2 3
In 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
I don't understand the "unique" part of it. When the matching is unique?
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.
So how is it that the anwser is not just 0 or 1?
Tree with n + 1 vertices and edges: {1, 2}, {1, 3}, {1, 4} ... {1, n} has n maximal matchings, but no perfect one.
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.
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.
I see. Thanks for taking the time out to help me. :)
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
Thank you, I didn't think of looking past the immediate element :)
Thanks for making time for my query and linking your code! :)
Just wondering, is the machine in Div1E Turing-Complete?
No loops
Can any suggest more problems like C. Playing Piano for further practice ?
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
can someone explain the solution for problem D/div2.
thanks in advance.
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.net/contest/1079/submission/45935081
Corner 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. :)
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
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
thanks
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?
Nevermind, I didn't see that message will spread from
53
to both sides ...Can anyone provide the recursive solution for Div2 C.
Here you go! 91966027
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.net/contest/1078/submission/55229631
In div2-E time complexity is O(n^4) but still it works, can someone explain how ?
In problem B, many contestants use this:
instead of iterating through all values of a and b like the editorial. I'm a beginner, can you please explain how this works?