You are not logged in. Please login at www.codechef.com to post your questions!

×

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{align*} 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{align*}$$ 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{align*} 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{align*}$$ 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{align*} 1 + 6 + 11 + 16 + 21 + 26 &= 81 \\\ 6 + 9 + 12 + 15 + 28 + 21 &= 81 \\\ 11 + 12 + 13 + 14 + 15 + 16 &= 81 \end{align*}$$ 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

This question is marked "community wiki".

asked 19 Jun '16, 15:16

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 22 Jun '16, 10:50

admin's gravatar image

0★admin ♦♦
19.8k350498541


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!

link

answered 21 Jun '16, 18:44

sahilarora.535's gravatar image

4★sahilarora.535
1235
accept rate: 0%

2

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

(22 Jun '16, 20:52) superty3★

@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.

link

answered 22 Jun '16, 09:38

tihorsharma123's gravatar image

2★tihorsharma123
49718
accept rate: 15%

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;}

link

answered 21 Jun '16, 23:01

hitman333's gravatar image

2★hitman333
212
accept rate: 0%

edited 21 Jun '16, 23:01

oops.i found the mistake.

(21 Jun '16, 23:32) hitman3332★

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

link

answered 21 Jun '16, 23:52

hitman333's gravatar image

2★hitman333
212
accept rate: 0%

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?

link

answered 22 Jun '16, 11:06

vishveshcoder's gravatar image

4★vishveshcoder
18729
accept rate: 0%

Your approach wont work for this case: 10 70

(25 Jun '16, 10:43) bhishma4★

@vishveshcoder a and d have to be positive integers.

link

answered 22 Jun '16, 12:05

vk24's gravatar image

3★vk24
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,191
×105
×88
×8

question asked: 19 Jun '16, 15:16

question was seen: 4,069 times

last updated: 25 Jun '16, 10:43