Dev Skill: Game of MODs

Problem link: Game of MODs

In this problem, we are given an integer n with q queries. Each query we have k integer. We need to calculate the maximum and minimum number can be formed after removing k digits from n. Here the digits won't change their position.

Solution: Some things to observer first.

• If k == size of n (digits), then the answer would be 0 0
• If there are leading zeros, we need to remove them, say we got a number like 000000009. this should be changed to 9.
• If we have only 0 digit, then the answer would be zero

We will use recursion technique for building up our desired result. The idea is that a character among first (k+1) characters must be present in the resultant number. So we pick the first (k+1) smallest or largest depending on the situation. Put it on the result, then recur for remaining characters.
This is done in the legend function below. I used a counter variable for checking whether we are creating maximum or minimum number. Look at line 18 for understanding. Only the change in the index can produce two defferent result. Complexity is O(n), the number of digits. Considering all the cases, queries, complexity would be 100*200*11 = 220000

স্ট্রিং ( String )

  স্ট্রিং(String)

স্ট্রিং একটি বেশ মজার এবং কাজের ডাটা স্ট্রাকচার। এর কাজ নরমাল ক্যারেক্টার অ্যারে এর মতই, কিন্তু এর ব্যবহার খুব সহজ এবং অনেক কাজ অনেক সহজে করা যায়। স্ট্রিং এর জন্য হেডার ফাইল : #include<string>
একটি কোড দেখা যাক -->

#include<string>
using namespace std;
int main()
{
                string a; // স্ট্রিং টাইপ একটি ভ্যারিয়েবল 'a' ডিক্লার করলাম
                cin >> a; // user থেকে ইনপুট নিলাম
                cout << a << endl; // ইনপুট এর স্ট্রিং প্রিন্ট করলাম
                return 0;
}

স্ট্রিং এর ক্ষেত্রে এভাবে নিয়ে আমরা স্ট্রিং প্রিন্ট করতে পারি। কিন্তু এখানে স্পেস এর পরে কোন ক্যারেক্টার প্রিন্ট হবেনা। তোমরা ইনপুট নিয়ে দেখতে পারো। এরকম ক্ষেত্রে আমরা তাহলে কি করবো? আমাদের দরকার পুরা একটি লাইন ইনপুট নেয়া। এরজন্য ইনপুট নিতে হবে এভাবে-->

getline ( cin, a );

getline() ফাংশন এর কাজ হচ্ছে লাইন শেষ না হওয়া পর্যন্ত ইনপুট নিবে। এখন আমরা স্পেস সহ ইনপুট নিতে পারবো। উপরের কোড এ cin>>a এর বদলে getline (cin,a) লিখে তোমরা ব্যাপারটা দেখতে পারো।

স্ট্রিং এর মজার ব্যাপার হচ্ছে স্ট্রিং কে আরেক স্ট্রিং এ সরাসরি কপি, অ্যাড করা যায়।

string a,b,c;
a = "I eat rice";
b = " and I eat pizza.";
c = a + b;
cout << c << endl;          // এখানে আউটপুট হবে : "I eat rice and I eat pizza"

সুন্দরভাবে concatanation হয়ে গেলো!! সি তে char array নিয়ে করতে গেলে ব্যাপারটা এত সহজ না।

string.size() ফাংশন স্ট্রিং এর সাইজ রিটার্ন করে (integer).
কোন একটি স্ট্রিং কে উলটা করে লিখার জন্য আমরা এভাবে for loop ব্যবহার কতে পারি-->

string a;
cin >> a;
int len = a.size();
string b = "";                 // একটি empty string ডিক্লার করলাম
for ( int i = len-1, pos = 0; i >= 0; i--, pos++ )
b [ pos ] = a [ i ];
cout << b << endl;       // রিভার্স করা স্ট্রিংটি 'b' এর মধ্যে আছে এখন।

সি++ এ আমরা reverse() ফাংশন ব্যবহার করে স্ট্রিং কে কোন লুপ কোড লিখা ছাড়াই রিভার্স করতে পারি এভাবেঃ
reverse ( a.begin(), a.end() );    // a = string variable

স্ট্রিং অনেকগুলি ক্যারেক্টার এর একটি অ্যারে। তাই নরমাল সি এর char array এর মত স্ট্রিং কেও ইনডেক্স অনুযায়ী এক্সেস করা যায়, প্রসেস করা যায়। যেমন, স্ট্রিং a এর 0th ইনডেক্স এর ক্যারেক্টার হবেঃ a [ 0 ]

স্ট্রিং একটি নরমাল ডাটা টাইপ (like int,float,double), কাজেই এটাকে আমরা অন্যান্য ডাটা টাইপ লিখার জন্য যেভাবে লিখি, সেভাবে লিখতে পারবো।
স্ট্রিং এর ভেক্টর: vector < string > string_vec;
স্ট্রিং এর স্ট্যাক: stack < string > string_stack;  এরকম।

