ankeshgupta007's blog

Doubt in DP states
By ankeshgupta007, history, 7 years ago, In English

Can this be done in O(n^2) space and O(n^3) time? Please share your approach.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ankeshgupta007 (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

First, you need to sort the values in non-decreasing order.

In this question, first of all, to think of a solution that will require O(n^3) space and O(n^4) time is actually pretty easy.

The States would be i,j,k where dp[i][j][k] would represent the min value of arranging the numbers from index i to j in a BST such that the root node is at a depth k. Now to calculate the value of dp[i][j][k] we will iterate from index i to j and consider one by one each index as the root. We can easily think of the recurrence for this. So I am assuming you already know that part.

Now in the above approach, we are keeping the depth also as a state. To reduce the complexity by a factor of n we can avoid keeping depth as a state. I will roughly explain my approach the main idea is if you have the value wi * (hi ^ 2) for any index i, when you will increase the depth by 1 the new value would be something like this wi * ((hi + 1)^2) which can be derived from the previous value directly. All you need is some extra values while calculating the new values,

wi * ((hi + 1)^2) = wi*(hi^2 + 1 + 2*hi)

which is wi*(hi^2) + wi + 2*wi*hi.

So the extra values which we need to store is summation of wi and summation of wi*hi. And you can get the new value which is wi * ((hi + 1)^2). And its also easy to get the new value of wi*(hi + 1). Because that would be wi*hi + wi and both the values are already there.

PS: I know I have not provided a good explanation but I think if you have the idea of the straight forward dp of this question you will get the idea of optimization from my explanation.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    I understand your approach. But what is doubtful is that, when I am updating my DP tables, I am optimizing wi*(hi^2) rather than wi*(hi^2)+2*wi*hi +wi.

    What I am trying to clarify is that are we making any implicit assumption that minimizing wi*(hi^2) simultaneously minimizes wi*(hi^2)+2*wi*hi +wi (because thats the term that is included in further calculations)

    PS: Sorry if I am thinking something wrong.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 

      int A[SIZE];
int N;
pair<int,pair<int,int> > func(int i,int j)
{
    if(i==j){
        return make_pair(A[i],make_pair(A[i],A[i]));
    }
    pair<int,pair<int,int> > rec1,rec2;
    pair<int,pair<int,int> > fans = make_pair(INT_MAX,make_pair(INT_MAX,INT_MAX));
    for(int k=i;k<=j;k++){
        if(k == i){
            rec2 = func(k+1,j);
            rec2.ff += rec2.ss.ff + 2*rec2.ss.ss + A[k];
            rec2.ss.ss += rec2.ss.ff + A[k];
            rec2.ss.ff += A[k];
        }
        else if(k==j){
            rec2 = func(i,k-1);
            rec2.ff += rec2.ss.ff + 2*rec2.ss.ss + A[k];
            rec2.ss.ss += rec2.ss.ff + A[k];
            rec2.ss.ff += A[k];
        }
        else{
            rec1 = func(i,k-1);
            rec1.ff += rec1.ss.ff + 2*rec1.ss.ss;
            rec1.ss.ss += rec1.ss.ff;
            rec2 = func(k+1,j);
            rec2.ff += rec2.ss.ff + 2*rec2.ss.ss + A[k] + rec1.ff;
            rec2.ss.ss += rec2.ss.ff + A[k] + rec1.ss.ss;
            rec2.ss.ff += A[k] + rec1.ss.ff;
        }
        if(fans.ff >= rec2.ff){
            fans = rec2;
        }
    }
    return fans;
}

      Here is the code, I have not added memoization. It's just the recursion part. I got your doubt actually you need to look at the fact that we want to optimize only wi*(hi^2), the other values need not be optimized. We only want the other values to calculate the new values of the given function. I haven't tested my code on any test case, so do point out if you find any mistake in the implementation.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Implementation isn't a problem. Problem is when you calculate all 3 DP table for range {i,...,j} , and use the same for k=j+1 in range {i,...,j,j+1,..}, you actually include wi*(hi^2)+2*wi*hi +wi and not wi*(hi^2). Thats where the subtlety lies.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh okay, I got the mistake. My approach is incorrect. Sorry, for suggesting you wrong approach.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Could you find a test case for the same?

            → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            I think that it might just hold true in this case, just a possibility.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I tried many small random cases but the solution is giving correct answer actually. I am also surprised to see that the solution is working. Actually, the above code without memoization is surely correct but I thought when we would apply memoization then it would become incorrect because of the same reason you provided above. Currently, I am also not completely satisfied regarding why the solution is working. So, if you get the intuition behind the correctness please do share.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                It fails. We can write inequalities and show.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  So, did you get the correct solution with the complexity that we want to achieve???

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  No :(

                  → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please tell me the name of the book?

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Sort all the values in increasing order of a_i's. We can then do something like dp[i][j][level] where the dp value denotes the cost for the binary search tree on values from a_i to a_j, with the root at depth = level. The recurrence is dp[i][j][level] = min(dp[i][k-1][level+1] + dp[k+1][j][level]+w_k*level^2) for k from i to j. This is O(N^2) space (we can keep only 2 columns for the level), but O(N^4) time.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wonder if it's possible in with D&C optimization on each layer of level... not sure but I'll try to prove it.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

I will continue from the solutions proposed by others. Let dph, l, r be the best value we can get if we arrange the numbers indexed from l to r such that the root of the tree is at depth h. The recurrence is, of course:

dph, l, r = minl ≤ i ≤ r(dph + 1, l, i - 1 + wih2 + dph + 1, i + 1, r)

We can build the solution in layers. The last layer is h = n, and here we only need to compute dph, l, l, since we can never build a tree with more than one node at depth n. The same logic applies for other values of h. For example, when h = n - 1, we only need to compute DP values where r - l ≤ 1. In general, we only need to compute DP values where r - l ≤ n - h.

I think that Knuth's optimization trick will work here. This would mean that we can compute each DP state in amortized constant time, so O(n3) total. Since we only need to track the last two DP layers this is O(n2) memory.

Can anyone prove the required property or give a counterexample?

EDIT:

Here's my stress test (100 random samples), and the O(n3) solution passed.

→ Reply