# Help with CSES Counting Towers

Problem Link: CSES - Counting Towers

My Code:

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

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
using lld = long double;

const int MOD = 1e9+7;
const int MAXN = 1e6+5;
const ll INF = 1e18;

int main() {
FASTIO

int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<vector<ll>> dp(n+1, vector<ll> (2));
dp[n] = 3, dp[n] = 5;
for(int i=n-1; i>=2; i--) {
dp[i] = 2*dp[i+1]+dp[i+1];
dp[i] %= MOD;
dp[i] = dp[i+1]+4*dp[i+1];
dp[i] %= MOD;
}
cout << (dp+dp)%MOD << "\n";
}

return 0;
}
``````

I have verified the above code on the sample test cases and even verified it on the 100 test cases (on which it fails by giving TLE). But I am still getting RE on the first two tests and TLE on the last two tests. I think it has to do with the huge values of n but then I can’t think of a way to get over this. Can anyone please help?

Why calculate again and again when you can pre-compute. Say you’ll pre-compute answers for all values of n<=N where N is maximum value of n. Then for each test case, you would be answering the query in O(1).
Try this, it may help.

3 Likes

I think I also figured out the reason for Run time error.

For n = 1, it is giving segmentation fault. Try resolving this.

2 Likes

Thanks @suman_18733097 for your time and efforts. 1 Like