Saltar a contenido

Soluciones · Refuerzo PUJ 17 de octubre

Los seis problemas de la sesión del 17 de octubre, 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/, listos para compilar y enviar al juez.

Hora 1. UVa 11078, Open Credit System

Idea

Para un \(j\) fijo, el antiguo que más le saca es el de mayor puntaje entre \(a[0], \dots, a[j-1]\). Ese máximo no se busca en cada vuelta: al avanzar \(j\) entra un solo candidato, así que basta llevarlo actualizado en un recorrido. La respuesta es el mejor \(\mathit{mayor} - a[j]\) que aparezca.

Probar todas las parejas cuesta \(n(n-1)/2\), unos \(5 \cdot 10^9\) con \(n = 100\,000\). En Python, con \(n = 10\,000\), esa versión tarda 2,8 s en un caso.

Complejidad

\(\Theta(n)\) por caso, con memoria \(\Theta(n)\) para los puntajes.

Python

Archivo: open-credit-system.py

# UVa 11078 - Open Credit System
import sys


def mayor_diferencia(a):
    mayor = a[0]
    mejor = a[0] - a[1]
    for j in range(1, len(a)):
        if mayor - a[j] > mejor:
            mejor = mayor - a[j]
        if a[j] > mayor:
            mayor = a[j]
    return mejor


def main():
    datos = sys.stdin.read().split()
    t = int(datos[0])
    pos = 1
    for caso in range(t):
        n = int(datos[pos])
        a = []
        for k in range(n):
            a.append(int(datos[pos + 1 + k]))
        pos = pos + 1 + n
        print(mayor_diferencia(a))


main()

C++

Archivo: open-credit-system.cpp

// UVa 11078 - Open Credit System
#include <cstdio>
#include <vector>

using namespace std;

int mayor_diferencia(const vector<int>& a) {
    int mayor = a[0];
    int mejor = a[0] - a[1];
    for (int j = 1; j < (int) a.size(); j++) {
        if (mayor - a[j] > mejor) {
            mejor = mayor - a[j];
        }
        if (a[j] > mayor) {
            mayor = a[j];
        }
    }
    return mejor;
}

int main() {
    int t;
    scanf("%d", &t);
    for (int caso = 0; caso < t; caso++) {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        for (int k = 0; k < n; k++) {
            scanf("%d", &a[k]);
        }
        printf("%d\n", mayor_diferencia(a));
    }
    return 0;
}

UVa 507, Jill Rides Again

Idea

Se recorre la ruta llevando la suma del tramo que empezó en inicio. Un prefijo con suma negativa solo resta a lo que venga después, así que cuando la suma baja de cero se descarta y el tramo vuelve a empezar en la calle siguiente (la idea de Kadane).

El reinicio es con suma < 0 y no con suma <= 0: un prefijo que suma cero no cambia la suma pero alarga el tramo, y el enunciado premia el largo. Al guardar el mejor, un tramo nuevo reemplaza al guardado si suma más, o si suma lo mismo y es estrictamente más largo. Con la comparación estricta, de dos tramos iguales en suma y en largo queda el primero que apareció, que es el de menor \(i\).

Probar todos los tramos con acumulados cuesta \(\Theta(s^2)\): en Python, una sola ruta de \(20\,000\) paradas tarda 20,8 s.

Complejidad

\(\Theta(s)\) por ruta, con memoria \(\Theta(s)\).

Python

Archivo: jill-rides-again.py

# UVa 507 - Jill Rides Again
import sys


def mejor_tramo(v):
    # v[k] es la calle entre las paradas k + 1 y k + 2
    suma = 0
    inicio = 0
    mejor = 0
    mi = 0
    mj = -1
    for k in range(len(v)):
        suma = suma + v[k]
        if suma > mejor or (suma == mejor and k - inicio > mj - mi):
            mejor = suma
            mi = inicio
            mj = k
        if suma < 0:
            suma = 0
            inicio = k + 1
    return mejor, mi, mj


def main():
    datos = sys.stdin.read().split()
    b = int(datos[0])
    pos = 1
    for r in range(1, b + 1):
        s = int(datos[pos])
        v = []
        for k in range(s - 1):
            v.append(int(datos[pos + 1 + k]))
        pos = pos + s
        mejor, mi, mj = mejor_tramo(v)
        if mejor > 0:
            print("The nicest part of route %d is between stops %d and %d"
                  % (r, mi + 1, mj + 2))
        else:
            print("Route %d has no nice parts" % r)


main()

C++

Archivo: jill-rides-again.cpp

// UVa 507 - Jill Rides Again
#include <cstdio>
#include <vector>

using namespace std;

// v[k] es la calle entre las paradas k + 1 y k + 2
long long mejor_tramo(const vector<int>& v, int& mi, int& mj) {
    long long suma = 0;
    int inicio = 0;
    long long mejor = 0;
    mi = 0;
    mj = -1;
    for (int k = 0; k < (int) v.size(); k++) {
        suma = suma + v[k];
        if (suma > mejor || (suma == mejor && k - inicio > mj - mi)) {
            mejor = suma;
            mi = inicio;
            mj = k;
        }
        if (suma < 0) {
            suma = 0;
            inicio = k + 1;
        }
    }
    return mejor;
}

int main() {
    int b;
    scanf("%d", &b);
    for (int r = 1; r <= b; r++) {
        int s;
        scanf("%d", &s);
        vector<int> v(s - 1);
        for (int k = 0; k < s - 1; k++) {
            scanf("%d", &v[k]);
        }
        int mi, mj;
        long long mejor = mejor_tramo(v, mi, mj);
        if (mejor > 0) {
            printf("The nicest part of route %d is between stops %d and %d\n",
                   r, mi + 1, mj + 2);
        } else {
            printf("Route %d has no nice parts\n", r);
        }
    }
    return 0;
}

UVa 108, Maximum Sum

Idea

Hay \((N(N+1)/2)^2 \approx 2{,}6 \cdot 10^7\) rectángulos. Sumarlos celda por celda es \(O(N^6)\); con acumulados en dos dimensiones cada suma sale en \(O(1)\) y el total baja a \(O(N^4)\).

La solución fija dos filas, arriba y abajo. Cada rectángulo entre ellas es un tramo de columnas, y si cada columna se reemplaza por su suma entre esas filas, el problema es el tramo de suma máxima de un arreglo, que se resuelve con un recorrido (Kadane). Al bajar abajo una fila, a cada columna se le suma la celda nueva, así que col se actualiza en \(\Theta(N)\).

Complejidad

\(N(N+1)/2\) pares de filas, cada uno con \(\Theta(N)\) para actualizar col y \(\Theta(N)\) para el recorrido: \(O(N^3)\). Memoria \(\Theta(N^2)\).

Python

Archivo: maximum-sum.py

# UVa 108 - Maximum Sum
import sys


def mejor_tramo(v):
    mejor = v[0]
    suma = 0
    for x in v:
        suma = suma + x
        if suma > mejor:
            mejor = suma
        if suma < 0:
            suma = 0
    return mejor


def mayor_rectangulo(m):
    n = len(m)
    mejor = m[0][0]
    for arriba in range(n):
        col = [0] * n
        for abajo in range(arriba, n):
            for c in range(n):
                col[c] = col[c] + m[abajo][c]
            s = mejor_tramo(col)
            if s > mejor:
                mejor = s
    return mejor


def main():
    datos = sys.stdin.read().split()
    n = int(datos[0])
    m = []
    for i in range(n):
        fila = []
        for j in range(n):
            fila.append(int(datos[1 + i * n + j]))
        m.append(fila)
    print(mayor_rectangulo(m))


main()

C++

Archivo: maximum-sum.cpp

// UVa 108 - Maximum Sum
#include <cstdio>
#include <vector>

using namespace std;

int mejor_tramo(const vector<int>& v) {
    int mejor = v[0];
    int suma = 0;
    for (int c = 0; c < (int) v.size(); c++) {
        suma = suma + v[c];
        if (suma > mejor) {
            mejor = suma;
        }
        if (suma < 0) {
            suma = 0;
        }
    }
    return mejor;
}

int mayor_rectangulo(const vector<vector<int>>& m) {
    int n = m.size();
    int mejor = m[0][0];
    for (int arriba = 0; arriba < n; arriba++) {
        vector<int> col(n, 0);
        for (int abajo = arriba; abajo < n; abajo++) {
            for (int c = 0; c < n; c++) {
                col[c] = col[c] + m[abajo][c];
            }
            int s = mejor_tramo(col);
            if (s > mejor) {
                mejor = s;
            }
        }
    }
    return mejor;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<vector<int>> m(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &m[i][j]);
        }
    }
    printf("%d\n", mayor_rectangulo(m));
    return 0;
}

