ARITHM - Editorial

PROBLEM LINK:

Contest
Practice

Author: Kevin Atienza
Testers: Sergey Kulik and Vasya Antoniuk
Translators: Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Simple

PREREQUISITES:

Arithmetic series

PROBLEM:

Given N and C, is there an arithmetic series with positive integral terms, positive common difference, exactly N terms and a sum of C?

QUICK EXPLANATION:

It’s sufficient to check if there is such a series with common difference 1 or 2.

To check if a series exists with a common difference d, check if 2C - (N-1)Nd is positive and divisible by 2N.

EXPLANATION:

Common difference

The problem would be easier if we know the common difference, say d, between the terms in the arithmetic series, because knowing this, the number of terms, and the sum, is enough to extract the elements of the arithmetic series. Specifically, remember that if a is the first term, then the terms of the series are

a, a + d, a + 2d, \ldots, a + (N-1)d

Then we must have

C = (a) + (a + d) + \ldots + (a + (N-2)d) + (a + (N-1)d)

The only unknown here is a so we can extract it from here. To do so, we can reverse this summation:

C = (a + (N-1)d) + (a + (N-2)d) + \ldots + (a + d) + (a)

By adding these two, we get

\begin{aligned} 2C &= (2a + (N-1)d) + (2a + (N-1)d) + \ldots + (2a + (N-1)d) + (2a + (N-1)d) \\\ &= (2a + (N-1)d)N \\\ &= 2Na + (N-1)Nd \\\ a &= \frac{2C - (N-1)Nd}{2N} \end{aligned}

Thus, we now have the initial term a! From this, we can extract all the other terms.

However, we require the terms to be positive integers, so we need to check if a is a positive integer. Here’s how we can do it:

  • a is positive if 2C - (N-1)Nd is positive.
  • a is an integer if 2C - (N-1)Nd is divisible by 2N.

These are very simple to implement!

Which common difference

Unfortunately, we don’t know the value of d. It may be the case that more than one d is valid, or no d is valid. So which ones do we check? Clearly, we can’t try all values in the range 1 \le d \le C because C is very large!

Let’s consider an example: C = 112 and N = 7. The answer for this case is Yes. The following are a few examples of arithmetic series for thie case:

\begin{aligned} 1 + 6 + 11 + 16 + 21 + 26 + 31 &= 112 \\\ 4 + 8 + 12 + 16 + 20 + 24 + 28 &= 112 \\\ 7 + 10 + 13 + 16 + 19 + 22 + 25 &= 112 \end{aligned}

But notice that there is something similar between all these series, namely, that the average value, 16, is the same all throughout! That actually makes sense, because if the sum of N values is C, then the average value must be C/N. You can indeed check that 112/7 = 16.

As another example, consider C = 81 and N = 6. In this case, we have the following series:

\begin{aligned} 1 + 6 + 11 + 16 + 21 + 26 &= 81 \\\ 6 + 9 + 12 + 15 + 28 + 21 &= 81 \\\ 11 + 12 + 13 + 14 + 15 + 16 &= 81 \end{aligned}

Note that the average value in this case is 81/6 = 13.5, which is not an integer, but that’s okay.

Here’s another observation: The arithmetic series with the largest first term seems to be the one with the smallest common difference, as in the examples above. This kinda makes sense, because given the common difference d and the average value C/N, we can actually compute the first term: The difference between the first and last term is (N-1)d, so the difference between the average and the first term must be d(N-1)/2. Thus, the first term must be C/N - d(N-1)/2! (Note that this is the same as the formula we got above.) In this formula, the smaller the d, the larger the first term, so the series with the largest first term is the one with the smallest d!

What does this mean for us? Well, since we want all terms to be positive, we only need to check the arithmetic series with the largest possible first term. If the first term of this series is not positive, then we can be sure that no valid series exists, because the first term of all other series are smaller! Thus, we only need to check the series with the smallest possible d.

Finally, how do we then determine this d? Well, notice that if C/N - d(N-1)/2 is an integer, and we let d' = d-2, then C/N - d'(N-1)/2 is also an integer! This means that if d > 2, then we can repeat this fact until d becomes \le 2. This means that we only need to check for the common difference d = 1 and d = 2!

Time Complexity:

O(1)

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester 1
tester 2

2 Likes

This is something like ‘Jugaad’, or a hack, and not a solution. I expected something much better than this. When I was solving the problem, I came to a point where I could say that this very equation is valid:

C - (N*(N+1))/2 = X*N + Y*(N*(N-1))/2

where X is a-1 (a = first term of AP), and Y = d-1 (d = common difference of the AP). This means that everytime a increases by 1, the left hand term increases by N, and whenever d increases by 1, the left hand term increases by (N*(N-1))/2. It was a Diophantine equation and we had to find non-negative solutions in X and Y to it.

A better editorial with a more intuitive proof would have been much better!

3 Likes

is there anything wrong in this method:

/**********

if(n==1)
then “yes”;
else if(n==2)
{
if(c>2)then “yes” else “no”;}
else
{
sum=n*(n+1)/2;
if(c<sum)then “no”;
else if(gcd(n,c)!=1)
then yes;
else n0;}

oops.i found the mistake.

could not understand why we only need to check for the common difference d=1 and d=2?

@hitman333 Suppose answer exists for any given common difference d , then a must be greater than or equal to 1 and a must be an integer. Ryt? In editorial there is one equation given a=(2c-n(n-1)d)/(2n)
when answer exists for a common difference d , then a must be integer. now replace d by d-2 and find the new value of a.Let it be a’ then a’=a+(n-1)(you can check it out) Now a’ is also integer since a is integer and (n-1) is intger and it is greater than equal to 1 also. So for d-4 also new a will be integer. So it basically depends on parity of d. If d is odd, u can check for d=1 and for even U can check for d=2. SO if answer exists for odd d , it will definitely exist for 1 also ,Similarly for even case.

1 Like

My method to solve this problem was see this series
a, a+d,…
so total sum is na + n(n-1)/2 d = C(no. of choclates)
now if C % gcd(n, n
(n-1)/2) is 0 then we are done…
What is wrong in this solution?

@vishveshcoder a and d have to be positive integers.

This is a pretty straightforward solution, with no real observations to be made:

We need to solve aN + (N(N-1)/2)d = C

=> N(2a + (N-1)d) = 2C

so C must be divisible by N.

=> 2a + (N-1)d = 2C/N
=> (N-1)d = 2C/N - 2a

in other words, we need to find an even number (2a) such that 2C/N - (2a) is divisible by (N-1)

let e = (2C/N) % (N - 1)
if e is even, we’re done. else we can try and see if e + N - 1 is even, in which case we’re done. The only observation required in this solution is that we need not try e + 2*(N - 1) since this has the same parity as e.

Edit: also check that (2C/N)-(2a) > 0

1 Like

Your approach wont work for this case: 10 70