Ketidaksetaraan Pengaturan Ulang

10

Latar Belakang

The Penataan ulang Ketimpangan adalah ketimpangan yang didasarkan pada menata ulang nomor. Jika saya memiliki dua daftar nomor dengan panjang yang sama, x 0 , x 1 , x 2 ... x n-1 dan y 0 , y 1 , y 2 ... y n-1 dengan panjang yang sama, di mana saya Saya diizinkan untuk mengatur ulang angka dalam daftar, cara untuk memaksimalkan jumlah x 0 y 0 + x 1 y 1 + x 2 y 2 + ... + x n-1 y n-1 adalah dengan menyortir 2 daftar di pesanan tidak menurun.

Baca artikel Wikipedia di sini.

Tugas

Anda akan menulis sebuah program yang mengambil input dari STDIN atau fungsi yang menerima 2 array (atau wadah terkait) nomor (yang memiliki panjang yang sama).

Dengan asumsi Anda menulis fungsi yang menerima 2 array (a dan b), Anda akan menemukan sejumlah cara Anda dapat mengatur ulang angka dalam array kedua (b) untuk memaksimalkan:

a[0]*b[0]+a[1]*b[1]+a[2]*b[2]+...+a[n-1]*b[n-1]

Dalam hal ini, jika array b adalah [1 0 , 2 1 , 2 2 , 3 3 , 3 4 ] (indeks untuk kejelasan),

[1 0 , 2 1 , 2 2 , 3 3 , 3 4 ],

[1 0 , 2 1 , 2 2 , 3 4 , 3 3 ], (tukar keduanya 3)

[1 0 , 2 2 , 2 1 , 3 3 , 3 4 ] (menukar keduanya 2)

[1 0 , 2 2 , 2 1 , 3 4 , 3 3 ] (menukar keduanya 3 dan menukar keduanya 2)

dianggap pengaturan yang berbeda. Array asli, itu sendiri, juga dianggap sebagai penataan ulang yang mungkin jika juga memaksimalkan jumlah.

Untuk input STDIN, Anda dapat mengasumsikan bahwa panjang array disediakan sebelum array (harap sebutkan sehingga Anda menggunakannya), atau bahwa array disediakan pada baris yang berbeda (juga harap sebutkan).

Berikut adalah 4 kemungkinan input (untuk kenyamanan):

5 1 1 2 2 2 1 2 2 3 3 (length before arrays)

1 1 2 2 2 1 2 2 3 3 (the 2 arrays, concatenated)

1 1 2 2 2
1 2 2 3 3 (the 2 arrays on different lines)

5
1 1 2 2 2
1 2 2 3 3 (length before arrays and the 2 arrays on different lines)

Untuk hasil, Anda diizinkan untuk mengembalikan jawaban (jika Anda menulis fungsi) atau mencetak jawaban ke STDOUT. Anda dapat memilih untuk mengeluarkan jawaban mod 10 9 +7 (dari 0 hingga 10 9 +6) jika lebih nyaman.

Kasus Uji (dan penjelasan):

[1 1 2 2 2] [1 2 2 3 3] => 24

2 entri pertama harus 1 dan 2. 3 entri terakhir adalah 2, 3 dan 3. Ada 2 cara untuk mengatur 2 antara 2 entri pertama dan 2 entri terakhir. Di antara 2 entri pertama, ada 2 cara untuk mengaturnya. Di antara 2 entri terakhir, ada 6 cara untuk mengaturnya.

[1 2 3 4 5] [6 7 8 9 10] => 1

Hanya ada 1 cara, yaitu pengaturan yang diberikan dalam array.

[1 1 ... 1 1] [1 1 ... 1 1] (10000 numbers) => 10000! or 531950728

Setiap permutasi yang dimungkinkan dari array kedua adalah valid.

Dennis ' Testcase : Pastebin => 583159312 (mod 1000000007)

Mencetak:

Ini kode-golf, jadi jawaban tersingkat menang.