Tarea base. UVa 100, The 3n + 1 problem

Idea

Una función calcula la longitud del ciclo de un número; otra recorre el rango del menor al mayor con un índice y conserva el máximo. Se ordena el rango solo para recorrerlo: lo que se imprime es la pareja original.

Complejidad

Por pareja, \(O((b-a+1) \cdot L)\) con \(L\) la longitud media de ciclo, unos cientos de pasos para valores menores que 10 000. Memoria \(O(1)\).

Python

Archivo: 3n-plus-1.py

import sys


def longitud_ciclo(n):
    cuenta = 1
    while n != 1:
        if n % 2 == 1:
            n = 3 * n + 1
        else:
            n = n // 2
        cuenta = cuenta + 1
    return cuenta


def maximo_ciclo(a, b):
    mejor = 0
    k = a
    while k <= b:
        c = longitud_ciclo(k)
        if c > mejor:
            mejor = c
        k = k + 1
    return mejor


def main():
    datos = sys.stdin.read().split()
    t = 0
    while t + 1 < len(datos):
        i = int(datos[t])
        j = int(datos[t + 1])
        if i <= j:
            m = maximo_ciclo(i, j)
        else:
            m = maximo_ciclo(j, i)
        print("%d %d %d" % (i, j, m))
        t = t + 2


main()

C++

Archivo: 3n-plus-1.cpp

#include <cstdio>

int longitud_ciclo(long long n) {
    int cuenta = 1;
    while (n != 1) {
        if (n % 2 == 1) {
            n = 3 * n + 1;
        } else {
            n = n / 2;
        }
        cuenta = cuenta + 1;
    }
    return cuenta;
}

int maximo_ciclo(int a, int b) {
    int mejor = 0;
    for (int k = a; k <= b; k++) {
        int c = longitud_ciclo(k);
        if (c > mejor) {
            mejor = c;
        }
    }
    return mejor;
}

int main() {
    int i, j;
    while (scanf("%d %d", &i, &j) == 2) {
        int m;
        if (i <= j) {
            m = maximo_ciclo(i, j);
        } else {
            m = maximo_ciclo(j, i);
        }
        printf("%d %d %d\n", i, j, m);
    }
    return 0;
}

Tarea intermedia. UVa 10189, Minesweeper

Idea

Para cada casilla libre se recorren los nueve desplazamientos \((df, dc) \in \{-1,0,1\}^2\) y se cuentan las minas dentro del tablero. Las casillas con mina se copian tal cual.

Complejidad

\(O(9nm)\) por campo, es decir \(O(nm)\). Memoria \(O(nm)\).

Python

Archivo: minesweeper.py

import sys


def contar(campo, n, m, f, c):
    total = 0
    df = -1
    while df <= 1:
        dc = -1
        while dc <= 1:
            g = f + df
            h = c + dc
            if (df != 0 or dc != 0) and g >= 0 and g < n and h >= 0 and h < m:
                if campo[g][h] == "*":
                    total = total + 1
            dc = dc + 1
        df = df + 1
    return total


def main():
    datos = sys.stdin.read().split()
    pos = 0
    numero = 0
    n = int(datos[pos])
    m = int(datos[pos + 1])
    pos = pos + 2
    while n != 0 or m != 0:
        campo = datos[pos:pos + n]
        pos = pos + n
        numero = numero + 1
        if numero > 1:
            print("")
        print("Field #%d:" % numero)
        f = 0
        while f < n:
            fila = ""
            c = 0
            while c < m:
                if campo[f][c] == "*":
                    fila = fila + "*"
                else:
                    fila = fila + str(contar(campo, n, m, f, c))
                c = c + 1
            print(fila)
            f = f + 1
        n = int(datos[pos])
        m = int(datos[pos + 1])
        pos = pos + 2


main()

C++

Archivo: minesweeper.cpp

#include <cstdio>

char campo[105][105];

int contar(int n, int m, int f, int c) {
    int total = 0;
    for (int df = -1; df <= 1; df++) {
        for (int dc = -1; dc <= 1; dc++) {
            int g = f + df;
            int h = c + dc;
            if ((df != 0 || dc != 0) && g >= 0 && g < n && h >= 0 && h < m) {
                if (campo[g][h] == '*') {
                    total = total + 1;
                }
            }
        }
    }
    return total;
}

