Hackerrank "Bricks Game"

Question

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

Answer 1

You are passing the stack vector by value, which means that on each call to pick, you will incur O(n) time to copy the vectors. You need to pass by reference or const reference.

See my answer here to another question with the same problem: https://codereview.stackexchange.com/a/144084/36120

• user1751434: Ah. That makes sense, thanks a ton. I changed my code to call the vectors by reference. The timeouts are gone, but now I am getting abort calls from some cases. Hmm..
• user1751434: Changed the memo vector to a map, and then it worked. Guess I was using up the memory limit