Auto comment: topic has been updated by kristevalex (previous revision, new revision, compare).

1068c is probably not what you wanted to post

edit: never mind

Another solution of 1067D - Computer Game:

It's clear that we will play one quest (for example 1st) until win, then upgrade another (or the same) quest (for example 2nd), and play the 2nd quest all the time.

Math expectation of the score:

Let's simplify this formula using wolframalpha.com.

Result: .

Let's denote:

• ;

• ;

• .

So answer is where M = max Y_i.

Complexity: .

So this problem can be solved using wolframalpha.com. I am not proud of myself but I think this is a downside for this problem.

Cool, almost every solution for div1D got WA105

Problem div2. D was easier than div2. C. Fairly straightforward DP. Problem C was harder partially due to it's language, difficult to understand.

For div2. C, the total number of rooks used should be n + m in the editorial. kristevalex

Unfortunately the system tests on today's Div 1 problem D were quite weak. I wrote up an explanation here: https://mirror.codeforces.com/blog/entry/62692. Make sure to take a look if you are trying to solve problem D in practice mode (or just interested in the problem).

A fast editorial.

A punctual editorial, great! Looking forward to solution for Div.1 C

After that we can find middle vertex in diameter and check if it is a center of k-multihedgehog using simple dfs.

Can anyone please explain how to check?

Someone can tell me what's wrong with my Div2 solution.C (1068C)? First I build a diagonal of rooks (1, 1), (2, 2), ... (n, n). Then for each connection a-b I put one rook of color min (a,b) on the cell (min(a, b), max(a, b)). My decision (https://mirror.codeforces.com/contest/1068/submission/44806161) got WA4

Got the wrong answer in 1068_A because I used ceil() function in C++.

Lessons learnt: Never ever use inbuilt ceil() function. Instead use (a+b-1)/b

How would you solve Div2C if the limit of 1000 on total edges was removed? I actually missed this detail and made the question really hard for myself. That would mean you cannot use more than n+m rooks in the worst case.

Deleted.

I have a different (imo simpler) way to find the expected size of the maximal matching in problem E. You don't need a DP to find the maximal matching in a tree. If we root the tree somewhere and construct the maximal matching bottom up there is no reason not to greedily match nodes that have an unmatched child.

Root the input and let f(v) be the probability that if we perform our greedy algorithm on the (random forest generated from the) subtree rooted at v, node v will be matched with one of its children. By linearity of expectation, the expected number of edges in the maximal matching is equal to the sum of f(v) over all v.

f(v) can be computed with a standard tree traversal:

• If v is a leaf, f(v) = 0 since v will never have a child to match with.
• Otherwise, the chance that a particular child u of v can be matched with v is (1 - f(u)) / 2. That's because u is unmatched with probability 1 - f(u) and the edge between u and v is included in the random forest with probability 1 / 2. Hence the probability 1 - f(v) that v does not find any match is the product of the terms (1 - (1 - f(u)) / 2) over all children u of v.

You can see my implementation here.

Can someone please explain 1067A — Array Without Local Maximums , i am unable to understand it from the editorial

Editorial for Div2 D is so poorly written... Can anybody help?

Is there any way to reduce complexity of my recursive dp solution from O(n*a^2) to O(n*a). Here is my solution for question 1068D or 1067A

For problems like Div1.C, I am curious if there are some efficient ways to make sure our construction works for small n.

Did anyone write the solution 1 for Div1B / Div2E ?

I tried implementing it but got WA 89. Can somebody find out what's missing? Submission

In question 1068B I submitted two solutions https://mirror.codeforces.com/contest/1068/submission/220826372 and https://mirror.codeforces.com/contest/1068/submission/220826179 both are quite similar only for the difference of a bracket but the first submission gave me AC while the second one TLE. can anyone help me find the reason for this?