DIVIDING - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Konstantin Sokol
Tester: Gerald Agapov
Editorialist: Tasnim Imran Sunny

DIFFICULTY:

Cakewalk

PREREQUISITES:

Simple Math

PROBLEM:

Given a list of N integers check if their sum is the same as the sum of first N natural numbers.

EXPLANATION:

The required stamp division is possible if:

C1 + … + CN = 1 + 2 + … + N

There’s a very common formula for the sum of first N natural numbers that is:
1 + 2 + … + N = N(N+1)/2*. (Proof)

So just compute the sum of all the numbers and check if the sum is N*(N+1)/2. Be careful of overflow, use 64 bit integers for computing the sum.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like
2

Hi,

This was exactly what I did and I got AC in Python only…

Possibly, my C++ solution was overflowing although I was using ULL…

Was there any issue like this? Or any trick which would prevent overflow?

1 Like
3

Here it is: AC Python solution: http://www.codechef.com/viewsolution/3636519

And the incorrect C++ one: http://www.codechef.com/viewsolution/3635612

4

No overflow in my case. I infact use long long and got AC.

http://www.codechef.com/viewsolution/3634526

1 Like
5

@kuruma The mistake is that you take n as an int due to which overflow occurs in total variable

1 Like
6

Yes, but then I’m declaring total as ULL… won’t it “typecast” immediately?

7

You also have to take n as long long int cuz when you multiply two integers and if they overflow the result would be wrong. Consider multiplying 10^6 * 10^6, if you have stored 10^6 in int than the result would overflow. It doesn’t matter if you have declared the storing variable as ull.

8

total = n*(n-1)/2 is where i think an overflow is possible because the intermediate variable will be stored in integer. A get around for that is total = n;total =(total*(n-1))/2;

9

Maybe the problem is that n*(n+1)/2 is evaluated as int and then cast to long long?

10

The way you calculate total is incorrect : n*((n+1)/2) for n = 2 gives 2 instead of 3.

11

Other than overflow error, you got WA because you use
int total = n*((n+1)/2);

for n=4 , total=8
but it should be 10.

the formula should be int total = n*(n+1)/2; because associativity is from left to right and one out of n and n+1 will definitely be even.
so that n*(n+1) will be even…

That’s why your code will give wrong answer for n=even

1 Like
12

there is a problem in your c++ code … your are taking n to be int and when you compute n*(n+1)/2 it tries to fit the answer in int …which overflows… so try taking long long int for int and you will get ac …also you need to change the statement n*((n+1)/2) to (n*(n+1))/2… this will get you a ac

link to your code with changes http://www.codechef.com/viewsolution/3641316

13

Thank you to all for the comments, I switched my previous declaration of total to:

unsigned long long int total = (n*(n+1ULL)/2);

and got AC at last!! :slight_smile:

Link to AC solution in Practice: http://www.codechef.com/viewsolution/3641364

Thank you,

Bruno

14

http://www.codechef.com/viewsolution/3636433
Whats wrong with that?

15

I’ve got AC-https://www.codechef.com/viewsolution/8251313
would somebody tell me what is happening behind sum=0ULL ??
ull is typedef unsigned long long .

16

with every addition of number arr[i] just subtract i+1 from the total sum and check weather the sum finally comes to be zero or not if zero then print yes else print no.

Code
long long int sum=0;
for(i=0;i<n;i++)
{
sum+=arr[i];
sum-=(i+1);
}

1 Like