Google Code Jam 2008 - semifinále

Řešení: Nejprve vyřešíme dva okrajové případy:

1. Pokud má objekt stejnou výšku a hmotnost jako nějaký nepták, tak je to určitě taky nepták.
2. Pokud jsme nedostali žádný exemplář ptáka, tak u ostatních zvířat druh určitě nedokážeme určit.

Pokud má zvíře výšku i hmotnost v rozsahu minima a maxima těchto hodnot u předaných ptáků, tak to určitě také bude pták. Nejsložitější je vymyslet podmínku, která rozliší, zda se jedná o neptáka, nebo zda to nedokážeme určit:

• Pokud má zvíře správnou hmotnost, ale výšku má nižší než nějaký menší nepták nebo naopak vyšší než větší nepták, tak jde určitě také o neptáka.
• Totéž platí s prohozenou výškou a hmotností.
• Pokud má navíc zvíře výšku nižší než menší nepták (nebo vyšší než větší nepták) a zároveň hmotnost nižší než lehčí nepták (nebo vyšší než těžší nepták), tak jde určitě také o neptáka.

V jiném případě výsledek nedokážeme určit.

function birds($birds, $not_birds, $test) {
	$weights = array();
	$heights = array();
	foreach ($birds as $bird) {
		list($heights[], $weights[]) = $bird;
	}
	$return = "";
	foreach ($test as $bird) {
		if (in_array($bird, $not_birds)) {
			$return .= "NOT BIRD\n";
		} elseif (!$birds) {
			$return .= "UNKNOWN\n";
		} elseif ($bird[0] >= min($heights) && $bird[0] <= max($heights) && $bird[1] >= min($weights) && $bird[1] <= max($weights)) {
			$return .= "BIRD\n";
		} else {
			foreach ($not_birds as $val) {
				list($height, $weight) = $val;
				if (($weight >= min($weights) && $weight <= max($weights) && ($height < min($heights) ? $bird[0] <= $height : $bird[0] >= $height))
				|| ($height >= min($heights) && $height <= max($heights) && ($weight < min($weights) ? $bird[1] <= $weight : $bird[1] >= $weight))
				|| ((($bird[0] <= $height && $height < min($heights)) || ($bird[0] >= $height && $height > max($heights)))
					&& (($bird[1] <= $weight && $weight < min($weights)) || ($bird[1] >= $weight && $weight > min($weights)))
				)) {
					$return .= "NOT BIRD\n";
					continue 2;
				}
			}
			$return .= "UNKNOWN\n";
		}
	}
	return $return;
}

Algoritmus by se dal ještě optimalizovat (minimálně vypočtením minima a maxima před cyklem), ale není to potřeba.

Řešení: Při barvení plotu budeme postupovat zleva doprava. Nabídky si setřídíme podle začátku barvení a prohledáme jenom ty, které začínají před první nenabarvenou laťkou. Podobně si nevšímáme nabídek, které nás v barvení neposunou dál a jen přebarví již nabarvený úsek. Tím významně snížíme počet prohledávaných kombinací, takže úlohu vyřešíme i pro velký vstup.

/** Nabarvení plotu s 10 000 laťkami maximálně třemi barvami
* @param array $offers pole ve tvaru array($zacatek => array($konec => $barva)) seřazené podle $zacatek a potom podle $konec sestupně
* @return int minimální počet nabídek nutných pro nabarvení plotu nebo 10 001, pokud plot nabarvit nelze
*/
function fence($offers, $start = 1, $colors = array(), $count = 0) {
	if ($start > 10000) {
		return $count;
	}
	$return = 10001;
	foreach ($offers as $a => $offer) {
		if ($a > $start) {
			break;
		}
		foreach ($offer as $b => $color) {
			if ($b < $start) {
				break;
			}
			$offers[$a] = array_slice($offers[$a], 1, null, true);
			if (isset($colors[$color]) || count($colors) < 3) {
				$return = min($return, fence($offers, $b + 1, $colors + array($color => true), $count + 1));
			}
		}
		$offers = array_slice($offers, 1, null, true);
	}
	return $return;
}

Funkce array_slice($offers, 1, null, true) se používá místo array_shift proto, že zachová přiřazení klíčů.

Řešení: Pro začátek je dobré si uvědomit, že pokud už do konce zbývá jen jedno kolo, musíme mít alespoň 500 tisíc. Naopak libovolná vyšší částka, menší než milion, nám nijak nepomůže. Stejně tak dvě kola před koncem musíme vsadit 250 tisíc, takže dává smysl mít částky 250, 500 nebo 750 tisíc. V jednotlivých kolech se tedy stačí držet těchto hranic.

Potom už stačí jen vyzkoušet všechny možnosti vsázení po těchto hranicích.

function millionaire($rounds, $probability, $money, &$cache = array()) {
	if ($money >= 1e6) {
		return 1;
	} elseif (!$rounds || !$probability) {
		return 0;
	}
	$return = &$cache[$rounds][$money];
	if (!isset($return)) {
		$return = 0;
		$margin = 1e6 / (1 << ($rounds – 1));
		for ($loose = $margin * floor($money / $margin); $loose >= 0; $loose -= $margin) {
			$win = $margin * floor((2*$money – $loose) / $margin);
			$p = $probability * millionaire($rounds – 1, $probability, $win, $cache) + (1 – $probability) * millionaire($rounds – 1, $probability, $loose, $cache);
			if ($p >= $return) {
				$return = $p;
			} else {
				break;
			}
		}
	}
	return $return;
}

Pro vyřešení velkého vstupu bylo potřeba využít cache a kromě toho si uvědomit, že pokud při zvýšení sázky klesne pravděpodobnost celkové výhry, tak už není částku nutné dále zvyšovat. Tím pádem lze začít u nejnižších sázek a není potřeba prozkoumat všechny možnosti.

Řešení: Při řešení budeme postupovat zleva doprava a budeme se soustředit na to, abychom obsadili první neobsazenou zastávku. To budeme opakovat tak dlouho, dokud nedojedeme na konec trasy.

/** Nalezení počtu jízdních řádů
* @param int $n počet zastávek
* @param array $buses pozice autobusů v zastávkách
* @param array $p maximální vzdálenost, kterou autobus najednou ujede
* @return int počet různých jízdních řádů modulo 30031
*/
function bus_stops($n, $buses, $p, &$cache = array()) {
	$next = max($buses) + 1;
	if ($next > $n) {
		return (reset($buses) > $n – count($buses) ? 1 : 0);
	}
	$return = 0;
	foreach ($buses as $key => $val) {
		$buses2 = $buses;
		array_splice($buses2, $key, 1);
		$buses2[] = $next;
		$x = &$cache[serialize($buses2)];
		if (!isset($x)) {
			$x = bus_stops($n, $buses2, $p, $cache);
		}
		$return += $x;
		if ($val + $p == $next || $next == $n) {
			break;
		}
	}
	return $return % 30031;
}

Prozkoumané možnosti se ukládají do cache, kde se jako klíč používá serializované pole. To není úplně nejšikovnější, protože serializace je poměrně časově náročná, ale pro vyřešení malého vstupu to stačí. Pro velký vstup bychom museli zvolit chytřejší přístup – napadá mě, že vzhledem k nízké maximální hodnotě P (10) by se daly prozkoumat všechny P-tice a výsledek odvodit z počtu přechodů mezi nimi.