Buried Treasure - AIO 2025 Solution

There are L possible locations where the treasure could be and we can check these locations one at a time. For each location, we loop over all N clues to check whether the location satisfies all the clues. If so, we add 1 to the answer.

Let's analyse the time complexity of this solution. For each location we can loop over all N clues in O(N) time, meaning the solution has an overall time complexity of O(NL). This is fast enough to pass subtasks 1 and 2 but is not fast enough to solve the final subtask.

Full Solution

Let's look at the first sample input that has N = 2 clues. The first clue has A₁ = 3 and B₁ = 6 while the second has A₂ = 5 and B₂ = 8.

A₁ = 3 tells us that the treasure must be located at location 3 or higher. Similarly, A₂ = 5 tells us that the treasure must be located at location 5 or higher. Of these two pieces of information, the second (with higher A_i) is more restrictive.

B₁ = 6 tells us that the treasure must be located at location 6 or lower. Similarly, B₂ = 8 tells us that the treasure must be located at location 8 or lower. Of these two pieces of information, the first (with lower B_i) is more restrictive.

Combining the two pieces of information we know that the treasure must be located at a location which is greater than or equal to 5 but less than or equal to 6. Therefore the answer is 2. In general, if we know the maximum A_i (which we will call A_max) and the minimum B_i (which we will call B_min) then this is enough to compute the answer:

We can find A_max and B_min in O(N) time, and so this solution has a time complexity of O(N) which is fast enough to score 100.

Code

Below you can see the full solution written in Python and C++. I suggest trying to code the solution yourself and only look at our code after you finish or if you get stuck.

# N is the number of clues.
N = 0
# L is the number of locations.
L = 0

# A and B contain clues. Note that the list starts from 0, and so the first
# clue is (A[0], B[0]) and the last clue is (A[N-1], B[N-1]).
A = []
B = []

# Read the values of N, L, and the clues.
N, L = map(int, input().strip().split())
for i in range(0, N):
  input_vars = list(map(int, input().strip().split()))
  A.append(input_vars[0])
  B.append(input_vars[1])

# Compute the answer
Amax = 1  # we know that A[i] >= 1 for all i
Bmin = L  # we know that B[i] <= L for all i
for i in range(N):
  Amax = max(Amax, A[i])
  Bmin = min(Bmin, B[i])

answer = max(0, Bmin-Amax+1)

print(answer)

#include <cstdio>
#include <algorithm> // this gives us std::max and std::min

/* N is the number of clues. */
int N;
/* L is the number of locations. */
int L;

/*
 * A and B contain clues. Note that the arrays start from 0, and so the first
 * clue is (A[0], B[0]) and the last clue is (A[N-1], B[N-1]).
 */
int A[200005];
int B[200005];

int main(void) {
  /* Read the values of N, L, and the clues. */
  scanf("%d%d", &N, &L);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A[i]);
    scanf("%d", &B[i]);
  }

  /* Compute the answer */
  int Amax = 1;  // we know that A[i] >= 1 for all i
  int Bmin = L;  // we know that B[i] <= L for all i
  for (int i = 0; i < N; i++) {
    Amax = std::max(Amax, A[i]);
    Bmin = std::min(Bmin, B[i]);
  }

  int answer = std::max(0, Bmin-Amax+1);

  printf("%d\n", answer);
}

Problem 2 - Buried Treasure

Solution

Subtask 2: N ≤ 1000 and L ≤ 1000

Full Solution

Code