AC_AC's blog

CSES DP SECTION — Book Shop
By AC_AC, history, 2 years ago, In English

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
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

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)

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

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

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

      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)!

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

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

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

      It's actually Memory Limit Exceeded.

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

      I know right! Same stuff happened to me and it was so annoying.

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

    this worked for me...

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

      bro can you paste the AC code (recursive one)

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

        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"; }

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

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

          include

          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;

          }

          → Reply
          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

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

            → Reply