COLLECT - Editorial

collect
combinatorics
editorial
june13
medium

#1

Problem Link:

Practice

Contest

Difficulty:

Medium

Pre-requisites:

Combinatorics

Problem:

You are given a line of bushes from 1 to N, each having C* berries. A query (L, R) scenario is as follows. K tourists visit contiguous ranges of bushes, collecting all their berries (which then regrow instantly). They then want to divide the total berries among themselves evenly (no two people should have their number of berries differing by more than 1). In how many ways can this division be done? Two divisions are considered different if there is a single berry that goes to different people in the two divisions, and all berries among all bushes are distinct. You may also have to update the C[] array in between execution.

Quick Explanation:

The solution to a query only depends on the total number of berries B, and the number of people K. Further, exactly (B % K) people will get floor(B/K) + 1 berries, and the remaining will get exactly floor(B/K). This is seen by arranging berries in a ceil(B/K) x K grid, and giving columns of berries to each person.

Now, dividing the berries among the people can be thought of as first choosing who all to give floor(B/K) berries, and then using formula for multinomial coefficient to divide B items into K sets where set i has size Xi. This gives K choose (B % K) for the first term, and B! / product(Xi!) for the second term. Notice that Xi = floor(B/K) + 1 for (B % K) such i, and is floor(B/K) for the remaining.

Final answer:
Given, L, R,
compute B = C[L] + C[L+1] + … + C[R], K = R - L + 1, x = floor(B/K), i = B % K.
f(B, K) = K!/(i!(K-i)!) * B! / ((x+1)!i * (x!K - i))

Also, we need to be able to compute sum of a range of array C[] as well as update elements of C[] quickly. This can be done using either a segment tree or a Fenwick tree etc. giving an overall complexity of O(logN) per query.

A few things to note:
Since the answer is large, we should take our answer modulo the number 3046201, which is prime. Further, the maximum value of any factorial we use is less than this, so we can precompute all factorials easily. We would also need to be able to find inverses and powers efficiently. These both can be done with logarithmic exponentiation in O(logP) time.

Explanation:

As mentioned in the Quick Explanation, the first thing to note is, in order to answer a query, we just need to know how many berries are there in total, and how many people we need to distribute these berries to. Once we know these: B = number of berries, K = number of people, let us call denote our answer as f(B, K).

The next natural thing to ask is, how many berries should go to each person?

Since we ensure that two people do not get a number of berries differing by more than one, we can say that everyone gets either “x” or “x+1” berries for some value “x”. Lets say “i” people get value “x+1”. Then, we have the constraint
“i * (x+1) + (K-i) * x = B”,
which gives us that
“K * x = B - i”.
Note that 0 <= i <= K (in fact, i = K can be considered as a degenerate case of i=0, and x=x+1, so we just take i < K). This gives us immediately that x = floor(B/K) and i = B % K.

Now, let us fix some set of people to get floor(B/K) (=“x”), and the others get floor(B/K)+1. For these people fixed, we count the number of ways. Then we sum over all such ways of dividing the sets.

Let us consider the general case of dividing a set of size N into subsets of size x1, x2, x3, …, xK, where sum(xi) = N. The first set can be chosen in Comb(N, x1) ways. The next set in Comb(N-x1, x2), … the i’th in Comb(N-x1-x2…-x(i-1), xi) ways. If you write Comb(n, r) as n!/(r!(n-r)!), and expand out the above, you will get a telescoped product that becomes N!/(x1! * x2! * x3! * … * xK!).

We know however, that exactly (B % K) of the above have value xi = x + 1, and that the remaining have value xi = x (recall, x = floor(B/K)). This means, our actual number of ways, after we have fixed our set of people who get (x+1) berries, the number of ways of dividing the berries is

B! / (((x+1)!)i * (x!K - i)), where i = B % K.

The number of ways of choosing a set of people to get (x+1) berries is Comb(K, i) = K!/(i! * (K - i)!)

Thus, given the values B and K, f(B, K) =
K!/(i! * (K - i)!) * B! / (((x+1)!)^i * (x!^(K - i)))

In the above formula, notice that we have a lot of Factorials, a few divisions, and a few powers. If we precompute values of factorials modulo P, as well as write a logarithmic exponentiation function, then division is also taken care of because a^-1 = a ^ (P-2) modulo P.

The final caveat is that we need to find sums of ranges and update individual elements efficiently. This however can be done in O(logN) time using either a segment tree or a Binary Indexed Tree.

Setter’s Solution:

Can be found here

Tester’s Solution:

Can be found here


#2

Nice problem, I was dying for an opportunity to use Fenwick tree. This problem also helped a lot understanding modulo multiplicative inverse. I won’t have to rely so much on BigInteger now.


#3

Links to the solution are broken. Kindly update them.


#4

http://www.codechef.com/viewsolution/2241223

This solution works well on my PC, but why is it throwing Runtime errors here ???
Any idea anyone ???


#5

Can you please explain the answer to the second query - 1 8 ?


#6

Solution links are broken.


#7

@pragrame, Nice explanation my friend. I am very weak at probablity… :(. The links to Setters and Testers solution are broken. Can you please help me (with a link) about how to find large factorials in C/C++ efficiently.

Also, I have a doubt that since factorials involves multiplication we can use modulo logic there is asked in question, but suppose we want combinations which involves division as well then what is the method ?


#8

@ajit_a Following is the logic to calculate factorials
This is possible because Modulo operation is distributive over addition, multiplication etc.

factTable[0] = factTable[1] = 1;

for (int n = 1; n < 3000002; ++n) {

factTable[n] = (factTable[n - 1] * n) % MOD;

}

Also for division, we can take “modular multiplicative inverse” and then multiply the inverse to our formula. When P is prime, we can calculate modular multiplicative inverse of a as,

a^(-1) = a^(P-2) modulo P

if P is not prime, we can use extended euclidean algorithm to calculate the the inverse.


#9

@bhambya Thanks for the reply. Its a good solution which stores the factorials for all the numbers in an array and then we can use it in O(1) whenever required.
Although I doubt if such a loop would run withing the time limit on CC this is certainly good in some cases where the upper bound is fixed.

I couldn’t quite understand the second part. Can you please explain with an example, like (1023/87)mod 3 or any other example which will help it understand.


#10

Fermat’s Little Theorem says that if a!=0 (well, 1/a not defined when a = 0), then a^(P-1) = 1 (mod P). We want “a^(-1)”, so lets multiply both sides by a^-1, we get a^(P-2) = a^-1 (mod P), when P is prime.

Your example is bad because 1023 * 87^-1 (mod 3) doesn’t make sense because 87 mod 3 = 0. You’re kind of trying to do 0/0 here.

Lets take 25(mod 29)/16(mod29) = 25 * (16^-1) = 25 * (16^27) = 7 (mod29).

Lets do the reverse to recheck:

25/16 = 7 (mod29) <=> 25 = 112 (mod29) <=> 25 = 29*3 + 25 (mod29). Yay, it matches!


#11

Excellent explanation!!


#12

@Pragrame. Thanks for the explanation. I also got some help from here http://discuss.codechef.com/questions/1283/olympic-editorial?page=1#1317

Still, I have a small (may be silly) doubt. MOD is usually 10^9 + 7. So If if need to find (A/B)% MOD, It will result into ((A % MOD)*(B^MOD-2))%MOD. Here, the second part (B^MOD-2) will be very large… so will it not overflow ? How to handle it ?

Please Correct me if I have misunderstood something.