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 Di made exactly the same. 45972559why 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

iwe know all fingers by which we can play this note. ThenIf

a_{i + 1}>a_{i}and we can play thei-th note by thej-th finger, then we can playa_{i + 1}byk-th finger for everyk>j(after we played thei-th note by thej-th finger).If

a_{i + 1}<a_{i}and we can play thei-th note by thej-th finger, then we can playa_{i + 1}byk-th finger for everyk<j(after we played thei-th note by thej-th finger).If

a_{i + 1}=a_{i}and we can play thei-th note by thej-th finger, then we can playa_{i + 1}byk-th finger for everyk≠j(after we played thei-th note by thej-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]`

and`dp[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 connect`v`

to its children`to`

's or not.`dp[v][0]`

means the answer: number of ways to split the tree such thatin the resulting perfect matching`v`

is:Also, every component has a perfect matching, for a subtree rooted at

`v`

without any constraint`dp[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:`(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) 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.

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.

Hello Golovanov399. I found that my solution 45943852 for problem 1079C - Playing Piano is wrong for test case:

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.

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} hasnmaximal 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

a_{i + 1}>a_{i}, then the next finger should be at least 1 greater. However, ifa_{i + 2}<a_{i + 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

a_{i + 1}<a_{i}and whena_{i + 1}=a_{i}. The most important part in every case is that checking at the value ofa_{i + 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! :)

That was really helpful. I was looking for such an answer.

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.com/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.com/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?