Dalam hal pengikatan, ikatan akan diputus pada saat pengajuan, mendukung pengajuan sebelumnya.

Perhatikan:

Kontainer mungkin tidak disortir.

Bilangan bulat dalam wadah mungkin nol atau negatif.

Program harus berjalan cukup cepat (paling lama satu jam) untuk array berukuran sedang (sekitar 10.000 panjangnya).

Terinspirasi oleh pertanyaan ini di Mathematics Stack Exchange.

code-golf math combinatorics permutations Elemen118
sumber
2
Berikan kasus uji dengan 10.000 elemen per larik, sehingga kami dapat memverifikasi kode kami berfungsi dengan benar dan cukup cepat.
Dennis
1
Dalam contoh yang Anda berikan untuk menukar larik kedua [1_0, 2_2, 2_1, 3_4, 3_3] tidak ada (menukar kedua 2 dan menukar kedua 3) tidak ada
Willem
apakah Anda menerima input seperti [. . .]respons plz
Abr001am
Jika kita mengirimkan fungsi, apakah kita harus mengambil dua argumen terpisah atau bisakah kita mengambil array array?
Dennis
Nah, array array sepertinya baik-baik saja, dan tidak terlalu mempengaruhi tantangan. Saya akan mengerjakan test case.
Element118

Jawaban:

4

CJam, 30 26 byte

q~](/:$_za+{e`0f=:m!:*}//*

Cobalah online di penerjemah CJam .

Ini menyelesaikan test case dalam waktu kurang dari satu detik:

$ time cjam <(echo 'q~](/:$_za+{e`0f=:m!:*}%)\:*\/N') < test-large.in | md5sum
5801bbf8ed0f4e43284f7ec2206fd3ff  -

real    0m0.308s
user    0m0.667s
sys     0m0.044s

Menjalankannya dalam juru bahasa online harus kurang dari 10 detik.

Algoritma

Hasilnya tidak tergantung pada urutan A , jadi kami dapat menganggapnya diurutkan. Ini berarti bahwa B juga harus diurutkan untuk mendapatkan produk titik maksimal.

Sekarang, jika r 1 , ... r n adalah panjang dari run dari A yang diurutkan , ada ∏r k ! pengaturan ulang yang berbeda dari elemen-elemen A yang masih menghasilkan urutan naik.

Demikian juga, jika s 1 ,… s n adalah panjang run dari B yang diurutkan, ada ks k ! penataan berbeda dari elemen B yang masih menghasilkan urutan naik.

Namun, ini menghitung semua pasangan beberapa kali. Jika kita mengambil pasangan elemen terkait yang disortir A dan diurutkan B dan mendefinisikan t 1 , ... t n sebagai panjang dari lintasan array yang dihasilkan, kt k ! adalah pengganda tersebut.

Jadi, hasil yang diinginkan adalah (∏r k !) × (ks k !) ÷ (∏t k !) .

