Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Cuadrícula dispersa

Guarda una cuadrícula casi vacía como la lista de sus celdas distintas de cero y responde operaciones de consulta, conteo, suma por fila y eliminación de columnas.

Lo que aprenderás

  • Guardar solo las celdas distintas de cero
  • Actualizar las claves guardadas cuando se desplazan las columnas
  • Responder consultas sin construir la cuadrícula completa

Problema

Ver original (inglés)

El plano de asientos de un estadio enorme está casi vacío, así que guardar cada celda desperdicia memoria. Una SparseGrid guarda solo las celdas con un valor distinto de cero; todas las demás valen 0. La cuadrícula empieza con rows filas, cols columnas y ninguna celda guardada. Procesa estas operaciones en orden:

  • set r c v: la celda (r, c) pasa a valer v. Asignar 0 elimina la celda del almacenamiento.
  • get r c: produce el valor de la celda (r, c).
  • count: produce cuántas celdas son distintas de cero.
  • row_sum r: produce la suma de los valores de la fila r.
  • width: produce la cantidad actual de columnas.
  • remove_col c: elimina la columna c. Sus celdas desaparecen, todas las celdas a su derecha se mueven una columna a la izquierda y la cuadrícula queda con una columna menos.

Las filas y las columnas se numeran desde 0, y cada índice está dentro de la cuadrícula en el momento de la operación.

Implementa sparse_grid(rows, cols, operations).

Entrada

rows: la cantidad de filas.

cols: la cantidad inicial de columnas.

operations: las operaciones, que se procesan en orden.

Salida

Devuelve las salidas de get, count, row_sum y width en el orden en que ocurren.

Restricciones

1 ≤ rows ≤ 1,000,000

1 ≤ cols ≤ 1,000,000

0 ≤ número de operaciones ≤ 1,000

−1,000,000 ≤ v ≤ 1,000,000

Ejemplos

Ejemplo 1
Entrada:
rows = 3
cols = 4
operations = ["set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"]

Salida esperada:
expected = [7, 3, 0]
Entrada:
long long rows = 3;
long long cols = 4;
std::vector<std::string> operations = {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};

Salida esperada:
std::vector<long long> expected = {7, 3, 0};
Entrada:
long rows = 3;
long cols = 4;
string[] operations = new string[] {"set 0 1 5", "set 0 3 2", "set 2 2 7", "row_sum 0", "count", "get 1 1"};

Salida esperada:
long[] expected = new long[] {7, 3, 0};

Explicación

La fila 0 tiene 5 y 2, así que su suma es 7; hay tres celdas guardadas; a (1, 1) nunca se le asignó un valor, así que vale 0.

Ejemplo 2
Entrada:
rows = 2
cols = 3
operations = ["set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"]

Salida esperada:
expected = [9, 2, 1]
Entrada:
long long rows = 2;
long long cols = 3;
std::vector<std::string> operations = {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};

Salida esperada:
std::vector<long long> expected = {9, 2, 1};
Entrada:
long rows = 2;
long cols = 3;
string[] operations = new string[] {"set 1 0 4", "set 1 2 9", "remove_col 0", "get 1 1", "width", "count"};

Salida esperada:
long[] expected = new long[] {9, 2, 1};

Explicación

Al eliminar la columna 0 se borra el 4 y el 9 de la columna 2 pasa a la columna 1, así que get 1 1 da 9, el ancho es 2 y queda una celda.

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Un mapa de (fila, columna) a valor funciona bien; una clave que no existe significa 0.

Pista 2

Asignar 0 a una celda debe borrarla para que `count` siga siendo correcto.

Pista 3

Cuando se elimina una columna, reconstruye el mapa: quita esa columna y resta uno a los números de columna mayores.

Complejidad esperada

tiempo O(q × s), espacio extra O(s), s = celdas guardadas

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.