Help in C. Three Displays

Hello,
I was solving [this][1] problem and firstly I formulated [recursion][2] which shows TLE on test 11(it obviously should). I then tried saving the answer, approaching the problem like dp. But I don’t know why the


[3] shows WA on test 7. I think I doing some mistake while saving the answer. Any help would be highly appreciated.  
Thanks :)


  [1]: http://codeforces.com/contest/987/problem/C
  [2]: http://codeforces.com/contest/987/submission/38748342
  [3]: http://codeforces.com/contest/987/submission/38736017

vector fs(n);
vector c(n);
vector<vector > dp(n, vector(3,INT_MAX));
for(int i=0;i<n;i++){
cin>>fs[i];
}
for(int i=0;i<n;i++){
cin>>c[i];
dp[i][0]=c[i];
}
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if(fs[i]>fs[j]){
dp[i][1] = min(dp[i][1], dp[j][0]+c[i] );
}
}
}
for(int i=1;i<n;i++){
for(int j=0;j<i; j++){
if(fs[i] > fs[j] && dp[j][1]!=INT_MAX){
dp[i][2] = min( dp[i][2], dp[j][1]+c[i]);
}
}
}
int ans= dp[0][2];
for(int i=1;i<n;i++){
ans = min(ans, dp[i][2]);
}
if(ans==INT_MAX){
cout<<"-1\n";
}else cout<< ans <<"\n";

1 Like

This problem uses similar approach like LIS O(n^2) version

Thanks for the response, but can u point out the mistake in my code?

Yes! If you give me your recursion formula.

I have posted the links in question. Here they are once again:
Using recursion : http://codeforces.com/contest/987/submission/38748342.
Using dp : http://codeforces.com/contest/987/submission/38736017.
I have used something like this : Let cache[i][j] be the minimum cost taking 1,2…i and maximum size being at position j.

Hey! Dishant in your dp you need to make cache[pos][last][second_last] as it might come to pos last with second last chosen or different from before or even not chosen So although answer will be different your code will return the same value. But if you make the dp as I told it would give tle (as it would be O(n^3)) so you should do something like meet2mky said

Here is my code - http://codeforces.com/contest/987/submission/38740788

EDIT : Example test case consider the input
7
1 2 3 4 5 6 7
7 6 5 4 3 2 1
your code is giving output 10 (due to multiple same pos last occurance) but the ans is 6 the cost of last 3 boards 1+2+3=6

Sorry for bad english

1 Like

If i’m not wrong for each j you may need to find two optimal(means they are best choice for cost) index i1 < i2 < j such that frameSize[i1] < frameSize[i2] < frameSize[j] and this will lead to O(n^3) time complexity.I’m still not able to find the transition function from one state to another state.

Thanks for the help :slight_smile:

I guess my solution is completely wrong. Thanks for all the time and effort :slight_smile: