Roller Coaster Fun - Kattis (Knapsack DP)

Debugging Help
#1

I recently started learning Dynamic Programming, and am currently trying to solve “Roller Coaster Fun” on Kattis. However, I’m only getting 10/30 test cases, and am stuck on what I am doing wrong.

My thinking is very similar to the coin problem (7.1 in the CPH, scroll down to “Coin Problem”), where we find the answer for each of the 25,000 times using the previous ones:

(this is pseudocode)

// fun[i] is the maximum amount of fun possible at time i
// k[i][j] is the number of times Jimmy goes on coaster j at time i
// all other functions/variables are as given in the problem

fun[1] = 0
fun[n] = max(fun[n - 1], // last fun value (don't go on any new ride)
             fun[n - t[0]] + f(0, k[n][0]),
             ..., 
             fun[n - t[i]] + f(i, k[n][i]), 
             ..., 
             fun[n - t[N - 1]] + f(N - 1, k[n][N - 1]))

Here is my full code:

// https://open.kattis.com/problems/rollercoasterfun

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 100
#define MAX_T 25000

vector<int> a(MAX_N), b(MAX_N), t(MAX_N);

vector<int> dp(MAX_T + 1);
vector<vector<int>> k(MAX_T + 1, vector<int>(MAX_N));

int f(int time, int i)
{
  return max(0, a[i] - k[time][i] * k[time][i] * b[i]);
}

int main()
{
  int N;
  cin >> N;

  for (int i = 0; i < N; ++i)
    cin >> a[i] >> b[i] >> t[i];

  dp[0] = 0;
  fill(k[0].begin(), k[0].end(), 0);

  for (int time = 1; time <= MAX_T; ++time)
  {
    dp[time] = dp[time - 1];
    k[time] = k[time - 1];
    for (int i = 0; i < N; ++i)
    {
      if (time - t[i] >= 0)
      {
        int newFun = dp[time - t[i]] + f(time - t[i], i);
        if (newFun > dp[time])
        {
          dp[time] = newFun;

          k[time] = k[time - t[i]];
          ++k[time][i]; // go on this ride one more time
        }
      }
    }

    // cout << time << ' ' << dp[time] << '\n';
  }

  int Q;
  cin >> Q;

  int q;
  for (int i = 0; i < Q; ++i)
  {
    cin >> q;
    cout << dp[q] << '\n';
  }

  return 0;
}

Any help would be appreciated!

#2

TLE or WA?

#3

Wrong answer after 10/30 test cases (so on test case 11).

#4

Might the problem be with integer overflow? I haven’t taken a thorough look at your code- I only see that it uses ints intead of long longs.

#5

I highly doubt it - the constraints are quite low (0 < N <= 100, 0 <= T <= 25000, so maximum time t_i is only 250,000). I’m pretty sure it is some sort of off-by-one error, or my reasoning isn’t sound (as I said, this is one of the first DP problems I’ve ever done).

#6

Hm, yeah, I guess so. Maybe try randomly generating test cases and compare your output with that of some established solution’s?