You are not logged in. Please login at www.codechef.com to post your questions!

×

Help in C. Three Displays

Hello,
I was solving this problem and firstly I formulated recursion 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 code shows WA on test 7. I think I doing some mistake while saving the answer. Any help would be highly appreciated.
Thanks :)

asked 30 May '18, 09:07

dishant_18's gravatar image

5★dishant_18
61419
accept rate: 12%


vector<int> fs(n);
vector<int> c(n);
vector<vector<int> > dp(n, vector<int>(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";
link

answered 30 May '18, 12:45

meet2mky's gravatar image

4★meet2mky
2013
accept rate: 26%

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

(30 May '18, 12:50) meet2mky4★

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

(30 May '18, 13:50) dishant_185★

Yes! If you give me your recursion formula.

(30 May '18, 14:43) meet2mky4★

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.

(30 May '18, 16:49) dishant_185★

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.

(30 May '18, 20:38) meet2mky4★

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

(30 May '18, 21:17) dishant_185★
showing 5 of 6 show all

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

link

answered 30 May '18, 17:48

ssp547's gravatar image

3★ssp547
3077
accept rate: 25%

edited 30 May '18, 17:59

Thanks for the help :)

(30 May '18, 21:16) dishant_185★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,172
×682

question asked: 30 May '18, 09:07

question was seen: 205 times

last updated: 30 May '18, 21:17