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:

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	int main()
	{
	//freopen("in.txt", "r", stdin);
	//freopen("in.txt", "w", stdout);
	//ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, t;
	cin>>t;
	for(int cas = 1;cas<=t;cas++)
	{
	cin>>n;
	vector<int> a;
	for(int i = 0;i<n;i++)
	{
	int x;
	cin>>x;
	a.push_back(x);
	}
	sort(a.begin(), a.end());
	ll cnt = 0LL;
	for(int i = 0;i<n;i++) for(int j = i+1;j<n-1;j++)
	{
	int ind = upper_bound(a.begin(), a.end(), a[i]+a[j]-1) - a.begin()-1;
	cnt+= ind - j;
	}
	cout << "Case " << cas << ": " << cnt << "\n";
	a.clear();
	}
	return 0;
	}

view raw LightOj 1307 - Counting Triangles.cpp hosted with ❤ by GitHub