LightOj 1307 - Counting Triangles Solution

Problem:

N সংখ্যক stick এর দৈর্ঘ্য দেয়া আছে । বলতে হবে এই Stick গুলি দিয়ে কত উপায়ে একটি valid ত্রিভুজ বানানো যাবে ।

constraints:

• $3\leq N \leq 2000$
• $1 \leq length \quad of  \quad each \quad  stick \leq 10^9$

Problem link: Lightoj 1307

Solution:

একটি valid ত্রিভুজ তখনই হবে, যদি এর যে কোন দুই বাহুর যোগফল এর ৩য় বাহুর চেয়ে বড় হয় । 

আমরা যদি ৩ টা নেস্টেড লুপ চালিয়ে all possible way তে সল্ভ করার চেষ্টা করি তবে অবশ্যই TLE খাবে ।

তাহলে, আমরা কি করতে পারি ?

আমরা প্রথমেই stick গুলোকে সর্ট করে নেই । 

এখন, প্রতিটা stick নিয়ে দেখব এর সাথে আর কোন দুইটি stick নিলে সেটা valid ত্রিভুজ হবে ।

২য় stick এর জন্যও কিন্তু আমরা লুপ চালিয়ে প্রতিটাই একবার করে নিয়ে দেখতে পারি, কারণ দুইটা নেস্টেড লুপ চালালেও TLE খাবে না, কারণ $N\leq 2000$ ।

তাহলে, এখন দেখতে হবে এই দুইটা stick এর সাথে কত উপায়ে ৩য় stick নির্বাচন করা যায়।

শর্ত মতে, ১ম বাহু + ২য় বাহু > ৩য় বাহু হতে হবে ।

অতএব, আমাদের দেখতে হবে  - ১ম বাহু ও ২য় বাহুর যোগফল অপেক্ষা ছোট, এমন কতগুলো stick আছে । 

যেহেতু stick গুলো সর্টেড আছে, তাই আমরা বাইনারি সার্চ করেই এটা বের করতে পারি । যেহেতু একই ভ্যালু রিপিট হতে পারে, অতএব আমাদেরকে upper bound বের করতে হবে । এতে করে আমাদের আরেকটা লুপ চালাতে হবে না । বাইনারি সার্চের কমপ্লেক্সিটি $O(log(n))$, অতএব আমাদের টোটাল কমপ্লেক্সিটি হচ্ছে $O(N^2log(n))$

upper_bound ওই ইন্ডেক্স এর pointer return করে যেই ইন্ডেক্স এর মান সার্চ করা মানের চেয়ে বড় । তার মানে ওই index এর আগে পর্যন্ত যে কোন মান সার্চ করা value এর চেয়ে ছোট বা সমান ।

তাহলে upper_bound দিয়ে আমাদেরকে সার্চ করতে হবে (১ম বাহু + ২য় বাহু - ১) । ২য় লুপ যদি j দিয়ে চালানো হয়, তবে এই (index - j) সংখ্যক stick কে ১ম ও ২য় বাহুর সাথে ৩য় বাহু হিসেবে ব্যবহার করা যাবে ।

Code: