Solution to Problem 2: The Leaf Eaters

It is quite easy to determine whether a leaf at position i would be eaten by a caterpillar of length k. This happens only if k-1 is divisible by i. Thus for each i, 1 ≤ i ≤ N we could determine if any one of the K caterpillars would eat leaf i. This naive algorithm would take time proportional to N * K and would work on 50% of the inputs. However to get 100% you need to do more. Note that we only need to count the number of leaves destroyed (or left intact, it is all the same). For each caterpillar, the number of leaves it destroys can be calculated easily. If caterpillar c has length l and there are N leaves then it would eat 1 + (N-1)/l (where / denotes integer division) leaves. We cannot simply sum up this number across all caterpillars since some leaves may be eaten by multiple caterpillars and so we would end up over counting. For example, if we had 10 leaves, and two caterpillers of length 2 and 3 respectively. The two caterpillars eat 5 and 4 leaves respectively. However, leaf 1 and 7 are eaten by both the caterpillars and in fact only 7 leaves and eaten in all (and not 9 = 5 + 4). Suppose we had just two caterpillars c1 and c2 with lengths l1 and l2 respectively. To determine the number of leaves eaten in all, we need add the number of leaves eaten by c1 and the number of leaves eaten by c2 and subtract from this the number of leaves eaten by both of them (since that is the number by which we overcounted in adding the number eaten by c1 and c2). When is a leaf i eaten by both c1 and c2? That happens precisely when i-1 is divisible by l1 and l2. That is precisely when i-1 is divisible by the least common multiple of l1 and l2 (lcm(l1,l2)). Thus the number of leaves eaten by both is given by 1 + (N-1)/lcm(l1,l2) If Des(S) is the number of leaves destroyed by the caterpillars in set S, and Com(S) is the number of leaves eaten by each caterpillar in set S then Des({c1,c2}) = Com({c1}) + Com({c2}) - Com({c1,c2}). If we had 3 caterpillars c1,c2,c3, then this would be Des({c1,c2,c3}) = Com({c1}) + Com({c2}) + Com({c3}) - Com({c1,c2}) - Com({c2,c3}) - Com({c1,c3}) + Com({c1,c2,c3}) To see why this expression is correct, consider a leaf that was destroyed by a single caterpillar. That is counted exactly once in the first line of the above expression and does not contribute to the next two lines. Any leaf that was eaten by exactly two caterpillars contributes 2 to the first row and -1 to the second row. Thus such leaves also contribute exactly 1. Finally, any leaf that was destroyed by all three caterpillars contribute 3 to the first row, -3 to the second row and finally 1 to the third row. Thus they also contribute 1 to the sum. Finally, any leaf that was not eaten by any caterpillar does not contribute at all! Thus the above expression calculates Des({c1,c2,c3}) exactly. Let us write k-sub(S) to mean the set of all subsets of S of size k. Now we can state the expression for Des({c1, ...., ck}) for arbitrary k. Let {c1,c2,...,ck} = S. Then Des(S) = Sum { Com(X) | X is a 1-subset of S} - Sum { Com(X) | X is a 2-subset of S} + Sum { Com(X) | X is a 3-subset of S} . . . +/- Sum { Com(X) | X is a k-subset of S} where the last sign is a + if k is odd and - if k is even. Why is this correct? This is what is called the "Inclusion-Exclusion Principle"and is a very useful counting principle in combinatorics. Let us use the notation |S| to denote the number of elements in a set S. Given a family of sets S_1, S_2, ... S_k the inclusion-exclusion principle states that |S_1 U S_2 U ...U S_k| = Sum { |S_i| | 1 ≤ i ≤ k } - Sum { |S_i /\ S_j| | 1 ≤ i<j ≤ k } + Sum { |S_i /\ S_j /\ S_l| 1 ≤ i < j < l ≤ k } . . . +/- |S_1 /\ S_2 /\ S_3 /\ S_4 ... /\ S_k| (where /\ denotes intersection of sets and U denotes the Union of sets). Why is this principle correct? Pick any element x that appears in n sets say S_i1 S_i2 ... S_in. Clearly x contributes 1 to the left hand side of this equation. Let us try and see how much it contributes to the right hand side. It contributes n to the first line, -C(n,2) via the second line, C(n,3) to the third line and so on till it contributes +1/-1 to line n depending on whether n is odd or even and finally it contributes 0 to every line after line n. We use C(n,i) ("n choose i") to denote number of ways we may pick a subset of size i from a set of size. Recall that C(n,i) = n!/i!(n-i)!)). Now the contribution of x to the right handside is: n - C(n,2) + C(n,3) - C(n,4) ... +/- 1 = Sum { (-1)^{i+1} C(n,i) | 1 ≤ i ≤ n } (where a^b is a to the power b. That is a multiplied with itself b times) = (-1) * Sum({ C(n,i) 1^(n-i) (-1)^i | 1 ≤ i ≤ n} = (-1) * ((1-1)^n - C(n,0)) [ The previous step uses the binomial theorem that states that (1+x)^n = Sum { C(n,i) x^i 1^{n-i} | 0 ≤ i ≤ n } ] = -1 * -1 = 1. This completes the proof of the Inclusion-Exclusion principle. Taking Si to be the set of leaves eaten by caterpillar i, we get that Desc({c1,...ck}) to be |S1 U S2 U ... U Sk| and Com({ci1,ci2 ... cin}) to be |Si1 /\ Si2 /\ ... /\ Sin|. Thus the equation we wrote down was just the statment of the Inclusion-Exclusion principle. Once we have this equation it suffices to see how to compute Com({ci1, ... , cin}). But that is nothing but 1 + (N-1)/lcm(li1, ..., lin). And further observing that lcm(li1,...lin) = lcm(lcm(li1,...,li{n-1}),lin), we can compute these Com values quite easily for all the 2^20 subsets within the 2 second limit and hence compute Des({c1,...,ck}).

Copyright (c) IARCS 2003-2021; Last Updated: 15 Mar 2005