Facebook Hacker Cup: власть подавляющая

Question

Многие люди в Facebook любят играть в Starcraft II ™.Некоторые из них создали собственную игру, используя редактор карт Starcraft II ™.В этой игре вы играете за благородного протосса, защищающего свой принятый родной мир Шакурас от массивной армии зергов.Вы должны нанести как можно больше урона зергам, прежде чем разбить себя.Вы можете построить только два типа юнитов, генераторов щитов и воинов.Генераторы щитов не наносят урона, но ваша армия выживает в течение одной секунды на каждый созданный вами генератор щитов.Воины наносят один урон каждую секунду.После истечения срока действия ваших генераторов щита ваша армия будет немедленно захвачена.Сколько генераторов щита и сколько воинов вы должны построить, чтобы нанести максимальный урон зергам перед тем, как ваша армия будет захвачена?Поскольку храбрость Протоссов ценится, если существует более одного решения, вы должны вернуть то, которое использует большинство воинов.

Ограничения

• 1 ≤ G (стоимость одного генератора щита)≤ 100
• 1 ≤ W (стоимость одного воина) ≤ 100
• G + W ≤ M (доступные средства) ≤ 1000000000000 (10 ¹² )

Answer 1

Вот решение, сложность которого составляет O (W) .Пусть g будет числом созданных нами генераторов, и аналогично пусть w будет числом построенных нами воинов (а G, W будут соответствующими ценами за единицу.).

Мы отмечаем, что мы хотим максимизировать w * g с учетом w * W + g * G <= M </b>.

Сначаламы избавимся от одной из переменных.Обратите внимание, что если мы выберем значение для g , то очевидно, что мы должны купить как можно больше воинов с оставшейся суммой денег M - g * G .Другими словами, w = floor ((Mg * G) / W) .

Теперь проблема состоит в том, чтобы максимизировать g * floor ((Mg * G) / W) при условии 0 <= g <= этаж (M / G) </b>.Мы хотим избавиться от пола, поэтому давайте рассмотрим W отдельных случаев.Запишем g = W * k + r , где 0 <= r <W </b> - остаток от деления g на W .

Идея состоит в том, чтобы исправить r и вставить выражение для g , а затем позволить k быть переменной в уравнении.Мы получим следующее квадратное уравнение в k :

Пусть p = floor ((M - r * G) / W) , тогда уравнение будет (- GW) * k ^ 2 + (Wp - rG) k + rp .

Это квадратное уравнение, которое переходит в отрицательную бесконечность, когда x переходит в бесконечность или отрицательную бесконечность, поэтому имеетглобальный максимум на k = -B / (2A) .Чтобы найти максимальное значение для допустимых значений k, мы попробуем минимальное допустимое значение k, максимальное допустимое значение k и две ближайшие целые точки действительного максимума, если они находятся в допустимом диапазоне.

Общий максимум для всех значений r - это то, что мы ищем.Поскольку для r имеются значения W , а для вычисления максимума для фиксированного значения требуется O (1) , общее время составляет O(W) .

Answer 2

Если вы строите г генераторов и ш воинов, вы можете нанести общий урон в размере w (урон за время) & времена; г (время до окончания игры).

Ограничение средств ограничивает значение г и ш до Ш & раз; ш + G & times; г & leq; M .

Если вы создаете г генераторов, вы можете построить не более ( M - г & times; G ) / W воинов и до г & раз; ( M - g & times; G ) / W урон.

Эта функция имеет максимум при г = M / (2 G ), в результате чего M ² / (4 G W ) урон.

Резюме:

• Сборка M / (2 G ) генераторов экрана.
• Сборка М / (2 G ) воинов.
• Do M ² / (4 G W ) урон.

---

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

увеличить g & times; ш
относительно g & times; G + w & times; Ш & leq; M и g , w & in; & # X2124; ⁺

Общая проблема Целочисленное программирование является NP-полной, поэтому лучшим алгоритмом для этого является проверка всех целочисленных значений, близких к вещественному решению, указанному выше.

Если вы найдете какую-либо пару ( г _i , w _i ), с полным ущербом d _i , вам нужно только проверить значения, где г _j & раз; ш _j & geq; * ** +1248 одна тысяча двести сорок семь * д * ** 1250 тысяча двести сорок-девять ** ** 1252 тысячу двести пятьдесят-одна * г . Это и исходное состояние W & раз; ш + G & times; г & leq; M ограничивает пространство поиска каждым найденным элементом.

---

F # -код:

let findBestSetup (G : int) (W : int) (M : int) =
    let mutable bestG = int (float M / (2.0 * float G))
    let mutable bestW = int (float M / (2.0 * float W))
    let mutable bestScore = bestG * bestW
    let maxW = (M + isqrt (M*M - 4 * bestScore * G * W)) / (2*G)
    let minW = (M - isqrt (M*M - 4 * bestScore * G * W)) / (2*G)
    for w = minW to maxW do
        // ceiling of (bestScore / w)
        let minG = (bestScore + w - 1) / w
        let maxG = (M - W*w)/G
        for g = minG to maxG do
            let score = g * w
            if score > bestScore || score = bestScore && w > bestW then
                bestG <- g
                bestW <- w
                bestScore <- score
    bestG, bestW, bestScore

Answer 3

Предполагалось, что W и G были подсчетами, а стоимость каждого была равна 1. Поэтому он устарел с обновленным вопросом.

Урон = LifeTime * DamagePerSecond = W * G

