พิจารณาวันที่ $T$ พุ่มไม้ที่ตำแหน่ง $x$ ใดๆ จะขยายเป็นรูปพีระมิดที่มีฐานเป็น $[x-T, x+T]$ จำนวนพุ่มไม้ทั้งหมดที่มีในวันนี้จะ เท่ากับผลรวมของพีระมิดเหล่านี้ ลบด้วย ผลรวมพื้นที่ที่พุ่มไม้ทุกคู่ทับกัน

เนื่องจากพื้นที่ที่แต่ละพุ่มไม้ทับกันจะเป็นรูปพีระมิดหากฐานเป็นจำนวนคี่ หรือ พีระมิดที่มียอดเป็นพุ่มไม้สองอันหากฐานเป็นจำนวนคู่ เราสามารถคำนวนจำนวนพุ่มไม้ของพื้นที่ที่มีฐานขนาด $b$ ได้ด้วยสมการดังนี้

1. $(b + 1)^2/4$ ถ้า $b$ เป็นเลขคี่
2. $b*(b+2)/4$ ถ้า $b$ เป็นเลขคู่

เราสามารถหาคำตอบได้ด้วยการ Binary Search คำตอบหา $T$ ที่น้อยที่สุดที่มีพื้นที่พุ่มไม้อย่างน้อย $K$

Time-complexity: $\mathcal{O}(N^2 \log K)$

long long area(long long l, long long r) {
  long long b = r - l + 1;
  if(b <= 0) return 0;
  if(b % 2 != 0) return (b + 1) * (b + 1) / 4;
  return b * (b + 2) / 4;
}

long long calculate(long long T) { // คำนวณจำนวนพุ่มไม้ในวันที่ T
  long long sum = 0;
  for(int i = 1; i <= n; i++) {
    sum += area(x[i] - T, x[i] + T);
    for(int j = i + 1; j <= n; j++) {
      sum -= area(x[j] - T, x[i] + T); // พื้นที่ทับซ้อน
    }
  }
  return sum;
}

Challenge: หาอัลกอริธึมที่คำนวณคำตอบได้ใน $\mathcal{O}(N \log K)$