Here is the link of problem at atcoder:
I tried it with a naive recursion approach. It's running good with the testcases in my pc but getting RE in atcoder compiler. I have no clue how it is getting RE.
Here is the solution
#include<bits/stdc++.h>
using namespace std;
int N,sum=0,mn=INT_MAX,h[100006];
int recur(int i,int sum)
{
if(N>=4)
{
return mn=min(sum,mn);
}
else
{
recur(i+1,sum+abs(h[i+1]-h[i]));
recur(i+2,sum+abs(h[i+2]-h[i]));
}
}
int main()
{
int n,i,j,k;
cin>>N;
for(i=1;i<=N;i++)
{
cin>>h[i];
}
cout<<recur(1,0)<<endl;
return 0;
}
It most definitely is not good with testcases on any PC. There's multiple mistakes, and you didn't elaborate on anything.
this is the easy frog jump 1 form at coder dp contest it is not working with the code given above (giving RE) but if i make a single change in function definition and make it
(passing vector with reference) then the code is working(AC)...what would be the probable reasons for the same
This is a common mistake — in C++ the default behavior of passing arguments in a function is pass-by-value.
This means that if you give an object as an argument to a function, it will by default try to copy it. In this case it knows how to copy vectors, so it does. The result is that on each call you're creating a copy of this vector, which is presumably of size $$$O(N)$$$. Since the recursion depth can be $$$O(N)$$$, at the bottommost point you end up with $$$O(N^2)$$$ memory allocated on the stack, which probably fails with some bad alloc or stack overflow.
When you're passing a reference, it's not copying anything and is instead only using the original vector, which is what you want here since you're not modifying it.
You missed that std::vector allocates memory for its elements from the heap.
Ah, of course. My bad. It'd be a bad alloc / ML then, never really stack overflow.