COOKFOOD - Editorial

kuruma · July 28, 2013, 3:00pm

PROBLEM LINKS

Practice

Contest

DIFFICULTY

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 A₁, A₂, A₃, … A_N in this order, and the second dish made by processes B₁, B₂, B₃, … B_N, then A_i != B_i for any 1 <= i <= N, because otherwise chef would need two equipments for the process A_i. Also, no two consecutive processes are the same for each individual dish. That is, A_i != A_i+1 and B_i != B_i+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 A₁ and K-1 choices for B₁. For a general other i, when we fill in A_i and B_i, we wish only that A_i != A_i-1, B_i != B_i-1 and A_i != B_i.

So, there seem to be K-1 choices for A_i != A_i-1 and similarly for B_i. but we haven’t ensured that A_i != B_i. 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 A_i and B_i 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 A_i and then B_i. We have two cases:

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

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

The above reasoning gives us that the number of choices for A_i and B_i 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.

Partial Solutions for subtasks:

Subtask 1:

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 A_pos-1 = a, and B_pos-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.

Subtask 2:

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.

Subtask 3:

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
but instead

x = ((a-b)%MOD + MOD) % MOD

Solutions:

Setter

Tester