Найдите сумму наименьших общих кратных всех подмножеств данного множества

Обсуждение

После прочтения фактического описания конкурса (страница 10 или 11) и набросок решения, я должен заключить, что автор наброска решения довольно неточен в своем письме.

Проблема высокого уровня заключается в вычислении ожидаемого срока службы, если компоненты выбираются случайным образом путем честного подбрасывания монеты. Это то, что приводит к вычислению LCM всех подмножеств — все подмножества эффективно представляют пространство выборки. Вы можете получить любой возможный набор компонентов. Время отказа устройства зависит от LCM комплекта. Таким образом, ожидаемый срок службы представляет собой среднее значение LCM всех комплектов.

Обратите внимание, что это должно включать LCM наборов только с одним элементом (в этом случае мы предполагаем, что LCM является самим элементом). Набросок решения кажется саботажным, возможно, потому, что они обработали его менее элегантно.

Что подразумевается под этими состояниями?

Автор скетча использует слово состояние только дважды, но, видимо, умудряется менять значения. При первом использовании слова состояние кажется, что они говорят о возможном выборе компонентов. Во втором случае они, вероятно, говорят о возможном времени отказа. Они могли запутать эту терминологию, потому что их решение для динамического программирования инициализирует значения из одного использования слова, а рекуррентное отношение вытекает из другого.

Означает ли dp динамическое программирование?

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

Если да, то какое рекуррентное соотношение решается? Как dp[i] вычисляется из dp[i-1]?

Все, что я могу предположить, это то, что в их решении состояние i представляет время до отказа , T(i), с количеством подсчетов времени до отказа, dp[i]. Полученная сумма будет суммировать все dp[i] * T(i).

Тогда dp[i][0] будет временем отказа, учитываемым только для первого компонента. Тогда dp[i][1] будет временем отказа, подсчитанным для первого и второго компонента. dp[i][2] будет для первого, второго и третьего. И т.д..

Инициализируйте dp[i][0] нулями, за исключением dp[T(c)][0] (где c — первый рассматриваемый компонент), который должен быть равен 1 (поскольку время отказа этого компонента уже подсчитано один раз).

Чтобы заполнить dp[i][n] из dp[i][n-1] для каждого компонента c:

• Для каждого i скопируйте dp[i][n-1] в dp[i][n].
• Добавьте 1 к dp[T(c)][n].
• Для каждого i добавьте dp[i][n-1] к dp[LCM(T(i), T(c))][n].

Что это делает? Предположим, вы знали, что у вас есть время до отказа j, но вы добавили компонент со временем до отказа k. Независимо от того, какие компоненты у вас были раньше, ваше новое время для отказа — LCM(j, k). Это следует из того, что для двух наборов A и B, LCM(A union B} = LCM(LCM(A), LCM(B)).

Точно так же, если мы рассматриваем время до отказа T(i) и время до отказа нашего нового компонента T(c), результирующее время до отказа составляет LCM(T(i), T(c)). Обратите внимание, что мы записали это время до отказа для dp[i][n-1] конфигураций, поэтому мы должны записать столько же новых раз до отказа после введения нового компонента.

Почему большие простые числа не влияют на количество состояний?

Каждое из них встречается либо 0, либо 1 раз. Не следует ли умножать количество состояний на 2 для каждого из этих простых чисел (что снова приводит к недопустимому пространству состояний)?

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

Что произойдет, если мы их включим? Количество состояний, которые нам нужно было бы представить, превратилось бы в непрактичное число. Поэтому автор объясняет такие числа по-разному. Обратите внимание, что если число, меньшее или равное 500, включает простое число больше 19, другие множители умножаются на 21 или меньше. Это делает такие числа пригодными для грубой силы, таблицы не нужны.

Первая часть редакционной статьи кажется полезной, но вторая часть довольно расплывчата (и, возможно, бесполезна; я скорее закончу этот ответ, чем разберусь в нем).

Предположим на данный момент, что входные данные состоят из попарно различных простых чисел, например, 2, 3, 5 и 7. Тогда ответ (для суммирования всех множеств, где НОК нулевых целых чисел равен 1)

(1 + 2) (1 + 3) (1 + 5) (1 + 7),

потому что НОК подмножества в точности равен произведению здесь, так что просто умножьте его.

Ослабим ограничение на то, что простые числа попарно различны. Если у нас есть ввод, например 2, 2, 3, 3, 3 и 5, то умножение выглядит как

(1 + (2^2 - 1) 2) (1 + (2^3 - 1) 3) (1 + (2^1 - 1) 5),

потому что 2 появляется с кратностью 2, а 3 появляется с кратностью 3, а 5 появляется с кратностью 1. Что касается, например, только набора троек, существует 2^3 - 1 способов выбрать подмножество, включающее 3, и 1 способа выберите пустой набор.

Назовите простое маленьким, если оно равно 19 или меньше, и большим в противном случае. Обратите внимание, что целые числа 500 или меньше делятся не более чем на одно большое простое число (с кратностью). Маленькие простые числа более проблематичны. Что мы собираемся сделать, так это вычислить для каждой возможной небольшой части простой факторизации НОК (т. е. одного из примерно 70 000 состояний) сумму НОК для задачи, полученной путем отбрасывания целых чисел, которые не могут делиться такой LCM и оставляя только большой простой множитель (или 1) для других целых чисел.