Так что вам нужно максимизировать W * G с ограничением G + W <= M. Поскольку и Генераторы, и Воины всегда хороши, мы можем использовать G + W = M. </p>

Таким образом, функциямы хотим максимизировать становится W * (МВт).Теперь мы устанавливаем производную = 0:М-2W = 0W = M / 2

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

Если М четное, то непрерывное решение идентично дискретному решению.Если M нечетно, то у нас есть два ближайших решения, одно с одним воином больше, чем у генераторов, а другое наоборот.И ОП сказал, что мы должны выбрать больше воинов.

Итак, окончательное решение:G = W = M / 2 для четного Mи G + 1 = W = (M + 1) / 2 для нечетных M.

Answer 4

Так как я решил это прошлой ночью, я думал, что выложу свое решение C ++. Алгоритм начинается с первоначального предположения, расположенного на глобальном максимуме непрерывного случая. Затем он ищет «немного» слева / справа от первоначального предположения, заканчивая рано, когда непрерывный случай падает ниже уже установленного максимума. Интересно, что 5 примеров ответов, опубликованных ФБ, содержали 3 неправильных ответа:

Case #1
  ours:   21964379805 dmg: 723650970382348706550
  theirs: 21964393379 dmg: 723650970382072360271 Wrong
Case #2
  ours:   1652611083 dmg: 6790901372732348715
  theirs: 1652611083 dmg: 6790901372732348715 
Case #3
  ours:   12472139015 dmg: 60666158566094902765
  theirs: 12472102915 dmg: 60666158565585381950 Wrong
Case #4
  ours:   6386438607 dmg: 10998633262062635721
  theirs: 6386403897 dmg: 10998633261737360511 Wrong
Case #5
  ours:   1991050385 dmg: 15857126540443542515
  theirs: 1991050385 dmg: 15857126540443542515

Наконец, код (он использует libgmpxx для больших чисел). Я сомневаюсь, что код является оптимальным, но он завершается за 0,280 мс на моем персональном компьютере для примера ввода, данного FB ....

#include <iostream>
#include <gmpxx.h>

using namespace std;

typedef mpz_class Integer;
typedef mpf_class Real;

static Integer getDamage( Integer g, Integer G, Integer W, Integer M)
{
    Integer w = (M - g * G) / W;
    return g * w;
}

static Integer optimize( Integer G, Integer W, Integer M)
{
    Integer initialNg = M / ( 2 * G);
    Integer bestNg = initialNg;
    Integer bestDamage = getDamage ( initialNg, G, W, M);

    // search left
    for( Integer gg = initialNg - 1 ; ; gg -- ) {
        Real bestTheoreticalDamage = gg * (M - gg * G) / (Real(W));
        if( bestTheoreticalDamage < bestDamage) break;
        Integer dd = getDamage ( gg, G, W, M);
        if( dd >= bestDamage) {
            bestDamage = dd;
            bestNg = gg;
        }
    }

    // search right
    for( Integer gg = initialNg + 1 ; ; gg ++ ) {
        Real bestTheoreticalDamage = gg * (M - gg * G) / (Real(W));
        if( bestTheoreticalDamage < bestDamage) break;
        Integer dd = getDamage ( gg, G, W, M);
        if( dd > bestDamage) {
            bestDamage = dd;
            bestNg = gg;
        }
    }

    return bestNg;
}

int main( int, char **)
{
    Integer N;

    cin >> N;
    for( int i = 0 ; i < N ; i ++ ) {
        cout << "Case #" << i << "\n";
        Integer G, W, M, FB;
        cin >> G >> W >> M >> FB;

        Integer g = optimize( G, W, M);

        Integer ourDamage = getDamage( g, G, W, M);
        Integer fbDamage = getDamage( FB, G, W, M);

        cout << "  ours:   " << g << " dmg: " << ourDamage << "\n"
             << "  theirs: " << FB << " dmg: " << fbDamage << " "
             << (ourDamage > fbDamage ? "Wrong" : "") << "\n";
    }
}

Answer 5

Не совсем решение, но здесь идет речь.

Предполагается, что вы уже получаете большое значение урона, когда количество щитов равно 1 (не может быть равно нулю или урон не будет)количество воинов равно (m-g)/w.Повторение вверх должно (опять-таки предположение) достичь точки компромисса между количеством щитов и воинов, где урон максимален.Это обрабатывается веткой bestDamage > calc.

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

        long bestDamage = 0;
        long numShields = 0;
        long numWarriors = 0;

        for( int k = 1;; k++ ){
            // Should move declaration outside of loop
            long calc = m / ( k * g ); // k = number of shields

            if( bestDamage < calc ) {
                bestDamage = calc;
            }

            if( bestDamage > calc ) {
                numShields = k;
                numWarriors = (m - (numShields*g))/w;
                break;
            }
        }

        System.out.println( "numShields:" + numShields );
        System.out.println( "numWarriors:" + numWarriors );
        System.out.println( bestDamage );

Answer 6

g = общее количество генераторов gc = стоимость генератора w = воины wc = стоимость воина m = деньги d = общий урон

g = (m - (w * wc)) / gc w = (m - (g * gc)) / wc

d = g * wd = ((m - (w * wc)) / gc) * ((m - (g * gc)) / wc) d = ((m - (w * wc)) / gc) * ((m - (((m - (w * wc)) / gc) * gc)) / wc) урон воинам как функция

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

Чтобы найти максимум, вам нужно дифференцировать это уравнение и найти, когдаэто равно нулю, что я забыл, как делать посев, я не занимался математикой около 6 лет