Kode

 q~                          Read and evaluate all input.
   ]                         Wrap the resulting integers in an array.
    (                        Shift out the first (length).
     /                       Split the remainder into chunks of that length.
      :$                     Sort each chunk.
        _z                   Push a copy and transpose rows with columns.
                             This pushes the array of corresponding pairs.
          a+                 Wrap in array and concatenate (append).
            {          }/    For A, B, and zip(A,B):
             e`                Perform run-length encoding.
               0f=             Select the runs.
                  :m!          Apply factorial to each.
                     :*        Reduce by multiplication.
                         /   Divide the second result by the third.
                          *  Multiply the quotient with the first result.
Dennis
sumber
6

Pyth, 29 28 byte

M/*FPJm*F.!MhMrd8aFCB,SGSHeJ

Cobalah online di Internet Pyth Compiler .

Algoritma

Hasilnya tidak tergantung pada urutan A , jadi kami dapat menganggapnya diurutkan. Ini berarti bahwa B juga harus diurutkan untuk mendapatkan produk titik maksimal.

Sekarang, jika r 1 , ... r n adalah panjang dari run dari A yang diurutkan , ada ∏r k ! pengaturan ulang yang berbeda dari elemen-elemen A yang masih menghasilkan urutan naik.

Demikian juga, jika s 1 ,… s n adalah panjang run dari B yang diurutkan , ada ks k ! penataan berbeda dari elemen B yang masih menghasilkan urutan naik.

Namun, ini menghitung semua pasangan beberapa kali. Jika kita mengambil pasangan elemen terkait yang diurutkan dari A dan diurutkan B dan mendefinisikan t 1 , ... t n sebagai panjang dari lintasan array yang dihasilkan, kt k ! adalah pengganda tersebut.

Jadi, hasil yang diinginkan adalah (∏r k !) × (ks k !) ÷ (∏t k !) .

Kode

M/*FPJm*F.!MhMrd8aFCB,SGSHeJ

M                             Define g(G,H):
                      SGSH      Sort G and H.
                     ,          For the pair of the results.
                   CB           Bifurcated zip (C).
                                This returns [[SG, SH], zip([SG, SH])].
                 aF             Reduce by appending.
                                This returns [SG, SH, zip([SG, SH])].
      m                         Map; for each d in the resulting array:
              rd8                 Perform run-length encoding on d.
            hM                    Mapped "head". This returns the lengths.
         .!M                      Mapped factorial.
       *F                         Reduce by multiplication.
     J                          Save the result in J.
    P                           Discard the last element.
  *F                            Reduce by multiplication.
 /                  
                          eJ    Divide the product by the last element of J.
                                Return the result of the division.

Verifikasi

Saya telah membuat 100 kasus uji pseudo-acak panjang 6, yang telah saya pecahkan dengan kode di atas dan pendekatan brute-force ini:

Ml.Ms*VGZ.pH

M             Define g(G,H) (or n(G,H) on second use):
         .pH    Compute all permutations of H.
  .M            Filter .pH on the maximal value of the following;
                 for each Z in .pH:
     *VGZ         Compute the vectorized product of G and Z.
    s             Add the products.
                  This computes the dot product of G and Z.
 l              Return the length of the resulting array.

Inilah hasilnya:

$ cat test.in
6,9,4,6,8,4,5,6,5,0,8,2
0,7,7,6,1,6,1,7,3,3,8,0
3,6,0,0,6,3,8,2,8,3,1,1
2,3,0,4,0,6,3,4,5,8,2,4
9,1,1,2,2,8,8,1,7,4,9,8
8,3,1,1,9,0,2,8,3,4,9,5
2,0,0,7,7,8,9,2,0,6,7,7
0,7,4,2,2,8,6,5,0,5,4,9
2,7,7,5,5,6,8,8,0,5,6,3
1,7,2,7,7,9,9,2,9,2,9,8
7,2,8,9,9,0,7,4,6,2,5,3
0,1,9,2,9,2,9,5,7,4,5,6
8,4,2,8,8,8,9,2,5,4,6,7
5,2,8,1,9,7,4,4,3,3,0,0
9,3,6,2,5,5,2,4,6,8,9,3
4,2,0,6,2,3,5,3,6,3,1,4
4,8,5,2,5,0,5,1,2,5,9,5
6,8,4,4,9,5,9,5,4,2,8,7
8,9,8,1,2,2,9,0,5,6,4,9
4,7,6,8,0,3,7,7,3,9,8,6
7,5,5,6,3,9,3,8,8,4,8,0
3,8,1,8,5,6,6,7,2,8,5,3
0,9,8,0,8,3,0,3,5,9,5,6
4,2,7,7,5,8,4,2,6,4,9,4
3,5,0,8,2,5,8,7,3,4,5,5
7,7,7,0,8,0,9,8,1,4,8,6
3,9,7,7,4,9,2,5,9,7,9,4
4,5,5,5,0,7,3,4,0,1,8,2
7,4,4,2,5,1,7,4,7,1,9,1
0,6,2,5,4,5,1,8,0,8,9,9
3,8,5,3,2,1,1,2,2,2,8,4
6,1,9,1,8,7,5,6,9,2,8,8
6,2,6,6,6,0,2,7,8,6,8,2
0,7,1,4,5,5,3,4,4,0,0,2
6,0,1,5,5,4,8,5,5,2,1,6
2,6,3,0,7,4,3,6,0,5,4,9
1,4,8,0,5,1,3,2,9,2,6,5
2,7,9,9,5,0,1,5,6,8,4,6
4,0,1,3,4,3,6,9,1,2,7,1
6,5,4,7,8,8,6,2,3,4,1,2
0,3,6,3,4,0,1,4,5,5,5,7
5,4,7,0,1,3,3,0,2,1,0,8
8,6,6,1,6,6,2,2,8,3,2,2
7,1,3,9,7,4,6,6,3,1,5,8
4,8,3,3,9,1,3,4,1,3,0,6
1,4,0,7,4,9,8,4,2,1,0,3
0,4,1,6,4,4,4,7,5,1,4,2
0,0,4,4,9,6,7,2,7,7,5,4
9,0,5,5,0,8,8,9,5,9,5,5
5,7,0,4,2,7,6,1,1,1,9,1
3,1,7,5,0,3,1,4,0,9,0,3
4,4,5,7,9,5,0,3,7,4,7,5
7,9,7,3,0,8,4,0,0,3,1,0
2,4,4,3,1,2,5,2,9,0,8,5
4,8,7,3,0,0,9,3,7,3,0,6
8,9,1,0,7,7,6,0,3,1,8,9
8,3,1,7,3,3,6,1,1,7,6,5
6,5,6,3,3,0,0,5,5,0,6,7
2,4,3,9,7,6,7,6,5,6,2,0
4,8,5,1,8,4,4,3,4,5,2,5
7,5,0,4,6,9,5,0,5,7,5,5
4,8,9,5,5,2,3,1,9,7,7,4
1,5,3,0,3,7,3,8,5,5,3,3
7,7,2,6,1,6,6,1,3,5,4,9
9,7,6,0,1,4,0,4,4,1,4,0
3,5,1,4,4,0,7,1,8,9,9,1
1,9,8,7,4,9,5,2,2,1,2,9
8,1,2,2,7,7,6,8,2,3,9,7
3,5,2,1,3,5,2,2,4,7,0,7
9,6,8,8,3,5,2,9,8,7,4,7
8,8,4,5,5,1,5,6,5,1,3,3
2,6,3,5,0,5,0,3,4,4,0,5
2,2,7,6,3,7,1,4,0,3,8,3
4,8,4,2,6,8,5,6,2,5,0,1
7,2,4,3,8,4,4,6,5,3,9,4
4,6,1,0,6,0,2,6,7,4,9,5
6,3,3,4,6,1,0,8,6,1,7,5
8,3,4,2,8,3,0,1,8,9,1,5
9,6,1,9,1,1,8,8,8,9,1,4
3,6,1,6,1,4,5,1,0,1,9,1
6,4,3,9,3,0,5,0,5,3,2,4
5,2,4,6,1,2,6,0,1,8,4,0
3,5,7,6,3,6,4,5,2,8,1,5
6,3,6,8,4,2,7,1,5,3,0,6
9,1,5,9,9,1,1,4,5,7,3,0
1,6,7,3,5,8,6,5,5,2,6,0
2,8,8,6,5,5,2,3,8,1,9,8
0,4,5,3,7,6,2,5,4,3,2,5
5,1,2,3,0,3,4,9,4,9,4,9
5,8,2,2,0,2,4,1,1,7,0,3
0,6,0,0,3,6,3,6,2,2,2,9
2,4,8,1,9,4,0,8,8,0,4,7
3,9,1,0,5,6,8,8,2,5,2,6
5,3,8,9,1,6,5,9,7,7,6,1
8,6,9,6,1,1,6,7,7,3,2,2
7,2,1,9,8,8,5,3,6,3,3,6
9,9,4,8,7,9,8,6,6,0,3,1
8,3,0,9,1,7,4,8,0,1,6,2
8,2,6,2,4,0,2,8,9,6,3,7
1,0,8,5,3,2,3,7,1,7,8,2
$ while read; do
> pyth -c 'M/*FPJm*F.!MhMrd8aFCB,SGSHeJMl.Ms*VGZ.pHAc2Q,gGHnGH' <<< "$REPLY"
> done < test.in
[4, 4]
[4, 4]
[8, 8]
[4, 4]
[8, 8]
[2, 2]
[4, 4]
[4, 4]
[4, 4]
[36, 36]
[2, 2]
[8, 8]
[24, 24]
[8, 8]
[2, 2]
[2, 2]
[6, 6]
[2, 2]
[8, 8]
[2, 2]
[12, 12]
[2, 2]
[8, 8]
[12, 12]
[4, 4]
[12, 12]
[4, 4]
[6, 6]
[8, 8]
[8, 8]
[6, 6]
[4, 4]
[48, 48]
[8, 8]
[4, 4]
[1, 1]
[4, 4]
[4, 4]
[8, 8]
[4, 4]
[12, 12]
[2, 2]
[96, 96]
[2, 2]
[4, 4]
[2, 2]
[6, 6]
[24, 24]
[24, 24]
[48, 48]
[4, 4]
[8, 8]
[12, 12]
[8, 8]
[4, 4]
[2, 2]
[24, 24]
[16, 16]
[2, 2]
[8, 8]
[24, 24]
[4, 4]
[24, 24]
[4, 4]
[12, 12]
[8, 8]
[12, 12]
[4, 4]
[8, 8]
[4, 4]
[16, 16]
[4, 4]
[8, 8]
[8, 8]
[4, 4]
[4, 4]
[4, 4]
[4, 4]
[72, 72]
[24, 24]
[4, 4]
[4, 4]
[4, 4]
[2, 2]
[12, 12]
[4, 4]
[8, 8]
[4, 4]
[36, 36]
[6, 6]
[12, 12]
[8, 8]
[4, 4]
[2, 2]
[8, 8]
[24, 24]
[6, 6]
[1, 1]
[2, 2]
[2, 2]

Untuk memverifikasi kiriman saya memenuhi persyaratan kecepatan, saya telah menjalankannya dengan test case ini .

$ time pyth -c 'M/*FPJm*F.!MhMrd8aFCB,SGSHeJAc2QgGH' < test-large.in | md5sum
5801bbf8ed0f4e43284f7ec2206fd3ff  -

real    0m0.233s
user    0m0.215s
sys     0m0.019s
Dennis
sumber
2

Matlab, 230 byte

Sunting: Banyak hal yang diperbaiki agar sesuai dengan kasus uji dennis, dan nnz digantikan oleh numel karena nilai nil.

f=1;t=-1;q=1;a=sort(input(''));b=sort(input(''));for i=unique(a)c=b(find(a==i));r=numel(c(c==t));f=f*factorial(numel(c))*sum(arrayfun(@(u)nchoosek(max(q,r),u),0:min(q,r)));z=c(end);y=numel(c(c==z));q=(t==z)*(q+r)+(t~=z)*y;t=z;end,f

Eksekusi

[2 2 1 2 1]
[3 2 3 2 1]

f =

    24

Testcase Dennis:

   A = importdata('f:\a.csv'); for i=1:100,a=sort(A(i,1:6));b=sort(A(i,7:12));
   f=1;t=-1;q=1;for i=unique(a)c=b(find(a==i));r=numel(c(c==t));f=f*factorial(numel(c))*sum(arrayfun(@(u)nchoosek(max(q,r),u),0:min(q,r)));z=c(end);y=numel(c(c==z));q=(t==z)*(q+r)+(t~=z)*y;t=z;end;
   disp(f);end

Output:

 4

 4

 8

 4

 8

 2

 4

 4

 4

36

 2

 8

24

 8

 2

 2

 6

 2

 8

 2

12

 2

 8

12

 4

12

 4

 6

 8

 8

 6

 4

48

 8

 4

 1

 4

 4

 8

 4

12

 2

96

 2

 4

 2

 6

24

24

48

 4

 8

12

 8

 4

 2

24

16

 2

 8

24

 4

24

 4

12

 8

12

 4

 8

 4

16

 4

 8

 8

 4

 4

 4

 4

72

24

 4

 4

 4

 2

12

 4

 8

 4

36

 6

12

 8

 4

 2

 8

24

 6

 1

 2

 2
Abr001am
sumber
Ya, itu memecahkan masalah, jadi input seharusnya tidak terlalu penting.
Element118
1

C ++, 503 byte

(hanya untuk bersenang-senang, bahasa non-golf)

#import<iostream>
#import<algorithm>
#define U 12345
#define l long long
using namespace std;int N,X=1,Y=1,Z=1,x[U],y[U],i=1;l p=1,M=1000000007,f[U];l e(l x,int y){return y?y%2?(x*e(x,y-1))%M:e((x*x)%M,y/2):1;}main(){for(f[0]=1;i<U;i++)f[i]=(f[i-1]*i)%M;cin>>N;for(i=0;i<N;i++)cin>>x[i];for(i=0;i<N;i++)cin>>y[i];sort(x,x+N);sort(y,y+N);for(i=1;i<N;i++)x[i]^x[i-1]?p=p*f[X]%M,X=1:X++,y[i]^y[i-1]?p=p*f[Y]%M,Y=1:Y++,x[i]^x[i-1]|y[i]^y[i-1]?p=p*e(f[Z],M-2)%M,Z=1:Z++;cout<<p*f[X]%M*f[Y]%M*e(f[Z],M-2)%M;}

Versi tidak disatukan:

#include <cstdio>
#include <algorithm>
#define MOD 1000000007
using namespace std;
int N; // number of integers
int x[1000010]; // the 2 arrays of integers
int y[1000010];
long long product = 1;
long long factorial[1000010]; // storing factorials mod 1000000007
long long factorialInv[1000010]; // storing the inverse mod 1000000007
long long pow(long long x, int y) {
    if (y == 0) return 1;
    if (y == 1) return x;
    if (y%2 == 1) return (x*pow(x, y-1))%MOD;
    return pow((x*x)%MOD, y/2);
}
int main(void) {
    //freopen("in.txt", "r", stdin); // used for faster testing
    //precomputation
    factorial[0] = factorial[1] = 1;
    for (int i=2;i<=1000000;i++) {
        factorial[i] = (factorial[i-1]*i)%MOD;
        factorialInv[i] = pow(factorial[i], MOD-2);
    }
    // input
    scanf("%d", &N);
    for (int i=0;i<N;i++) {
        scanf("%d", &x[i]);
    }
    for (int i=0;i<N;i++) {
        scanf("%d", &y[i]);
    }
    // sort the 2 arrays
    sort(x, x+N);
    sort(y, y+N);
    int sameX = 1;
    int sameY = 1;
    int sameXY = 1;
    for (int i=1;i<N;i++) {
        if (x[i]==x[i-1]) {
            sameX++;
        } else {
            product *= factorial[sameX];
            product %= MOD;
            sameX = 1;
        }
        if (y[i]==y[i-1]) {
            sameY++;
        } else {
            product *= factorial[sameY];
            product %= MOD;
            sameY = 1;
        }
        if (x[i]==x[i-1] && y[i]==y[i-1]) {
            sameXY++;
        } else {
            product *= factorialInv[sameXY];
            product %= MOD;
            sameXY = 1;
        }
    }
    product *= factorial[sameX];
    product %= MOD;
    product *= factorial[sameY];
    product %= MOD;
    product *= factorialInv[sameXY];
    product %= MOD;
    printf("%lld\n", product);
    return 0;
}
Elemen118
sumber