Фон

Перестройка Неравенство является неравенство, которое основано на перестановкой чисел. Если у меня есть два списка чисел одинаковой длины, x ₀ , x ₁ , x ₂ ... x _n-1 и y ₀ , y ₁ , y ₂ ... y _n-1 одинаковой длины, где I разрешено переставлять числа в списке, способ максимизировать сумму x ₀ y ₀ + x ₁ y ₁ + x ₂ y ₂ + ... + x _n-1 y _n-1 состоит в сортировке 2 списков в неубывающий порядок.

Прочитайте статью Wikipedia здесь.

задача

Вы бы написали программу, которая принимает входные данные из STDIN, или функцию, которая принимает 2 массива (или связанных контейнеров) чисел (одинаковой длины).

Предполагая, что вы пишете функцию, которая принимает 2 массива (a и b), вы найдете количество способов, которыми вы можете переставить числа во втором массиве (b), чтобы максимизировать:

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

В этом случае, если массив b равен [1 ₀ , 2 ₁ , 2 ₂ , 3 ₃ , 3 ₄ ] (индексы для наглядности),

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

[1 ₀ , 2 ₁ , 2 ₂ , 3 ₄ , 3 ₃ ], (поменяйте местами 3)

[1 ₀ , 2 ₂ , 2 ₁ , 3 ₃ , 3 ₄ ] (поменяйте местами 2)

[1 ₀ , 2 ₂ , 2 ₁ , 3 ₄ , 3 ₃ ] (поменяйте местами 3 и поменяйте местами 2)

считаются разными мероприятиями. Сам исходный массив также считается возможной перестановкой, если он также максимизирует сумму.

Для ввода STDIN вы можете предположить, что длина массивов указана перед массивами (просьба указать, что вы используете их), или что массивы указаны в разных строках (также укажите, пожалуйста).

Вот 4 возможных входа (для удобства):

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)

Для вывода вы можете вернуть ответ (если вы пишете функцию) или распечатать ответ в STDOUT. Вы можете выбрать вывод мод 10 ⁹ +7 (от 0 до 10 ⁹ +6), если это более удобно.

Тестовые случаи (и объяснение):

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

Первые 2 записи должны быть 1 и 2. Последние 3 записи - это 2, 3 и 3. Есть 2 способа расположить 2 между первыми 2 записями и последними 2 записями. Среди первых 2 записей есть 2 способа их переставить. Среди последних 2 записей есть 6 способов их перегруппировать.

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

Существует только 1 способ, который представляет собой расположение в массивах.

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

Каждая возможная перестановка второго массива действительна.

Тест Денниса: Pastebin => 583159312 (мод 1000000007)

Подсчет очков:

Это код-гольф, поэтому выигрывает самый короткий ответ.

В случае ничьей, связи будут разорваны к моменту подачи, что благоприятствует более раннему представлению.

Принять к сведению:

Контейнеры могут быть несортированными.

Целые числа в контейнерах могут быть нулевыми или отрицательными.

Программа должна работать достаточно быстро (максимум час) для массивов небольшого размера (около 10000 в длину).

Вдохновленный этим вопросом о математике стек обмена.

code-golf math combinatorics permutations Element118
источник

2

Пожалуйста, предоставьте контрольный пример с 10000 элементами на массив, чтобы мы могли убедиться, что наш код работает правильно и достаточно быстро.

Денис

1

В примере, который вы даете для перестановки второго массива [1_0, 2_2, 2_1, 3_4, 3_3] (поменяйте местами две 2 и поменяйте местами 3), отсутствует

Виллем

вы принимаете входные данные, такие как [. . .]ответ плз

Abr001am

Если мы передаем функцию, нужно ли нам принимать два отдельных аргумента или мы можем принимать массив массивов?

Денис

Ну, массив массивов выглядит хорошо и не слишком сильно влияет на задачу. Я буду работать над тестом.

Элемент118

4

CJam, 30 26 байтов

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

Попробуйте онлайн в интерпретаторе CJam .

Он завершает этот контрольный пример менее чем за секунду:

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

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

Запуск его в онлайн-переводчике должен занять не более 10 секунд.

Алгоритм

Результат не зависит от порядка A , поэтому мы можем предположить, что он отсортирован. Это означает, что B также должен быть отсортирован, чтобы получить максимальное произведение точек.

Теперь, если r ₁ ,… r _n - длина прогонов отсортированного A , есть kr _k ! различные перестановки элементов A, которые все еще приводят к возрастанию.

Аналогично, если s ₁ ,… s _n - длина прогонов отсортированного B , то есть ks _k ! различные перестановки элементов B, которые все еще приводят к возрастанию.

Тем не менее, это подсчитывает все спаривания несколько раз. Если мы возьмем пары соответствующих элементов отсортированных A и B и определим t ₁ ,… t _n как длину прогонов результирующего массива, kt _k ! является вышеупомянутым множителем.

Таким образом, желаемый результат равен (∏r _k !) × (∏s _k !) ÷ (∏t _k !) .

Код

 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.

Деннис
источник

6

Pyth, 29 28 байт

M/*FPJm*F.!MhMrd8aFCB,SGSHeJ

Попробуйте онлайн в компиляторе Pyth .

Алгоритм

Результат не зависит от порядка A , поэтому мы можем предположить, что он отсортирован. Это означает, что B также должен быть отсортирован, чтобы получить максимальное произведение точек.

Теперь, если r ₁ ,… r _n - длина прогонов отсортированного A , есть kr _k ! различные перестановки элементов A, которые все еще приводят к возрастанию.

Аналогично, если s ₁ ,… s _n - длина прогонов отсортированного B , то есть ks _k ! различные перестановки элементов B, которые все еще приводят к возрастанию.

Тем не менее, это подсчитывает все спаривания несколько раз. Если мы возьмем пары соответствующих элементов отсортированного A и отсортированного B и определим t ₁ ,… t _n как длину прогонов результирующего массива, kt _k ! является вышеупомянутым множителем.

Таким образом, желаемый результат равен (∏r _k !) × (∏s _k !) ÷ (∏t _k !) .

Код

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.

верификация

Я псевдослучайно сгенерировал 100 тестовых случаев длины 6, которые я решил с помощью приведенного выше кода и этого подхода грубой силы:

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.

Это были результаты:

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

Чтобы убедиться, что моя заявка удовлетворяет требованиям скорости, я запустил ее в этом тестовом примере .

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

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

Деннис
источник

2

Matlab, 230 байт

Редактировать: Многие вещи исправлены, чтобы соответствовать тестовым кейсам Денниса, и nnz заменяется цифрой из-за значений 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

выполнение

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

f =

    24

Тест Денниса:

   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

Выходы:

Abr001am
источник

Ну, это решает проблему, поэтому ввод не должен иметь большого значения.

Element118

1

C ++, 503 байта

(просто для удовольствия, не для игры в гольф)

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

Безголовая версия:

#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
источник

Перестановка Неравенство

Фон

задача

Тестовые случаи (и объяснение):

Подсчет очков:

Принять к сведению:

Ответы:

CJam, 30 26 байтов

Алгоритм

Код

Pyth, 29 28 байт

Алгоритм

Код

верификация

Matlab, 230 байт

выполнение

Тест Денниса:

C ++, 503 байта