Editorial for Wesley's Anger Contest 2 Problem 6 - Haunted Houses
Submitting an official solution before solving the problem yourself is a bannable offence.
The first key observation is that process of ghosts removing moves from their routines is identical to the symmetric difference of the sets of moves each ghost performs (this is similar to the exclusive or operator). We can represent the moves a ghost performs as a binary integer with -bits (bitmask). Since there are at most groups of ghosts, with each containing at most ghosts, we can brute force all possible assignments (where is the number of ghost houses and is the maximum size of a group) and determine for each assignment which moves will be performed in which house. This can be done by taking the bitwise of the bitmasks of the moves for each ghost. Be sure to ensure that at least half of the ghosts in that group are in the same house.
We then need to merge the results of the groups together. There are a number of ways this can be done. This editorial will walk through one of the more interesting interpretations of the problem.
We can represent the result of each group as a frequency array of the moves that are performed in each house. Since each move in each house is either performed once, or not at all, there are possible combinations (where is the number of moves). This can be represented as a bitmask with bits. When merging two frequency arrays and , we can see that if there are ways for a combination with mask to occur in the first group, and ways for a combination with mask to occur in the second group, then it contributes ways for a combination with mask to occur with both groups combined ( is the xor operator). This is similar to polynomial multiplication, with the exception that is now . Since the size of the polynomials are quite large, the standard quadratic multiplication algorithm will take too long. In addition, the polynomials have enough nonzero terms, such that sparse multiplication will also take too long. One way to multiply polyonimals quickly is using Fast Fourier Transforms. Fast Fourier Transforms can be modified to support the operator, as well as modular arithmetic. This is known as the Fast Walsh-Hadamard Transform. This will provide us the the number of combinations a specific combination of moves will occur in each house, for all groups combined.
The sum of the scariness of the houses can then be recovered easily for each element in the merged frequency array. To answer the queries, we can maintain a prefix sum array after the merged frequency array is sorted by the sum of scariness of the houses. Each query can then be answered in time by binary searching the prefix sum array.
Where is the number of groups, is the maximum size of a group, is the number of haunted houses, is the number of moves, is the number of ghosts, and is the number of queries.
For this problem, , , , and .