Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Thank you for your participation, see you soon (I hope)!

In english?

Excuse me, where can I read about

dp? Thanks.just surf on the internet ,you will get a whole bunch of stuff to learn...

I've found a lot of

dp: https://en.wikipedia.org/wiki/DP What exactly should I look for?Dynamic Programming

REALLY!!!!!ARE YOU KIDDING OR WHAT ....

Topcoder Tutorial

DP IOI training here

these are two good resources

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 ?

Awesome explanation !!!

Thanks a lot :). I appreciate the encouragement :)

P.S. — Are you refering to A or D ?

I was refering to problem D, again awesome explanation !!! I'm adding you to my friends list :)

Please follow me on Quora and read my answers there. I've written a few posts :)

No. Who cares about your Quora?

The people I was talking to do :)

The real question you need to be asking yourself is who cares about your imaginary dragons and weird, snarky comments from a fake account ?

Lol. Making a personal attack doesn't change the fact that you are a shameless advertiser.

I am writing posts so that it clarifies my concepts and can share my knowledge to help others. That's my only intention.

When you have a cheap mentality, everything looks cheap. Advertisement for what ? Quora doesn't give me any money if people read my answers.

Moreover, I'm on CF so that I can learn and increase my knowledge, not get drawn into random fights. My suggestion is that if you don't like my posts, don't read them. :)

I wish you well and have no intention in interacting further with you. :)

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?

Think about randomized binary search in

O(log(n^{2}))I tried to do binary search in

O(log(n^{2})) which equalsO(logn), but I failed. If a number doesn't equal any |a_{i}-b_{j}|, it can't be the answer. So there are O(n^2) numbers which can be the answer. But I don't know how to find the k-th of them quickly. What does "randomized binary search" mean?You can choose random distance ≥

land ≤r, (just find good interval for each element, and take random element from these intervals), because if you will take random element (not n/2-th) it will work inO(log(n^{2})) too.I'll use |

a_{i}-b_{j}| to indicate the shortest distance bewteena_{i}andb_{j}.Do you mean if we know the answer is in [

l,r]，then we randomly select a number from numbers which are in [l,r] and are equal to some |a_{i}-b_{j}|?If so, is there any convenient way to randomly select a number? It's not uniform that randomly select an

i, then randomly select a number from |a_{i}-b_{j}|. In fact for a fixedi, there may be no suchj. A solution is calculating how manyjsatisfyingl≤ |a_{i}-b_{j}| ≤rfor eachiusing two pointers, then selecting aniusing weighted random. But I think this is too complex.I don't know any other way ╮(╯▽╰)╭

OK, thanks. It's a very interesting idea!

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 matchi-th bridegrom (in increasing order) withi-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?

I know that this comment is 3 years old but

Suppose the $$$i$$$-th bridegroom is match with the $$$p[i]$$$-th bride (in increasing order).

Then we can see that if there exist two indices $$$i < j$$$ such that $$$p[i] > p[j]$$$, then swapping $$$p[i]$$$ and $$$p[j]$$$ does not increase the maximum distance that needs to be travelled.

Thus $$$p[i] = i$$$ for all $$$i$$$ is an optimal solution.

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 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 you share your logic or your program ?

ps[] prefix sum Base case : dp[i][j][0] = ps[j] — ps[i-1]

all books in segment are in same shelfTransition : dp[i][j][k] = max(dp[i][j][k], (dp[i][be][x] & dp[be+1][j][k-x]))

Ans : dp[0][n-1][k-1]

Complexity : O(n^3) for states and O(n^2) for each transition

Any success ghoshsai5000

I think the main problem is AND-ing may not necessarily have optimal substructure !

What I mean is ... If we want to know the best AND of a segment [1, 4] into 2 segments, it might not necessarily be the best [1, 2]&[3, 4].

I'm not able to come up with a good counter example. I hope you understood my point.

You make one segment [3, 4] ... Now to know the maximum AND with the last segment [3, 4], you might not necessarily need the best AND of [1, 2]. You might need something less than best in that segment.

Thank you :)

I hope you understood. I tried my best. Wasn't able to come up with a counter example :)

That's why the intended solution greedily sets as many higher order bits as possible.

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