私のアルゴリズムの欠点は、すべてのペアの和がKを分けない最大の部分集合を見つけることですか？

Question

私は私の論理が何であるかについてのコメントを残しました。たとえば、K=3とS={1,7,2,4}がある場合、すべてのペアの合計がKを除外しない最大のサブセットは{1,7,4}です。 2つ目のループでは

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

あなたのアルゴリズムけれども、多分間違った問題への迅速な解決策としてのforeach内の最大を計算することができますが、予期しない動作があなたのコードのバグが原因です。 （しかし、あなたがそれを修正しても、私はそれがオンラインジャッジのために遅すぎると思っています、あなたはいくつかのトリッキーなケースを見逃す可能性があります、それを提出しようとすることができます）。

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); 
    } 
} 

簡単な修正は、最初のHashSetの新しいグローバルリストにあり、そしてそのリストに

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); 
    } 
} 

---

を更新Iを数えていない場合は、この問題は（O(k)で簡単に解決することができます/ここでO(N)）

であるO時間は、Cの私の受け入れコード++

です

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

だから実際に、私達はちょうどモジュラーkは0,1,2 ...、K-1、店に等しいことをどのように多くの要素を数える：10

この背後にある考え方は、剰余演算でありますc[1] & c[k-1]でそれらの数字のために、論理的に続いてc[0], c[1]...c[k-1]

、中にそれらを一緒に選択することができませんので、我々は、より大きな数のものを選択してください。同様に、c[2] & c[k-2]は一緒に選択することはできません。

私のコードが表示され、チェックアウトすることがあります。

この問題を知るもう一つの難しい場所は、結果セットのサイズが1ならば、唯一の要素でもkで割り切れるものであっても常に有効な集合です。 （つまり、ansは決して0になりません）

Answer 2

、あなたがss.Add(n); を書くとき、あなたはHashSetのSSのCOPYに 'n' を追加します。

foreachセクションの後では、subsetsは前のセットのままです。

手動

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 
    }