 Practice

Contest

Simple

# PRE-REQUISITES

Recurrences, Simple Math

# Problem:

Chef is cooking two dishes, each one takes N processes to be prepared. Chef has K equipments which allow for K processes to be done at a given moment.

Chef has to cook two dishes in parallel.

This means that if the first dish is prepared by applying processes A1, A2, A3, … AN in this order, and the second dish made by processes B1, B2, B3, … BN, then Ai != Bi for any 1 <= i <= N, because otherwise chef would need two equipments for the process Ai. Also, no two consecutive processes are the same for each individual dish. That is, Ai != Ai+1 and Bi != Bi+1.

Knowing this, please report the number of ways in which in which he can prepare the two dishes. Since the number of ways can be very huge, you have to report it modulo 1000000007.

# Explanation:

Let us fill in values for the processes for A and B simultaneously from i = 1 to N. For i = 1, there are K choices for A1 and K-1 choices for B1. For a general other i, when we fill in Ai and Bi, we wish only that Ai != Ai-1, Bi != Bi-1 and Ai != Bi.

So, there seem to be K-1 choices for Ai != Ai-1 and similarly for Bi. but we haven’t ensured that Ai != Bi. We have to still subtract from these (K-1)^2 choices, those where the two are equal to each other, but aren’t equal to the previous two. There are K-2 choices for the them not being equal to the previous two, and for each of these choices, by setting Ai and Bi to this value, we get such a bad case. Thus the total number of ways of getting from i-1 to i, is (K-1)^2 - (K-2).

Another way of arriving at the above is, let us first fill in Ai and then Bi. We have two cases:

Case 1: Ai != Bi-1 and Ai-1 : there are K-2 cases.
Given this, Bi != Bi-1 as well as Ai, hence there are K-2 choices for Bi.

Case 2: Ai = Bi-1. This already gives us that Ai != Ai-1. There is 1 choice for this.
Given the above, Bi != Bi-1 only (since its anyway equal to Ai). Thus, there are K-1 choices for Bi.

The above reasoning gives us that the number of choices for Ai and Bi are (K-2)^2 + K-1. Note that this is also what we had got earlier.

Thus, final answer = (K * (K-1)) * ((K-2)^2 + K-1)^(N-1).

Remember to output this modulo 1000000007.

Also, for full points, we have that an O(N) method to find powers is too slow. In order to find powers in O(logN) time, we use the “logarithmic exponentiation” method.

### Logarithmic Exponentiation

Let us have a function f(a, b) that returns a^b modulo MOD (where MOD = 1000000007).
Then, since a^(b) = (a^2)^[b/2] * a^(b % 2), we have
f(a, b) = (f((a*a) % MOD, b/2) * (b&2 == 1? a : 1)) % MOD;

In the above, we necessarily need that a and b are “long long” (or 64-bit datatypes), else it will overflow an int.

The above method gives us an O(logN) time method to find powers.

With inputs as small as N, K <= 5, we know that the answer is only atmost about 600000, so iterating recursively over all possibilities should also work.

Let f(pos, a, b) := While filling in values from 1 to N, we are at pos, and we have Apos-1 = a, and Bpos-1 = b.
Then, f(pos, a, b) = sum {f(pos+1, c, d): c != a, d != b, c != d, 1<= c, d <= K},
with base cases f(N+1, a, b) = 1,
and the final answer as f(1, 0, 0).

With a DP, the above can be done in O(N * K^4) even.

In fact, the crucial point to note is that f(pos, a, b) really does not depend on the values of a and b. Just that fact that a != b, and the symmetry in all the values would imply that we could just go from pos to pos+1 in each step, which is the essential idea for the full 100, or even for the O(N) approach in subtasks 2 and 3.

This just uses an O(N) approach to find the answer.

The reasoning for this is as described in the Explanation section, except that we don’t bother about MOD, or about O(logN) exponentiation.

Here, we need to take care of the value not crossing MOD. Things like integer overflows etc should be handled.

# Overflow Bugs:

For those who are not used to this arcane “answer modulo 1000000007”, you might be wondering what is going on.

The computer stores integers in 32 bits (int datatype) or 64 bits (long long in c++, long in Java). This means, that for an int, the bounds are:
(1 bit for sign and 31 bits for numbers) = -2^31 to 2^31-1. But what is 2^31?

2^31
= 2 * 2^30
= 2 * (2^10)^3
~ 2 * (10^3)^3
= 2 * 10^9.

So, if you are adding two numbers < MOD, you won’t overflow int. But what if you do

x = (a+b+c) % MOD? Here, a, b and c can go to about 10^9, and then adding all three may go unto 3*10^9, which can overflow int.

For such cases, you would rather use 64 bit integers.
Again, what would the range be for 64 bits integers?
(1 for sign and 63 for numbers) = -2^63 to 2^63-1. AndÉ

2^63
= 2^3 * 2^60
= 8 * (2^10)^6
~ 8 * (10^3)^6
= 8 * 10^18

Now, since MOD is about 10^9, by multiplying two numbers < MOD, you can still be within the range of a 64bit integer. But now, you will need to immediately take “% MOD”, else further multiplications will have errors.
For example, in this problem, using:

``````x = (x*((k-1)+(k-2)*(k-2)))%MOD; // Even though x, k and MOD are 64 bit integers, this is WRONG. Why?
``````

To see why its wrong, just : substitute worst-case (i.e. largest) values into the variables and see if its overflowing even the 64bit datatype anywhere.

### On % operator

One more thing to note about “%” operator, is that if (x < 0) then (x % MOD) will also be < 0. So, if you needed to find (a-b) modulo MOD, you would not do
`x = (a-b) % MOD // this may give you a value < 0`
``````x = ((a-b)%MOD + MOD) % MOD