-5

Guys I am new to competitive programming I was solving a problem(455A BOREDOM) ,I took a solution and tried it to understand it. I believe I understand that that well but I have a small doubt.

   #include<bits/stdc++.h>
    using namespace std;
    #define MAX 100005
    long long dp[100005];
        long long count1[100005];
        int main(){
        int n,x;
        cin>>n;
        for(int i=0;i<n;i++){
            cin >> x;
            count1[x]++;
           // res=max(res,x);
        }
        dp[0]=0;
        dp[1]=count1[1];
        for(int i=2;i<MAX;i++){
            dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]);
        }
        cout<<dp[MAX-1];
    }

However as you can see that the loop is running MAX(100005) even for small test cases. When I tried to optimize that I came up with the following solution:

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long dp[100005];
    long long count1[100005];
    int n;
    cin>>n;

    int x;
    int res=-100000;

    for(int i=0;i<n;i++){
        cin >> x;
        count1[x]++;
        res=max(res,x);
    }

    dp[0]=0;
    dp[1]=count1[1];

    for(int i=2;i<=res;i++){
        dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]);
    }

    cout<< dp[res];


}

However this is giving me the wrong answer on test case 12 https://codeforces.com/contest/455/submission/47841668

The site reported the following error on test case 12:

runtime error: signed integer overflow: 98997 * 8608623459288743937 cannot be represented in type 'long long'

on this line dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]);

Can anyone tell me where i did the mistake ? Why that competitive programmer that kind of mistake is that normal?

drescherjm
  • 10,365
  • 5
  • 44
  • 64
akash12121
  • 5
  • 1
  • 10
    Competitive programming is a load of nonsense. Instead, get yourself a good book on C++ and learn how to solve real-world problems with real-world code. – Lightness Races in Orbit Jan 02 '19 at 13:11
  • You probably should have included the diagnostics for the failure and the test case. The site tells you what the problem is ***runtime error: signed integer overflow: 98997 * 8608623459288743937 cannot be represented in type 'long long'*** on this line `dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]);` – drescherjm Jan 02 '19 at 13:40
  • Note that when you moved your variables to the local scope inside main() they are no longer initialized to 0 that they were as global variables. So count is full of garbage data. – drescherjm Jan 02 '19 at 13:45

1 Answers1

2

The difference is that now that you moved long long count1[100005]; to be inside int main() it is no longer default initialized to 0 as it would when it was a global variable.

Why are global and static variables initialized to their default values?

So when you do this 

for(int i=0;i<n;i++){
    cin >> x;
    count1[x]++;
    res=max(res,x);
}

count1[x] has random garbage values that you increment and then use in the calculation here: dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]) which caused your runtime error reported by the site:

runtime error: signed integer overflow: 98997 * 8608623459288743937 cannot be represented in type 'long long' on this line dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]);

You can see that count1[i] in this case is 8608623459288743937

To fix this you can replace long long count1[100005]; with long long count1[100005]= {};

How to initialize all members of an array to the same value?

Note: That dp is also not automatically initialized to 0. However it is not a problem since you don't read uninitialized values of dp like you did with count1. dp[i-1] and dp[i-2] have been initialized when you use them here dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]);

drescherjm
  • 10,365
  • 5
  • 44
  • 64