Next Permutation

সাবটাস্ক 1 এর জন্য:

সাবটাস্ক 1 এর জন্য আমরা 1 থেকে 9 দৈর্ঘ্যের যত পারমুটেশন সম্ভব সব বের করে রাখব। এই কাজটা অনেকভাবে করা যায়। সবচেয়ে সহজ হল C++ এর $next\_permutation()$ ফাংশন ব্যবহার করা। এই ফাংশন ব্যবহার করে লেক্সিগ্রাফিকালি পরবর্তী পারমুটেশন পাওয়া যায়।

সব সাবটাস্কের জন্য কিছু কথা:

সবার আগে আমরা দেখি কোন ক্ষেত্রে সমাধান অসম্ভব। ধরি, প্রদত্ত পারমুটেশনটা হল $p[0 \dots n-1]$ এবং এতে $d$ সংখ্যক descent রয়েছে। যদি $d = n-1$ হয়, এটা সবচেয়ে বড় পারমুটেশন, সুতরাং এক্ষেত্রে পরবর্তী পারমুটেশনের অস্তিত্ব নেই। যদি $d=0$ হয়, তবে এটা সবচেয়ে ছোট পারমুটেশন এবং বাকি সকল পারমুটেশনের অন্তত একটা descent রয়েছে, তাই এক্ষেত্রেও পরবর্তী পারমুটেশনের অস্তিত্ব নেই। অন্য ক্ষেত্রে পরবর্তী পারমুটেশনের অস্তিত্ব থাকবে না যদি এটা $d$ descent বিশিষ্ট পারমুটেশনগুলোর মধ্যে সবচেয়ে বড় হয়। $d$ descent বিশিষ্ট পারমুটেশনগুলোর মধ্যে সবচেয়ে বড়টা হল: ${N, N-1,\dots, N-d+1, 1, 2, \dots, N-d}$। এটা এমন একটা পারমুটেশন যার প্রথমে সবচেয়ে বড় $d$ টা উপাদান বড় থেকে ছোট ক্রমে রয়েছে এবং বাকিগুলা ছোট থেকে বড় ক্রমে রয়েছে। এগুলো ছাড়া বাকি সব ক্ষেত্রে সমাধান সম্ভব।

মনে করি আমাদের কাছে একটা বুলিয়ান ফাংশন $f(n, x, d)$ আছে যা বলে দেয় $n$ সংখ্যক উপাদান নিয়ে $d$ সংখ্যক descent অর্জন করা যায় কি না যেখানে এদের পূর্বের উপাদানের order হবে $x$ (অর্থাৎ, পূর্বের উপাদান ঐ $n$ সংখ্যক উপাদানের $x-1$ টা থেকে ছোট; আর স্পষ্টভাবে বললে, প্রথম উপাদানটা 1 থেকে $x-1$ এর মধ্যে হলে প্রথম উপাদানের বামে একটা descent তৈরি হবে, নতুবা নয়)। এই ফাংশন ব্যবহার করে আমরা পরবর্তী পারমুটেশনটা বের করব।

