I_lOVE_ROMAN's blog

Runtime error in a atcoder problem.
By I_lOVE_ROMAN, history, 2 years ago, In English

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;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It most definitely is not good with testcases on any PC. There's multiple mistakes, and you didn't elaborate on anything.

  • You're not returning anything from the recur function
  • You have an "N>=4" case which is just weird, N doesn't change, so what is this supposed to do? I'm guessing something like "i>=N" is what you meant, though that would still be wrong. But at least explain the logic if you expect help.
  • This is exponential in time complexity so it will definitely get TL even if you fix the RE.
→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 

    int rec(vector <int> in,int level){
    if(level==0) return 0;
    if(dp[level]!=-1) return dp[level];

    ll ans1=INT_MAX,ans2=INT_MAX;

    if(level-1>=0) ans1=rec(in,level-1)+abs(in[level]-in[level-1]);
    if(level-2>=0) ans2=rec(in,level-2)+abs(in[level]-in[level-2]);

    return dp[level]=min(ans1,ans2);
}

    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

    int rec(vector <int> &in,int level)

    (passing vector with reference) then the code is working(AC)...what would be the probable reasons for the same

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        You missed that std::vector allocates memory for its elements from the heap.

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah, of course. My bad. It'd be a bad alloc / ML then, never really stack overflow.

          → Reply