CF - Firecrackers

Official Editorial

Explanation

We can initially attempt this problem by figuring out which firecrackers should explode. Obviously, we should attempt to explode the firecrackers with a minimal detonation time to increase the number of firecrackers exploded before eventually being caught. Also, observe that the firecrackers with a longer detonation time should be dropped first.

To find the maximum number of firecrackers before the hooligan gets caught by the guard, sort the detonation times in increasing order and figure out the maximum number of firecrackers to drop before getting caught by applying binary search.

If we can determine the amount of time before getting caught, then the binary search will be trivial.

There are two cases which determine the amount of time before getting caught:

1. It can be proven that if $a < b$, then the amount of time before getting caught is precisely $b - 1$ seconds.
2. It can be proven that if $a > b$, then the amount of time before getting caught is precisely $n - b$ seconds.

Note: these times are computed by assuming that both the hooligan and guard act optimally.

After computing the amount of time before getting caught, we can simulate whether a particular firecracker will explode in time.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#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;

Copy
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();

Copy
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):
		# Check whether a given firecracker could be exploded before being caught by the guard
		if current_time + exploding_times[i] > time_before_caught:
			return False
		else:
			current_time += 1