Snow Boots

Solución en video

Por I-Chen Chou

Nota: La solución en video podría no ser la misma que las otras soluciones. Código en C++.

Solución

Explicación

Vemos cada posición y bota como un estado, y ejecutamos una búsqueda en profundidad (DFS) para explorar cada estado mientras marcamos los visitados.

Desde cualquier estado, avanzamos hasta la longitud máxima de paso de la bota sobre baldosas que puede manejar, o cambiamos a cualquier bota posterior que también funcione en la baldosa actual.

Cuando llegamos a la última baldosa, registramos el índice de la bota actual, quedándonos con el valor más pequeño.

Consideremos el caso de ejemplo. Empezamos en la baldosa $1$ con la bota $1$ . La bota $1$ puede avanzar hasta $5$ baldosas adelante, pero como la baldosa $2$ tiene profundidad $3\gt0$ no podemos avanzar.

Supongamos que cambiamos hasta la bota $3$ , que nos permite avanzar hasta $2$ baldosas con profundidades menores o iguales a $6$ . Podemos movernos a la baldosa $2$ porque su profundidad es $3\le6$ . No podemos avanzar a la baldosa $3$ porque su profundidad es $8\gt6$ . Avanzamos una baldosa y ahora enfrentamos un conjunto similar de opciones.

Cada paso o cambio lleva a un estado nuevo, que marcamos como visitado para no repetirlo. Eventualmente este proceso llega a la baldosa $8$ con varias botas distintas. Cada vez que llegamos por primera vez a la baldosa $8$ registramos el índice de esa bota, y a lo largo del DFS nos quedamos con el índice mínimo como respuesta.

Hay $\mathcal{O}(NB)$ estados en total y como $N$ y $B$ son a lo sumo $250$ , visitar todos los $\mathcal{O}(N + B)$ estados vecinos será a lo sumo $\mathcal{O}(N^2B + NB^2)$ , lo cual corre a tiempo.

Implementación

Complejidad temporal: $\mathcal{O}(N^2B + NB^2)$

C++JavaPython


#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
 
using namespace std;
 
 
const int MAX_N = 250;
int n;
int m;
vector<int> depths(MAX_N);
vector<vector<bool>> vis(MAX_N, vector<bool>(MAX_N));
vector<pair<int, int>> shoes(MAX_N);
 
int ans = INT32_MAX;
 
void dfs(int depth, int boot) {
	// ya visitamos este camino
	if (vis[depth][boot]) { return; }
 
	vis[depth][boot] = true;
 
	// llegamos al granero, actualizamos la respuesta
	if (depth == n - 1) {
		ans = min(boot, ans);
		return;
	}
 
	// probamos todos los pasos posibles
	for (int i = depth + 1; i <= depth + shoes[boot].second && i < n; i++) {
		if (depths[i] <= shoes[boot].first) { dfs(i, boot); }
	}
 
	// probamos todos los cambios posibles
	for (int i = boot; i < m; i++) {
		if (depths[depth] <= shoes[i].first) { dfs(depth, i); }
	}
}
 
int main() {
	freopen("snowboots.in", "r", stdin);
	freopen("snowboots.out", "w", stdout);
 
	cin >> n >> m;
 
	for (int i = 0; i < n; i++) { cin >> depths[i]; }
 
	for (int i = 0; i < m; i++) { cin >> shoes[i].first >> shoes[i].second; }
 
	dfs(0, 0);
 
	cout << ans << "\n";
}


import java.io.*;
import java.util.*;
 
public class snowboot {
	static List<Pair<Integer, Integer>> B = new ArrayList<>();
	static int[] D;
	static boolean[][] vist;
	static int N, M, A = 10000;
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader("snowboots.in");
		N = in.nextInt();
		M = in.nextInt();
		D = new int[N];
		vist = new boolean[N + 1][M + 1];
		for (int i = 0; i < N; i++) { D[i] = in.nextInt(); }
		for (int i = 0; i < M; i++) {
			int a, b;
			a = in.nextInt();
			b = in.nextInt();
			B.add(new Pair<>(a, b));
		}
 
		dfs(0, 0);
		PrintWriter out =
		    new PrintWriter(new BufferedWriter(new FileWriter("snowboots.out")));
		out.println(A);
		out.close();
	}
 
	private static void dfs(int n, int t) {
		// Si ya exploramos ese camino, volvemos
		if (vist[n][t]) return;
		vist[n][t] = true;
 
		// Si llega al destino tomamos el mínimo entre lo que
		// tenemos y lo que obtuvimos
		if (n == N - 1) A = Math.min(A, t);
 
		// Intentamos ir a cada granja posible con una bota
		for (int i = n + 1; i < N && i - n <= B.get(t).last(); i++) {
			if (D[i] <= B.get(t).first) dfs(i, t);
		}
 
		// Probamos todos los cambios de bota en la granja actual
		for (int i = t + 1; i < B.size(); i++) {
			if (D[n] <= B.get(i).first) dfs(n, i);
		}
	}
 
	private static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;
 
		public InputReader() {
			try {
				reader = new BufferedReader(new InputStreamReader(System.in), 32768);
			} catch (Exception e) {
				throw new NullPointerException("Could not create input stream");
			}
		}
 
		public InputReader(String fileName) {
			try {
				reader = new BufferedReader(new FileReader(new File(fileName)), 32768);
			} catch (Exception ex) {
				throw new NullPointerException(
				    "Input file does not exist! Put it in the project folder.");
			}
			tokenizer = null;
		}
 
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) { throw new RuntimeException(e); }
			}
			return tokenizer.nextToken();
		}
 
		public boolean hasNextInt() throws IOException { return reader.ready(); }
 
		public int nextInt() { return Integer.parseInt(next()); }
 
		public double nextDouble() { return Double.parseDouble(next()); }
 
		public long nextLong() { return Long.parseLong(next()); }
 
		public char nextChar() { return next().charAt(0); }
 
		/**
		 * Al llamar next(), se salta esa línea entera.
		 * No se hace flush de buffers.
		 * No funciona cuando se quiere escanear el resto de la línea.
		 *
		 * @return la línea entera
		 */
 
		public String nextLine() {
			String str = "";
			try {
				str = reader.readLine();
				tokenizer = null;
			} catch (IOException e) { throw new RuntimeException(e); }
			return str;
		}
	}
 
	private static class Pair<F, S> {
		F first;
		S second;
 
		public Pair(F a, S b) {
			first = a;
			second = b;
		}
 
		public F one() { return first; }
 
		public S last() { return second; }
 
		@Override
		public String toString() {
			return "[" + first.toString() + ", " + second.toString() + "]";
		}
	}
}


with open("snowboots.in") as r:
	n, b = map(int, r.readline().split())
	depth = list(map(int, r.readline().split()))
	max_depth = [[*map(int, r.readline().split())] for _ in range(b)]
 
stor = [[0] * b for _ in range(n)]
stor[0][0] = 1
for i in range(n):
	cur = -1
	for j in range(b):
		s, d = max_depth[j]
		if s >= depth[i]:
			for k in range(1, d + 1):
				if stor[i - k][j] and i - k >= 0:
					stor[i][j] = 1
					cur = j
					break
		if cur != -1:
			break
 
	for j in range(cur + 1, b):
		s, d = max_depth[j]
		if s >= depth[i]:
			stor[i][j] = 1
 
for i in range(b):
	if stor[-1][i]:
		print(i, file=open("snowboots.out", "w"))
		break