Indian National Olympiad in Informatics

Related:
Online Programming Contest, 4-5 September 2004

IARCS home > OLYMPIAD

Advanced Division

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}).