Doubt in DP states - Codeforces

Блог пользователя ankeshgupta007

Doubt in DP states

Автор ankeshgupta007, история, 7 лет назад, По-английски

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

ankeshgupta007
7 лет назад
18

Комментарии (18)

Написать комментарий?

ankeshgupta007

7 лет назад, # |

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

→ Ответить

sam29

7 лет назад, # |

← Rev. 2 →

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.

→ Ответить

ankeshgupta007

7 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

sam29

7 лет назад, # ^ |


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.

→ Ответить

ankeshgupta007

7 лет назад, # ^ |

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.

→ Ответить

sam29

7 лет назад, # ^ |

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

→ Ответить

ankeshgupta007

7 лет назад, # ^ |

Could you find a test case for the same?

→ Ответить

ankeshgupta007

7 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

sam29

7 лет назад, # ^ |

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.

→ Ответить

ankeshgupta007

6 лет назад, # ^ |

It fails. We can write inequalities and show.

→ Ответить

sam29

6 лет назад, # ^ |

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

→ Ответить

ankeshgupta007

6 лет назад, # ^ |

← Rev. 2 →

No :(

→ Ответить

SleepyShashwat

7 лет назад, # |

Can you please tell me the name of the book?

→ Ответить

ankeshgupta007

7 лет назад, # ^ |

It came in my exam!

→ Ответить

SleepyShashwat

7 лет назад, # ^ |

Sorry,I didnt see the 7 marks in the brackets.

→ Ответить

ajs97

6 лет назад, # |

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.

→ Ответить

Noam527

6 лет назад, # ^ |

I wonder if it's possible in $\text{[math]}$ with D&C optimization on each layer of level... not sure but I'll try to prove it.

→ Ответить

ivan100sic

6 лет назад, # |

← Rev. 2 →

+10

I will continue from the solutions proposed by others. Let dp_h, 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:

dp_h, l, r = min_{l ≤ i ≤ r}(dp_{h + 1, l, i - 1} + w_ih² + dp_{h + 1, i + 1, r})

We can build the solution in layers. The last layer is h = n, and here we only need to compute dp_h, 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(n³) total. Since we only need to track the last two DP layers this is O(n²) memory.

Can anyone prove the required property or give a counterexample?

EDIT:

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

→ Ответить