I think you meant "if p is even" in the second hint.

That is still not O(n). Insertion/Deletion in a set takes O(lg n) time because it is implemented as a red black tree. Check the hints in the wealth disparity thread for linear time approach.

So your approach is O(n lg n), which I think should pass, but not sure.

max_element is O(n) so your algorithm is O(n²) which cannot pass for large n. You can easily optimize this code. Think how you could eliminate that w vector and use something else ;)

You seem to be trying all paths to the destination of length K. But the problem is that there can be an exponential number of paths. That is why your program crashes, because the stack overflows while exploring so many paths.

Hey, just signed up to see the questions. Pretty simple TBH, but the last two questions I've seen before. They're from codeforces right? I saw those while climbing the C ladder on a2oj.

Great initiative though, keep going! Sadly I cannot take out time participate due to pre boards :( (I'll try though)

(

One correction: Take maximum over all i for dp[i][k] instead of only n-1.

Adding that condition means that you are adding that element but still counting it as an omission. Try my original conditions, I think they can be proved in the same vein as Kadane's algorithm.

Let dp[i][j] be the best segment in A[0..i] when at most j elements have been omitted. Use Kadane's on j=0. For other j: dp[i][j] is either M[i] + dp[I-1][j] or dp[i-1][j] or dp[i][j-1]. We either take this element, or we don't take this element and count it as omitted and use best result for j-1 omissions. Or we use the best segment formed by j-1 omissions for i elements. DP[n-1][k] is our answer.

Here's my quick implementation: #518644 • Fedora Project Pastebin

I thought about it for a while and I don't think this problem has optimal substructure property, which is required for all DP and Greedy approaches, thus there is no "strict" DP approach. However, skip next para for a sketchy DP-like approach which isn't really DP.

My justification is as follows. Let's say we know the best disparity pairs for all subtrees of a node. How do you combine these solutions? One way is to think like this: either the current element will be a part of the best pair for the subtree that contains this node as well, or it won't. If this element minus the smaller element of some subproblem solution has larger disparity, we can say this node and that minimum node is the answer. But what if this node is really low in value? Then it won't get featured in the solution. But if for some earlier parent, this node is really low and optimal, we just ignored a solution. No substructure.

So another thing we noticed from this discussion is that if we know the minimum in the subtrees of the current node, we can say that the answer will be one of V[current node] - V[minimum of so...