Overview

This problem asks you to find the maximum number of people in a subset of candidates whose bitwise OR of skill values exactly equals the target value \(K\).

Analysis

1. Basic Condition: The bitwise OR of the selected members’ skill values must exactly match \(K\). That is:

   • All bits of \(K\) must be covered by at least one member
   • Members with bits set that are not in \(K\) cannot be used (because the OR result would exceed \(K\))

2. Special Case \(K=0\): All members’ skill values must be 0. If even one member has a non-zero value, the OR cannot be 0.

3. Filtering Valid Candidates: Exclude candidates that have bits set which are not in \(K\) (check using \((a_i | K) == K\)).

4. Checking Necessary Conditions: For each bit of \(K\), at least one valid candidate must have that bit set.

5. Maximizing the Number of People: If the OR of all valid candidates equals \(K\), then selecting all of them gives the maximum number of people.

Algorithm

1. Handling the case \(K=0\):

   • Count only candidates whose skill values are 0, and output that count if any exist

2. Filtering valid candidates:

   • Extract only those \(A_i\) satisfying \((A_i | K) == K\)

3. Checking necessary conditions:

   • For each bit of \(K\), verify that at least one valid candidate has that bit set

4. Determining the maximum number of people:

   • Compute the OR of all valid candidates and confirm it matches \(K\)
   • If it matches, output the total number of valid candidates; otherwise, output -1

Complexity

• Time complexity: \(O(N \log K)\)
  • Filtering valid candidates: \(O(N)\)
  • Bit counting: checking up to \(\log_2 K\) bits for each candidate
• Space complexity: \(O(N)\)
  • List to store valid candidates

Implementation Notes

1. Handle the \(K=0\) case first

2. Use bitwise operations for efficient condition checking

3. Dynamically determine the bit length of \(K\) and verify coverage for each bit

4. Perform a final check that the OR of all valid candidates exactly matches \(K\)

   Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    if K == 0:
        # すべてのメンバーのスキルが0でなければならない
        count = 0
        for a in A:
            if a == 0:
                count += 1
        if count > 0:
            print(count)
        else:
            print(-1)
        return
    
    # Kの各ビットが立っている必要がある
    # ただし、Kにないビットが立っている候補者は除外
    valid_A = []
    for a in A:
        if (a | K) == K:
            valid_A.append(a)
        # そうでない候補者は使えない（Kにないビットを立ててしまう）
    
    if not valid_A:
        print(-1)
        return
    
    # Kのビットごとに考える
    bits = []
    k_tmp = K
    while k_tmp:
        bits.append(k_tmp & 1)
        k_tmp //= 2
    # ビット長を揃えるため、必要なら0パディング
    max_bits = len(bits)
    
    # 各ビットについて、そのビットが立っている候補者の数を数える
    count_per_bit = [0] * max_bits
    for a in valid_A:
        for i in range(max_bits):
            if (a >> i) & 1:
                count_per_bit[i] += 1
    
    # 各ビットについて、少なくとも1人はそのビットを持っている必要がある
    for i in range(max_bits):
        if (K >> i) & 1 and count_per_bit[i] == 0:
            print(-1)
            return
    
    # 最小人数は各ビットで1人ずつだが、最大人数を求めたい
    # 貪欲に、すべての候補者を使えるか試す
    # ただし、Kのビット以外は0でなければならないので、候補者はすべてKの部分集合
    # 問題は、各ビットについて少なくとも1人はいること
    # 最大人数は、基本的にはすべての候補者を使えるか？
    # ただし、すべての候補者を使ったときのORがKになるか？
    total_or = 0
    for a in valid_A:
        total_or |= a
    if total_or != K:
        print(-1)
        return
    
    # すべての候補者を使えばORはKになる
    # しかし、実際にはすべての候補者を使えるか？
    # 実は、すべての候補者を使うと、KのビットがすべてカバーされるのでOK
    # ただし、冗長な候補者（なくてもORがKになる）がいても問題ない
    # したがって、最大人数はvalid_Aの全要素数
    print(len(valid_A))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.