Saltar a contenido

Soluciones · Refuerzo PUJ 7 de noviembre

UVa 11516, UVa 12032, UVa 336, UVa 11686 y los tres problemas de la tarea de la sesión del 7 de noviembre, cada uno con la idea, lo que cuesta y el código en Python y en C++. Los archivos están también en la carpeta codigo/.

Antenas en una calle. UVa 11516, WiFi

Idea

Probar dónde poner las antenas obliga a manejar posiciones reales. La pregunta que sí se contesta de una pasada es ¿alcanzan \(n\) antenas si cada una cubre un tramo de \(a\) metros?: con las casas ordenadas, se pone un tramo desde la primera casa sin cubrir, que cubre hasta \(\text{casa} + a\), y se cuentan los tramos. Es monótona, porque con tramos más largos cada antena cubre más. Se busca sobre el ancho \(a\), el doble de la distancia: las casas están en posiciones enteras, así que el mejor ancho es entero y la respuesta, \(a/2\), termina en .0 o en .5. Los límites son \(0\) y la distancia entre la primera y la última casa. Las casas llegan sin ordenar.

Complejidad

\(\Theta(m \log m)\) por caso: ordenar cuesta \(m \log m\) y la bisección da unas veinte vueltas de \(\Theta(m)\), porque el ancho no pasa de un millón.

Python

import sys


def antenasNecesarias(casas, ancho):
    # Cuántas antenas hacen falta si cada una cubre un tramo de 'ancho' metros.
    # casas viene ordenada; cada antena se pone para la primera casa sin cubrir.
    antenas = 1
    cubreHasta = casas[0] + ancho
    for c in casas:
        if c > cubreHasta:
            antenas = antenas + 1
            cubreHasta = c + ancho
    return antenas


def menorAncho(casas, n):
    # El menor ancho entero con el que alcanzan n antenas.
    lo = 0
    hi = casas[-1] - casas[0]
    while lo < hi:
        medio = (lo + hi) // 2
        if antenasNecesarias(casas, medio) <= n:
            hi = medio
        else:
            lo = medio + 1
    return lo


