CF#1550C এবং এর্ডোস-সেকেরেস থিওরেম

28 January 2025 · 3 min read

এর্ডোস-সেকেরেস থিওরেম(এরোস-সেকেরেস থিওরেম): যদি $n^2 + 1$ টি বাস্তব সংখ্যার একটি সিকুয়েন্স দেওয়া থাকে, তাহলে ঐ সিকুয়েন্স হতে অন্তত একটি মনোটনিক সাবসিকুয়েন্স (monotonic subsequence) পাওয়া যাবে, যার লেন্থ হবে $n+1$ ।

সিকুয়েন্স বা ধারা নিয়ে আশা করি সবার জানা আছে, ক্রমানুসারে সাজানো যেকোন বস্তুর সমষ্টি। হতে পারে তা সংখ্যা বা অন্যকিছু। যেমন $2, 3, 5, 7, 11, 13, 17$ একটি সিকুয়েন্স, যা $2$ থেকে $17$ পর্যন্ত সব মৌলিক সংখ্যাকে নির্দেশ করছে। আর সাবসিকুয়েন্স হলো, ঐ মূল সিকুয়েন্স থেকে কিছু উপাদান বা সংখ্যা বাদ দিয়ে নতুন আরেকটি ধারা, তবে উপাদান বা সংখ্যাগুলোর ক্রম অপরিবর্তিত থাকবে বা মূল সিকুয়েন্সের মতোই হতে হবে। যেমন, $2, 3, 5$ একটি সাবসিকুয়েন্স। কিন্তু, $2, 5, 3$ নয়, কেননা এটি আমাদের সিকুয়েন্সের ক্রমানুসারে হচ্ছে না। আবার $5, 6, 7$ ও সাবসিকুয়েন্স নয়, কেননা $6$ আমাদের মূল সিকুয়েন্সে নেই।

এবার মনোটনিক সিকুয়েন্স নিয়ে বলা যাক:

$1, 2, 3, 3, 5, 7, 8, 9, 9, 10, 11, 14$ এই ধারাটি লক্ষ করা যাক। এখানে প্রতিটি পদ তার পরের পদের চেয়ে ছোট বা সমান। অর্থাৎ, $a_i \leq a_{i+1}$ । এই টাইপের সিকুয়েন্স করে বলে Non-decreasing/ weekly increasing sequence।

$1, 2, 3, 5, 7, 8, 9, 10, 12, 14, 15$ , এই সিকুয়েন্সটিতে প্রতিটি পদ তার পরের পদের চেয়ে ছোট। অর্থাৎ $a_i < a_{i+1}$ । এদের increasing বা strictly increasing সিকুয়েন্স বলে।

$9, 9, 7, 5, 5, 2, 1, 1, 1$ , এখানে প্রতিটি পদ তার পরের পদের চেয়ে বড় বা সমান। অর্থাৎ $a_i \geq a_{i+1}$ , যা non-increasing sequence/weakly decreasing নামে পরিচিত।

$9, 8, 5, 3, 1, -5$ , এখানে প্রতিটি পদ তার পরের পদের চেয়ে বড়, $a_i > a_{i+1}$ , যা decreasing বা strictly decreasing sequence বলে।

আর এই চার ধরনের সিকুয়েন্সকেই বলা হয় মনোটনিক সিকুয়েন্স। এক কথায় সব strictly/weakly increasing এবং decreasing সিকুয়েন্সই মনোটনিক সিকুয়েন্স ।

আবার আমাদের থিওরেমে ফিরে আসা যাক। এবার $n=2$ , ধরি তাহলে $n^2 + 1 = 5$ লেন্থের যেকোন একটি সিকুয়েন্স নিই। ধরলাম, $7, 2, 5, 3, 9$ , দেখতে পাব $2, 5, 9$ একটি মনোটনিক সাবসিকুয়েন্স / strictly increasing subsequence।

Array: $[1, 2, 3, 4]$
Subarray: $[1, 2, 3, 4]$ , $[1, 2, 3]$ , $[2, 3, 4]$ , $[1, 2]$ , $[2, 3]$ , $[3, 4]$ , $[1]$ , $[2]$ , $[3]$ , $[4]$

এবার আমাদের কোডফোর্সেসের সমস্যায় আসি।

কোডফোর্সেস থেকে পড়ে আসতে : C. Manhattan Subarrays