সাফিক্স ধাপ: প্রদত্ত পারমুটেশনটার একটা সাফিক্স বিবেচনা কর, আমরা শুধু এই অংশে পরিবর্তনটা আনতে চাই। যেহেতু সবচেয়ে ছোট পারমুটেশন বের করতে চাই এই সাফিক্সের দৈর্ঘ্যে যথাসম্ভব ছোট রাখতে হবে। $i = n-2$ থেকে শুরু করে $i=0$ পর্যন্ত একটা লুপ চালাব, কোন $i$ এর জন্য $p[i]$ থেকে $p[n-1]$ পর্যন্ত উপাদানগুলোকে কোনভাবে সাজিয়ে আমরা উদ্দেশ্য সাধন করতে চাই। ধরি আমাদের সমস্যার সমাধান হল $q[0\dots n-1]$। এখানে অবশ্যই $p[i] < q[i]$ এবং $i$ থেকে $n-1$ ইনডেক্স পর্যন্ত $p$ তে যে উপাদানগুলো আছে, $q$ তেও সেই উপাদানগুলো আছে। এখন $p$ এর এই সাফিক্সের উপাদানগুলোকে ছোট থেকে বড় একটা একটা করে বিবেচনা করি। ধরি এখন $z$ বিবেচনা করছি, তাহলে $q[i]=z$ এবং $z > p[i]$। এখন আমরা ফাংশন $f$ ব্যবহার করে সমাধানের অস্তিত্ব যাচাই করে দেখতে চাই, তবে তার জন্য কত descent অর্জন করতে হবে তা খুঁজে বের করতে হবে। ধরি, $p[i]$ থেকে $p[n-1]$ এর মধ্যে মোট descent সংখ্যা $d$। তাহলে কি আমরা বলতে পারি না $q[i]$ থেকে $q[n-1]$ এর মধ্যে $d$ সংখ্যক descent থাকতে হবে? তবে এখানে একটা কেস আছে; যদি $p[i-1] > p[i]$ এবং $p[i-1] < z$ হয়, তাহলে আমাদের বাম দিকে একটা descent কমে যাচ্ছে। এই descent টা অবশ্যই $q[i]$ থেকে $q[n-1]$ এর মধ্যে চলে আসতে হবে। সুতরাং, যদি $p[i-1] > p[i]$ এবং $p[i-1] < z$ হয়, $d$ এর মান 1 বাড়িয়ে দিবে। এখন তাহলে $f(n-i-1, x, d)$ সত্য হলে আমরা বলতে পারি, $q[i] = z$ ব্যবহার করে একটা সমাধান আছে এবং আমরা সমাধান বের করার পর্বরতী বিল্ডিং ধাপে চলে যেতে পারব। কিন্তু $x$ কত হবে? $p[i]$ থেকে $p[n-1]$ উপাদানগুলোর মধ্যে যতটা $z$ হতে ছোট + 1।

বিল্ডিং ধাপ: এখন আমরা জানি $q[i] = z$ হবে। এরপরে $j = i+1$ থেকে $j = n-1$ পর্যন্ত একটা একটা করে উপাদান বসাতে থাকব। কোন একটা $j$ এর জন্য অবশ্যই আমি এখানে সম্ভাব্য সবচেয়ে ছোট উপাদানটা বসাব। কোন একটা উপাদান স্থির করে, সমাধান সম্ভব কিনা যাচাই করার জন্য $f$ ফাংশন ব্যবহার করতে পারব।

ফাংশন $f$ আপাতত বিবেচনায় না আনলে, প্রতি টেস্টকেসে এই দুই ধাপের কমপ্লেক্সিটি দাঁড়ায় $O(n^2)$। এই দুই ধাপ সাবটাস্ক 2, 3 এবং 4 এর জন্য মোটামুটি একই। এখন আসি $f(n, x, d)$ কেমনে বের করবে তাতে।

যদি তোমার শুধু পূর্ণ সমাধানের প্রতি আগ্রহ থাকে, তবে তুমি চাইলে সাবটাস্ক 2 ও 3 এর বর্ণনা না পড়ে এগিয়ে যেতে পারো

সাবটাস্ক 2 এর জন্য:

$f(n, x, d)$ ফাংশনটা এই রিকারেন্স রিলেশন মেনে চলেঃ প্রত্যেক $i$ $(1 \leq i \leq n)$ এর জন্য, সকল $f(n-1,i, d-less(i, x))$ এর OR অর্থাৎ এদের মধ্যে অন্তত একটা সত্য হলেই কেবল $f(n, x, d)$ সত্য হবে। এখানে, যদি $i < x$ হয়, $less(i, x) = 1$ হবে অন্যথায় $less(i, x) = 0$ হবে।

DP দিয়ে এই কাজটা $O(n^4)$ কমপ্লেক্সিটিতে করা যায়। খেয়াল কর যে, এই DP প্রত্যেক টেস্টকেসের জন্য একই, সুতরাং কমপ্লেক্সিটি দাঁড়ায় $O(T\cdot n^2 + n^4)$।

সাবটাস্ক 3 এর জন্য:

উপরের DP এর স্টেট 3 টা, দেখা যাক ভিতরের লুপটা বাদ দেওয়া যায় কি না। খেয়াল কর যে, $i < x$ হলে, সবসময় আমরা $f(n-1, i, d-1)$ কল করি, অন্যথায় $f(n-1, i, d)$ কল করি। তাহলে, $g(n, x, d)$ হল, সকল $f(n-1, i, d-1)$ এর OR যেখানে $1 \leq i \lt x$ । আর $h(n, x, d)$ হল, সকল $f(n-1, i, d)$ এর OR যেখানে $x \leq i \leq n$। অর্থাৎ $g$ হল একটা প্রিফিক্স OR ফাংশন আর $h$ হল একটা সাফিক্স OR ফাংশন। দুইটাই $O(n^3)$ কমপ্লেক্সিটিতে করা যাবে। তাহলে দাঁড়ায়, $f(n,x,d) = g(n,x,d)|h(n,x,d)$। সুতরাং $f$ এর কমপ্লেক্সিটিতও $O(n^3)$ তে নেমে আসে। মোট কমপ্লেক্সিটি দাঁড়ায় $O(T\cdot n^2 + n^3)$।

