Grouping Names Using Bitmask

創建於：2025年2月4日

問題

Here is the problem statement extracted from the images:

Problem: Grouping Names Based on Unique Alphabets

You are given an array of N names. Each name consists of uppercase English letters. You need to form groups of names based on the set of unique alphabets they contain.

A name A can be in the same group as name B if the set of unique characters in A and B differs by at most one character in one of the following ways:

One unique character in A is missing in B.
One unique character in B is missing in A.
One unique character in A is replaced by another unique character in B.

Your task is to determine:

The maximum possible size of any group.
The minimum number of groups required to cover all N names.

Input Format

The first line contains an integer T, the number of test cases.
For each test case:
- The first line contains an integer N, the number of names.
- The second line contains N space-separated strings, representing the names.

Output Format

For each test case, print two space-separated integers:

The maximum possible size of any group.
The minimum number of groups required to cover all N names.

Constraints

$1 \leq T \leq 10$
$1 \leq N \leq 10^4$
$1 \leq |S| \leq 20$ , where $|S|$ denotes the length of each name.

Example

Input

text
1
5
HARI HARRY LATA SARAI

Output

3 2

Notes

1-based indexing is followed.
The order of the alphabets in names does not matter.

Would you like a solution in a specific programming language? code in c++

思考

Defining neighbors

I'm pulling together the idea of two names being "neighbors" if their unique alphabets can be transformed into one another by adding, removing, or replacing exactly one letter. This involves analyzing character sets and transformation rules.

Analyzing character sets

I’m thinking through how two character sets are "neighbors" if they differ by exactly one letter, either by missing one unique character or by having one extra character.

Mapping character sets

OK, let me see. Two character sets are "neighbors" if they differ by exactly two letters and have the same size, or if they are identical.

Interpreting conditions

Hmm, I’m thinking about whether identical sets can be grouped under the "differs by at most one character" rule, since identical sets differ by zero modifications, which is less than or equal to one.

Charting connections

I'm piecing together a graph where each name is a node and edges link names differing by at most one character. Bitmask representation simplifies this, focusing on letter presence.

Mapping connections

I'm examining how two names with masks m1 and m2 are connected: identical names, subsets differing by one bit, and precise one-bit changes. This leads me to analyze specific bitmask conditions for connections.

Clarifying conditions

I’m working through the implication of "at most one character" and how it aligns with operations like missing, replaced, and identical sets, to ensure clarity in character set comparisons.

Clarifying allowed differences

Interestingly enough, the conditions allow for differences of 1 or 2 characters, but identical sets are not explicitly excluded. This leads me to further analyze the specified sample names.

Taking a closer look

I’m piecing together info about the sample input to match it with the problem statement, ensuring the maximum and minimum groups align with the expected result.

Spotting connections

I’m identifying connections: HARI and HARRY differ by two bits, HARI and SARAI by one bit, but LATA and the others by five bits. Progress is being made in this analysis.

Mapping potential groups

I'm curious about grouping names with maximum group size of 3 and exactly 2 groups, validating the idea of character set differences up to 2.

Clarifying connections

OK, let me see. Two masks are connected if they either match perfectly or differ by exactly one bit, meaning they either have the same or almost identical sets.

Piecing together the approach

Representing each name as a 26-bit integer, constructing a graph of these masks, and focusing on unique names within the component to manage computational feasibility.

Optimizing graph connectivity

To manage 10 test cases efficiently, I’m leveraging a dictionary to link each name to its 26-bit mask, ensuring quick access and minimizing computational strain by focusing on distinct masks.

Crafting candidate masks

I’m mapping out 26 ways to add or remove each bit from a mask and 676 ways to swap bits, identifying options that maintain a symmetric difference of two bits.

Executing the Union-Find

Precomputing neighbors for each mask, then merging connected names using Union-Find ensures efficient group identification while managing overlapping computations.

Processing the task

First, I parse inputs and calculate bitmasks. Then, using an unordered_map and union-find DSU, I efficiently manage name groups and their neighbors.

Mapping neighbors

First, I list existing names. Then, I generate potential neighbors by tweaking each bit and quickly union indices with matching masks for effective group optimization.

Confirming unions

I’m mapping out if candidate neighbors with 0 difference are already counted. Counting connected components and max group size is also key to ensure accurate unions.

Validating constraints

I’m checking 1-bit and 2-bit difference candidates, ensuring their bit count matches the original. Validated differences confirm the constraints, making the process transparent and trustworthy.