স্ট্রিং এর জিনিসগুলি ভালোভাবে রপ্ত করার জন্য তোমরা নিচের সমস্যাগুলি চেষ্টা করতে পারোঃ

১। একটি স্ট্রিং প্যালিন্ড্রম কিনা চেক কর।
example :
hello -> not palindrome
1234321 -> palindrome
wecanacwe ->not palindrome

২। একটি স্ট্রিং দেয়া হবে। যেখানে কেবলমাত্র 0 এবং 1থাকবে। একে ডেসিমাল ভ্যালুতে প্রকাশ কর
example :
00000010 -> the decimal value is 2
111 -> the decimal value is 7

৩। একটি স্ট্রিং এ মোট কতটি ওয়ার্ড আছে এবং কিকি লিখ।
example :
Hello, how are you ?
--> there are 4 words. They are : Hello, how, are, you.

Lexicographic rank of a string(without duplicate character)

লেক্সিকোগ্রাফিক বলতে বুঝায় অ্যালফাবেটিকাল অর্ডার। যেমনঃ কোন স্ট্রিং "xyz" হলে, আমরা বলতে পারি এই স্ট্রিং এর লেক্সিকোগ্রাফিক অর্ডারের প্রথমে আছে "xyz", এরপরে "xzy" .. অর্থাৎ স্ট্রিং এর সকল পারমুটেশন এর সিরিয়াল, যারা কিনা ছোট থেকে বড় আকারে সর্টেড অবস্থায় আছে। এখন এরকম একটি স্ট্রিং দেখে আমাদের বলতে হবে এর র‍্যাঙ্ক কত। যেমনঃ "abc" এর ক্ষেত্রে, rank of "abc" = 1, rank of "acb" = 2 .... এভাবে।
একদম ব্যাসিকভাবে চিন্তা করলে আমরা সকল পারমুটেশন জেনারেট করে দেখতে পারি যে স্ট্রিং টি কততম পারমুটেশন এর সাথে মিলে গেছে। তাহলে সেটিই আমাদের স্ট্রিং এর র‍্যাঙ্ক।



এভাবে আমাদের টাইম কমপ্লেক্সিটি অনেক বেড়ে যাবে, প্রায় এক্সপোনেন্ট হারে!! (exponent) এজন্য আমাদের আরো ভালো এপ্রোচ দরকার।
আমরা একটি স্ট্রিং ধরি, "FRIEND" এর র‍্যাঙ্ক বের করতে হবে। এখানে প্রথম ক্যারেক্টার  "F" এবং "F" এর চেয়ে ছোট ২ টি ক্যারেক্টার আছে ("D", "E") এবং "F" কে তার জায়গায় ফিক্সড করলে আমাদের বাকি থাকে আরো ৫ টি জায়গা এবং "F" এর আগের ২ টি ক্যারেক্টার ঐ ৫ টি জায়গায় বসতে পারবে ৫ ফ্যাক্টরিয়াল (5!) উপায়ে। তাহলে ২ টির জন্য কম্বিনেশন হবে ২*৫!
এখন আমরা তাহলে "F" এর কাজ শেষ হলে, "F" কে ফিক্সড করে দেই। মানে "F" নিয়ে আমাদের আর মাথা ব্যথা করতে হবে না। এখন দ্বিতীয় ক্যারেক্টার "R" নিয়ে দেখি। "R" এর চেয়ে ছোট ৪ টি ক্যারেক্টার আছে ("D", "E", "I", "N"). ["F" কে আমরা ফিক্সড করে দিয়েছি, কাজেই "F" বাদ] 
তাহলে আমরা "R" এর জন্য পাবোঃ ২*৫! + ৪*৪! (আগের "F" এরগুলোও ধরতে হবে)।
একই ভাবে আমরা বাকি ক্যারেক্টার গুলোর জন্য করে ফেলিঃ

"I" = 2*5! + 4*4! + 2*3!
"E" = 2*5! + 4*4! + 2*3! + 1*2!
"N" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1!
"D" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0!
তাহলে, "FRIEND" এর জন্য র‍্যাঙ্ক হবে ঃ 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0! = 351
যেহেতু, র‍্যাঙ্ক ১ থেকে শুরু হয়, কাজেই আমাদের ফাইনাল রেজাল্ট হবে 1 + 351 = 352.



এর কপ্লেক্সিটি O(n²)। আমরা একটু বুদ্ধি খাটালে এর কমপ্লেক্সিটিকে কমিয়ে আনতে পারবো। এজন্য আমরা কিউমুলেটিভ ভাবে প্রতিটি ক্যারেক্টারের চেয়ে ছোট ক্যারেক্টারকে একটি অ্যারেতে সেভ করে রাখবো।এরপরে প্রতিবার সেখান থেকে কাউন্ট নিয়ে আমরা কাজ করবো O(n) কপ্লেক্সিটিতে