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

Active In

International Olympiad in Informatics

Indian Computing Olympiad (ICO)

Competitive Programming

San Francisco

Artificial Intelligence

Featured Contributions

reply in this discussion

reply in this discussion

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.

Read more… (51 words)

reply in this discussion

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 ;)

Read more… (34 words)

reply in this discussion

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.

Read more… (41 words)

reply in this discussion

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)

(

Read more… (54 words)

reply in this discussion

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

Read more… (13 words)

reply in this discussion

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.

Read more… (34 words)

reply in this discussion

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.

Read more… (73 words)

reply in this discussion

reply in this discussion

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...*

Read more… (264 words)