fundo

A desigualdade de rearranjo é uma desigualdade baseada em números de reorganização. Se eu tiver duas listas de números do mesmo comprimento, x ₀ , x ₁ , x ₂ ... x _n-1 e y ₀ , y ₁ , y ₂ ... y _n-1 do mesmo comprimento, onde eu É permitido reorganizar os números na lista, uma maneira de maximizar a soma x ₀ y ₀ + x ₁ y ₁ + x ₂ y ₂ + ... + x _n-1 y _n-1 é classificar as 2 listas em ordem não decrescente.

Leia o artigo da Wikipedia aqui.

Tarefa

Você escreveria um programa que recebe a entrada do STDIN ou uma função que aceita 2 matrizes (ou contêineres relacionados) de números (que têm o mesmo comprimento).

Supondo que você escreva uma função que aceite 2 matrizes (aeb), você encontrará o número de maneiras pelas quais pode reorganizar os números na segunda matriz (b) para maximizar:

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

Nesse caso, se a matriz b for [1 ₀ , 2 ₁ , 2 ₂ , 3 ₃ , 3 ₄ ] (índices de clareza),

[1 ₀ , 2 ₁ , 2 ₂ , 3 ₃ , 3 ₄ ],

[1 ₀ , 2 ₁ , 2 ₂ , 3 ₄ , 3 ₃ ], (troque os dois 3)

[1 ₀ , 2 ₂ , 2 ₁ , 3 ₃ , 3 ₄ ] (troque os dois 2)

[1 ₀ , 2 ₂ , 2 ₁ , 3 ₄ , 3 ₃ ] (troque os dois 3 e troque os dois 2)

são considerados arranjos diferentes. A matriz original, por si só, também conta como um possível rearranjo se também maximizar a soma.

Para entrada STDIN, você pode assumir que o comprimento das matrizes é fornecido antes das matrizes (indique para usá-las) ou que as matrizes sejam fornecidas em linhas diferentes (também indique).

Aqui estão as 4 entradas possíveis (por conveniência):

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)

Para saída, você pode retornar a resposta (se você escrever uma função) ou imprimir a resposta em STDOUT. Você pode escolher a saída mod 10 ⁹ +7 (de 0 a 10 ⁹ +6), se for mais conveniente.

Casos de teste (e explicação):

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

As 2 primeiras entradas devem ser 1 e 2. As 3 últimas entradas são 2, 3 e 3. Existem 2 maneiras de organizar os 2 entre as 2 primeiras entradas e as 2 últimas entradas. Entre as 2 primeiras entradas, existem 2 maneiras de reorganizá-las. Entre as duas últimas entradas, existem 6 maneiras de reorganizá-las.

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

Existe apenas uma maneira, que é o arranjo fornecido nas matrizes.

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

Toda permutação possível da segunda matriz é válida.

Caso de teste de Dennis: Pastebin => 583159312 (mod 1000000007)

Pontuação:

Este é o código-golfe, por isso a resposta mais curta vence.

Em caso de empate, os empates serão interrompidos no momento da submissão, favorecendo a submissão anterior.

Tome nota:

Os recipientes podem não ser separados.

Os números inteiros nos contêineres podem ser zero ou negativos.

O programa precisa ser executado com rapidez suficiente (no máximo uma hora) para matrizes de tamanho modesto (com cerca de 10000 de comprimento).

Inspirado por esta pergunta no Mathematics Stack Exchange.

code-golf math combinatorics permutations Element118
fonte

2

Forneça um caso de teste com 10000 elementos por matriz, para que possamos verificar se nosso código funciona corretamente e é rápido o suficiente.

Dennis

11

No exemplo que você fornece para trocar a segunda matriz [1_0, 2_2, 2_1, 3_4, 3_3] (troque os dois 2 e troque os dois 3)) está faltando

Willem

você aceita entradas como [. . .]responder plz

Abr001am

Se enviarmos uma função, teremos que tomar dois argumentos separados ou poderíamos ter uma matriz de matrizes?

Dennis

Bem, a matriz de matrizes parece boa e não afeta muito o desafio. Vou trabalhar no caso de teste.

precisa

4

CJam, 30 26 bytes

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

Experimente on-line no intérprete CJam .

Ele conclui este caso de teste em menos de um segundo:

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

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

A execução no intérprete online deve levar menos de 10 segundos.

Algoritmo

O resultado não depende da ordem de A , portanto podemos assumir que ele foi classificado. Isso significa que B também deve ser classificado para atingir o produto de ponto máximo.

Agora, se r ₁ ,… r _n é o comprimento das execuções do A ordenado , existem kr _k ! rearranjos diferentes dos elementos de A que ainda resultam em ordem crescente.

Da mesma forma, se é ₁ , ... s _n são o comprimento das pistas da ordenada B , há Πs _k ! rearranjos diferentes dos elementos de B que ainda resultam em ordem crescente.

No entanto, isso conta todos os pares várias vezes. Se pegarmos os pares dos elementos correspondentes da ordem A e da ordem B e definirmos t ₁ ,… t _n como o comprimento das execuções da matriz resultante, kt _k ! é o multiplicador acima mencionado.

Assim, o resultado desejado é (kr _k !) × (∏s _k !) ÷ (∏t _k !) .

Código

 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
fonte

6

Pitão, 29 28 bytes

M/*FPJm*F.!MhMrd8aFCB,SGSHeJ

Experimente online no Pyth Compiler .

Algoritmo

O resultado não depende da ordem de A , portanto podemos assumir que ele foi classificado. Isso significa que B também deve ser classificado para atingir o produto de ponto máximo.

Agora, se r ₁ ,… r _n é o comprimento das execuções do A ordenado , existem kr _k ! rearranjos diferentes dos elementos de A que ainda resultam em ordem crescente.

Da mesma forma, se é ₁ , ... s _n são o comprimento das pistas da ordenada B , há Πs _k ! rearranjos diferentes dos elementos de B que ainda resultam em ordem crescente.

No entanto, isso conta todos os pares várias vezes. Se pegarmos os pares dos elementos correspondentes da ordem A e da ordem B e definirmos t ₁ ,… t _n como o comprimento das execuções da matriz resultante, kt _k ! é o multiplicador acima mencionado.

Assim, o resultado desejado é (kr _k !) × (∏s _k !) ÷ (∏t _k !) .

Código

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.

Verificação

Eu pseudo-gerei aleatoriamente 100 casos de teste de comprimento 6, que resolvi com o código acima e essa abordagem de força bruta:

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.

Estes foram os resultados:

$ 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]

Para verificar se meu envio atende aos requisitos de velocidade, executei-o neste caso de teste .

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

real    0m0.233s
user    0m0.215s
sys     0m0.019s

Dennis
fonte

2

Matlab, 230 bytes

Edit: Muitas coisas corrigidas para combinar com os casos de teste de dennis, e nnz é substituído por numel devido a valores nulos.

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

Execução

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

f =

    24

Caso de teste de 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

Saídas:

Abr001am
fonte

Bem, isso resolve o problema, então a entrada não deve importar muito.

precisa

1

C ++, 503 bytes

(apenas por diversão, um idioma que não seja de golfe)

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

Versão não destruída:

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

Element118
fonte

Desigualdade de rearranjo

fundo

Tarefa

Casos de teste (e explicação):

Pontuação:

Tome nota:

Respostas:

CJam, 30 26 bytes

Algoritmo

Código

Pitão, 29 28 bytes

Algoritmo

Código

Verificação

Matlab, 230 bytes

Execução

Caso de teste de Dennis:

C ++, 503 bytes