# Hackerrank “Bricks Game”

Problem URL

This is the solution I came up with the minimax problem stated above. I did a top-down recursive approach with memoization, and I think this should be $O(n)$, since we are filling out a memoization table with $n$ elements, with constant number of operations per each recursive call. Nevertheless, I am getting timeout errors for something like n = 1000, which probably indicates this is not an $O(n)$ implementation after all.

Can I get some advice on what my misunderstanding is?

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int pick(vector<int> stack, int idx, int end, vector<int> memo){
// Check if memoized.
if (memo[idx] != -1) return memo[idx];

int last = end - 1;
// Base Case
// Nothing to Pick.
if(idx > last) return 0;
// Only one brick.
else if(idx > last - 1) return stack[last];
// Two bricks.
else if(idx > last - 2) return stack[last] + stack[last - 1];
// Three bricks.
else if(idx > last - 3) return stack[last] + stack[last - 1] + stack[last - 2];

int case1,case2,case3;
int p2,p3,p4,p5,p6;

p2 = pick(stack,idx+2,end,memo);
p3 = pick(stack,idx+3,end,memo);
p4 = pick(stack,idx+4,end,memo);
p5 = pick(stack,idx+5,end,memo);
p6 = pick(stack,idx+6,end,memo);

case1 = stack[idx] +
min({p2,p3,p4});

case2 = stack[idx] +
stack[idx+1] +
min({p3,p4,p5});

case3 = stack[idx] +
stack[idx+1] +
stack[idx+2] +
min({p4,p5,p6});

memo[idx] = max({case1,case2,case3});

return memo[idx];
}

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int tests;
int stackSize;
vector<int> stack(100000,0),memo(100000,-1);
cin >> tests;
for(int test = 0 ;test < tests; test++){
cin >> stackSize;
for(int i=0;i<stackSize;i++) cin >> stack[i];
cout << pick(stack,0,stackSize,memo) << endl;
fill(memo.begin(),memo.begin() + stackSize ,-1);
}
return 0;
}