SEATRSF - Editorial

[djdolls]

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Jingbo Shang
Editorialist: Ajay K. Verma

DIFFICULTY:

EASY

PREREQUISITES:

High school maths, Inclusion-exclusion 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:
A = number of sequences on N elements, with each element in [a, b],
B = number of sequences on N elements, with each element in [a, b - 1],
C = number of sequences on N elements, with each element in [a + 1, b], and
D = number of sequences on N elements, with each element in [a + 1, b - 1].

The number of N-element sequences with each element in [a, b] satisfying the constraint that

1. at least one element of the sequence is equal to a, and,
2. at least one element of the sequence is equal to b, is given by
   (A - B - C + D).

The number of N-element 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:
(Q + 1)^N - 2 * Q^N + (Q - 1)^N.

Since the value of “a” can be anything in the range [1, M - Q], the number of sequences with the max-min 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 max-min difference Q after k transformations.

Invariance of max-min 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₁, a₂, …, a_N.
Let us define two new variables

m = min(a₁, a₂, …, a_N),
s = a₁ + a₂ + … + a_N

After the transformation the sequence becomes b₁, b₂, …, b_N given by
m + s - a₁, m + s - a₂, …, m + s - a_N

Note that,
(b_i - b_j) = (m + s - a_i) - (m + s - a_j) = -(a_i - a_j).

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
b_i1 - b_i2 = -(a_i1 - a_i2) = (a_i2 - a_i1)
which is the same as the difference between the largest and smallest element of the original sequence.

This means, we can ignore the transformation completely, and now our problem has been reduced to find the number of N-element 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 max-min 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
(1, 1 + Q)
(2, 2 + Q)
…
(M - Q, M)

Now, let us find out the number of N-element 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
A = (b - a + 1)^N = (Q + 1)^N

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
B = number of sequences with elements in [a, b], but none equal to b
C = number of sequences with elements in [a, b], but none equal to a
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 B and C

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:
B = number of sequences with elements in [a, b - 1]
C = number of sequences with elements in [a + 1, b]
D = number of sequences with elements in [a + 1, b - 1]

Equivalently,
B = (b - a)^N = Q^N
C = (b - a)^N = Q^N
D = (b - a - 1)^N = (Q - 1)^N

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
A - (B + C - D) = (Q + 1)^N - 2Q^N + (Q - 1)^N.

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 exponentiation

Finally, 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.
Tester’s solution can be found here.

[abhi_93104]

I think it will be (M - Q) * ((Q + 1)^N - 2*Q^N + (Q - 1)^N).
Please correct me if i m wrong.

[djdolls]

thanks, fixed.

[mjnovice]

this question, seemed daunting to me at first. But on some head scratching and paper work, it became fairly evident that “k” was useless. and no matter how many times the operation was made the answer remained max(sequence)-min(sequence). And after this the job remained to find all pairs a,b sych that a-b = some number, and the number of sequences possible with each such pair, which can be found very easily by the formula given above by abhi_93104, replacing a by M and b by Q.

[samkit]

Same here but different outcome…I figured out that max(seq) - min(seq) would be same no matter what. Somehow I was trying to correlate k’s existence with other factors which was getting me nowhere. Result:Not able to solve this problem

[samkit]

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