In english?

Excuse me, where can I read about dp? Thanks.

Here are my solutions to the problems of this contest that I could do.

I have written an editorial about D here, in case anybody requires further explanation. :) I have also written a post about the O(n) solution to A here.

P.S. — What is the bonus solution to Problem D ?

For bonus question of C,

Call a vertex a root if it's degree > 2.

Case 1 : There is atleast one vertex with degree > 2

If there is more than one root, then the solution stays the same as a decomposition is not possible. If there was exactly one root, then we have to make it the root and the solution stays the same. Making any other vertex the root will not satisfy the given conditions.

Case 2 : All vertices have degree <= 2

To minimise the number of paths, we must choose a leaf vertex since it has only one child and it will result in 1 simple path from one leaf to another.

For maximising the number of paths, we will have to pick any non-leaf vertex which has a degree of 2. There will be two paths, one to each leaf.

problem E is clearly visible from D&C ...how to solve by DP in an easy way..

I'm really curious about how to solve F in O(n⋅logn). Could someone tell me the method?

Can someone explain last paragraph of editorial of problem F, as I can't understand which segments we are talking about and why the intersection of segments is the validation for possible matching for that specific answer.

For problem F

"So we can solve the problem in O(n * L) — fix the cut, and match i-th bridegrom (in increasing order) with i-th bride (if we will order brides in the traversal order starting from border), and relax answer with current inconvenience."

Why this solution is always optimal?

For problem F Round Marriage.

I find a solution in O(n * log_2(L)) with the key idea in the tutorial.

What I do is just optimizing the progress of finding the range of x.

We can use two-pointers to work out it.

More in the code: 39254791

Can someone please explain why this DP is wrong : dp[i][j][k] as maximum value obtained by distributing books in segment [i, j] into k shelves? Complexity O(n^3.n^2) ?

Can someone please explain why this DP in pD is wrong : dp[i][j][k] as maximum value obtained by distributing books in segment [i, j] into k shelves? Complexity O(n^3.n^2) ? 300iq ghoshsai5000 Can you help me out?

Can someone explain me problem C?

For problem F, is the following correct :

First, binsrch on ANS, now we will check whether such answer exists using hall's theorem. So we want to count for each 1 <= L <= R <= N whether number of brides reachable from grooms of [L,R] is atleast R-l+1. So start with [1,i] for all 1<=i<=N. Get the count for these. Now, we update our values for [2,i], then [3,i] and so on using Lazy propagation on Segment tree. Basically, when we remove some element, we invalidate a range of brides for the segment [j,i]. Note that since its cyclic, we wont update all i from j <= i <= n when updating from [j-1,i] to [j,i], because some of them might be accessed for say i = n. Thus, we need Lazy range addition and min. Overall, logL * nlogn.

Is this correct though? I am not confident in applying Hall's theorem.

I think I have a simpler solution for problem E:

Sort the queries in increasing $$$r_i$$$. Then mantain $$$dp[i]$$$ which is the rightmost index in the array which we can achieve a maximum of $$$i$$$ in. Iterate through the queries, initially setting $$$dp[0]=r_i$$$ and then iterating backwards like the knapsack DP trick (I think this is covered in Errichto's AtCoder DP video in the knapsack problem) to update all the $$$dp[i]$$$. Complexity $$$O(nq)$$$.

73507542