Google Code Jam 2008 - kvalifikace

Řešení: Bohužel nejde použít hladový algoritmus, protože dlouhá posloupnost ukrojená na začátku by nám mohla zkomplikovat situaci v budoucnu. Proto raději vyzkoušíme všechny možnosti:

function switches($engines, $queries, &$switches_queries) {
	$min_switches = null;
	foreach ($engines as $engine) {
		$pos = array_search($engine, $queries);
		if ($pos === false) {
			return 0;
		} elseif ($pos) {
			$switches = &$switches_queries[count($queries) - $pos][$engine];
			if (!isset($switches)) {
				$switches = switches($engines, array_slice($queries, $pos), $switches_queries);
			}
			if (!isset($min_switches) || $min_switches > $switches) {
				$min_switches = $switches + 1;
			}
		}
	}
	return $min_switches;
}

V  kódu je použitá funkce array_search, která mezi dotazy hledá název aktuálního vyhledávače. Pokud ho nenajde, tak jsme hotovi, protože pro zbylé dotazy už vyhledávač nemusíme měnit. Pokud ho naopak najdeme hned na začátku, tak už nic nezkoušíme, protože bychom se dostali do nekonečné smyčky. V jiných případech vyzkoušíme pro zbylé dotazy všechny vyhledávače.

Stejně jako u pouštění vajíček se používá dynamické programování, abychom nemuseli kratší posloupnosti počítat pořád dokola. Keš ale nedržíme ve statické proměnné, protože po sobě následující úlohy mohou používat různé vyhledávače, pro které se počet změn samozřejmě může lišit. Místo toho se používá parametr předávaný referencí, kterému bohužel v PHP nejde určit výchozí hodnota, takže je před zavoláním funkce potřeba tuto proměnnou nainicializovat na prázdné pole (mohla by to dělat obálková funkce).

Řešení je přímočaré:

/** Výpočet počtu vlaků potřebných v jednotlivých stanicích
* @param array $departures pole s prvky $departure_time => array(array("from" => $station, "arrival" => $arrival_time), ...), časy zadané v minutách
* @return array dvouprvkové pole s potřebnými počty vlaků v jednotlivých stanicích
*/
function timetable($departures) {
	$needed = array(0, 0);
	$going = array();
	$available = array(0, 0);
	ksort($departures);
	foreach ($departures as $departure => $trains) {
		foreach ($going as $key => $train) {
			if ($train["arrival"] <= $departure) {
				$available[1 - $train["from"]]++;
				unset($going[$key]);
			}
		}
		foreach ($trains as $train) {
			if (!$available[$train["from"]]) {
				$needed[$train["from"]]++;
			} else {
				$available[$train["from"]]--;
			}
			$going[] = $train;
		}
	}
	return $needed;
}

Projdeme seznam všech odjezdů a pro každý nejprve zjistíme, jestli už se nevrátil nějaký vlak. Potom pro všechny vlaky odjíždějící v daný čas zjistíme, jestli v zastávce máme k dispozici nějakou soupravu ($available) a pokud ne, tak si poznamenáme, že budeme potřebovat o jednu navíc ($needed). Aktuální vlak si přidáme do jedoucích vlaků ($going).

K řešení úlohy lze přistoupit několika způsoby. Jednak můžeme pravděpodobnost přesně vypočítat jako poměr obsahu volné plochy a plochy celé rakety (se zohledněním mouchy), to je ale poměrně pracné. Druhou možností je raketu bombardovat náhodnými mouchami a vždycky jen zjistit, jestli raketu trefila:

define("TRIES", 1e6);
define("MT_RAND_MAX", mt_getrandmax());

function swatter_string($x, $f, $r, $g) {
	$center = round($x / ($g+2*$r)) * ($g+2*$r);
	return ($x > $center - $r - $f && $x < $center + $r + $f);
}

function swatter_rand($f, $R, $t, $r, $g) {
	$hits = 0;
	$tries = 0;
	for ($i=0; $i < TRIES; $i++) {
		$x = $R * mt_rand() / MT_RAND_MAX;
		$y = $R * mt_rand() / MT_RAND_MAX;
		$distance = $x*$x + $y*$y;
		if ($distance < $R*$R) {
			$tries++;
			if ($distance > ($R-$t-$f) * ($R-$t-$f) || swatter_string($x, $f, $r, $g) || swatter_string($y, $f, $r, $g)) {
				$hits++;
			}
		}
	}
	return $hits / $tries;
}

Postupně generujeme dvojice náhodných čísel pro souřadnice X a Y. Pokud splňují podmínku, že jsou uvnitř rakety, tak zjistíme, jestli strefí rám rakety nebo svislá či vodorovná lanka výpletu. Nakonec jen vrátíme poměr tref a počtu úspěšných pokusů. Problém tohoto přístupu spočívá v tom, že úplné zadání toleruje absolutní nebo relativní chybu jen 10^-6, pro jejíž dosažení bychom museli provést tolik pokusů, že by skript běžel neúměrně dlouho.

Proto vyzkoušíme ještě jedno řešení, nazveme ho numerické. Budeme postupovat po ose Y a v každém bodě zjistíme šířku rakety a šířku překážek na raketě v daném bodě.

function swatter_numeric($f, $R, $t, $r, $g) {
	if ($g <= 2*$f) {
		return 1;
	}
	$hits = 0;
	$tries = 0;
	$R_in = $R-$t-$f;
	$y_center = 0;
	for ($y=$R/TRIES; $y < $R; $y += $R/TRIES) {
		if ($y - $y_center >= $g/2+$r) {
			$y_center += $g+2*$r;
		}
		$tries += sqrt($R*$R - $y*$y);
		if ($y < $R_in && ($y < $y_center - $r - $f || $y > $y_center + $r + $f)) {
			$x = sqrt($R_in*$R_in - $y*$y);
			$squares = (int) (($x+$f+$r) / ($g+2*$r));
			$hits += $squares * ($g-2*$f);
			$hits += max(0, $x - $squares * ($g+2*$r) - $r - $f);
		}
	}
	return 1 - $hits / $tries;
}