সাবটাস্ক 4 এর জন্য:

এখন আমরা $f(n, x, d)$ এর মান $O(1)$ এ বের করা শিখব :p কেস এনালাইসিস করে আগানো লাগবে। $n$ সংখ্যক উপাদানের মাঝে $n-1$ সংখ্যক descent থাকতে পারে, তবে $x$ এর উপরে নির্ভর করে $n$ টাও হতে পারে।

• প্রথমত, যদি $d > n$ অথবা $d < 0$ হয়, তবে সম্ভব না।
• যদি $d = 0$ হয়, তবে সকল উপাদান ছোট থেকে বড় ক্রমে থাকতে হবে এবং সবচেয়ে ছোট উপাদানটা $x$ হতে বড় হতে হবে। অর্থাৎ, $d = 0$ হলে, উত্তর হবে $x==1$।
• একইভাবে যদি $d=n$ হয়, তবে সকল উপাদান বড় থেকে ছোট ক্রমে থাকতে হবে এবং সবচেয়ে বড় উপাদানটা $x$ থেকে ছোট হতে হবে। অর্থাৎ $d=n$ হলে, উত্তর হবে $x==n+1$।

বাকি সব ক্ষেত্রে সমাধান সম্ভব! কিভাবে? সবগুলা সংখ্যাকে ছোট থেকে বড় ক্রমে বসিয়ে দিব। এখন যদি, $x > 1$ হয়, তবে ঐখানে একটা descent চলে আসবে এবং $d$ এর মান 1 কমিয়ে দিব। এরপরে শেষের $d+1$ সংখ্যক উপাদানকে আমরা উল্টিয়ে (reverse) দিব, ফলে $d$ সংখ্যক descent চলে আসবে।

খেয়াল কর, এইখানে আমরা উপরে বর্ণিত বিল্ডিং ধাপের জন্য একটা এলগোরিদম পেলাম যেটা $O(n\log{}n)$ এ কাজ করে (চাইলে $O(n)$ এও করা যাবে)। এটা পরবর্তী সাবটাস্কের জন্য কাজে লাগবে।

সাবটাস্ক 5 এর জন্য:

এখন আমাদের $f(n, x, d)$ কাজ করে কন্সট্যান্ট টাইমে। আমাদের বিল্ডিং ধাপ কাজ করে লিনিয়ার টাইমে। বটলনেক হল সাফিক্স ধাপ, যেখানে এখনো $O(n^2)$ সময় লাগছে। ইনডেক্স $i$ থেকে শুরু হওয়া একটা সাফিক্স ঠিক করার পরে, $p[i]$ থেকে বড় সকল উপাদান নিয়ে যাচাই করে দেখা লাগছে $q[i]$ তে এটা বসিয়ে সমাধান সম্ভব কি না। সকল উপাদান আসলে বিবেচনায় আনার দরকার নেই। বরং ব্যাপ্তির সীমানা (border case) গুলা নিয়ে যাচাই করলেই হবে :p

• $p[i]$ থেকে বড় উপাদানগুলোর মধ্যে সবচেয়ে ছোটটা
• $p[i]$ থেকে বড় উপাদানগুলোর মধ্যে সবচেয়ে বড়টা
• যদি $i > 0$ হয়, তবে $p[i-1]$ থেকে বড় উপাদানগুলোর মধ্যে সবচেয়ে ছোটটা (অবশ্যই এটা $p[i]$ থেকে বড় হওয়া লাগবে)

যেহেতু আমরা যাচাই কন্সট্যান্ট টাইমে করতে পারছি, আমাদের পুরো সমাধানটা $O(n\log{}n)$ এ চলে আসল। $f(n,x,d)$ তে $x$ এর মান ইনপুট দেওয়ার জন্য আমাদের order জানিয়ে দেয় এমন একটা ডাটা স্ট্রাকচার লাগবে, সেটা হতে পারে Fenwick Tree বা তোমার পছন্দের কোন ডাটা স্ট্রাকচার।