Firecrackers

Explicación

Podemos abordar inicialmente este problema averiguando qué petardos deben explotar. Obviamente, debemos intentar explotar los petardos con un tiempo de detonación mínimo para aumentar el número de petardos explotados antes de ser atrapados. También, observemos que los petardos con un tiempo de detonación más largo deben soltarse primero.

Para hallar el número máximo de petardos antes de que el holigan sea atrapado por el guardia, ordenamos los tiempos de detonación de forma creciente y averiguamos el número máximo de petardos a soltar antes de ser atrapados aplicando búsqueda binaria.

Si podemos determinar la cantidad de tiempo antes de ser atrapados, entonces la búsqueda binaria será trivial.

Hay dos casos que determinan la cantidad de tiempo antes de ser atrapados:

Se puede demostrar que si $a < b$ , entonces la cantidad de tiempo antes de ser atrapados es precisamente $b - 1$ segundos.
Se puede demostrar que si $a > b$ , entonces la cantidad de tiempo antes de ser atrapados es precisamente $n - b$ segundos.

Nota: estos tiempos se calculan asumiendo que tanto el holigan como el guardia actúan de forma óptima.

Tras calcular la cantidad de tiempo antes de ser atrapados, podemos simular si un petardo particular explotará a tiempo.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++JavaPython


#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int corridor_size;
		int num_of_firecrackers;
		int hooligan_location;
		int guard_location;
 
		std::cin >> corridor_size >> num_of_firecrackers >> hooligan_location >>
		    guard_location;
		std::vector<int> exploding_times(num_of_firecrackers);
		for (int &x : exploding_times) { std::cin >> x; }
 
		std::sort(begin(exploding_times), end(exploding_times));
		int max_firecrackers = std::min(
		    num_of_firecrackers, std::abs(hooligan_location - guard_location) - 1);
 
		// Calcular el tiempo máximo antes de que el guardia atrape
		// al holigan dadas sus posiciones iniciales.
		int time_before_caught = 0;
		if (hooligan_location < guard_location) {
			time_before_caught = guard_location - 1;
		} else if (hooligan_location > guard_location) {
			time_before_caught = corridor_size - guard_location;
		}
 
		auto works = [&](int firecrackers_exploded) -> bool {
			int curr_time = 1;
			for (int i = firecrackers_exploded - 1; i >= 0; i--) {
				// Comprobar si un petardo dado podría explotar
				// antes de ser atrapado por el guardia.
				if (curr_time + exploding_times[i] > time_before_caught) {
					return false;
				} else {
					curr_time++;
				}
			}
			return true;
		};
 
		int lo = 0, hi = max_firecrackers;
		int max_exploded = 0;
 
		while (lo <= hi) {
			int mid = lo + (hi - lo) / 2;
			if (works(mid)) {
				max_exploded = mid;
				lo = mid + 1;
			} else {
				hi = mid - 1;
			}
		}
 
		std::cout << max_exploded << '\n';
	}
}


import java.io.*;
import java.util.*;
 
public class Firecrackers {
	public static void main(String[] args) {
		Kattio io = new Kattio();
 
		int testNum = io.nextInt();
		for (int t = 0; t < testNum; t++) {
			int corridorSize = io.nextInt();
			int numOfFirecrackers = io.nextInt();
			int hooliganLocation = io.nextInt();
			int guardLocation = io.nextInt();
 
			int[] explodingTimes = new int[numOfFirecrackers];
 
			for (int i = 0; i < numOfFirecrackers; i++) {
				explodingTimes[i] = io.nextInt();
			}
 
			Arrays.sort(explodingTimes);
			int maxFirecrackers = Math.min(
			    numOfFirecrackers, Math.abs(hooliganLocation - guardLocation) - 1);
 
			//  Calcular el tiempo máximo antes de que el guardia atrape
			//  al holigan dadas sus posiciones iniciales.
			int timeBeforeCaught = 0;
			if (hooliganLocation < guardLocation) {
				timeBeforeCaught = guardLocation - 1;
			} else if (hooliganLocation > guardLocation) {
				timeBeforeCaught = corridorSize - guardLocation;
			}
 
			int lo = 0, hi = maxFirecrackers;
			int maxExploded = 0;
 
			while (lo <= hi) {
				int mid = lo + (hi - lo) / 2;
				if (works(explodingTimes, mid, timeBeforeCaught)) {
					maxExploded = mid;
					lo = mid + 1;
				} else {
					hi = mid - 1;
				}
			}
			io.println(maxExploded);
		}
		io.close();
	}
 
	private static boolean works(int[] explodingTimes, int fireCrackersExploded,
	                             int timeBeforeCaught) {
		int currTime = 1;
		for (int i = fireCrackersExploded - 1; i >= 0; i--) {
			// Comprobar si un petardo dado podría explotar
			// antes de ser atrapado por el guardia.
			if (currTime + explodingTimes[i] > timeBeforeCaught) {
				return false;
			} else {
				currTime++;
			}
		}
		return true;
	}
 
	// CodeSnip{Kattio}
}


def works(
	exploding_times: list, firecrackers_exploded: int, time_before_caught: int
) -> bool:
	current_time = 1
	for i in range(firecrackers_exploded - 1, -1, -1):
		# Comprobar si un petardo dado podría explotar antes de ser atrapado por el guardia
		if current_time + exploding_times[i] > time_before_caught:
			return False
		else:
			current_time += 1
	return True
 
 
for _ in range(int(input())):
	corridor_size, num_of_firecrackers, hooligan_location, guard_location = map(
		int, input().split()
	)
	exploding_times = list(map(int, input().split()))
	exploding_times.sort()
 
	max_firecrackers = min(
		num_of_firecrackers, abs(hooligan_location - guard_location) - 1
	)
 
	# Calcular el tiempo máximo antes de que el guardia atrape al holigan dadas sus posiciones iniciales
	if hooligan_location < guard_location:
		time_before_caught = guard_location - 1
	elif hooligan_location > guard_location:
		time_before_caught = corridor_size - guard_location
 
	left = 0
	right = max_firecrackers
	max_exploded = 0
	while left <= right:
		mid = left + (right - left) // 2
 
		if works(exploding_times, mid, time_before_caught):
			max_exploded = mid
			left = mid + 1
		else:
			right = mid - 1
 
	print(max_exploded)