int main() {
    int n, m;
    int numero = 0;
    scanf("%d %d", &n, &m);
    while (n != 0 || m != 0) {
        for (int f = 0; f < n; f++) {
            scanf("%s", campo[f]);
        }
        numero = numero + 1;
        if (numero > 1) {
            printf("\n");
        }
        printf("Field #%d:\n", numero);
        for (int f = 0; f < n; f++) {
            for (int c = 0; c < m; c++) {
                if (campo[f][c] == '*') {
                    printf("*");
                } else {
                    printf("%d", contar(n, m, f, c));
                }
            }
            printf("\n");
        }
        scanf("%d %d", &n, &m);
    }
    return 0;
}

Tarea exigente. UVa 10920, Spiral Tap

Idea

Con centro \(c = (SZ+1)/2\), el anillo \(r\) contiene los números de \((2r-1)^2+1\) a \((2r+1)^2\). Se halla el menor \(r\) con \((2r+1)^2 \ge P\) avanzando anillo por anillo desde el centro y se calcula \(d = P - (2r-1)^2 - 1\), el desplazamiento dentro del anillo, que tiene \(8r\) casillas en cuatro lados de \(2r\):

  • \(0 \le d < 2r\): línea \(c+r\), columna \(c+r-1-d\) (lado de arriba, hacia la izquierda).
  • \(2r \le d < 4r\): columna \(c-r\), línea \(c+r-(d-2r+1)\) (lado izquierdo, hacia abajo).
  • \(4r \le d < 6r\): línea \(c-r\), columna \(c-r+(d-4r+1)\) (lado de abajo, hacia la derecha).
  • \(6r \le d < 8r\): columna \(c+r\), línea \(c-r+(d-6r+1)\) (lado derecho, hacia arriba).

Si \(P = 1\) (anillo 0) la respuesta es el centro.

Complejidad

\(O(SZ)\) por consulta, porque el anillo se busca paso a paso. Memoria \(O(1)\).

Python

Archivo: spiral-tap.py

import sys


def anillo(p):
    r = 0
    while (2 * r + 1) * (2 * r + 1) < p:
        r = r + 1
    return r


def coordenadas(sz, p):
    c = (sz + 1) // 2
    r = anillo(p)
    if r == 0:
        linea = c
        col = c
    else:
        d = p - (2 * r - 1) * (2 * r - 1) - 1
        if d < 2 * r:
            linea = c + r
            col = c + r - 1 - d
        elif d < 4 * r:
            linea = c + r - (d - 2 * r + 1)
            col = c - r
        elif d < 6 * r:
            linea = c - r
            col = c - r + (d - 4 * r + 1)
        else:
            linea = c - r + (d - 6 * r + 1)
            col = c + r
    return (linea, col)


def main():
    datos = sys.stdin.read().split()
    t = 0
    sz = int(datos[t])
    p = int(datos[t + 1])
    while sz != 0 or p != 0:
        res = coordenadas(sz, p)
        print("Line = %d, column = %d." % (res[0], res[1]))
        t = t + 2
        sz = int(datos[t])
        p = int(datos[t + 1])


main()

C++

Archivo: spiral-tap.cpp

#include <cstdio>

long long anillo(long long p) {
    long long r = 0;
    while ((2 * r + 1) * (2 * r + 1) < p) {
        r = r + 1;
    }
    return r;
}

int main() {
    long long sz, p;
    scanf("%lld %lld", &sz, &p);
    while (sz != 0 || p != 0) {
        long long c = (sz + 1) / 2;
        long long r = anillo(p);
        long long linea, col;
        if (r == 0) {
            linea = c;
            col = c;
        } else {
            long long d = p - (2 * r - 1) * (2 * r - 1) - 1;
            if (d < 2 * r) {
                linea = c + r;
                col = c + r - 1 - d;
            } else if (d < 4 * r) {
                linea = c + r - (d - 2 * r + 1);
                col = c - r;
            } else if (d < 6 * r) {
                linea = c - r;
                col = c - r + (d - 4 * r + 1);
            } else {
                linea = c - r + (d - 6 * r + 1);
                col = c + r;
            }
        }
        printf("Line = %lld, column = %lld.\n", linea, col);
        scanf("%lld %lld", &sz, &p);
    }
    return 0;
}