基于带固定说谎次数Oracle的C语言球集多数颜色判定方案问询

问题背景 #

• 有N个（10/20/30/40）黑白两色球，存在绝对多数颜色
• Oracle可回答任意两球是否同色，但最多会说谎L次（L随N变化：N=10时L=1，N=20时L=2，以此类推）
• 查询规则：发起两球同色查询，Oracle返回YES/NO，其中包含最多L次谎言
• 核心目标：100%确定球集的多数颜色

当前方案与痛点 #

• 现有实现：通过查询球对，用并查集（Union-Find）合并同色响应的球组，基于最大组推导多数颜色
• 失效场景：多球多谎言场景下，无法有效区分真实响应与谎言，导致结论错误
• 效率问题：当前方案查询次数过多，不符合评分规则下的最优得分需求

需求方向 #

需要以下三个方向的具体指导：

1. 能应对Oracle最多L次谎言、100%准确判定多数颜色的可靠策略
2. 在保证结论准确的前提下，最小化查询次数的方法
3. 适用于该场景的相关算法或数据结构

评分规则 #

若查询次数为M，回答正确时：

• M < (L+1)*N/2：得分0
• M >= (L+1)*(N-1)：得分1
• (L+1)N/2 ≤ M < (L+1)(N-1)：得分 = ((L+1)*(N-1)-M)/12

当前简化实现代码 #

// Define the maximum number of balls
#define MAX_BALLS 40

// Function to find the group of a ball using recursion and path compression
int findGroup(int ball, int groups[MAX_BALLS])
{
    // If the ball is its own representative, return the ball
    if (groups[ball] == ball)
        return ball;
    
    // Recursively find the representative of the group and perform path compression
    return groups[ball] = findGroup(groups[ball], groups);
}

// Function to union two groups based on their representatives
void unionGroups(int ball1, int ball2, int groups[MAX_BALLS], int sizes[MAX_BALLS])
{
    // Find the representatives of both balls
    int root1 = findGroup(ball1, groups);
    int root2 = findGroup(ball2, groups);

    // If they have different representatives, merge the smaller group into the larger one
    if (root1 != root2)
    {
        if (sizes[root1] < sizes[root2])
        {
            groups[root1] = root2;
            sizes[root2] += sizes[root1];
        }
        else
        {
            groups[root2] = root1;
            sizes[root1] += sizes[root2];
        }
    }
}

// Main function to handle the game logic
void nextQuestion(int n, int plurality, int lies, int color, int exact_lies, int query_size, int query[n][n])
{
    // Initialize arrays to track groups and their sizes
    int groups[MAX_BALLS], sizes[MAX_BALLS];
    for (int i = 0; i < n; i++)
    {
        groups[i] = i;  // Each ball starts as its own group
        sizes[i] = 1;   // Each group initially has a size of 1
    }

    // Union groups based on query responses
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (query[i][j] == 1)
                unionGroups(i, j, groups, sizes); // Merge groups if the balls have the same color
        }
    }

    // Find the largest group and its representative
    int largestGroupSize = 0, largestGroupRep = -1;
    for (int i = 0; i < n; i++)
    {
        int groupSize = sizes[findGroup(i, groups)];
        if (groupSize > largestGroupSize)
        {
            largestGroupSize = groupSize;
            largestGroupRep = i;
        }
    }

    // Check if the largest group represents the majority color
    if (largestGroupSize > n / 2 || largestGroupSize + lies > n / 2)
    {
        printf("%d\n", largestGroupRep); // Print the representative of the majority color
        return;
    }

    // If not, continue querying to find a contradiction
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (query[i][j] == -1)
            {
                printf("%d %d\n", i, j); // Print the pair of balls that contradicts the majority color
                return;
            }
        }
    }
}

改进诉求 #

当前方案在多谎言场景下失效，且查询效率偏低，希望得到具体的改进建议或方向指引。

内容的提问来源于stack exchange，提问作者TermoPollo