我的算法中找到每对的总和不整除 K 的最大子集的缺陷在哪里？

Question

我对我的逻辑是什么发表了评论。它应该工作的方式是，例如，如果我们有 K=3 和 S={1,7,2,4}，则每对的总和不整除 K 的最大子集是 {1,7,4}。

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution
{
    static void Main(String[] args)
    {
        int k = Int32.Parse(Console.ReadLine().Split(' ')[1]);
        var S = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);

        // first get all pairs in S whose sum doesn't divide k, 
        // each pair in their own subset set of S
        var subsets = from i in S
                      from j in S
                      where i < j && ((i + j) % k != 0)
                      select new HashSet<int>() { i, j };

        // for each subset, for each number in the original set 
        // not already in the subset, if the number summed with
        // every numer in the subset doesn't divide k, add the
        // number to the subset
        foreach(var ss in subsets)
             foreach(int n in S.Where(q => !ss.Contains(q)))
                if(ss.All(m => (m + n) % k != 0))
                   ss.Add(n);

        // get the size of the largest subset, print to console
        int max = subsets.Select(ss => ss.Count).Max();
        Console.WriteLine(max);
    }
}

Answer 1

在你的第二个循环中，当你写 ss.Add(n); 您将 'n' 添加到哈希集 ss.

的副本

所以在 foreach 部分之后，subsets 保留在前面的集合中。

您可以手动计算 foreach 中的最大值作为快速解决方案

Answer 2

虽然您的算法可能是错误的，但意外的行为是由于您的代码中的错误造成的。（不过就算搞定了，我觉得在线评判的速度太慢了，也可能会漏掉一些棘手的案例，可以尝试提交）。

HashSet 对象 subsets 没有更新，因为当您调用 Add 时，整数被添加到另一个 HashSet.

的副本中

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;


public class Test
{
    public static void Main(String[] args)
    {
        ...
       foreach(var ss in cnt){
             foreach(int n in S.Where(q => !ss.Contains(q)))
                if(ss.All(m => (m + n) % k != 0)){
                   ss.Add(n);
                }
          // Log here, you will see the size is updated to 3
            Console.WriteLine(ss.Count);
        }
        // Log here, it is still printing 2 !         
        foreach(var ss in cnt)
             Console.WriteLine(ss.Count);
        // get the size of the largest subset, print to console
        int max = ...
        Console.WriteLine(max);
    }
}

一个简单的解决方法是首先新建一个哈希集的全局列表，然后更新该列表

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;


public class Test
{
    public static void Main(String[] args)
    {
        int k = Int32.Parse(Console.ReadLine().Split(' ')[1]);
        var S = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        List<HashSet<int>> cnt = new List<HashSet<int>>();
        // first get all pairs in S whose sum doesn't divide k, 
        // each pair in their own subset set of S
        cnt = (from i in S
                      from j in S
                      where i < j && ((i + j) % k != 0)
                      select new HashSet<int>() { i, j }).ToList();

        // for each subset, for each number in the original set 
        // not already in the subset, if the number summed with
        // every numer in the subset doesn't divide k, add the
        // number to the subset

        foreach(var ss in cnt){
             foreach(int n in S.Where(q => !ss.Contains(q)))
                if(ss.All(m => (m + n) % k != 0)){
                   ss.Add(n);
                }
        }

        // get the size of the largest subset, print to console
        int max = cnt.Max(ss => ss.Count);
        Console.WriteLine(max);
    }
}

不过，这个问题可以在O(k)内轻松解决（如果不算I/O时间也就是O(N)）

这是我接受的 C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,k,a,c[105] = {0},ans=0;
int main() {
    cin >> n >> k;
    for(int i=0; i<n;i++) cin >> a, c[a%k]++;

    for(int i=1; i<=k/2; i++){
        if(k%2 == 0 && i==k/2 && c[i]) ans++;
        else ans += max(c[i], c[k-i]);
    }
    if(c[0] && ans) ans++;
    if(!ans) ans++;
    cout << ans << endl;
    return 0;
}

这背后的概念是模运算：

(a+b)%k = 0 is equavalent to (a%k + b%k)%k = 0

所以实际上，我们只是统计模k等于0,1,2...k-1的元素有多少，存入c[0], c[1]...c[k-1]

那么按理来说，c[1]和c[k-1]中的那些数不能一起选，所以我们选数大的那个。同样，c[2] & c[k-2]不能一起选，等等

虽然有一些特殊情况，你可以看看我的代码并检查一下。

要注意这个问题的另一个棘手的地方是（我认为这是一个糟糕的问题陈述），如果结果集大小为 1，那么它始终是一个有效集，即使唯一的元素可以被 k 整除。（即 ans 永远不会为 0）

Answer 3

通过您的方法，您将计算出所有数字都满足条件的子集，但您不会将数字的子集添加到总体 subsets。因此，当您寻找最大的子集时，您将找不到正确的子集。

    foreach(var ss in subsets)
    {
         foreach(int n in S.Where(q => !ss.Contains(q)))
         {
            if(ss.All(m => (m + n) % k != 0))
               ss.Add(n);
         }
     //Add the subset ss to subsets or replace it
    }

我的算法中找到每对的总和不整除 K 的最大子集的缺陷在哪里？

Where's the flaw in my algorithm to find the largest subset whose every pair's sum doesn't divide K?

c#

linq

algorithm

complexity-theory

time-complexity