Why am I getting MLE (Memory Limit Exceeded) error in this problem

help
,
1

Problem link: https://codeforces.com/problemsets/acmsguru/problem/99999/123

// #include<bits/stdc++.h>
#include<iostream>
// #define f(a,b) for(int i=a;i<b;i++)
// #define dbg(x); cout<<"\n"<<#x<<": "<<x<<"\n";
#define ret return
using namespace std;
const int MAX=41;
int f[MAX]={0};
int fibo(int k){
	if(k==0)	ret 0;
	if(k==1||k==2)	ret (f[k]=1);
	if(f[k])	ret f[k];
	int m=(k&1)?(k+1)/2:k/2;
	f[k]=(k&1)?(fibo(m)*fibo(m)+fibo(m-1)*fibo(m-1)):(2*fibo(m-1)+fibo(k))*fibo(m);
	ret f[k];
}
int sum(int k){
	ret fibo(k+2)-1;
}
int main(){ 
	// ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
	int k;
	cin>>k;
	cout<<sum(k)<<"\n";
	ret 0; 
}
2

Most likely stack overflow…
Try writing an iterative solution

4

Well it’s very simple
Just tabulate first k numbers and sum them up afterwards

6

yeah that was naive approach

maybe using vector instead of static array will do

7

No difference.
Even in recursion this is normal
Use Fibonacci function till k and store them in an array
Then do summation of that.

8 
int table[42];
int fib(int k){
      if(k==0 or k==1) //base conditions 
          return 1;
      if(table[k]!=0) return table[k];
      return table[k]=fib(k-1)+fib(k-2);

This is Fibonacci right?
Then just loop through 0 to k(inclusive) and add the values in a variable

1 Like
9

Don’t use a table, and no arrays. Don’t even need sum. Find the n+2th term and subtract 1
Use fib1=1
Fib2=2
For i 3 to n+2
Fib2=fib1+fib2
Fib1=fib2-fib1

Cout<<fib2-1

2 Likes
10

Yeah arrays obviously increase space.
I just wrote like that because he was using recursion to solve it

1 Like