Wo ist der Fehler in meinem Algorithmus, um die größte Teilmenge zu finden, deren Summe die Summe jedes Paares K nicht teilt?

Question

Ich habe Kommentare über meine Logik hinterlassen. Die Art und Weise, wie es funktionieren soll, ist, dass zum Beispiel, wenn wir K=3 und S={1,7,2,4} haben, die größte Untermenge, deren Summe jedes Paar K nicht teilt, {1,7,4} ist.

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

Ihren Algorithmus für das Problem vielleicht falsch aber ist das unerwartete Verhalten auf einen Fehler im Code durch. (Aber selbst wenn Sie es beheben, ich denke, es ist zu langsam für den Online-Richter, auch können Sie einige knifflige Fälle verpassen, können Sie versuchen, es einzureichen).

HashSet Objekt subsets wird nicht aktualisiert, wie wenn Sie Add nennen, die ganze Zahl auf die Kopie eines anderen HashSet hinzugefügt wird.

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

Eine einfache Lösung ist es, neue eine globale Liste von Hashset ersten und Update, die

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

---

jedoch Liste kann dieses Problem leicht in O(k) gelöst werden (wenn nicht ich zähle/O Zeit, die ist O(N))

Hier ist mein akzeptierter Code in 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; 
} 

Das Konzept dahinter ist die modulare Arithmetik:

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

Also eigentlich, wir nur zählen, wie viele Elemente, die modular k 0,1,2 ... k-1, zu speichern gleich sie in c[0], c[1]...c[k-1]

Dann logisch, für die Zahlen in c[1] & c[k-1] können nicht wählen, zusammen, so dass wir wählen, das mit größeren zählen. Ebenso kann c[2] & c[k-2] nicht zusammen gewählt werden, etc.

Es gibt einige Sonderfälle, aber Sie können meinen Code sehen und überprüfen Sie es.

Noch ein kniffliger Ort, um dieses Problem zu erkennen ist (was ich denke, es ist schlecht geschriebene Problemstellung), wenn die Ergebnismenge eins ist, dann ist es immer eine gültige Menge, sogar das einzige Element ist durch k teilbar. (d. h. ans ist nie 0)

Answer 2

In Ihrer zweiten Schleife, wenn Sie schreiben ss.Add(n); Sie hinzufügen 'n', um eine Kopie des Hashset ss.

so bleibt nach dem foreach-Abschnitt subsets bei den vorherigen Sätzen.

Sie die maximale innerhalb der foreach als eine schnelle Lösung manuell berechnen

Answer 3

Mit Ihrem Ansatz werden Sie die Teilmenge mit allen Zahlen herausfinden, die die Bedingung erfüllen, aber Sie fügen die Teilmenge der Zahlen nicht zu Ihrem Gesamt subsets hinzu. Wenn Sie also nach der größten Teilmenge suchen, finden Sie nicht die richtige.

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 
    }