PROBLEM LINK:Author: Sergey Nagin DIFFICULTY:EASY PREREQUISITES:High school maths, Inclusionexclusion principle, Modular exponentiation PROBLEM:Given three integers N, M and Q, find the number of sequences of N elements, with each element in [1, M] such that the difference between the maximum and minimum element of the sequence is Q. QUICK EXPLANATION:If we fix the minimum value of the sequence to an integer a, then the maximum value of the sequence is b = a + Q. Now consider the following four values: The number of Nelement sequences with each element in [a, b] satisfying the constraint that The number of Nelement sequences with element in the range [x, y] is given by N^{y  x + 1}, as each element of the sequence has (y  x + 1) choices. Hence, the number of sequences satisfying the above constraints will be: Since the value of "a" can be anything in the range [1, M  Q], the number of sequences with the maxmin difference constraint is (M  Q) times the above expression. Special care has to be taken for the case when M <= Q, in which case there are no valid sequences. EXPLANATION:Serja starts with a sequence of N elements, and applies a specific transformation k times. After that he computes the difference between the maximum and minimum element of the resulting sequence. He wants to know how many starting sequences with each element in range [1, N] will produce the same maxmin difference Q after k transformations. Invariance of maxmin difference:The first observation to make is that the transformation does not alter the difference between maximum and minimum element of the sequence. Assume that we have a sequence a_{1}, a_{2}, ..., a_{N}. Let us define two new variables m = min(a_{1}, a_{2}, ..., a_{N}), After the transformation the sequence becomes b_{1}, b_{2}, ..., b_{N} given by Note that, This means that after the transformation, the order of element is reversed, hence if a_{i} was the maximum (minimum) of the original sequence, then b_{i} will be the minimum (maximum) of the new sequence. Let us say that a_{i1} was the smallest element of the original sequence, and a_{i2} was the largest element of the original sequence. After transformation b_{i2} will be the smallest element and b_{i1} will be the largest element. The difference between the new maximum and new minimum element is This means, we can ignore the transformation completely, and now our problem has been reduced to find the number of Nelement sequences with each element in [1, M] such that the difference between maximum and minimum element of the sequence is equal to a given value Q. Case when Q = 0:The problem constraints specify that Q >= 1, hence this case will never occur. If the value of Q was allowed to be 0, then in that case the answer would be M, as all elements of the sequence should be the same and can take any of the values from 1 to M. Case when M is too small (M <= Q):Since all elements of the sequence are chosen from the range [1, M], the maximum difference between two element can be (M  1). If the desired maxmin difference Q is larger than this value, then we certainly cannot construct any such sequence. In other words, if (M <= Q), then the answer is 0. Case when M > Q > 0:Since the difference between maximum and minimum element of the sequence is Q, the possible candidate for the minimum and maximum elements are Now, let us find out the number of Nelement sequence with minimum value a and maximum value b. First, let us find the number of sequences, where all elements are in the range [a, b]. Since any element of the sequence can take any value in the range [a, b], i.e., it has (b  a + 1) choices, the number of such sequences is given by Although all the elements are in the range [a, b], it is possible that none of the element of the sequence is equal to a, or b. Hence, we need to remove those sequences which do not contain either a or b. Let Hence, the number of sequences with elements in [a, b] which do not contain either a or b, will be given by (B + C  D). Further, we can see the following definitions of B, C and D are equivalent: Equivalently, Therefore, the number of subsequences with elements in [a, b] and having at least one element equal to a, and at least one element equal to b, is given by Note that the number of sequences is independent of a and b, and only depends on Q. We have (M  Q) candidate pairs for (a, b) as shown above. Hence, the answer will be (M  Q) * ((Q + 1)^{N}  2Q^{N} + (Q  1)^{N}) Modular exponentiationFinally, in order to compute the value of (Q + 1)^{N}, Q^{N}, (Q  1)^{N} we need to use the modular exponentiation, which have been the part of many problems of previous contests. Here is the snippet that does the same. // Calculates x^y mod P power(x, y, P uint64_t) uint64_t { if (y == 0) return (1 % P); t := power(x, y/2, P); t = (t * t) % P; if (y & 1) t = (t * x) % P; return t; } Time Complexity:O (lg N) AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution will be put up soon.
This question is marked "community wiki".
asked 14 Oct '13, 16:24

I think it will be (M  Q) * ((Q + 1)^N  2*Q^N + (Q  1)^N). Please correct me if i m wrong. answered 14 Oct '13, 16:46

"D = number of sequences with elements in [a, b], but none equal to a, b. These are the sequences which have been counted in both Q and R"
I think in above sentence B,C should come in place of Q,R.