যেখানে একটি অ্যারে দেওয়া আছে, আমাদের বলতে হবে এমন সব সাব-অ্যারের সংখ্যা যেখানে এমন কোনো তিনটি পয়েন্ট $p, q, r$ পাওয়া যাবে না, যাতে $d(p, r) = d(p, q) + d(q, r)$ হয়। এখানে $d$ ফাংশন দিয়ে Manhattan distance বুঝানো হচ্ছে। যেখানে, $d(p, q) = \lvert x_p - x_q \rvert + \lvert y_p - y_q \rvert$

আর আমাদের যেকোন একটি পয়েন্ট $p(x, y)$ হলে, এর $y$ হবে অ্যারের index এবং $x$ হবে ঐ ইনডেক্সের ভ্যালু।

এবার একটু ভাবা যাক কখন $d(p, r) = d(p, q) + d(q, r)$ ?

$d(p, r) = d(p, q) + d(q, r)$ তখন-ই সত্য হবে, যখন $q$ পয়েন্টটি $p$ এবং $r$ এর মাঝের কোনো পয়েন্ট হবে। $p \leq q \leq r$ অথবা $p \geq q \geq r$ এরকম কিছু হয়, যা মনোটোনিক সিকুয়েন্স! যদি এরকম কোনো পয়েন্ট আমরা পাই, তাহলে ঐ সাব-অ্যারেটি বাদ। মানে কাউন্ট করব না।

এখন যদি আমরা প্রত্যেকটি সাব-অ্যারের জন্য এভাবে কাউন্ট করতে যায়, তাহলে তার কমপ্লেক্সিটি হয়ে দাঁড়াবে $O(N(N+1)/2) = O(N^2)$ । কেননা আমাদের $N$ লেন্থের একটি অ্যারেতে সাব-অ্যারে থাকে $N \times (N+1)/2$ ।

এবার এর্ডোস-সেকেরেস থিওরেম থেকে জানতে পারি $n^2 + 1$ লেন্থের একটি সিকুয়েন্সের মধ্যে অবশ্যই একটি সিকুয়েন্স থাকবে $n+1$ লেন্থের, যা মনোটোনিক সাবসিকুয়েন্স হবে। তাহলে, আমাদের $p, q, r$ মানে তিন লেন্থের একটি সাবসিকুয়েন্স দরকার, যা মনোটোনিক হয়। এর জন্য আমাদের সর্বোচ্চ $n+1 = 3 \Rightarrow n=2$ , $n^2 + 1 = 2^2 + 1 = 5$ লেন্থের একটি সাব-অ্যারের দরকার। তাহলে আমাদের প্রত্যেকটি সাব-অ্যারের সর্বোচ্চ লেন্থ ৪ এর বেশী হবে না। কেননা, ৫ হলেই ৩ লেন্থের একটি সাব-সিকুয়েন্স অবশ্যই পাওয়া যাবে । এখন আমরা $O(N)$ এ সল্ভ করে ফেলতে পারি।

আরেকটা বিষয় মনে করে দিই, আমাদের ১ এবং ২ লেন্থের সব সাব-অ্যারেই কিন্তু $GOOD$ , মানে কাউন্ট করতে হবে। যদি আমাদের অ্যারের লেন্থ হয় $N$ , তাহলে আমাদের $N$ টি এক লেন্থের সাব-অ্যারে এবং $N-1$ টি দুই লেন্থের সাব-অ্যারে আছে।

কোড:

#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
bool check(int px, int py, int qx, int qy, int rx, int ry){
	return ((abs(px-rx)+abs(py-ry)) != (abs(px-qx)+abs(py-qy)+abs(qx-rx)+abs(qy-ry)));
}
 
int32_t main() {
  int t;
  cin >> t;
 
  while (t--) {
    int n;
    cin >> n;
    int arr[n+1];
    for(int i=0; i<n; i++) cin >> arr[i];
    int ans = n+(n-1);
    for(int i=0; i<n; i++){
    	for(int j=i+2; j<n; j++){
    		if(j >= n) break;
    		bool ok = true;
    		for(int p=i; p<=j-2; p++){
    			for(int q=p+1; q<j; q++){
    				ok &= check(p,arr[p],q, arr[q], j, arr[j]);
    			}
    			if(!ok) break;
    		}
    		if(ok) ans++;
    		else 	break;
    	}
    }
    
    cout << ans << "\n";
    
  }
}

এখানে কখনোই j এর মান i থেকে শুরু করে i+5 এর পর্যন্তই যেতে পারবে না, n নাহয় দূরে থাক ।

Originally published on WordPress; comments live there.