Piecing together differences

I'm noting that 1-bit removal or addition maintains bit count, while 2-bit differences keep the same bit count. This ensures accurate union-find operations.

Assessing performance

OK, let me see: evaluating iterations and union operations reveals the solution's strength. Distinct masks and set bit counts are balanced, ensuring efficiency and a feasible worst-case scenario.

Figuring out group needs

I’m thinking about how each connected component forms a group, influencing the max group size and group count. The sample input has 4 names, indicating a potential problem typo.

Mapping out union-find

I'm using union-find with path compression and union by size to manage groups. Each distinct mask's parent and size iteratively unify adjacent indices, ensuring efficient progression.

Enhancing union efficiency

I'm optimizing union-find by focusing on representative indices for each mask in a map. This simplifies merging neighbor indices, ensuring streamlined and effective group unification.

Summing group sizes

OK, let's tally union-find set sizes and combine equal masks into one representative. This approach efficiently merges groups, ensuring a more streamlined and compact final result.

Pulling together union-find

Checking each map entry for neighbors before making connections. Every unique mask is reviewed, skipping duplicates to keep things efficient. Candidate unions are mapped carefully.

Constructing union-find

I’m setting up a DSU class to manage union and find operations, carefully tracking group sizes and counts. This approach ensures precise data handling without missing any potential groupings.

Managing union-find efficiently

I'm focusing on managing up to 7.28 million operations, utilizing unordered maps to map indices to representatives for each mask. This approach streamlines union-find optimization.

Streamlining union-find

Using an unordered map to ensure all indices with the same mask are unified efficiently, and merging groups with shared masks to boost performance further.

Evaluating connections

I’m determining neighbors for each mask by flipping bits to create candidates and unify them efficiently. This approach ensures any potential cycles are effectively managed.

Navigating unique and full masks

I’m examining both unique and full masks for candidate generation. Unique masks ensure replacements and one-bit differences are valid. Full masks handle replacements with valid bit crosses, confirming comprehensive group unity.

Navigating edge cases

Interestingly enough, while union-finds handle identical candidates seamlessly, I’m ensuring replacements and one-bit differences are valid. This careful distinction maintains accurate group management throughout.

Confirming validity

I’m checking that each candidate aligns with the union-find rule of equal set size and exactly one different letter. This validation ensures accurate neighbor generation.

Evaluating set modifications

Hmm, I’m thinking through set differences, ensuring valid replacements align with the union-find rule. Calculating candidates keeps the process accurate and interesting.

Validating set transformations

I’m honing in on pairs by ensuring accurate letter removal and addition from set masks. Transition unions conform to union-find rules, confirming valid and necessary replacements.

Establishing and validating connections

I’m sorting names by their unique bitmasks, linking neighbors, and checking replacements. This manages all union-find requirements well. Progress is steady and promising.

Piecing together structures

Pairing libraries like iostream, vector, and unordered_map with fast input/output for efficiency, as I shape the final C++17 code. It’s interesting to see the progress unfold.

Crafting union-find

Mapping masks to representatives, I’m merging names with identical or close masks, efficiently organizing groups. This streamlines the process as progress continues steadily.

Identifying connections

OK, let me see. Igniting 1-bit and 2-bit differences, I merge representatives. After counting the groups, I pinpoint the largest and tally the total groups.

Reasoned about grouping names by alphabets for 1m 15s

回答

We can solve this problem by “compressing” each name into a 26‐bit integer (bitmask) representing its unique letters. Two names can be “grouped” (i.e. they are in the same connected component) if their masks are “neighbors” under the following rules:

0 or 1‐bit difference by addition/removal:
- If the masks are identical (0 difference) they obviously belong together.
- If one mask can be obtained from the other by adding or removing exactly one letter then the symmetric difference has exactly one bit set.
Replacement (2‐bit difference):
- If the masks are the same “size” (same popcount) and they differ by exactly two bits then one letter has been replaced by another. For example, $\{A, H, I, R\} \quad \text{and} \quad \{A, H, R, Y\}$ differ by “dropping” I and “adding” Y.

Once we define the neighbor relation in terms of bitmasks, we can build a “graph” (or more directly use a disjoint–set union, DSU) where every name is a node and we add an edge between two names if their bitmasks are “neighbors” according to the rules above.

A good optimization is that instead of comparing every pair of names (which would be too slow when $N \le 10^4$ ), we do the following:

For each name compute its mask.
Use a hash map (e.g. unordered_map<int,int>) to store one representative index for each distinct mask (and union together all names that have the same mask).
For each distinct mask, generate “neighbor candidate” masks by:
- For each bit (letter) position, try removing the letter (if it exists) and adding a letter (if it is missing).
- For each letter that is present, for each letter that is missing, “replace” the present letter by the missing one.
If a candidate mask exists in our map, we union the two groups.

Finally, after processing, each connected component represents a “group.” We then count:

The maximum group size (the largest connected component).
The number of groups (the number of connected components).

Below is the complete C++ solution.

cpp
#include <bits/stdc++.h>
using namespace std;
 
// Disjoint Set Union (Union‐Find) structure
struct DSU {
    vector<int> parent;
    vector<int> sz;
    DSU(int n) : parent(n), sz(n, 1) {
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }
    
    int find(int a) {
        if(parent[a] == a) return a;
        return parent[a] = find(parent[a]);
    }
    
    void unionn(int a, int b) {
        a = find(a);
        b = find(b);
        if(a == b) return;
        if(sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while(T--){
        int N;
        cin >> N;
        vector<string> names(N);
        for (int i = 0; i < N; i++){
            cin >> names[i];
        }
 
        DSU dsu(N);
 
        // Map each distinct mask to one representative index.
        unordered_map<int,int> maskToRep;
        maskToRep.reserve(N * 2);
 
        // For each name, compute the bitmask and union names with the same mask.
        vector<int> masks(N, 0);
        for (int i = 0; i < N; i++){
            int mask = 0;
            for (char c : names[i]){
                mask |= (1 << (c - 'A'));
            }
            masks[i] = mask;
            if(maskToRep.find(mask) == maskToRep.end()){
                maskToRep[mask] = i;
            } else {
                dsu.unionn(i, maskToRep[mask]);
            }
        }
 
        // For every distinct mask, generate all neighbor candidates and union groups.
        for(auto &p : maskToRep){
            int mask = p.first;
            int rep = p.second;
 
            // 1-bit differences: removal or addition.
            for(int i = 0; i < 26; i++){
                int bit = 1 << i;
                int candidate;
                if(mask & bit){
                    // Removal: remove the letter i
                    candidate = mask ^ bit;
                    if(maskToRep.find(candidate) != maskToRep.end()){
                        dsu.unionn(rep, maskToRep[candidate]);
                    }
                } else {
                    // Addition: add the letter i
                    candidate = mask | bit;
                    if(maskToRep.find(candidate) != maskToRep.end()){
                        dsu.unionn(rep, maskToRep[candidate]);
                    }
                }
            }
 
            // 2-bit differences: replacement (remove one letter, add another)
            for (int i = 0; i < 26; i++){
                if(mask & (1 << i)){
                    for (int j = 0; j < 26; j++){
                        if(!(mask & (1 << j))){
                            int candidate = (mask ^ (1 << i)) | (1 << j);
                            if(maskToRep.find(candidate) != maskToRep.end()){
                                dsu.unionn(rep, maskToRep[candidate]);
                            }
                        }
                    }
                }
            }
        }
 
        // Count sizes of each connected component.
        unordered_map<int,int> compSize;
        compSize.reserve(N);
        int maxSize = 0;
        for (int i = 0; i < N; i++){
            int root = dsu.find(i);
            compSize[root]++;
            maxSize = max(maxSize, compSize[root]);
        }
 
        int groups = compSize.size();
        cout << maxSize << " " << groups << "\n";
    }
    return 0;
}

Explanation

Input & Mask Creation:
Each name is converted into a bitmask where bit $i$ (for $0 \le i < 26$ ) is set if the letter ('A' + i) is in the name.
Union by Same Mask:
Using the maskToRep map, we union all names that have exactly the same bitmask.
Generating Neighbors:
For each distinct mask:
- For each bit position, we try removing (if the bit is set) or adding (if not set) the letter.
- Then for each pair (letter in, letter out) we generate a candidate mask corresponding to a replacement. If a candidate exists in our map (meaning some name has that mask), we union the two representative indices.
Result Computation:
Finally, we count the sizes of the connected components. The maximum size is the size of the largest component, and the number of groups is the number of distinct components.

This solution efficiently meets the problem requirements with $N\le10^4$ and maximum name length 20. Let me know if you have any questions or need further clarifications!

問題