PROBLEM LINK:
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
Then we must have
The only unknown here is a so we can extract it from here. To do so, we can reverse this summation:
By adding these two, we get
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:
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:
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)