This division 2 problem was kindly donated by wrong. Make no mistake, thinking of good problems is not easy, so giving them for free to Topcoder just so that we still get to get three SRMs a month instead of only two, is a good thing.
This problem asks us to count the number of ways we could add a new element to a sequence so that the final sequence is an arithmetic progression or a geometric progression. Perhaps the first thing to notice is that the element added is always going to be the last element. We cannot insert this element in the middle of the sequence, this means that we cannot really modify the nature of the first elements of the sequence. If the original sequence is not an arithmetic progression, then we cannot make it an arithmetic progression by adding a new element to the last position. The same happens with geometric progressions.
For now, we will focus on the arithmetic progression aspect of it. If the original sequence seq is an arithmetic progression, then for every i seq[i]-seq[i-1] = a constant. We will call this constant dif as seq[i]-seq[i-1] is a difference. How can we find dif? Simply pick any pair of consecutive elements, and subtract them. We will pick the first two elements: (dif = seq[1] - seq[0]). Now, note that we should not make assumptions, the original sequence will not necessarily have at least two elements. How can we calculate dif if the sequence only has one element?
If the sequence only has one element, it does not really matter, we could add any number to it and the result will be an arithmetic sequence. Because all sequences of two elements have a single difference between its only two elements, which are consecutive. This means that if the original sequence only had one element, there would be infinitely many numbers we could add. The problem statement specifies that this situation is possible, and it tells us to return -1 in that case. Therefore, if the sequence has one element, return -1.
Back to cases with more than one element in the sequence. We have calculated (dif = seq[1]-seq[0]) for the original sequence to be an arithmetic progression, we should verify that for every i, (seq[i]-seq[i-1] = dif). This will imply that the difference is always constant. In case we find that the difference is constant, we can claim that seq is an arithmetic progression, we can also claim that dif is the constant difference. Do not forget that we are going to add a number X to the end of this sequence, and that the new sequence must stay an arithmetic progression, because of this: (X - seq[n-1] = dif) Where seq[n-1] is the last element in the original sequence. We can conclude that if (X = seq[n-1] + dif), then we can have an arithmetic progression after adding X and only after adding X.
In the case of geometric progressions, the situation is very similar, except that we will have a constant q such that: (q * seq[i-1] = seq[i]). The value of q can be calculated by (q = seq[i] / seq[i-1] ). Note that we are doing a division so we would not want seq[i-1] to be 0, but that is not a problem because all elements of seq are going to be greater than 0 per the constraints definition. Then we can use the newly found value of q, and make sure that the sequence is geometric, that is : (q*seq[i-1] = seq[i] ) . Note that it is not convenient to use division in this case because of rounding causing issues. If the sequence is a geometric progression and the constant factor is q, then we can say that a new number Y to be added to the end of the sequence must be such that: (Y = seq[n-1]*q ).
Adding both logics together includes some challenges. There are four cases to consider:
- The sequence is both an arithmetic and a geometric progression.- This can actually happen with for example seq={4,8} (From the examples) 4+4 = 8 and also 4*2 = 8. If we follow the logics from the previous paragraphs, we will find that (X = 8+4 = 12) and (Y = 8*2 = 16) . In other words, we can add both 12 and 16 to the sequence and the new sequence will be arithmetic or geometric. In this case the result is 2, there are two different number (12 and 16) that do the job.
It is actually possible that both X and Y are equal. In example 2) seq = {1,1} and (X = 1+0 = 1) and (Y = 1*1 = 1). Since both are equal, there is only one number (1) that we need to count. The result is 1.
The trick is to simply say: If (X=Y) then the result is 1, else it is 2. Some coders made the mistake of assuming that only {1,1} was special like this and only handled that specific sequence. But for example, {500,500,500} and any sequence of equal numbers will have equal values of X and Y. - The sequence is only an arithmetic progression.- Then the only number that can do the job is X, the result is 1.
- The sequence is only a geometric progression.- Then the only number that can do the job is Y, the result is 1. We can add these two cases together and just say that if the sequence is only arithmetic or only geometric, the result is 1.
- The sequence is neither arithmetic nor geometric.- Then we cannot do anything, we can add any number, the new sequence will not become arithmetic or geometric because we cannot change the first part of it. The result is 0.
Hey, this problem was definitely easier to solve than to explain, but it may be clearer with just some sample source code:
int theCount(vector <int> seq)
{
int n = seq.size();
// If there is only one element,
// then there are infinitely many ways
// to have this.
if (n==1) {
return -1;
}
// Arithmetic difference
int dif = seq[1] - seq[0];
// Geometric factor
int q = seq[1] / seq[0];
// Verify that the sequence is arithmetic/gemetric or both
bool cangeo = true;
bool canari = true;
for (int i=1; i<n; i++) {
canari &= ( seq[i]-seq[i-1] == dif );
cangeo &= ( seq[i-1]*q == seq[i] );
}
// Possible values for the next element in the
// arithmetic progression and the geometric progression
int x = seq[n-1]*q;
int y = seq[n-1]+dif;
// If both are possible, verify that the numbers are
// actually different, For example with {1,1} it is
// possible to have {1,1,1} no matter if we use an
// arithmetic progression or a geometric one. (example 2)
if ( cangeo && canari ) {
return ( x!=y ) ? 2 : 1;
} else if (cangeo || canari) {
return 1;
} else {
return 0;
}
}
