Respuestas pendientes

Un problema de sumas

El problema pedía encontrar un algoritmo subcuadrático para determinar si dos elementos en un vector de enteros con una suma dada. Si confiamos en el caracter O(1) de las tablas hash podemos obtener un algoritmo lineal aun más breve que el cuadrático mostrado anteriormente (y sin recurrir al code golfing 😀 ):

def sum1_n(s, v):
    d = {}
    for x in v:
        if s-x in d:
            return True
        d[x] = True
    return False

Si no confiamos en eso, puede hacerse en tiempo O(n log n) ordenando la secuencia y reemplazando las búsquedas en la tabla por búsquedas binarias (como sugirió Fer) o directamente escanear el vector ordenado con dos punteros desde los extremos (no es difícil determinar las reglas de avance).

Ahora pueden probar su suerte buscando algoritmos subcuadráticos para resolver 3SUM; es solo un poquito más difícil… 😛

Circuitos hamiltonianos

Este otro problema pedía determinar si era posible encontrar circuitos hamiltonianos en grillas cuadradas con una cantidad impar de vértices. Para ver que esto no es posible, dividamos a los vértices de la grilla en dos clases de acuerdo al siguiente esquema:

ham_cycle_parity

División de los nodos del grafo en dos clases, indicadas por el color utilizado para representarlos.

Si recorremos un circuito en el grafo no es difícil convencernos de que en cada paso cambiaremos de clase de vértice. Ahora, en un circuito hamiltoniano la cantidad de pasos será impar, dándonos para el último vértice una clase distinta que para el primero. Como esto es incompatible con el hecho de que se trata de un circuito, es imposible encontrar un circuito hamiltoniano en grillas con una cantidad impar de vértices (no solo cuadradas!).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s