Google Code Jam 2008 – finále

Řešení: U dvou přísad by se dalo postupovat tak, že bychom si do pole $plusminus u každého člověka poznamenali, od jakého do jakého množství jedné přísady mu džus bude chutnat. V tomto poli bychom pak hledali maximální hodnotu. Pro tři přísady stačí vyzkoušet sestavit toto pole pro všechny možné hodnoty třetí přísady.

<?php
function juices($people) {
    $return = 0;
    sort($people);
    foreach (array_reverse($people, true) as $key => $val) {
        list($a, $b, $c) = $val;
        $plusminus = array();
        foreach ($people as $val2) {
            list($a2, $b2, $c2) = $val2;
            if ($a + $b2 + $c2 <= 10000) {
                $plusminus[$b2]++;
                $plusminus[10001 - $a - $c2] -= 1;
            }
        }
        ksort($plusminus);
        $value = 0;
        foreach ($plusminus as $val) {
            $value += $val;
            $return = max($return, $value);
        }
        unset($people[$key]);
    }
    return $return;
}
?>

Pro dekrementaci pole $plusminus se nepoužívá operátor --, ale konstrukce -= 1. Důvodem je, že hodnotu null operátor -- nesníží.

Řešení: Funkce začne na startovním políčku a ověří, jestli balónek ještě nevypadl z místnosti a jestli jsme dané políčko už nenavštívili. Pokud ne, tak nejprve aktivuje jeden balónek a potom druhý.

<?php
function pingpong($size, $ball1, $ball2, $x, $y, &$hits = array()) {
    if ($x >= 0 && $x < $size[0] && $y >= 0 && $y < $size[1] && !isset($hits["$x:$y"])) {
        $hits["$x:$y"] = true;
        pingpong($size, $ball1, $ball2, $x + $ball1[0], $y + $ball1[1], $hits);
        pingpong($size, $ball1, $ball2, $x + $ball2[0], $y + $ball2[1], $hits);
    }
    return count($hits);
}
?>

Pro vyřešení velkého vstupu by bylo potřeba zjistit, do jakých rohů se míčky vůbec nedostanou, a ve zbytku určit podíl aktivovaných pastí.

Řešení: Osobně bych vyzkoušel všechny možnosti a postupem od větví, které se můžou nejméně rozvětvit, bych se pokusil minimalizovat čas testování. Existuje ale i elegantnější řešení – počet min v prostřední řadě totiž přímo plyne z mapy čísel. Stačí si uvědomit, že počet min v každé devítici políček je určen číslem uprostřed tohoto čtverce (pro krajní šestice to určuje prostřední políčko u okraje). Takto můžeme zjistit počet min v každé trojici řad a tím pádem i v horních a dolních (N + 1) / 2 řadách. A když od součtu těchto řad (kde je prostřední řada dvakrát) odečteme celkový počet min získaný stejným způsobem, máme přesně počet min v prostřední řadě.

<?php
function mines($number) {
    $cols = count($number);
    $return = 0;
    for ($i = ($cols % 3 ? 0 : 1); $i < $cols; $i += 3) {
        $return += $number[$i];
    }
    return $return;
}

function minelayer($numbers) {
    $rows = count($numbers);
    $return = 0;
    for ($j = ($rows + (($rows - 1) % 6 ? 1 : 3)) / 2; $j < $rows; $j += 3) {
        $return += mines($numbers[$j]);
        $return += mines($numbers[$rows - $j - 1]);
    }
    for ($j = ($rows % 3 ? 0 : 1); $j < $rows; $j += 3) {
        $return -= mines($numbers[$j]);
    }
    return abs($return);
}
?>

Pokud je polovina počtu řádek dělitelná třemi, tak prostřední řádku nelze snadno započítat dvakrát, dá se ale naopak velmi snadno vynechat. Z tohoto důvodu se na konci funkce vrací absolutní hodnota rozdílu.

Řešení: Mapu budeme procházet do šířky a u každého políčka si poznamenáme, jak je daleko od nejbližšího lesa. Jakmile dorazíme do nějakého lesa, zapíšeme do něj nulu, ale nesmíme zapomenout připočítat cestu, kterou jsme museli urazit z předchozího lesa. Výsledkem je potom součet vzdáleností všech políček od nejbližšího lesa a napočítaných cest mezi lesy.

<?php
function bridges($map) {
    $queue = array(array(0, 0, 0));
    $return = 0;
    $distances = array();
    while ($queue) {
        $val = min($queue);
        unset($queue[array_search($val, $queue)]);
        list($distance, $y, $x) = $val;
        if (isset($map[$y][$x]) && $map[$y][$x] != '.' && (!isset($distances["$y:$x"]) || $distance < $distances["$y:$x"])) {
            if ($map[$y][$x] == 'T') {
                $return += floor(($distance + 2) / 2) * ceil($distance / 2);
                $distance = 0;
            }
            $distances["$y:$x"] = $distance;
            $queue[] = array($distance+1, $y-1, $x);
            $queue[] = array($distance+1, $y+1, $x);
            $queue[] = array($distance+1, $y, $x-1);
            $queue[] = array($distance+1, $y, $x+1);
        }
    }
    return $return + array_sum($distances);
}
?>

V každém průchodu cyklem se hledá nejmenší prvek pomocí funkcí min a array_search, využívají se přitom pravidla pro porovnávání polí. Nové ostrovy ke zkontrolování by se do pole $queue mohly zatřiďovat, což by trvalo jen O(log n) místo O(n), algoritmus je ale dost rychlý i bez toho.

Pro započtení vzdálenosti mezi lesy se používá součet posloupnosti každého druhého čísla. Protože pokud to do lesa bylo např. 5 hodin, tak 5 přepíšeme na 0 (rozdíl 5), 4 na 1 (rozdíl 3) a 3 na 2 (rozdíl 1).