Tuenti Contest

tracker086 #61 Jun '11

Cachis el 3 lo tengo terminado, me pasa el test correctamente, pero en el submit se me queda colgado, y en la web me sale With Errors! para mi que el submit tiene mas o menos pruebas que el test xD y hasta aqui me ha funcionado mi truco xD

EDIT: Vale nada, era cuestion de esperar un poco y ya funcionaba xD. asiq a por el 4º xD

Nazari #62 Jun '11

#2 ¿Donde has leído que en tuenti se cobre tan poco? Es que me extraña un poco que vengan entonces ingenieros de otros países, o una entrevista que vi a Kartones sobre la vida en tuenti y se mostraba contento.

¿Alguien esta intentando pasarlo en PHP? porque joder se el resultado que me tiene que dar el ejercicio dos 'Tlang', pero cuando quiero hacerlo con REGEX en php no lo logro...

5 respuestas

BLZKZ #63 Jun '11

#62 en un anuncio suyo en el tablón de mi universidad

1 respuesta

NeB1 #64 Jun '11

#62 Yo lo he hecho sin regexp. Alguien ha empezado el 7??

tracker086 #65 Jun '11

#62 Yo tambien sin regexp. Con una pila y a tirar millas xD

r2d2rigo #66 Jun '11 Inocente

Sin regexp? La madre que os pario. Como pasen algun test chungo os va a reventar por todos lados.

#62, tu tambien conoces a Kartones? :p

2 respuestas

M

markov #67 Jun '11

En el cuarto, hay que leer todo ese fichero ? son 19 MB!!!

1 respuesta

tracker086 #68 Jun '11

#67 jajaja, esa es la gracia....yo aun no me he puesto con el, lo he leido..pero vamos, parece facil, solo si acaso optimizarlo para que no sea demasiado pesado leer todo el archivo o no tener que leerlo muchas veces.....pero weno a ver jaja

LOc0 #69 Jun '11

#62

Si he entendido bien el enunciado en #1...

Tlang

<?php

	while(($l=trim(fgets(STDIN))))
			echo Tlang($l)."\n";

	function Tlang($c)
	{
			return ($d=preg_replace_callback('/\^([=#@]) +?(\-?\d+)(?: +?(\-?\d+))?\$/', function($m){return isset($m[3])?eval('return '.$m[2].' '.strtr($m[1],'=#@','+*-').' '.$m[3].';'):($m[1]=='@'?-1*$m[2]:$m[2]);}, $c))==$c?$c:Tlang($d);
	}
?>

tracker086 #70 Jun '11

Actualizado #1 con el ejercicio 4...si alguien tiene acceso a los demas, si puede ponerlos y yo los paso al #1 mejor.

Hoy poco he podido hacer, así que ya mañana me quitare el 4º de encima, que no parece nada dificil, salvo optimizarlo!

1 respuesta

LOc0 #71 Jun '11

#70
¿Puede alguien subir el fichero del 4 a algún lado? Thanks.

Salu2

1 respuesta

NeB1 #72 Jun '11

#66 Yo me he creado mi propio compilador de lenguaje, no creo que lo rebienten la verdad es que me compliqué la vida un pelín xDDDD

Una noche que no le dedico tiempo y ya ván por el 19, paso de seguir T_T. Me quedo en el 7, que al final solo es implementar una búsqueda en anchura o como más te guste.

Prueba 5

Prueba 6

Prueba 7

Zeroner #73 Jun '11

#71 https://contest.tuenti.net/img/in.zip

1 respuesta

M

markov #74 Jun '11

En el challenge 4, se supone que el fichero de 19 MB lo debemos abrir para lectura en el codigo no? ¿como se va a llamar? ¿in?

lo que leemos por entrada estandar es lo de "sample input file" no ?

1 respuesta

LOc0 #75 Jun '11

#73 Gracias.

#74 El nombre del fichero ese es "in" a secas. Por la entrada estándar te van a meter una ristra de tasks separados por comas.

Estaría bien que los que paséis del premio pongáis vuestras soluciones a ver si aprendemos algún truco nuevo. (El cuarto por ejemplo me parece interesante a ver en qué lenguaje lo habéis hecho y qué "optimizaciones" habéis metido).

Salu2

Nazari #76 Jun '11

#63 Ah vale, no dudaba de ti, simplemente tenia curiosidad por saber si tuenti se había pronunciado o si había salido de boca de algún trabajador, nunca me imagine que pagaran esa miseria y menos en madrid...

#66 No, lo conozco de sus blogs kartones y de poco mas.

M

markov #77 Jun '11

Si, estaría bien que cada uno posteara sus soluciones, aunque mejor cuando acabe el concurso, no creeis ?

S2

eisenfaust #78 Jun '11

Y ni un triste hilo sobre Project Euler...

M

markov #79 Jun '11

Puff no se que hacer en el cuarto, tengo el algoritmo y funciona bien (en java) para ficheros pequeños ... pero para el fichero 'in' va lentisimo.

tracker086 #80 Jun '11

Una pregunta del 4º. Se supone q tu tienes la tarea 3 no? q tiene de dependencias la 4,5,6. Cuando llegas a dependencias tienes q calcular la duracion de 4,5,6? o solo la de 4?

Sq si me fijo en el enunciado pùyesto en 1#. Si lo calculas a mano por ejemplo 3, para que de 27, solo se podria hacer asi. Lo pongo paso a paso:

3 dura 9 segundos y tiene de dependencias: 0,1,2 vale, pillamos 0
0 dura 2: 9+2 = 11 y tiene de dependencias: 4 pillamos 4
4 dura 7: 11+7=18 y tiene de dependencias: 5 pillamos 5
5 dura 9: 18+9 = 27 y no tiene dependencias:

