Counting Submasks
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
A game has 20 skills, and each player's learned skills are a 20-bit integer (bit i set means skill i is learned). For each
i, count the indices j (including j = i) whose skill set is contained in player i's, i.e.
where & is bitwise AND. Return the counts as an array.
Examples
| a | result |
|---|---|
[1, 3, 2, 0, 7] | [2, 4, 2, 1, 5] |
[5, 5, 4] | [3, 3, 1] |
[6, 9] | [1, 1] |
Example 1 — the submasks of 3 (011) are 0, 1, 2, 3, all present; 7 contains every value; 0 only itself.
Example 2 — equal values contain each other; 4 (100) does not contain 5 (101).
Example 3 — 6 and 9 share no bits.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(a: int[]) → int[]
Constraints
-
a.length -
a[i]
Expected complexity
- Time
- O(N + B * 2^B), B = 20
- Space
- O(2^B)
Examples
| a | Expected |
|---|---|
[1,3,2,0,7] | [2,4,2,1,5] |
[5,5,4] | [3,3,1] |
[6,9] | [1,1] |
Hint
Hint
Start with f[m] = how many elements equal m, then turn it into "how many elements are submasks of m" with the
sum-over-subsets DP: for each bit b, for each m with bit b set, f[m] += f[m ^ (1 << b)]. Each submask is added exactly
once, and the answer for i is f[a[i]]. This is ; comparing every pair () exceeds the time
limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1258 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 3 | verdict only |