Блог пользователя I_lOVE_ROMAN

Автор I_lOVE_ROMAN, история, 3 года назад, По-английски

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; }
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        9 месяцев назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          9 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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