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

CSES DP SECTION — Book Shop

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

I was solving Book Shop of CSES DP section.

I am getting TLE even after multiple attempts, Can you tell me how to optimize my TOP-DOWN approach.
I have tried replacing 2-d array with 2-d vector .
I have also tried swapping the dimensions of dp array ( some caching thing ).

my code

#include "bits/stdc++.h"
using namespace std;
int dp[1001][100001];
vector <int >price, page;
int state(int index, int total)
{	
	if (index < 0) return 0;
	if (dp[index][total] != -1) return dp[index][total];
	int &ans = dp[index][total];
	if (total >= price[index]) {
		ans = page[index] + state(index - 1, total - price[index]);
	}
	ans = max(ans, state(index - 1, total));
	return ans;
}	
int main() {
 
	ios::sync_with_stdio(false); cin.tie(nullptr); 
	int n, req; cin >> n >> req;
	price.resize(n); page.resize(n);
	for (auto &x : price) cin >> x;
	for (auto &x : page) cin >> x;
	memset(dp, -1, sizeof(dp));
	cout << state(n - 1, req);

AC_AC
6 лет назад
29

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

Показать архивные | Написать комментарий?

ExpertCoder

6 лет назад, скрыть # |

Everything is fine. Just set dp[index][total] = ans before returning.

→ Ответить

AC_AC

6 лет назад, скрыть # ^ |

it is referenced with variable named ans,so i guess it should be fine, right??

→ Ответить

nochill

6 лет назад, скрыть # |

The time constraints in the CSES Problem set are very tight! In some problems using long long instead of int might also give TLE. So its always better to use Iterative method rather than Recursive(for CSES)

→ Ответить

AC_AC

6 лет назад, скрыть # ^ |

yeah i read it somewhere, so should i assume that it is unsolvable using TOP-DOWN approach(on CSES)??

→ Ответить

nochill

6 лет назад, скрыть # ^ |

It might work for some Problems I'm not too sure about that but I do remember trying top_down approach for some Problems and got TLE too! Not that the solution was wrong, but the time constraints were just too tight for recursive solutions!! So yeah if you want AC in CSES then you have to solve iteratively(atleast for most of them or even all of them)!

→ Ответить

dastination

6 лет назад, скрыть # ^ |

I kept on getting runtime error on my bottom up dp solution just because I used long long

→ Ответить

rifatrraazz

6 лет назад, скрыть # ^ |

It's actually Memory Limit Exceeded.

→ Ответить

Unknownwarrior

3 года назад, скрыть # ^ |

yes

→ Ответить

abhilash_8642

5 лет назад, скрыть # ^ |

this worked for me...

→ Ответить

Ricky_99

4 года назад, скрыть # ^ |

bro can you paste the AC code (recursive one)

→ Ответить

abhilash_8642

4 года назад, скрыть # ^ |

Sorry I haven't written recursive . But iterative one :

include<bits/stdc++.h>

using namespace std;

int mod = 1e9 +7; int main(){ int n,x; cin>>n>>x; pair<int,int> h[n];

for(int i=0;i<n;i++){
    cin>>h[i].first;
}
for(int i=0;i<n;i++){
    cin>>h[i].second;
}
int dp[n+1][x+1];
dp[0][0]=0;
for(int i=0;i<=n;i++){
    dp[i][0] = 0;
}
for(int i=0;i<=x;i++){dp[0][i]=0;}
for(int i=1;i<=n;i++){
    for(int j=1;j<=x;j++){
        dp[i][j] = dp[i-1][j];
        if(j>=h[i-1].first){
            dp[i][j] = max(dp[i-1][j- h[i-1].first]+h[i-1].second,dp[i][j]);
        }
        dp[i][j] %= mod;
    }
}

cout<<dp[n][x]<<"\n"; }

→ Ответить

uju

4 года назад, скрыть # ^ |

← Rev. 2 →

I am using iterative way but still getting tle what could be the reason here is the code

include

using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(0);

int n, x;
cin >> n >> x;
int dp[x + 1][n + 1];
int prices[n + 1];
int pages[n + 1];
memset(dp, 0, sizeof(dp));

for (int i = 1; i <= n; i++)
{
    cin >> prices[i];
}
for (int j = 1; j <= n; j++)
{
    cin >> pages[j];
}

for (int i = 1; i <= x; i++)
{
    for (int j = 1; j <= n; j++)
    {
        dp[i][j] = max(dp[i][j - 1], (i - prices[j]) >= 0 ? (dp[i - prices[j]][j - 1] + pages[j]) : 0);
    }
}

cout << dp[x][n] << "\n";
return 0;

}

→ Ответить

SidJain

3 года назад, скрыть # ^ |

Your code seems perfect to me. Did you find the error?

→ Ответить

Ditto

3 года назад, скрыть # ^ |

Yes.

→ Ответить

Stupido

2 года назад, скрыть # |

Surprisingly, my solution with a complexity of O(1e8) was accepted, and it ran in only 0.1 seconds.

→ Ответить

ashishrana0253

2 года назад, скрыть # ^ |

can you paste your code here

→ Ответить

Stupido

2 года назад, скрыть # ^ |

← Rev. 4 →

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,m;
vector<ll>price,page;
int32_t main()
{
    fast
    ll i,j=0,x;
    cin>>n>>x;
    price.resize(n);
    page.resize(n);
    for(auto &it:price){cin>>it;}
    for(auto &it:page){cin>>it;}
    vector<ll>dp(x+1,INT_MIN);
    dp[0]=0;
    for(auto it:price)
    {
        for(i=x;i>=it;i--)
        {
            dp[i]=max(dp[i],dp[i-it]+page[j]);
        }j++;
    }
    ll ans=0;
    for(i=0;i<=x;i++){ans=max(ans,dp[i]);}
    cout<<ans<<'\n';
}

→ Ответить

SevenAlarm

2 года назад, скрыть # |

I'm surprised that this is for 3 years ago but the latest comments are from 2 weeks ago.

I just got accepted on the task and I had the same problem. I mean technically it should've been an MLE. I dont know if anyone has said this before or not, but here instead of defining a DP[100000][100] I just defined a DP[100000][2] since you only need dp[j][i-1] to update your DP, So you can just store the previous row of your DP table and use parity to go over the loop and store your values.

here's my code:

#include <bits/stdc++.h>
using namespace std;
 
const int mxx = 1e5 + 1;
const int mxn = 1e3 + 1;
int dp[mxx][2];
int s[mxn], h[mxn];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, x;
    cin >> n >> x;
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < x + 1; i++) {
        if (h[0] <= i) dp[i][0] = s[0];
        else dp[i][0] = 0;
    }
 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= x; j++) {
            if (h[i] > j) dp[j][i%2] = dp[j][1 - (i%2)];
            else dp[j][i%2] = max(dp[j][1 - (i%2)], dp[j - h[i]][1 - (i%2)] + s[i]);
        }
    }
 
    cout << dp[x][(n-1) % 2];
}

→ Ответить