Editorial for COCI '11 Contest 6 #6 Košare
Submitting an official solution before solving the problem yourself is a bannable offence.
Each box can be represented using a bitmask: bit will tell us whether
toy is present in this box. Our problem can now be reformulated: find the number of subsets of boxes such that total bitwise-or has no zeroes in its binary representation.
We could use dynamic programming and find solutions for each . This solution has a complexity of
and earns
of the points. We won't go into details of this solution, but various implementations can be found among competitors' solutions.
Let's see how to come up with a faster solution. Let be the number of masks from the input that are submasks of
. Then the number of subsets whose bitwise-or is a submask of
is equal to
. Once we have
calculated, we get the solution in complexity
by using the inclusion-exclusion principle.
But how to get sequence ? Let's take some mask
that begins with
. Here
denotes the rest of the bitmask. Let's say we already know the number of its submasks that begin with
. Number of submasks that begin with
is equal to number of submasks of
. This suggests a recursive approach: we solve our problem separately for masks beginning with
and
, and then combine those solutions into the total solution.
Complexity of finding is
.
Total complexity becomes .
It is also possible to avoid using the inclusion-exclusion principle, since we can calculate within at the bottom of the same recursion we use for finding
.
could also be found by brute force in complexity
, and this approach is worth
of the points.
Comments