CP আর interview pack: উত্তরের উপর binary search, LIS আর bug gallery

SPOJ হলো contest problem-এর বড় একটা archive-ওয়ালা online judge। ওখানে AGGRCOW নামে একটা classic আছে, "Aggressive cows"। Farmer John-এর গোয়ালে একটা সরল রেখা বরাবর N-টা ঘর, আর ওর C-টা গরু কাছাকাছি দাঁড়ালেই মারামারি করে। সে চায়, যেকোনো দুইটা গরুর মধ্যে সবচেয়ে কম দূরত্বটা যত বড় সম্ভব হোক। Bob সবচেয়ে বড় দূরত্ব থেকে নিচে নেমে প্রতিটা চেষ্টা করে, আর প্রতিটা চেষ্টায় সব ঘর হেঁটে দেখে। Amara আরও ভালো একটা জিনিস খেয়াল করে: গরুগুলো 3 দূরে দূরে আঁটলে 2 দূরে দূরেও আঁটবে। যে হ্যাঁ একবারই না-তে বদলায়, সেটা একটা sorted সারি, আর sorted সারিকে অর্ধেক করা যায়।