Subset maksimum berpasangan tidak dibagi oleh

8

Saya memiliki satu set angka, dan ingin menghitung subset maksimum sehingga jumlah dari dua elemen itu tidak habis dibagi integer . Saya mencoba untuk memecahkan masalah ini, tetapi saya telah menemukan solusi kuadratik, yang bukan respons yang efisien. , di mana adalah jumlah elemen dan diberikan konstan. Apakah ada solusi yang lebih baik daripada kuadratik?K
K<100,N<10000NK

manduinca
sumber
Bisakah Anda menggambarkan solusi Anda? Apakah Anda yakin ada solusi yang lebih baik? Apakah hasil edit mempertahankan niat Anda?
Evil
Anda dapat menemukan beberapa solusi pada tautan ini .
Gadheyan .ts
@ Gadheyan.ts masalah yang Anda sebutkan adalah kasus yang sangat khusus dari masalah ini. Dalam masalah itu, set angka yang diberikan adalah dalam bentuk , sementara di sini kita memiliki set angka yang berubah-ubah. Masalah yang Anda sebutkan dapat diselesaikan di . {1,2,,N}O(1)
orezvani

Jawaban:

13

Memang ada algoritma waktu linear untuk ini. Anda hanya perlu menggunakan beberapa konsep teori bilangan dasar. Mengingat dua nomor dan , jumlah mereka adalah dibagi ke , hanya jika jumlah sisa mereka dibagi ke . Dengan kata lain,n1n2KK

K(n1+n2)        K((n1 mod K)+(n2 mod K)).

Konsep kedua yang perlu Anda pertimbangkan adalah bahwa, jumlah dua angka adalah , hanya jika salah satu dari mereka benar-benar lebih kecil dari dan yang lainnya tidak kurang dari . Dengan kata lain,r1r2KK/2K/2

r1+r2=K      r1<K/2, r2K/2      (r1r2, w.l.g. r1<r2).

Konsep ketiga yang perlu Anda pertimbangkan adalah bahwa, jika jumlah dua angka adalah , keduanya menyimpang dari oleh yaitur1r2KK/21kK/2

r1+r2=K      kK/21   such that   r1=K/21k, r2=K/2+k.

Jadi, untuk setiap dalam konsep ketiga, Anda perlu memasukkan atau dalam set solusi, tetapi tidak keduanya. Anda diizinkan untuk meletakkan salah satu angka yang sebenarnya dapat dibagi oleh dan jika genap, Anda dapat menambahkan hanya satu angka yang sisanya adalah .kr1r2KKK/2

Karena itu, berikut adalah algoritmenya.

Diberikan set , mari cari solusi setN={n1,n2,,nN}S,

  1. PertimbangkanR={r1=(n1 mod K),r2=(n2 mod K),,rN=(nN mod K)}
  2. S
  3. untuk hingga :k1K/21
  4. jika :count(R,k)count(R,Kk)
  5. tambahkan semua ke , sedemikian rupa sehingganiSri=k
  6. lainnya:
  7. tambahkan semua ke , sedemikian rupa sehingganiSri=Kk
  8. tambahkan hanya satu ke sedemikian rupa sehingga // jika adaniSri=0
  9. jika genap:K
  10. tambahkan hanya satu ke sedemikian rupa sehingga // jika adaniSri=K/2
  11. KeluaranS

Algoritma ini cukup panjang, tetapi idenya sangat sederhana.

orezvani
sumber
@ WD Saya berasumsi bahwa . Saya sengaja meletakkan asumsi semacam itu untuk menghindari angka genap; Saya menambahkan yang berikut: "wlg "r1r2r1<r2
orezvani
@ DW Tidak sepenuhnya menghindari angka genap. Jika Anda melanjutkan, Anda akan melihat mengapa saya telah memasukkan konsep / lemma tersebut. Pada dasarnya, untuk bilangan genap , jika sisa beberapa persis , maka kami hanya tertarik pada salah satu dari itu (jika kita memasukkan lebih dari satu, kita akan melanggar kondisi pertanyaan). Itu sebabnya, saya memperlakukan semua dengan kondisi itu secara terpisah. KniK/2nini
orezvani
@ WD Saya meletakkan wlg untuk . Saya pikir itu benar-benar tidak perlu tapi saya katakan hanya untuk masalah konvensi. r1<r2
orezvani
Oke, saya mengerti maksud Anda sekarang! Terima kasih telah menjelaskan.
DW
1

Pertimbangkan seperangkat S ukuran n yang berisi semua bilangan asli. Kita harus membentuk subset maksimal dari set ini. Kami menggunakan properti modulus dasar dan menambahkan beberapa pengurangan untuk menyelesaikan masalah. Semoga bermanfaat buat kalian semua.