def main():
    datos = sys.stdin.read().split()
    pos = 0
    casos = int(datos[pos])
    pos = pos + 1
    salida = []
    caso = 0
    while caso < casos:
        n = int(datos[pos])
        m = int(datos[pos + 1])
        pos = pos + 2
        casas = []
        i = 0
        while i < m:
            casas.append(int(datos[pos]))
            pos = pos + 1
            i = i + 1
        casas.sort()
        ancho = menorAncho(casas, n)
        # la distancia máxima es la mitad del ancho: termina en .0 o en .5
        if ancho % 2 == 0:
            salida.append(str(ancho // 2) + '.0')
        else:
            salida.append(str(ancho // 2) + '.5')
        caso = caso + 1
    print('\n'.join(salida))


main()

C++

#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

int antenasNecesarias(const vector<int> &casas, int ancho) {
  // Cuántas antenas hacen falta si cada una cubre un tramo de 'ancho' metros.
  // casas viene ordenado; cada antena se pone para la primera casa sin cubrir.
  int antenas = 1;
  int cubreHasta = casas[0] + ancho;
  for (size_t i = 1; i < casas.size(); i++) {
    if (casas[i] > cubreHasta) {
      antenas = antenas + 1;
      cubreHasta = casas[i] + ancho;
    }
  }
  return antenas;
}

int menorAncho(const vector<int> &casas, int n) {
  // El menor ancho entero con el que alcanzan n antenas.
  int lo = 0;
  int hi = casas[casas.size() - 1] - casas[0];
  while (lo < hi) {
    int medio = lo + (hi - lo) / 2;
    if (antenasNecesarias(casas, medio) <= n) {
      hi = medio;
    } else {
      lo = medio + 1;
    }
  }
  return lo;
}

int main() {
  int casos;
  scanf("%d", &casos);
  for (int caso = 0; caso < casos; caso++) {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> casas(m);
    for (int i = 0; i < m; i++) {
      scanf("%d", &casas[i]);
    }
    sort(casas.begin(), casas.end());
    int ancho = menorAncho(casas, n);
    // la distancia máxima es la mitad del ancho: termina en .0 o en .5
    printf("%.1f\n", ancho / 2.0);
  }
  return 0;
}

Hora 1. UVa 12032, The Monkey and the Oiled Bamboo

Idea

Encontrar el mínimo directamente obliga a razonar sobre todos los saltos a la vez. La pregunta que sí se contesta de una pasada es ¿se llega arriba empezando con fuerza \(k\)?: se simula la subida llevando la fuerza actual, cada salto se compara contra ella y el que la iguala la gasta en uno. Es monótona, porque con \(k+1\) ningún salto que cabía deja de caber. Los límites son el salto más grande, que hay que dar, y ese mismo más \(n\), porque cada salto baja la fuerza a lo sumo en uno.

Complejidad

\(\Theta(n \log(\max s_i + n))\) por caso: cada vuelta de la bisección recorre los saltos una vez.

Python

import sys


def alcanza(saltos, k):
    # Con fuerza inicial k, ¿se llega al último peldaño?
    fuerza = k
    puede = True
    for s in saltos:
        if s > fuerza:
            puede = False
        elif s == fuerza:
            fuerza = fuerza - 1
    return puede


def minimaFuerza(saltos):
    # El menor k que cumple alcanza(saltos, k).
    lo = max(saltos)
    hi = lo + len(saltos)
    while lo < hi:
        medio = (lo + hi) // 2
        if alcanza(saltos, medio):
            hi = medio
        else:
            lo = medio + 1
    return lo


def main():
    datos = sys.stdin.read().split()
    pos = 0
    casos = int(datos[pos])
    pos = pos + 1
    caso = 1
    salida = []
    while caso <= casos:
        n = int(datos[pos])
        pos = pos + 1
        alturas = []
        i = 0
        while i < n:
            alturas.append(int(datos[pos]))
            pos = pos + 1
            i = i + 1
        saltos = [alturas[0]]
        i = 1
        while i < n:
            saltos.append(alturas[i] - alturas[i - 1])
            i = i + 1
        salida.append('Case ' + str(caso) + ': ' + str(minimaFuerza(saltos)))
        caso = caso + 1
    print('\n'.join(salida))


main()

C++

#include <cstdio>
#include <vector>

using namespace std;

bool alcanza(const vector<int> &saltos, int k) {
  // Con fuerza inicial k, se llega al ultimo peldano?
  int fuerza = k;
  bool puede = true;
  for (size_t i = 0; i < saltos.size(); i++) {
    if (saltos[i] > fuerza) {
      puede = false;
    } else if (saltos[i] == fuerza) {
      fuerza = fuerza - 1;
    }
  }
  return puede;
}

int minimaFuerza(const vector<int> &saltos) {
  // El menor k que cumple alcanza(saltos, k).
  int lo = 0;
  for (size_t i = 0; i < saltos.size(); i++) {
    if (saltos[i] > lo) {
      lo = saltos[i];
    }
  }
  int hi = lo + (int)saltos.size();
  while (lo < hi) {
    int medio = lo + (hi - lo) / 2;
    if (alcanza(saltos, medio)) {
      hi = medio;
    } else {
      lo = medio + 1;
    }
  }
  return lo;
}

int main() {
  int casos;
  scanf("%d", &casos);
  for (int caso = 1; caso <= casos; caso++) {
    int n;
    scanf("%d", &n);
    vector<int> alturas(n);
    for (int i = 0; i < n; i++) {
      scanf("%d", &alturas[i]);
    }
    vector<int> saltos;
    saltos.push_back(alturas[0]);
    for (int i = 1; i < n; i++) {
      saltos.push_back(alturas[i] - alturas[i - 1]);
    }
    printf("Case %d: %d\n", caso, minimaFuerza(saltos));
  }
  return 0;
}

Hora 2. UVa 336, A Node Too Far

Idea

Se construye la lista de adyacencia y se corre un recorrido en amplitud por consulta, con una cola y un arreglo de distancias que arranca en \(-1\). El recorrido visita los nodos por distancia creciente, así que la condición dist[u] < ttl deja en la cola los nodos a distancia TTL sin expandirlos. La respuesta es el total de nodos menos los alcanzados, y el nodo de partida cuenta como alcanzado, incluso con TTL 0. indiceDe traduce el número del nodo a un índice entre 0 y \(V - 1\), y main pregunta si el nodo está antes de llamar a bfs: un nodo ausente no alcanza a ninguno.

Complejidad

\(O(V + E)\) por consulta para el recorrido, con \(V \le 30\) y \(E \le 435\). Cada búsqueda en el diccionario cuesta \(O(\log V)\) en C++ y \(O(1)\) en promedio en Python.

Python

Archivo: a-node-too-far.py

import sys
from collections import deque


def indiceDe(indice, adj, nodo):
    # El índice del nodo; si es la primera vez que aparece, se le asigna uno.
    if nodo not in indice:
        indice[nodo] = len(indice)
        adj.append([])
    return indice[nodo]


def bfs(adj, inicio, ttl):
    # Cuántos nodos quedan a distancia menor o igual a ttl desde inicio.
    dist = [-1] * len(adj)
    cola = deque()
    dist[inicio] = 0
    cola.append(inicio)
    alcanzados = 1
    while len(cola) > 0:
        u = cola.popleft()
        if dist[u] < ttl:
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    alcanzados = alcanzados + 1
                    cola.append(v)
    return alcanzados


def main():
    datos = sys.stdin.read().split()
    pos = 0
    caso = 0
    salida = []
    conexiones = int(datos[pos])
    pos = pos + 1
    while conexiones != 0:
        indice = {}
        adj = []
        i = 0
        while i < conexiones:
            ia = indiceDe(indice, adj, int(datos[pos]))
            ib = indiceDe(indice, adj, int(datos[pos + 1]))
            pos = pos + 2
            adj[ia].append(ib)
            adj[ib].append(ia)
            i = i + 1
        nodo = int(datos[pos])
        ttl = int(datos[pos + 1])
        pos = pos + 2
        while nodo != 0 or ttl != 0:
            caso = caso + 1
            alcanzados = 0
            if nodo in indice:
                alcanzados = bfs(adj, indice[nodo], ttl)
            salida.append('Case ' + str(caso) + ': ' + str(len(adj) - alcanzados)
                          + ' nodes not reachable from node ' + str(nodo)
                          + ' with TTL = ' + str(ttl) + '.')
            nodo = int(datos[pos])
            ttl = int(datos[pos + 1])
            pos = pos + 2
        conexiones = int(datos[pos])
        pos = pos + 1
    print('\n'.join(salida))


main()

C++

Archivo: a-node-too-far.cpp

#include <cstdio>
#include <map>
#include <queue>
#include <vector>

using namespace std;

int indiceDe(map<int, int> &indice, vector<vector<int> > &adj, int nodo) {
  // El indice del nodo; si es la primera vez que aparece, se le asigna uno.
  if (indice.count(nodo) == 0) {
    int nuevo = (int)indice.size();
    indice[nodo] = nuevo;
    adj.push_back(vector<int>());
  }
  return indice[nodo];
}

int bfs(const vector<vector<int> > &adj, int inicio, int ttl) {
  // Cuantos nodos quedan a distancia menor o igual a ttl desde inicio.
  vector<int> dist(adj.size(), -1);
  queue<int> cola;
  dist[inicio] = 0;
  cola.push(inicio);
  int alcanzados = 1;
  while (!cola.empty()) {
    int u = cola.front();
    cola.pop();
    if (dist[u] < ttl) {
      for (size_t i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (dist[v] == -1) {
          dist[v] = dist[u] + 1;
          alcanzados = alcanzados + 1;
          cola.push(v);
        }
      }
    }
  }
  return alcanzados;
}

int main() {
  int conexiones;
  int caso = 0;
  while (scanf("%d", &conexiones) == 1 && conexiones != 0) {
    map<int, int> indice;
    vector<vector<int> > adj;
    for (int i = 0; i < conexiones; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      int ia = indiceDe(indice, adj, a);
      int ib = indiceDe(indice, adj, b);
      adj[ia].push_back(ib);
      adj[ib].push_back(ia);
    }
    int nodo, ttl;
    while (scanf("%d %d", &nodo, &ttl) == 2 && (nodo != 0 || ttl != 0)) {
      caso = caso + 1;
      int alcanzados = 0;
      if (indice.count(nodo) > 0) {
        alcanzados = bfs(adj, indice[nodo], ttl);
      }
      printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",
             caso, (int)adj.size() - alcanzados, nodo, ttl);
    }
  }
  return 0;
}

Hora 3. UVa 11686, Pick up sticks

Idea

Cada nodo pasa por tres estados: sin visitar, en el camino actual y terminado. Una arista hacia un nodo en camino cierra un ciclo, porque desde ese nodo ya se había bajado hasta el actual. Una arista hacia un nodo terminado no cierra nada por sí sola: ese nodo ya revisó todo lo que sale de él, y si pudiera volver al actual, la arista de regreso ya se habría detectado. orden recibe cada nodo al terminar, y main lo imprime del último al primero. El recorrido arranca desde todo nodo sin visitar, porque el grafo puede tener varias componentes.

Complejidad

\(\Theta(n + m)\) por caso en las tres soluciones. La memoria adicional del recorrido es \(\Theta(n)\), en la pila de llamadas o en el vector. Medida con ulimit -s de 8192 KB, la recursiva de C++ pasó con 86 851 nodos de profundidad y reventó con 87 826, así que al juez se envía la versión con pila. La de Python tampoco se envía: en Python 3.8, con el mismo límite de recursión, reventó con 10 968.

Python

Archivo: pick-up-sticks.py

import sys

SIN_VISITAR = 0
EN_CAMINO = 1
TERMINADO = 2


def dfs(adj, color, orden, u):
    # Recorre lo que sale de u y devuelve si encontró un ciclo.
    hayCiclo = False
    color[u] = EN_CAMINO
    for v in adj[u]:
        if color[v] == EN_CAMINO:
            hayCiclo = True
        elif color[v] == SIN_VISITAR:
            if dfs(adj, color, orden, v):
                hayCiclo = True
    color[u] = TERMINADO
    orden.append(u)
    return hayCiclo


def main():
    sys.setrecursionlimit(1100000)
    datos = sys.stdin.buffer.read().split()
    pos = 0
    salida = []
    n = int(datos[pos])
    m = int(datos[pos + 1])
    pos = pos + 2
    while n != 0 or m != 0:
        adj = [[] for u in range(n + 1)]
        i = 0
        while i < m:
            adj[int(datos[pos])].append(int(datos[pos + 1]))
            pos = pos + 2
            i = i + 1
        color = [SIN_VISITAR] * (n + 1)
        orden = []
        hayCiclo = False
        u = 1
        while u <= n:
            if color[u] == SIN_VISITAR:
                if dfs(adj, color, orden, u):
                    hayCiclo = True
            u = u + 1
        if hayCiclo:
            salida.append('IMPOSSIBLE')
        else:
            orden.reverse()
            salida.append('\n'.join([str(u) for u in orden]))
        n = int(datos[pos])
        m = int(datos[pos + 1])
        pos = pos + 2
    print('\n'.join(salida))


main()

C++, recursiva

Archivo: pick-up-sticks.cpp

#include <cstdio>
#include <vector>

using namespace std;

const int SIN_VISITAR = 0;
const int EN_CAMINO = 1;
const int TERMINADO = 2;

void dfs(const vector<vector<int> > &adj, vector<int> &color,
         vector<int> &orden, bool &hayCiclo, int u) {
  // Recorre lo que sale de u; una arista a un nodo en camino cierra un ciclo.
  color[u] = EN_CAMINO;
  for (size_t i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i];
    if (color[v] == EN_CAMINO) {
      hayCiclo = true;
    } else if (color[v] == SIN_VISITAR) {
      dfs(adj, color, orden, hayCiclo, v);
    }
  }
  color[u] = TERMINADO;
  orden.push_back(u);
}

int main() {
  int n, m;
  while (scanf("%d %d", &n, &m) == 2 && (n != 0 || m != 0)) {
    vector<vector<int> > adj(n + 1);
    for (int i = 0; i < m; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      adj[a].push_back(b);
    }
    vector<int> color(n + 1, SIN_VISITAR);
    vector<int> orden;
    bool hayCiclo = false;
    for (int u = 1; u <= n; u++) {
      if (color[u] == SIN_VISITAR) {
        dfs(adj, color, orden, hayCiclo, u);
      }
    }
    if (hayCiclo) {
      printf("IMPOSSIBLE\n");
    } else {
      for (int i = n - 1; i >= 0; i--) {
        printf("%d\n", orden[i]);
      }
    }
  }
  return 0;
}

C++, con pila

siguiente[u] recuerda cuál arista de u toca revisar, el dato que en la recursiva guarda la variable i de cada llamada. Imprime los mismos órdenes que la recursiva.

Archivo: pick-up-sticks-pila.cpp

#include <cstdio>
#include <vector>

using namespace std;

const int SIN_VISITAR = 0;
const int EN_CAMINO = 1;
const int TERMINADO = 2;

void dfs(const vector<vector<int> > &adj, vector<int> &color,
         vector<size_t> &siguiente, vector<int> &orden, bool &hayCiclo,
         int inicio) {
  // La pila guarda el camino actual; siguiente[u] es la arista de u que
  // toca revisar, lo que en la recursiva guarda la variable i de cada llamada.
  vector<int> pila;
  color[inicio] = EN_CAMINO;
  pila.push_back(inicio);
  while (!pila.empty()) {
    int u = pila.back();
    if (siguiente[u] < adj[u].size()) {
      int v = adj[u][siguiente[u]];
      siguiente[u] = siguiente[u] + 1;
      if (color[v] == EN_CAMINO) {
        hayCiclo = true;
      } else if (color[v] == SIN_VISITAR) {
        color[v] = EN_CAMINO;
        pila.push_back(v);
      }
    } else {
      color[u] = TERMINADO;
      orden.push_back(u);
      pila.pop_back();
    }
  }
}

int main() {
  int n, m;
  while (scanf("%d %d", &n, &m) == 2 && (n != 0 || m != 0)) {
    vector<vector<int> > adj(n + 1);
    for (int i = 0; i < m; i++) {
      int a, b;
      scanf("%d %d", &a, &b);
      adj[a].push_back(b);
    }
    vector<int> color(n + 1, SIN_VISITAR);
    vector<size_t> siguiente(n + 1, 0);
    vector<int> orden;
    bool hayCiclo = false;
    for (int u = 1; u <= n; u++) {
      if (color[u] == SIN_VISITAR) {
        dfs(adj, color, siguiente, orden, hayCiclo, u);
      }
    }
    if (hayCiclo) {
      printf("IMPOSSIBLE\n");
    } else {
      for (int i = n - 1; i >= 0; i--) {
        printf("%d\n", orden[i]);
      }
    }
  }
  return 0;
}

Tarea base. UVa 10935, Throwing cards away I

Idea

Se llena la cola con las cartas de 1 a \(n\). En cada ronda se saca el frente, se imprime y se pasa el nuevo frente al final. primera decide el separador: un espacio antes de la primera carta y , antes de las otras, y así \(n = 1\) deja Discarded cards: sin espacio final. En Python, jugar(n) arma la línea como texto y la devuelve con la carta que queda; en C++ se imprime a medida que salen las cartas.

Complejidad

\(\Theta(n)\) por número de entrada: \(n - 1\) rondas con trabajo constante.

Python

Archivo: throwing-cards-away-i.py

# UVa 10935 - Throwing cards away I
import sys
from collections import deque


def jugar(n):
    # devuelve la línea de descartadas y la carta que queda
    mazo = deque()
    for carta in range(1, n + 1):
        mazo.append(carta)
    linea = "Discarded cards:"
    primera = True
    while len(mazo) >= 2:
        if primera:
            linea = linea + " " + str(mazo.popleft())
            primera = False
        else:
            linea = linea + ", " + str(mazo.popleft())
        mazo.append(mazo.popleft())
    return linea, mazo[0]


def main():
    datos = sys.stdin.read().split()
    i = 0
    while i < len(datos) and int(datos[i]) != 0:
        linea, ultima = jugar(int(datos[i]))
        print(linea)
        print("Remaining card: %d" % ultima)
        i = i + 1


main()

C++

Archivo: throwing-cards-away-i.cpp

// UVa 10935 - Throwing cards away I
#include <cstdio>
#include <queue>

using namespace std;

void jugar(int n) {
    queue<int> mazo;
    for (int carta = 1; carta <= n; carta++) {
        mazo.push(carta);
    }
    printf("Discarded cards:");
    bool primera = true;
    while (mazo.size() >= 2) {
        if (primera) {
            printf(" %d", mazo.front());
            primera = false;
        } else {
            printf(", %d", mazo.front());
        }
        mazo.pop();
        mazo.push(mazo.front());
        mazo.pop();
    }
    printf("\nRemaining card: %d\n", mazo.front());
}

int main() {
    int n = 0;
    scanf("%d", &n);
    while (n != 0) {
        jugar(n);
        n = 0;
        scanf("%d", &n);
    }
    return 0;
}

Tarea intermedia. UVa 11286, Conformity

Idea

Por cada estudiante se ordenan sus cinco cursos y se suma uno a esa clave. Después se recorre el diccionario llevando la mayor cuenta y el total acumulado: una cuenta mayor reinicia el total y una cuenta igual se le suma.

En Python la clave es una tupla, porque una lista no puede ser clave de dict. Los cursos tienen tres dígitos, así que ordenarlos como texto da el mismo orden que como número. En C++ la clave es un vector<int> ya ordenado, y map lo compara elemento por elemento. Sin ordenar los cursos la muestra da 3 y 3, y sin sumar los empates da 2 y 1, en lugar de 2 y 3.

Complejidad

\(O(n \log n)\) por caso en C++, con \(n\) operaciones sobre un map y trabajo constante por clave. En Python, \(O(n)\) en promedio con dict. Comparar cada estudiante con todos los demás pagaría \(\Theta(n^2)\), unos \(10^8\) pasos en el caso más grande.

Python

Archivo: conformity.py

# UVa 11286 - Conformity
import sys


def ganadores(combinaciones):
    # combinaciones trae una tupla ordenada de cursos por estudiante
    cuenta = {}
    for k in combinaciones:
        if k in cuenta:
            cuenta[k] = cuenta[k] + 1
        else:
            cuenta[k] = 1
    mayor = 0
    total = 0
    for k in cuenta:
        if cuenta[k] > mayor:
            mayor = cuenta[k]
            total = cuenta[k]
        elif cuenta[k] == mayor:
            total = total + cuenta[k]
    return total


def main():
    datos = sys.stdin.read().split()
    pos = 0
    n = int(datos[pos])
    pos = pos + 1
    while n != 0:
        combinaciones = []
        for i in range(n):
            combinaciones.append(tuple(sorted(datos[pos:pos + 5])))
            pos = pos + 5
        print(ganadores(combinaciones))
        n = int(datos[pos])
        pos = pos + 1


main()

C++

Archivo: conformity.cpp

// UVa 11286 - Conformity
#include <algorithm>
#include <cstdio>
#include <map>
#include <vector>

using namespace std;

int main() {
    int n = 0;
    scanf("%d", &n);
    while (n != 0) {
        // la clave es el vector de cursos ya ordenado
        map<vector<int>, int> cuenta;
        for (int i = 0; i < n; i++) {
            vector<int> cursos(5);
            for (int j = 0; j < 5; j++) {
                scanf("%d", &cursos[j]);
            }
            sort(cursos.begin(), cursos.end());
            cuenta[cursos] = cuenta[cursos] + 1;
        }
        int mayor = 0;
        int total = 0;
        for (map<vector<int>, int>::iterator it = cuenta.begin(); it != cuenta.end(); it++) {
            if (it->second > mayor) {
                mayor = it->second;
                total = it->second;
            } else if (it->second == mayor) {
                total = total + it->second;
            }
        }
        printf("%d\n", total);
        n = 0;
        scanf("%d", &n);
    }
    return 0;
}

Tarea exigente. UVa 699, The Falling Leaves

Idea

subarbol recibe la columna donde está su raíz. Lee un valor; si no es -1, lo suma a la pila de esa columna y se llama dos veces, una para cada hijo. Al volver al programa principal, el árbol ya está leído completo y las pilas tienen su suma. Las columnas se imprimen de la menor a la mayor.

Las columnas pueden ser negativas, y por eso las pilas van en un diccionario: dict en Python, recorrido con sorted, y map en C++, que ya recorre en orden. En Python, subarbol lee de la lista de palabras y devuelve la posición donde sigue la entrada, como en UVa 839. En C++ el programa principal lee la raíz para reconocer el -1 final, y subarbol recibe ese valor ya leído. El enunciado acota el ancho de la salida y no la altura del árbol, así que la versión en Python sube el límite de recursión con sys.setrecursionlimit(100000).

Complejidad

\(O(t \log c)\) por árbol en C++ con map, con \(t\) nodos y \(c\) columnas distintas. En Python, \(O(t + c \log c)\) en promedio. La pila de llamadas llega a la altura del árbol.

Python

Archivo: the-falling-leaves.py

# UVa 699 - The Falling Leaves
import sys


def sumar(pilas, x, valor):
    if x in pilas:
        pilas[x] = pilas[x] + valor
    else:
        pilas[x] = valor


def subarbol(datos, pos, x, pilas):
    # lee el subárbol que empieza en datos[pos], cuya raíz está en la
    # columna x, y devuelve dónde sigue la entrada
    valor = int(datos[pos])
    pos = pos + 1
    if valor != -1:
        sumar(pilas, x, valor)
        pos = subarbol(datos, pos, x - 1, pilas)
        pos = subarbol(datos, pos, x + 1, pilas)
    return pos


def main():
    sys.setrecursionlimit(100000)
    datos = sys.stdin.read().split()
    caso = 1
    pos = 0
    while int(datos[pos]) != -1:
        pilas = {}
        pos = subarbol(datos, pos, 0, pilas)
        linea = ""
        for x in sorted(pilas):
            if linea != "":
                linea = linea + " "
            linea = linea + str(pilas[x])
        print("Case %d:" % caso)
        print(linea)
        print("")
        caso = caso + 1


main()

C++

Archivo: the-falling-leaves.cpp

// UVa 699 - The Falling Leaves
#include <cstdio>
#include <map>

using namespace std;

// lee un subárbol cuya raíz está en la columna x y suma sus valores a las
// pilas; ya se sabe que la raíz vale raiz y no es -1
void subarbol(int raiz, int x, map<int, long long>& pilas) {
    pilas[x] = pilas[x] + raiz;
    int izq;
    scanf("%d", &izq);
    if (izq != -1) {
        subarbol(izq, x - 1, pilas);
    }
    int der;
    scanf("%d", &der);
    if (der != -1) {
        subarbol(der, x + 1, pilas);
    }
}

int main() {
    int caso = 1;
    int raiz = -1;
    scanf("%d", &raiz);
    while (raiz != -1) {
        map<int, long long> pilas;
        subarbol(raiz, 0, pilas);
        printf("Case %d:\n", caso);
        bool primera = true;
        for (map<int, long long>::iterator it = pilas.begin(); it != pilas.end(); it++) {
            if (primera) {
                printf("%lld", it->second);
                primera = false;
            } else {
                printf(" %lld", it->second);
            }
        }
        printf("\n\n");
        caso = caso + 1;
        raiz = -1;
        scanf("%d", &raiz);
    }
    return 0;
}