Funcia
Lv.4bitmaskdpsos-dp

Counting Submasks

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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.

a[j]&a[i]=a[j]a[j] \mathbin{\&} a[i] = a[j]

where & is bitwise AND. Return the counts as an array.

Examples

aresult
[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

  • 1≤N=1 \le N = a.length ≤200,000\le 200{,}000
  • 0≤0 \le a[i] <220=1,048,576< 2^{20} = 1{,}048{,}576

Expected complexity

Time
O(N + B * 2^B), B = 20
Space
O(2^B)

Examples

aExpected
[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 O(N+20⋅220)O(N + 20 \cdot 2^{20}); comparing every pair (O(N2)O(N^2)) exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251258 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.