Untuk dua bilangan asli N1 dan N2: (N1 + N2) mod (K) = (R1 + R2) mod (K) di mana R1 = N1modK dan R2 = N2% K. 1. Jika kita (N1 + N2) modK = 0 artinya (R1 + R2)% K = 0. 2. Itu berarti R1 + R2 harus sama dengan K, 2K, 3K .... 3. Tetapi R1 terletak antara 0 & K-1 dan begitu juga R2, yang berarti jumlah mereka tidak dapat melebihi K-1 + K-1 = 2 (K-1). 4. Dari 2 dan 3 kita dapat menyimpulkan bahwa R1 + R2 harus sama dengan K. 5. Selanjutnya jika R1 + R2 = K itu berarti keduanya harus sama dengan K / 2 (hanya mungkin jika K genap) atau salah satunya harus lebih rendah dari lantai [K / 2] dan satu lebih besar dari yang sama. 6. Misalkan R1 = T dan R2 = KT, jika kita mengambil angka N1 dari S yang sisanya adalah R1 dan angka apa pun N2 dari S yang sisanya adalah R2 maka jumlah mereka akan habis dibagi oleh K. Oleh karena itu, himpunan bagian Solusi dapat memiliki keduanya angka dengan sisa R1 atau yang dengan sisa R2 tetapi tidak keduanya.

Sekarang Misalkan kita membangun R array ukuran K dengan indeks 0 hingga K-1, Elemen dalam setiap indeks menunjukkan jumlah angka dalam himpunan S dengan sisa (pada pembagian dengan K) sama dengan nomor indeks. Kita tidak dapat memiliki lebih dari 2 angka dengan sisa 0 karena jumlahnya akan habis dibagi oleh K oleh karena itu kita harus menginisialisasi penghitung kita dengan min (R [0], 1). Untuk T = 1 hingga T

Kode untuk algoritma yang sama dalam C ++ adalah seperti yang ditunjukkan di bawah ini:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {

    int n,k;
    cin>>n>>k;
    vector <int> a(n);
    vector <int> r(k,0);
    for(int i=0;i<n;i++)
    {   
        cin>>a[i];
        r[a[i]%k]++;
    }
    int ctr=min(1,r[0]);
    for(int a=1;a<(k/2+1);a++)
        {
            if(a!=k-a)
                ctr+=max(r[a],r[k-a]);
        }
    if(k%2==0&&r[k/2]!=0)
        ctr++;
    cout<<ctr;
    return 0;
}
Dhruva Bhagdikar
sumber
Bisakah Anda menerjemahkan kode Anda menjadi pseudocode?
Evil
1. Baca k, n 2. Buat dua array A dan R dengan ukuran n dan k 3. i = 0, ctr = 0, a = 1 4. sementara (i <n) membaca A [i] R [A [ i]% k] ++ i = i + 1 sementara 5. ctr = minimum (1, R [0]) 6. while (a <k / 2 + 1) lakukan jika (a! = ka) ctr = ctr + maksimum (R [a], R [ka]) endif a = a + 1 sementara 7. jika (k memberikan 0 sisanya ketika dibagi 2 dan R [k / 2] bukan nol) ctr = ctr + 1 8. cetak ctr 9. End
Dhruva Bhagdikar
Saya maksudkan di posting, dengan menggunakan edit, maaf atas ketidaknyamanan dan terima kasih atas kodesemu.
Jahat
0

Saya mencoba menerjemahkan ke kode C #, yang pertama hanya menghitung ukuran array subset dan lainnya termasuk seluruh subset (hash).

Menghitung:

static int nonDivisibleSubset(int k, int[] S)
{
    var r = new int[k];

    for (int i = 0; i < S.Length; i++)
        r[S[i] % k]++;

    int count = Math.Min(1, r[0]); 

    if (k % 2 == 0 && r[k / 2] != 0) 
        count++;                                    

    for (int j = 1; j <= k / 2; j++) 
    {                                                         
        if (j != k - j)
            count += Math.Max(r[j], r[k - j]);
    }

    return count;
}

Dengan subset:

static int nonDivisibleSubset(int K, int[] S)
{
    var r = new HashSet<int>();
    var d = S.GroupBy(gb => gb % K).ToDictionary(Key => Key.Key, Value => Value.ToArray());

    for (int j = 1; j <= K / 2; j++)
    {
        var c1 = d.GetValueOrDefault(j, new int[0]);
        var c2 = d.GetValueOrDefault(K - j, new int[0]);

        if (c1.Length == c2.Length) continue;

        r.UnionWith(c1.Length > c2.Length ? c1 : c2);
    }

    if (d.ContainsKey(0))
        r.Add(d[0].Max());

    if (K % 2 == 0 && d.ContainsKey(K / 2))
        r.Add(d[K / 2].Max());

    return r.Count;
}
BigChief
sumber
1
Ini bukan situs pengkodean.
Yuval Filmus
apakah ini situs matematika?
BigChief
Luasnya situs itu sulit ditentukan. Anda dapat melihat sekeliling untuk melihat pertanyaan mana yang ditutup dan yang tidak.
Yuval Filmus
Maksud saya adalah untuk menambah kedalaman pada kode yang sudah diposting, juga blok kode yang terakhir mengembalikan subset yang secara eksplisit memaksimalkan subset lengkap alih-alih hanya mengembalikan ukuran subset. Semoga ini bermanfaat bagi siapa pun yang mencoba memahami masalah yang dihadapi. Saya juga berharap menerima umpan balik tentang kebenaran. Kode posting atau persamaan matematika memiliki beberapa persamaan?
BigChief
Kode posting biasanya disukai. Kami lebih suka kodesemu atau deskripsi tekstual.
Yuval Filmus