กำหนดให้ $A_i$ คือความสูงในการกระโดดของนักเรียนคนที่ $i$ เมื่อ $1 \leq i \leq N$ ซึ่งเลขลำดับจะใช้ต่างจากที่โจทย์กำหนดเพื่อความสะดวกในการอธิบาย

ในข้อนี้ เราต้องการที่จะแบ่งนักเรียนออกเป็นกลุ่ม ๆ โดยที่แต่ละกลุ่มจะต้องมีจำนวนนักเรียนอยู่ระหว่าง $L$ คนถึง $U$ คนเท่านั้น และเราต้องจัดกลุ่มเพื่อให้ระยะกระโดดที่มากที่สุดของแต่ละกลุ่ม ที่น้อยที่สุด (ต่อจากนี้จะขอเรียกว่าเป็นค่าคำตอบ) มีค่ามากที่สุดเท่าที่จะเป็นไปได้

สมมติว่าโจทย์ใหม่กำหนดค่า $k$ มาให้ และต้องการให้ตรวจสอบว่าสามารถจัดให้นักเรียนที่กระโดดได้สูงที่สุดของแต่ละกลุ่มจะต้องกระโดดได้อย่างน้อย $k$ ไมโครเมตรได้หรือไม่ การตรวจสอบสามารถทำได้ด้วย Dynamic Programming ดังนี้ กำหนดให้ $dp(i)$ เป็นจริงก็ต่อเมื่อเราสามารถจัดกลุ่มนักเรียนคนที่ $1$ ถึงคนที่ $i$ แล้วทำให้คำตอบมีค่าอย่างน้อย $k$ ไมโครเมตรได้ จะได้ว่า Recurrence Formula เป็นดังนี้

$dp(i) = dp(l) \vee dp(l + 1) \vee ... \vee dp(r)$

เมื่อ $l$ คือ $\max(0, i - U)$, $r$ คือ $\min(i - L, last - 1)$ และ $last$ คือเลขลำดับของนักเรียนที่มากที่สุดที่กระโดดได้สูงอย่างน้อย $k$ ไมโครเมตร ส่วน $\vee$ คือเครื่องหมาย "หรือ" ในทางตรรกศาสตร์

Recurrence Formula นี้มาจากการที่เราจะต้องแบ่งกลุ่มให้มีจำนวนนักเรียนอยู่ระหว่าง $L$ คนถึง $U$ คนดังที่โจทย์ได้กล่าวไว้ แต่ในขณะเดียวกัน เพื่อให้นักเรียนที่กระโดดได้สูงที่สุดของกลุ่มกระโดดสูงอย่างน้อย $k$ ไมโครเมตร เราจึงต้องจัดกลุ่มให้มีนักเรียนอย่างน้อย 1 คนที่กระโดดได้สูงอย่างน้อย $k$ ไมโครเมตร จึงทำให้ต้องคำนึงถึงลำดับของนักเรียนคนแรกที่กระโดดได้สูงอย่างน้อย $k$ ไมโครเมตรไปทางซ้ายของนักเรียนคนที่ $i$

หากเราทำ Recurrence Formula นี้ปกติแล้ว จะใช้เวลา $\mathcal{O}(N)$ ต่อการคำนวณ 1 ครั้ง แต่เราสามารถลดเวลาการทำงานลงเหลือ $\mathcal{O}(\log N)$ ได้ สังเกตว่า $dp(i)$ จะเป็นจริง ก็ต่อเมื่อมี $dp(l), dp(l + 1), ... , dp(r)$ ที่เป็นจริงอย่างน้อยหนึ่งตัวเท่านั้น เราจึงกำหนดให้เซต $T$ ประกอบด้วย $i$ เมื่อ $dp(i)$ เป็นจริง และใช้การ Binary Search เพื่อตรวจสอบว่าภายในช่วง $[l, r]$ มีค่าที่เป็นจริงหรือไม่ ซึ่งสำหรับเซต $T$ เราสามารถใช้ std::vector ได้เพราะหากเราคำนวณค่าของ $dp(i)$ จาก $1$ ถึง $i$ แล้ว สมาชิกภายใน $T$ จะเรียงจากน้อยไปมากเสมอ ทำให้สามารถ Binary Search ได้ภายใน $\mathcal{O}(\log N)$ นอกจากนี้ เราจะเก็บเลขลำดับของนักเรียนที่กระโดดได้สูงอย่างน้อย $k$ ไมโครเมตรใน std::deque เพื่อใช้ในการหาค่าของ $last$ ได้ในเวลา $\mathcal{O}(1)$

หลังจากคำนวณค่า $dp(i)$ เป็นที่เรียบร้อยแล้ว เราจะสามารถจัดกลุ่มนักเรียนให้มีคำตอบอย่างน้อย $k$ ไมโครเมตร เมื่อ $dp(N)$ เป็นจริง

สังเกตว่าหากเราสามารถจัดกลุ่มนักเรียนให้ทุกกลุ่มกระโดดได้อย่างน้อย $k$ ไมโครเมตร คำตอบของโจทย์เดิมย่อมมีค่าอย่างน้อย $k$ เราจึงสามารถใช้คุณสมบัติที่ว่า หากเราสามารถจัดกลุ่มนักเรียนให้คำตอบมีค่าอย่างน้อย $k$ ไมโครเมตร ก็จะสามารถสรุปได้ว่าเราสามารถจัดกลุ่มนักเรียนให้คำตอบมีค่าอย่างน้อย $1, 2, 3, ..., k - 1$ ไมโครเมตรเช่นกัน ทำให้เราสามารถ Binary Search ค่า $k$ เพื่อหา $k$ ที่มากที่สุดที่ยังสามารถจัดกลุ่มนักเรียนให้มีคำตอบอย่างน้อย $k$ ไมโครเมตรได้ ซึ่งก็คือคำตอบของข้อนี้นั่นเอง

โค้ดตัวอย่างดังนี้

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, a, b; // N, L and U in this implementation
int A[N], dp[N];

bool f(int m) {
  memset(dp, 0, sizeof dp);
  deque<int> pos; // Storing position of student whose jump height >= m
  vector<int> T;  // Storing index of dp whose value is true
  dp[0] = 1, T.emplace_back(0); // Base case
  for (int i = 1; i < a; i++)
    if (A[i] >= m)
      pos.emplace_back(i);
  for (int i = a; i <= n; i++) {
    if (A[i] >= m)
      pos.emplace_back(i);
    if (!pos.empty() && pos.front() == i - b)
      pos.pop_front(); // Remove irrelevant position
    if (pos.empty())
      continue; // No student with jump height >= m available

    int last = pos.back(), x = max(0, i - b),
        y = min(i - a, last - 1); // last, l and r
    int chk = upper_bound(T.begin(), T.end(), y) -
              lower_bound(T.begin(), T.end(), x); // Binary search on T
    if (chk)
      dp[i] = 1, T.emplace_back(i);
  }
  return (bool)dp[n];
}

int main() {
  scanf("%d %d %d", &n, &a, &b);
  for (int i = 1; i <= n; i++)
    scanf("%d", A + i);
  int l = 0, r = 1e9;
  bool valid = false; // True if at least one solution exists
  while (l < r) { // Binary search on k
    int m = (l + r + 1) >> 1;
    if (f(m))
      l = m, valid = true;
    else
      r = m - 1;
  }
  if (valid)
    printf("%d\n", l);
  else
    printf("-1\n");

  return 0;
}

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