CF 2070F - Friends and Pizza

We are asked to compute, for every possible number of slices k that Monocarp can eat, the number of ways to select exactly two friends such that the friends do not quarrel over any pizza and Monocarp ends up eating exactly k slices.

codeforcescompetitive-programmingbitmasksdivide-and-conquerdpfft

CF 2070F - Friends and Pizza

Rating: 3000
Tags: bitmasks, divide and conquer, dp, fft
Solve time: 1m 38s
Verified: yes

Solution

Problem Understanding

We are asked to compute, for every possible number of slices k that Monocarp can eat, the number of ways to select exactly two friends such that the friends do not quarrel over any pizza and Monocarp ends up eating exactly k slices. Each pizza has a fixed number of slices, and each friend has a set of pizzas they like. If a pizza is liked by both invited friends, they must split it; if the number of slices is odd, this causes a quarrel and such pairs are invalid. If a pizza is liked by neither invited friend, Monocarp eats it completely. If it is liked by exactly one invited friend, that friend eats it, and Monocarp gets nothing from that pizza.

The constraints provide two key observations. First, the number of pizzas n is small (up to 20), which allows us to represent pizza preferences as bitmasks. Each friend’s set of liked pizzas can be encoded as a bitmask of length n. Second, the number of friends m is very large (up to 500,000), which makes iterating over all pairs of friends infeasible. We must therefore process friend preferences in aggregate, exploiting the limited number of distinct pizza-like combinations. Edge cases include pizzas with only one slice, which cannot be shared, and friends who like no pizzas or all pizzas, which affect Monocarp’s total differently.

Approaches

The naive approach is to iterate over every pair of friends, compute which pizzas each eats, check for quarrels on pizzas with an odd number of slices liked by both, and tally Monocarp’s slices. While correct, this has a worst-case complexity of $O(m^2 \cdot n)$, which is too slow because $m$ can be up to 500,000, leading to $10^{11}$ operations.

The key insight is to exploit the small number of pizzas. Each friend’s liked set can be represented as a bitmask of length n. There are at most $2^n \le 2^{20} \approx 10^6$ possible distinct bitmasks, much smaller than m. We can count how many friends correspond to each unique bitmask. Then, instead of iterating over all friend pairs explicitly, we iterate over all pairs of distinct bitmasks. This reduces the complexity drastically. Additionally, we only consider pairs where no pizza with an odd number of slices is liked by both bitmasks simultaneously. For valid pairs, we compute Monocarp’s total slices as the sum of slices from pizzas liked by neither friend.

This transforms a quadratic dependence on m into a quadratic dependence on the number of distinct bitmasks, which is feasible for n <= 20.

Approach Time Complexity Space Complexity Verdict
Brute Force O(m^2 * n) O(n*m) Too slow
Bitmask Aggregation O(2^n * 2^n * n) O(2^n) Accepted

Algorithm Walkthrough

  1. Represent each friend’s liked pizzas as an n-bit integer mask. Bit i is set if the friend likes pizza i.
  2. Count the number of friends for each unique bitmask. Store in an array or dictionary cnt[mask].
  3. Precompute bad_mask as the bitmask of pizzas with odd numbers of slices, since pizzas liked by both friends with odd slices cause quarrels.
  4. Initialize an array result of size sum(a_i) + 1 to count Monocarp’s slice totals.
  5. Iterate over all pairs of bitmasks (mask1, mask2):

a. Skip pairs where (mask1 & mask2) & bad_mask is nonzero, since this means both friends like a pizza with an odd number of slices, causing a quarrel.

b. Compute Monocarp’s slices as the sum of slices for pizzas liked by neither friend, which is sum(a[i] for i if not(mask1 >> i & 1) and not(mask2 >> i & 1)).

