Editorial for COCI '13 Contest 6 #2 Font

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

We need to find the number of different subsets of the set of given words such that the combined words in the subsets contain all lowercase letters of the English alphabet. In a set of $N$ $N$ words, we can choose $2^N$ $2^{N}$ different subsets. Because $N$ $N$ is an integer less than $25$ $25$ , we have a maximum of $2^{25} = 33\,554\,432$ $2^{25} = 33 554 432$ subsets. This number is small enough for us to be able to pass through all possible subsets and check whether they contain the whole alphabet.

A regular way of passing through all subsets of a set is using a recursive function.

Copy

f( i ):
    if i = N + 1: check whether the inserted sets contain the whole alphabet
    (we've passed through all words)
    else:
        add the i'th word to the set
        call f( i + 1 )
        remove the i'th word from the set
        call f( i + 1 )

Additionally, we need to decide how to represent these sets in the computer's memory so we could implement the addition and removal of a word in the set.

One possible way is using an array $appeared[26]$ $a p p e a r e d [26]$ which keeps track of how many times each letter of the alphabet appears in the current subset and using a variable $total$ $t o t a l$ which keeps track of how many different letters there are in the current subset.

When we add a word to the subset, we increment the counter in the array $appeared[letter]$ $a p p e a r e d [l e t t e r]$ for each letter of the word, and increment the counter $total$ $t o t a l$ only if $0$ $0$ was written so far in $appeared[letter]$ $a p p e a r e d [l e t t e r]$ (if we've added a letter which hasn't appeared in the set so far). A similar procedure is done for removing a word from the set.

The complexity of this algorithm is $\mathcal O(2^M \times L)$ $O (2^{M} \times L)$ , where $L$ $L$ is the maximal length of the word. This solution is sufficient for $50\%$ $50 %$ of points.

Another way of representing sets of letters in the computer's memory is using a bitmask. A bitmask is a series of ones and zeroes where the $i^\text{th}$ $i^{th}$ place is zero only if the $i^\text{th}$ $i^{th}$ element is present in the set and zero if it isn't. For example, the set $\{a, b, d, z, y\}$ ${a, b, d, z, y}$ is represented with a bitmask $110 \dots 01011$ $110 \dots 01011$ (the numbers are enumerated from right to left). The union operator of the sets represented with bitmasks corresponds to the OR operator of their bitmasks.

The advantage of this implementation of sets in the memory is because the processor deals with bitwise operations really quickly, the complexity being $\mathcal O(1)$ $O (1)$ .

The complexity of the algorithm when using this kind of implementation of set operations is $\mathcal O(2^M)$ $O (2^{M})$ .

Comments

There are no comments at the moment.