si os fijais en las dependencias de 3, hemos ignorado 1 y 2..

asi lo tengo, y con el enunciado me funciona bien, pero en el test me da todo WRONG.

1 respuesta

M

markov #81 Jun '11

#80 estás obviando que las tareas independientes se pueden hacer en paralelo, es decir:

(para la tarea 3)
como la tarea 3 depende de 0, 1 y 2 tienes que ver cual de las 3 tarda más (teniendo en cuenta que la tarea 0 depende de 4 y 5). Por tanto:
la tarea 1 tarda 3
la tarea 2 tarda 4
la tarea 0 tarda: 9 (de la tarea 5) + 7 (de la tarea 4) + 2 de la propia tarea 0 = 18

Luego como 0, 1 y 2 son independientes se pueden realizar en paralelo y el tiempo que se tarda es el maximo de las 3 (18).
Al final hay que añadir lo que tarda la propia tarea 3 que es 9: 18 + 9 = 27

¿Cómo has solventado el problema del fichero grande ? (qué lenguaje estás usando?)
S2

1 respuesta

tracker086 #82 Jun '11

#81Vale, gracias!! vamos que lo que tienes que hacer, es, sumar lo que dura la tarea en si, y luego mirar cual de sus dependencias la q tarda mas, y sumar esa no? vale

Pues te digo, antes lo hacia solo cogiendo la priemra dependencia, entonces por eso tardaba poco. Ahora he compilao mostrando por pantalla cada vez que suma 1 nuevo tiempo, y lleva un tiempo descomunal, lleva sumados mas de 600 tiempos y tarda como un par de segundos en calcular un nuevo tiempo xD

1 respuesta

M

markov #83 Jun '11

#82 pero has leido el fichero y lo has almacenado en algun array o algo ? porque eso me da a mi un overflow.
ahora mismo la opcion de leer linea a linea la tengo descartada. Usare algo similar al fseek de C pero para Java y asi leer solo las lineas que valgan la pena
S2

1 respuesta

Zeroner #84 Jun '11

Yo he mapeado el fichero a memoria con python http://docs.python.org/library/mmap.html

1 respuesta

tracker086 #85 Jun '11

#83 No lo he leido entero, primero pense en solucionarlo y luego optimizarlo.

Estoy por leer todo el fichero y luego operar.....lo mismo sale mas rapido xD

M

markov #86 Jun '11

#84 y eso va rápido ?, además necesitarías 19 MB de memoria no ? no se si habrá algún límite en el concurso...

85 ya te digo que con 19 MB si tratas de leer el fichero y almacenarlo en alguna estructura te tirará un error de overflow

S2

1 respuesta

0buS #87 Jun '11

El 4 parece un problema de grafos ponderados xD

1 respuesta

tracker086 #88 Jun '11

#86 Nada idea absurda la mia xD. He intentado meterlo primero en una lista...y lleva como 4 o5 minutos y aun no ha terminao xD

M

markov #89 Jun '11

#87 si, la manera (creo) más fácil de hacerlo es con grafos (o árboles)
creo que el problema se enfoca más en la eficiencia al manejar ficheros grandes.

S2

LOc0 #90 Jun '11

¿Alguien ha hecho el cuarto en PHP xD? Vaya trameada. Lo dejo ya. Algoritmo "recursivo-de-palo" y cargando el puto fichero en un array de cadenas tipo

[0] -> "duracion,dep1,dep2,...depn"
[1] -> "duracion,dep1,dep2,...,depn"
.
.
[n]

El array en memoria he comprobado con serialize() grosso modo que ocupa unos 25MB El problema de memoria de verdad me da a mi que son las 71734189789741123234234 llamadas recursivas del algoritmo de palo. Si tuviera tiempo/ganas lo probaba en C con mmap pero va a ser que no.

task_duration

<?php
	
define('FICHERO', 'tasks.in');
ini_set("memory_limit","2048M"); //memory_get_peak_usage() devuelve 700MB con el fichero "in"

function dura($t)
{
	global $tasks;
	
	$d=explode(',', $tasks[$t]);
	$dura=$d[0];
	
	if(count($d)>1)
	{	
		$deps=array_slice($d, 1);

		if(count($deps)>1)
		{
			$max=0;
			
			foreach($deps as $d)
				if(($du=dura($d))>$max)
					$max=$du;
		
			$dura+=$max;
		}
		else
			$dura+=dura($deps[0]);
	}

	return $dura;
}

function gen_tasks($fichero)
{
	$tasks=array();
	
	for($i=3, $fin=$fichero[1]+3; $i<$fin; $i++)
	{
		$t=explode(',', $fichero[$i]);
		$tasks[]=$t[1];
	}
	
	for($i=$fin+1, $tot=count($fichero); $i<$tot; $i++)
	{
		$deps=explode(',', $fichero[$i]);
		$tasks[$deps[0]].=','.implode(',',array_slice($deps,1));
	}
	
	return $tasks;
}

$tasks=gen_tasks(file(FICHERO, FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES));

while(($linea=trim(fgets(STDIN))))
	foreach(preg_split('/ *, */', $linea) as $t)
		echo "$t ".dura($t)."\n";
?>

$time echo "3" | php tasks_mem.php
3 2046078

real 0m13.296s
user 0m12.503s
sys 0m0.790s

Core2 Duo E8400 3.0 Ghz (un sólo thread).

Salu2

PD: leer directamente de disco cada vez = MUERTE.

1 respuesta

85 ya te digo que con 19 MB si tratas de leer el fichero y almacenarlo en alguna estructura te tirará un error de overflow

Usuarios habituales

Tags