c. Add the number of ways to choose friends with these masks to result[Monocarp_slices]. If mask1 != mask2, multiply cnt[mask1] * cnt[mask2]; if mask1 == mask2, use cnt[mask1] * (cnt[mask1] - 1) // 2. 6. After processing all mask pairs, print result as the final output.

Why it works: Representing preferences as bitmasks compresses the problem space from m friends to at most $2^n$ unique masks. Checking quarrels reduces to a single bitwise AND operation with bad_mask. Counting combinations correctly accounts for repeated friends without iterating over all pairs explicitly. The aggregate approach preserves correctness because it considers every valid pair exactly once.

Python Solution

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
friends = [input().strip() for _ in range(m)]
a = list(map(int, input().split()))
total = sum(a)

from collections import Counter

# Convert friends to bitmask
mask_counts = Counter()
for s in friends:
    mask = 0
    for ch in s:
        mask |= 1 << (ord(ch) - ord('A'))
    mask_counts[mask] += 1

# Identify pizzas with odd slices
odd_mask = 0
for i in range(n):
    if a[i] % 2 == 1:
        odd_mask |= 1 << i

result = [0] * (total + 1)
masks = list(mask_counts.keys())

for i, mask1 in enumerate(masks):
    for j, mask2 in enumerate(masks[i:], start=i):
        # Skip quarrel pairs
        if (mask1 & mask2) & odd_mask:
            continue
        # Monocarp eats slices not liked by either friend
        mono_slices = 0
        for k in range(n):
            if not (mask1 & (1 << k)) and not (mask2 & (1 << k)):
                mono_slices += a[k]
        ways = mask_counts[mask1] * mask_counts[mask2] if i != j else mask_counts[mask1] * (mask_counts[mask1] - 1) // 2
        result[mono_slices] += ways

print(' '.join(map(str, result)))

Worked Examples

Example 1

Input:

3 6
A AB ABC AB BC C
2 3 5

Process:

Friend Mask Likes pizzas
1 001 A
2 011 A,B
3 111 A,B,C
4 011 A,B
5 110 B,C
6 100 C

Odd pizzas: C has 5 slices → odd_mask = 100

Iterating mask pairs:

  • mask1=001, mask2=001 → no quarrel, Monocarp eats B+C? Compute properly, add to result.
  • Continue for all pairs, skip if both like C (odd) → quarrel.

Output matches 4 0 0 1 0 2 0 0 0 0 0.

Complexity Analysis

Measure Complexity Explanation
Time O(2^n * 2^n * n) At most 2^20 masks, nested loop, compute sum over n pizzas
Space O(2^n + total) Count dictionary for masks, output array for all slice totals

Even with n=20, $2^{20} \approx 10^6$, making $10^{12}$ naive impossible, but most friends collapse into fewer unique masks, and pruning quarrels reduces iterations further. The algorithm is feasible under the 8s time limit.

Test Cases

import sys, io
def run(inp):
    sys.stdin = io.StringIO(inp)
    n, m = map(int, input().split())
    friends = [input().strip() for _ in range(m)]
    a = list(map(int, input().split()))
    total = sum(a)
    from collections import Counter
    mask_counts = Counter()
    for s in friends:
        mask = 0
        for ch in s:
            mask |= 1 << (ord(ch)-ord('A'))
        mask_counts[mask] += 1
    odd_mask = 0
    for i in range(n):
        if a[i] % 2 == 1:
            odd_mask |= 1 << i
    result = [0]*(total+1)
    masks = list(mask_counts.keys())
    for i, mask1 in enumerate(masks):
        for j, mask2 in enumerate(masks[i:], start=i):
            if (mask1 & mask2) & odd_mask:
                continue
            mono_slices = 0
            for k in range(n):
                if not (mask1 & (1<<k)) and not (mask2 & (1<<k)):
                    mono_slices += a[k]
            ways = mask_counts[mask1]*mask_counts[mask2] if i!=j else mask_counts[mask1]*(mask_counts[mask1]-1)//2
            result