Например, если на входе 2, 30, 41, 46 и 51, а состояние равно 2, то мы сохраняем 2 как 1, отбрасываем 30 (= 2 * 3 * 5; 3 и 5 маленькие), сохраняем 41 как 41 (41 большое), сохранить 46 как 23 (= 2 * 23; 23 большое) и отбросить 51 (= 3 * 17; 3 и 17 маленькие). Теперь мы вычисляем сумму LCM, используя ранее описанную технику. Используйте включение-исключение, чтобы избавиться от подмножеств, LCM которых малая часть которых правильно делит состояние вместо того, чтобы быть точно равным. Может быть, я буду работать полный пример позже.

What is meant by these states?

Я думаю, что здесь состояния относятся к тому, находится ли число в наборе B = {b0, b1,..., bk-1} LCM набора A.

Does dp stand for dynamic programming and if so, what recurrence relation is being solved?

Я полагаю, что dp в эскизе решения означает динамическое программирование.

How is dp[i] computed from dp[i-1]?

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

Why do the big primes not contribute to the number of states? Each of them occurs either 0 or 1 times. Should the number of states not be multiplied by 2 for each of these primes (leading to a non-feasible state space again)?

Мы можем использовать простую факторизацию и показатели степени только для представления числа.

Вот один пример.

6 = (2^1)(3^1)(5^0) -> состояние "1 1 0" для представления 6 18 = (2^1)(3^2)(5^0) -> состояние "1 2 0" для представления 18

Вот как мы можем получить LMC 6 и 18, используя Prime Factorization

НОК (6,18) = (2 ^ (макс. (1,1)) (3 ^ (макс. (1,2)) (5 ​​^ макс. (0,0)) = (2 ^ 1) (3 ^ 2) (5^0) = 18

2^9 > 500, 3^6 > 500, 5^4 > 500, 7^4>500, 11^3 > 500, 13^3 > 500, 17^3 > 500, 19^3 > 500

мы можем использовать только подсчет показателей простого числа 2, 3, 5, 7, 11, 13, 17, 19 для представления LCM в наборе B = {b0, b1, ..., bk-1} для данного установить A = {a0, a1, ..., aN-1} (1 ≤ N ≤ 100), где 2 ≤ ai ≤ 500.

9 * 6 * 4 * 4 * 3 * 3 * 3 * 3 ‹= 70000, поэтому нам нужно только два dp[9][6][4][4][3][3][3][3] для отслеживания всех состояний LCM. Итак, dp[70000][2] достаточно.

Я составил небольшую программу на C++, чтобы проиллюстрировать, как мы можем получить сумму LCM заданного множества A = {a0, a1, ..., aN-1} (1 ≤ N ≤ 100), где 2 ≤ ai ≤ 500. В эскизе решения нам нужно перебрать 70000 максимально возможных LCM.

int gcd(int a, int b) {
    int remainder = 0;
    do {
        remainder = a % b;
        a = b;
        b = remainder;
    } while (b != 0);
    return a;
}

int lcm(int a, int b) {
    if (a == 0 || b == 0) {
        return 0;
    }
    return (a * b) / gcd(a, b);
}


int sum_of_lcm(int A[], int N) {

    // get the max LCM from the array
    int max = A[0];
    for (int i = 1; i < N; i++) {
        max = lcm(max, A[i]);
    }
    max++;

    //
    int dp[max][2];
    memset(dp, 0, sizeof(dp));
    int pri = 0;
    int cur = 1;

    // loop through n x 70000
    for (int i = 0; i < N; i++) {
        for (int v = 1; v < max; v++) {
            int x = A[i];
            if (dp[v][pri] > 0) {
                x = lcm(A[i], v);
                dp[v][cur] = (dp[v][cur] == 0) ? dp[v][pri] : dp[v][cur];
                if ( x % A[i] != 0 ) {
                    dp[x][cur] += dp[v][pri] + dp[A[i]][pri];
                } else {
                    dp[x][cur] += ( x==v ) ? ( dp[v][pri] + dp[v][pri] ) : ( dp[v][pri] ) ;
                }
            }
        }
        dp[A[i]][cur]++;
        pri = cur;
        cur = (pri + 1) % 2;
    }

    for (int i = 0; i < N; i++) {
        dp[A[i]][pri] -= 1;
    }
    long total = 0;
    for (int j = 0; j < max; j++) {
        if (dp[j][pri] > 0) {
            total += dp[j][pri] * j;
        }
    }
    cout << "total:" << total << endl;

    return total;
}



int test() {
    int a[] = {2, 6, 7 };
    int n = sizeof(a)/sizeof(a[0]);
    int total = sum_of_lcm(a, n);
    return 0;
}

Output
total:104

Состояний на единицу больше, чем степеней простых чисел. У вас есть числа до 2 ^ 8, поэтому степень 2 находится в [0..8], что составляет 9 состояний. Аналогично для других штатов.

«dp» вполне может означать динамическое программирование, я не уверен.

Рекуррентное соотношение является сердцевиной проблемы, поэтому вы узнаете больше, решая ее самостоятельно. Начните с небольших простых примеров.

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