ในข้อนี้เราต้องการหากรงที่ขนาด เล็กที่สุด ที่สามารถเคลื่อนย้ายแมวได้

เราเริ่มต้นจากการสมมติว่ามีกรงขนาดคงที่ค่าหนึ่ง สมมติขนาด $Z$

ต่อมาเราต้องการทดสอบว่า หากมีกรงขนาด $Z$ แล้วจะสามารถย้ายแมวตามที่โจทย์ต้องการได้หรือไม่ สังเกตว่า หากแมว $x$ และ แมว $y$ มีขนาดเท่ากันและไม่ใหญ่กว่ากรง (นั่นคือ $Z \geq s_x = s_y$) เราสามารถย้ายไปไว้ด้านซ้ายสุดทั้งคู่ได้ แล้วจะไม่เกิดปัญหาอะไรเลย

จากแนวคิดข้างต้น ทำให้เรามีวิธี greedy หากทราบขนาด $Z$ แล้ว นั่นคือหากเราทราบขนาดกรง $Z$ เราสามารถ "ละเว้น" (ignore) แมวขนาดเล็กไม่เกิน $Z$ ได้เลย จะไม่เกิดปัญหาอะไรขึ้นทั้งนั้น

เช่น 3 5 2 2 5 3 หากกรงขนาด $Z = 2$ เราสามารถพิจารณาแค่ 3 5 5 3 (ละเว้นแมวขนาด $2$ ออก) แต่หากกรงขนาด $Z = 3$ เราจะพิจารณาแค่ 5 5 (ละเว้นแมวขนาดน้อยกว่าหรือเท่ากับ $3$ ออก) จะเห็นว่าเหลือเพียง แมวขนาด $5$ ซึ่งตรงตามเงื่อนไขแล้ว

ต่อมา ขั้นตอนวิธีการตรวจสอบว่าการจัดแมวแบบปัจจุบันนั้น ถูกต้องตามเงื่อนไขหรือไม่ สามารถทำได้โดยง่าย ดังนี้

int cats[2000005]; // Let cats' indices be 1-based
int N;             // Let N be the number of cats
bool ok = true;
for (int i = 1; i <= N; i += 2) {
  if (cats[i] == cats[i + 1]) {
    // Perfectly OK
  } else {
    ok = false;
    break;
  }
}
// ok is now the status of cats array

ดังนั้นตอนนี้เราจึงมีอัลกอริทึมที่สามารถทำงานในเวลา $\mathcal{O}(N \max{s_i})$ แล้ว

ต่อมา เราต้องการพัฒนาเวลาขึ้นไปอีก โดยเราสามารถสังเกตได้ว่า ไม่จำเป็นต้องลองหา $Z$ ทุกค่า เรารู้ว่าคำตอบจะต้องเป็นหนึ่งในค่า $s_i$ แน่ๆ หรือไม่ก็ตอบ $0$ (เพราะหากไม่ตอบ $0$ แสดงว่าจะต้องเกิดการย้ายแมวอย่างน้องหนึ่งครั้ง และสมมติคำตอบเป็น $Z$ โดยที่ไม่เท่ากับ $s_i$ ใดๆ จะเห็นได้ว่า $Z-1$ ก็สามารถย้ายแมวได้ชุดเดียวกันกับ $Z$ เสมอ) เราจึงไล่ $Z$ เฉพาะค่าใน $s_i$

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

ถึงแม้ว่าเราจะทำได้รวดเร็วขึ้นอย่างมากแล้วก็จะยังไม่เพียงพอต่อการแก้โจทย์ข้อนี้ การสังเกตต่อมาจะเป็นกระบวนการที่ได้ใช้ค่อนข้างบ่อยในวงการ Programming คือเราสังเกตว่าหาก $Z$ สามารถเป็นกรงที่ใช้งานได้ เราจะทราบแน่ๆว่า ทุกๆ กรงที่ขนาดใหญ่กว่า $Z$ ก็สามารถเป็นคำตอบได้เช่นกัน เราจึงเริ่มจากการกำหนดค่า $Z$ มั่วค่าหนึ่ง หาก $Z$ ใช้งานได้ เราจะมั่นใจได้ว่า คำตอบมีค่าไม่เกิน $Z$ แต่หากใช้งานไม่ได้ คำตอบจะมีค่ามากกว่า $Z$ แน่ๆ เราสามารถเริ่มจากการกำหนดช่วงของคำตอบที่เป็นไปได้ สมมติคือช่วง $[L, R] = [0, \max\limits_{i=1}^{N}{s_i}]$ เราสามรถทำกระบวนการดังต่อไปนี้ซ้ำไปเรื่อยๆจนกว่า $L = R$ ได้ คือสุ่ม $Z$ ในช่วง $[L, R)$ แล้วทดสอบว่า $Z$ ใช้ได้หรือไม่ หากใช้ได้ ก็ทำการเปลี่ยนค่า $R$ เป็น $Z$ หากใช้ไม่ได้ก็ทำการเปลี่ยนค่า $L$ เป็น $Z+1$ ซึ่งโดยปกติแล้วจะมีวิธีการเลือกค่า $Z$ เป็น $\frac{L+R}{2}$ จะได้ค่าที่ดีที่สุด เพราะจะทำให้แต่ละครั้งเราสามารถลด search space ได้อย่างน้อยครึ่งหนึ่ง ทำให้ใช้จำนวนครั้งที่ต้องตรวจสอบไม่เกิน $\mathcal{O}(\log \max\limits_{i=1}^{N}{s_i})$ ครั้ง (Bonus: พิสูจน์ข้อความดังกล่าว)

แต่ละครั้งที่ทำการตรวจสอบ จะใช้เวลา $\mathcal{O}(N)$ ทำให้สุดท้ายใช้เวลารวม $\mathcal{O}(N \log \max\limits_{i=1}^{N}{s_i})$ ซึ่งเป็นเวลาที่ทัน

ต่อมาสามารถ optimize ขึ้นได้อีก โดยแทนที่จะกำหนดช่วง $[L, R]$ เป็น $[0, \max\limits_{i=1}^{N}{s_i}]$ เราจะเปลี่ยนเป็น $[0, N]$ โดยในแต่ละรอบ หากเลือกตัวปัจจุบันเป็น $i (0 \leq i \leq N)$ เราจะกำหนดค่า $Z$ เป็น $ss_i$ เมื่อ $ss_i$ แทน $s$ หลัง sort จากน้อยไปมาก และ $ss_0 = 0$ (ด้วยเหตุผลข้างต้นที่ได้กล่าวไว้ว่าค่า $Z$ ที่เป็นคำตอบได้มีเฉพาะค่าใน $s_i$)

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

Bonus: มันจะมีวิธีที่ดีกว่านี้มั้ย? ลองคิดอัลกอริทึมที่สามารถแก้ปัญหาดังกล่าวในเวลา $\mathcal{O}(N)$ ดู