Facebook Hacker Cup – Solución Double Squares

Muchos lo sabréis, este fin de semana ha sido la ronda clasificatoria de la Facebook Hacker Cup.

Han habido algunos problemillas pero al final las cosas se podían hacer por más quejas que haya tenido la gente.
En mi caso, hice bien Double Squares y Studious Student pero me lié un poco con el Peg Game. Aunque los algoritmos son bastante mejorables, me gustaría compartir mi código con vosotros (hecho en PHP en mi caso) y por supuesto espero vuestras colaboraciones.

Double Squares

Nos pedían, dado un listado de números, que diéramos cuántas combinaciones de x²+y² daban ese número. Por ejemplo, 10 se puede hacer como 3²+1², 25 se puede hacer como 0²+5² y también como 3²+4², etc… además nos decían que nos pasarían un archivo input tipo esto:

5
10
25
3
0
1
8

donde la primera fila es cuántos números te vienen luego y luego ya tienes que ir calculando cuantas combinaciones x,y son válidas.

Para este caso, la salida esperada es:

1 (3²+1²)
2 (5²+0² y 4²+3²)
0 (No se puede hacer 3 como suma de cuadrados)
1 (0²+1²)
1 (2²+2²)

Parecía fácil aunque el problema principal era que en el fichero de entrada salían números grandes como esto:

20
602519112
3
1475149141
5
1000582589
2082925
326864818
326122507
5525
27625
1328649093
1991891221
1538292481
1941554117
10
77068225
138125
801125
29641625
71825

Y claro… ya con el primero 602519112 como no tengas bien hecho el algoritmo, ya puedes tener un quad core jejejeje

Os dejo aquí mi solución (que facebook ha dado como correcta)

#!/usr/bin/php
<?php
if($_SERVER['argc'] != 2) die('Filename must be provided' . PHP_EOL);
 
$sFileName = $_SERVER['argv'][1];
 
$fd = fopen($sFileName, 'r');
$lines = (int)trim(fgets($fd));
for($l=0;$l<$lines;$l++) {
    $total = 0;
    $value = (int)trim(fgets($fd));    
    // Pensadlo un poco y veréis que no hace falta iterar más
    for($i=0;$i*$i <= $value / 2;$i++) {
       $test = sqrt($value-$i*$i);
       // Si la raíz cuadrada es un número entero, existe un b² = numero - i²
       if((int)$test == $test)  $total++;
    }
    echo $total . PHP_EOL;
 
}
fclose($fd);
?>

Esto va bastante decente de velocidad, aunque se puede mejorar por ejemplo en el bucle no realizar siempre la división por dos.
Veréis que también usaba (int) ya que creía que al forzar el type casting algo mejoraría, aunque en realidad no es así 🙂

La salida esperada por Facebook es

4
0
1
1
2
18
0
0
6
8
4
1
2
1
1
36
10
16
32
9

Mañana os dejo la solución del Studious Student, hecha con usort + closures!

You may also like...

1 Response

  1. brujo says:

    K passada!!! 😯

Leave a Reply to brujo Cancel reply

Your email address will not be published. Required fields are marked *