PHPizando

Hola, ya ha terminado el primer round de codejam, segun lo que lei los mejores 840 pogramadores pasaran al segundo round.

Si entran a http://code.google.com/codejam/contest podran ver los problemas y las resoluciones propuestas por los programadores.
Como particularidad al problema de los buscadores, que comente en el post anterior me gustaria mostrarle algunos datos;
De los top 20, el que menos tardo en resolver el problema marco unos 10 minutos, mientras que al que mas tardo le tomo unas 2 horas la resolucion dle problema. El promedio de resolucion del problema de los top 20 fue de 36 minutos.
De esos 20 programadores catorce usaron C++, cuatro usaron JAVA, uno uso Haskell y uno uso LISP.

A continuacion voy a copiar la solucion propuesta por el que califico primero, su apodo es rem.

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <ctime>
using namespace std;

typedef long long int64;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<double> vd;

#define _CRT_SECURE_NO_WARNINGS
#define For(i,a,b) for (int i(a),_b(b); i <= _b; ++i)
#define Ford(i,a,b) for (int i(a),_b(b); i >= _b; --i)
#define Rep(i,n) for (int i(0),_n(n); i < _n; ++i)
#define Repd(i,n) for (int i((n)-1); i >= 0; --i)
#define Fill(a,c) memset(&a, c, sizeof(a))
#define MP(x, y) make_pair((x), (y))
#define All(v) (v).begin(), (v).end()

template<typename T, typename S> T cast(S s) {
	stringstream ss;
	ss << s;
	T res;
	ss >> res;
	return res;
}

template<typename T> inline T sqr(T a) { return a*a; }
template<typename T> inline int Size(const T& c) { return (int)c.size(); }
template<typename T> inline void checkMin(T& a, T b) { if (b < a) a = b; }
template<typename T> inline void checkMax(T& a, T b) { if (b > a) a = b; }

char buf[1024*1024];

int main() {
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);

	gets(buf);
	For(test, 1, atoi(buf)) {
		int s, q;
		map<string,int> num;
		gets(buf);
		s = atoi(buf);
		Rep(i, s) {
			gets(buf);
			num[buf] = i;
		}
		gets(buf);
		q = atoi(buf);
		vi dp(s, 0);
		Rep(i, q) {
			gets(buf);
			assert(num.count(buf) > 0);
			int id = num[buf];
			Rep(j, s)
				if (j != id)
					checkMin(dp[j], dp[id]+1);
			dp[id] = 1000000;
		}
		printf("Case #%d: %d\n", test, *min_element(All(dp)));
	}

	exit(0);
}

Saludos!

No solo mi primera presentacion en el google codejam, si no tambien mi primer post. Lamentablemente no pude clasificar por que falle. Cometi el error de intentar resolver los problemas con ansi c, lo cierto es que no soy muy bueno con el y perdi mucho tiempo, por lo que opte por usar PHP.

A continuacion voy a traducir el problema, y voy a mostrarles la solucion que propuse, el algoritmo funciona correctamente y resuelve el problema.

Hay una leyenda urbana que dice que si buscas Google en Google el universo hara implosion. Tenemos un secreto para contarte… es cierto! por favor no lo intentes o le cuentes a alguien. Bien, solo estamos bromeando.

Esto es cierto en un universo muy muy lejano. En ese universo, si buscas el nombre del buscador en que te encuentras ese universo se destruira.

Para combatir con esto, tenemos una interesante solucion. Todas las busquedas esran puestas juntas. Seran pasadas a un sistema central que decide que decide que busqueda va a cada buscador. El sistema central manda una serie de busquedas a un buscador, y puede cambiar a otro buscador en cualquier momento. Las busquedas son procesadas en el orden que se van recibiendo. El sistema central nunca enviara una busqueda que sea igual al nombre del buscador en el que esta, en ese caso debera cambiar de buscador. Para reducir costos, el numero de cambios de buscador a buscador debe ser minimo.

Como entrada para resolver este problema contaremos con un archivo, que tendra el siguiente formato;
En la primer linea dira la cantidad de casos a resolver, luego nos describiran los N casos,de la siguiente forma;
numero de buscadores
buscadores1
buscadores2
buscadoresN
numero de busquedas
busqueda1
busqueda2
busquedaN

Ejemplo;
2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol

Y la salida de este ejemplo seria;
Case #1: 1
Case #2: 0

La solucion que yo propuse es la siguiente;

Casos::loadData("datos.in");

$i=1;
while(($caso=array_shift(Casos::$Casos))){
	echo 'Case #'.$i.': '.$caso->calcular()."\r\n";
	$i++;
}

class Caso{
	public $engines=array();
	public $querys=array();

	public function calcular(){

		$aux=$this->engines;
		$total=0;

		while (($qry=array_shift($this->querys))){

			$aux=$this->quitar($qry,$aux);
			if(count($aux)==0){
				$aux=$this->quitar($qry,$this->engines);
				$total++;
			}
		}

		return $total;
	}

	public function quitar($qry,$unaArr){

		$aux=array();

		while(($aEng=array_shift($unaArr))){
			if($qry!=$aEng){
				array_push($aux,$aEng);
			}
		}

		return $aux;
	}

}

abstract class Casos{
	public static $Casos=array();

	public function loadData($file){
		$archivo = file($file);
		$i=0;
		for($m=0;$m<$archivo[0];$m++){
			$caso=new Caso();
			$i++;
			$totalEng=$archivo[$i];
			for($j=0;$jengines,$archivo[$i]);
			}
			$i++;
			$totalQry=$archivo[$i];
			for($j=0;$jquerys,$archivo[$i]);
			}
			array_push(self::$Casos,$caso);
		}
	}
}

Para el que quiera el problema original en ingles puede hacerlo en http://code.google.com/codejam/