How can we optimise dynamic programming of the form:
Base case : dp[i] = a[i] * i
dp[i] = max(dp[i], dp[j] + (a[i] - a[j]) * (i - j)), for 1 ≤ j < i
It is given that n ≤ 105 and |ai| ≤ 1012. Naively, it can be computed in O(n2). But I can't further improve my solution.
I tried the following :
(a[i] - a[j]) * (i - j) = a[i] * i + a[j] * j - a[i] * j - a[j] * i
Thus, we can store another array, dp2[i] = dp[i] + a[i] * i. Then the recurrence becomes :
Base case : dp[i] = 0
dp[i] = max(dp[i], dp2[j] - a[i] * j - a[j] * i)
Finally : dp[i] = dp[i] + a[i] * i and dp2[i] = dp[i] + a[i] * i
But, it is still O(n2).
Any hints would be appreciated.
Can you assume something about the array a[i]? I think that if a[i] ≤ a[i + 1] you can argue that the optimal choice is monotone and then apply some technique from this thread
No, the values of a[i] are random. Basically, I was trying to solve this problem where, array a is prefix sum in this case.
If the array values were monotone then the answer could be found greedily. -_-
Could it be just a fake problem?
Let me try a solution.
I've been thinking for over an hour and I can't see any progress. I saw your question and I usually do not use SPOJ. I see that nobody has solved it. So I'll just stress out your question: "Is it possible that this problem is unsolvable in polynomial time?" It's really interesting and I can't believe it could be basically wasted in a place like this where almost nobody saw it or is probably to see in the close future (maybe half of the people that ever read it, read it as a result of seeing this blog)
I guess you could use "More remarks, on querying" from here and number 4 from here.
How to use 4th idea here?
Just like you would for the lower envelope of lines, but you would replace the usual 2D Convex-Hull with the algorithm described in the paper. It ends up being O(N * log2(N)), but i'm not sure how fast it is in practice.
When computing
you are looking for the 3D extreme point in the direction
.
There are quite a few sophisticated datastructures for this problem, those are usually hard to implement and/or slow in practice.
The testdata of the SPOJ problem appears to not be too evil, so one can get AC by using KD-Trees for the extreme point queries. Extreme point queries are done like nearest neighbour search.
The runtime strongly depends on the input and is somewhere around
or Θ(n5 / 3) (or maybe even Θ(n2) for evil inputs).
Could you elaborate, please? What sophisticated structures are you talking about? The only way I see to compute that 3D extreme point is by using a 3D convex hull. I think you haven't implemented that (because it wouldn't depend on the input data and because it seems almost impossible to code in less than a couple of days and it would have a huge constant), so how did you solve it? And why have you formulated it as "looking for the 3D extreme point in a direction". Should this tell me something? (I haven't seen that before so I cannot understand how that statement could be of any special use) I only can think of it as the upper part of the 3D convex hull of the planes with equations z = ax + by + c for some (a, b, c).
I used KD-Trees for the extreme point queries. The static version (build once, no insertions) can be implemented quite quickly. To handle insertions, maintain
KD-trees of sizes 
. Inserting a point adds a KD-Tree of size 1. Then keep merging KD-Trees of equal sizes by rebuilding them into a single one.
The extreme point in the direction
is the nearest neighbour to the point 
. The extreme point query on the KD-Tree can thus be done the same way as a nearest neighbour query.
I formulated the problem as an extreme point query, as I could find some theoretical datastructures for extreme point queries and nearest neighbour search with google.
I didn't implement any of the sophisticated datastructures (or Cha06 from here). These are based on the 3D convex hull. I mentioned them in the case someone was looking for a theoretical answer, which seems to be
.
The extreme point query on a point set is dual to finding the highest point above (x, y) in a set of planes. Maybe one could compute the upper envelope of the planes via a 3D-convex hull of the corresponding dual points and sweep through the envelope in y direction, then answer queries as in the 2D convex hull optimization. This would still be unpleasant to implement, but there should be some 3D convex hull codes in
somewhere on the internet.
Nice solution. Thanks for the help.
Could you explain what kind of evil inputs would cause your solution to TLE?