Unexpected failed test case for codeforces 455A boredom

-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?

edited Jan 2 at 14:18

drescherjm

6,54423552

asked Jan 2 at 13:06

akash12121

7

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 2 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 2 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 2 at 13:45

add a comment |

-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?

edited Jan 2 at 14:18

drescherjm

6,54423552

asked Jan 2 at 13:06

akash12121

7

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 2 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 2 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 2 at 13:45

add a comment |

-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?

edited Jan 2 at 14:18

drescherjm

6,54423552

asked Jan 2 at 13:06

akash12121

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?

c++ dynamic-programming

edited Jan 2 at 14:18

drescherjm

6,54423552

asked Jan 2 at 13:06

akash12121

edited Jan 2 at 14:18

drescherjm

6,54423552

asked Jan 2 at 13:06

akash12121

edited Jan 2 at 14:18

drescherjm

6,54423552

edited Jan 2 at 14:18

drescherjm

6,54423552

edited Jan 2 at 14:18

drescherjm

6,54423552

asked Jan 2 at 13:06

akash12121

asked Jan 2 at 13:06

akash12121

asked Jan 2 at 13:06

akash12121

7

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 2 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 2 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 2 at 13:45

add a comment |

7

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 2 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 2 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 2 at 13:45

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 2 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 2 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 2 at 13:45

add a comment |

1 Answer
1

active

oldest

votes

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]);

edited Jan 2 at 15:24

answered Jan 2 at 13:51

drescherjm

6,54423552

THANK YOU VERY MUCH FOR WRITING SUCH A HELPFUL ANSWER

– akash12121
Jan 2 at 14:58

2

@akash12121 Please, stop SHOUTING at everybody!

– Lightness Races in Orbit
Jan 2 at 16:43

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54006912%2funexpected-failed-test-case-for-codeforces-455a-boredom%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

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?

edited Jan 2 at 15:24

answered Jan 2 at 13:51

drescherjm

6,54423552

THANK YOU VERY MUCH FOR WRITING SUCH A HELPFUL ANSWER

– akash12121
Jan 2 at 14:58

2

@akash12121 Please, stop SHOUTING at everybody!

– Lightness Races in Orbit
Jan 2 at 16:43

add a comment |

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?

edited Jan 2 at 15:24

answered Jan 2 at 13:51

drescherjm

6,54423552

THANK YOU VERY MUCH FOR WRITING SUCH A HELPFUL ANSWER

– akash12121
Jan 2 at 14:58

2

@akash12121 Please, stop SHOUTING at everybody!

– Lightness Races in Orbit
Jan 2 at 16:43

add a comment |

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?

edited Jan 2 at 15:24

answered Jan 2 at 13:51

drescherjm

6,54423552

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?

edited Jan 2 at 15:24

answered Jan 2 at 13:51

drescherjm

6,54423552

edited Jan 2 at 15:24

answered Jan 2 at 13:51

drescherjm

6,54423552

answered Jan 2 at 13:51

drescherjm

6,54423552

answered Jan 2 at 13:51

drescherjm

6,54423552

THANK YOU VERY MUCH FOR WRITING SUCH A HELPFUL ANSWER

– akash12121
Jan 2 at 14:58

2

@akash12121 Please, stop SHOUTING at everybody!

– Lightness Races in Orbit
Jan 2 at 16:43

add a comment |

THANK YOU VERY MUCH FOR WRITING SUCH A HELPFUL ANSWER

– akash12121
Jan 2 at 14:58

2

@akash12121 Please, stop SHOUTING at everybody!

– Lightness Races in Orbit
Jan 2 at 16:43

THANK YOU VERY MUCH FOR WRITING SUCH A HELPFUL ANSWER

– akash12121
Jan 2 at 14:58

@akash12121 Please, stop SHOUTING at everybody!

– Lightness Races in Orbit
Jan 2 at 16:43

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu