Modular exponentiation

Modular exponentiation: কন্টেস্ট প্রোগ্রামিংয়ে মডুলার এক্সপনেনটিয়েশন রিলেটেট প্রব্লেম মাঝে মাঝেই থাকে । বেশিরভাগ সময় নেইভ সল্যুশন  করতে গিয়ে দেখা যায় টাইম লিমিট খায় । এই ধরনের প্রব্লেমকে অপ্টিমাইজ করার জন্য কিছু টেকনিক বা অ্যালগরিদম আছে । আচ্ছা আজাইরা ইন্ট্রো গল্প বাদ দিয়ে চলেন শুরু করা যাক ।

বেসিক সমাধান -: এক্সপনেনটিয়েশনকে  নরমারলি x^n এইভাবে প্রকাশ করা হয় । তো এইটার রেজাল্ট বের করার জন্য বেসিক যেই সল্যুশন সেটা হলো x*x*x*x*......*x এইভাবে n টাইম পর্যন্ত গুন করা।  বেসিক এই সল্যুশন করতে মোটামুটি x*x^n-1 এইভাবে ভাঙতে হবে। এইটার একটা রিকারসিভ সল্যুশন যদি লেখি তাহলে কোড টা দারায় এইরকম

int power(int x,int n)

{

    if(n==0)

        return 1;

    return x*Power(x,n-1);

} 

এইটা মোটামুটি ইফিসিয়েন্টই মনে হচ্ছে তাই না ? এইটার টাইম কমপ্লেক্সিটি কত? আমিই বলে দেই O(n) । আচ্ছা প্রব্লেম ডেসক্রিপশনে যদি x^n এইখানে n এর মান যদি 10¹⁸ এইরকম থাকে তখন আমরা উপযুক্ত সমাধান পাবো ? তাহলে কি করতে হবে আমাদের আরও অপ্টিমাইজড সমাধান খোঁজা উচিৎ ।

অপ্টিমাইজড সমাধান-: x^n এর অপ্টিমাইজড সমাধান একটাই  আমাদের রান টাইম কমিয়ে নিয়ে আসতে হবে n টাইম পর্যন্ত গুন না করেই রেজাল্ট বের করতে হবে । আমরা যত তাড়াতাড়ি  x^n মান বের করতে পারবো আমাদের সল্যুশন তত ইফিসিয়েন্ট হবে।
আমাদের যেই n এর মান দেয়া থাকবে চেক করতে হবে সেইটা জোড় না বিজোড় ?
১ । n যদি জোড় হয় তাহলে x^n কে ভেঙ্গে (x^2)n/2 এই আকারে প্রকাশ করবো
  এইখানে কি হলো জাস্ট একটা স্টেপে আমরা n এর মানকে অর্ধেকে নিয়ে আসলাম । আমাদের রান টাইম আগের থেকে অনেক কম লাগতেছে কিন্তু।

২। n যদি বিজোড় হয় তাহলে n কে জোড় বানাতে হবে অর্থাৎ স্টেপটা হবে x*x^n-1 এইরকম
 উদাহরণ ঃ মনে করি আমাদেরকে 4¹⁰ এর মান বের করতে হবে। আমারা নরমালি ১০ বার ৪ কে গুন করলেই রেজাল্ট পেয়ে যাবো কিন্তু আমরা ১০ বার না আরও কম সময়েই রেজাল্টটা পেতে পারি । ওকে তাহলে স্টেপ গুলো শুরু করি

1.  এইখানে n এর মান ১০ যা একটি জোড়  সংখ্যা তাই আমরা প্রথম স্টেপেই একে ভেঙ্গে ফেলতে পারি    4¹⁰ ⥤ (4^{2)^5}⥤16⁵
2. এখন আমাদেরকে 16^5 মান বের করতে হবে । এইখানে n এর মান ৫ যা একটি বিজোড় সংখ্যা
   16⁵⥤16*16⁴⥤16*(16²)²
3. ফাইনালি আমরা 256^2 কে একটা স্টেপে গণনা করলেই রেজাল্ট পাচ্ছি । 16*256*256=1048576 

Code:

int ext(int x,int n)

{

    if(n==0)

        return 1;

    else if(n%2 == 0)        //n is even

        return exp(x*x,n/2);

    else                             //n is odd

        return x*exp(x*x,(n-1)/2);

}

তাহলে আমরা বলতে পারি এইটা একটা ইফিসিয়েন্ট ম্যাথড । আমরা ১০ স্টেপের কাজকে জাস্ট ৩ স্টেপেই করে ফেললাম ।
এইটার কমপ্লেক্সিটি হবে  O(log N)

আচ্ছা এখন এইরকম রেজাল্ট যদি আসে যেইটা ডেটা টাইপের রেঞ্জের বাইরে তখন কি করবো ? 😕😕সেইখেত্রে আমাদেরকে মডুলাস (%) ব্যাবহার করতে হবে  এবং আমাদেরকে x^n এর মান বের করার পরিবর্তে (x^n)%m বের করতে হবে ।
উদাহরণ ঃ আমরা যদি 2¹⁰⁹ এর মান বের করতে চাই তাহলে O(n) সল্যুশনে এইটা টাইমআউট হবে , O(log N) সল্যুশনে এইটা যথা সময়ে রান হবে কিন্তু গারবেজ মান দিবে । তো এই প্রবলেম থেকে বাচার জন্য অবশ্যই মডুউল অপারেশান ব্যাবহার করতে হবে ।

Code:

  

int exp(int x,int n,int M)

{

    if(n==0)

        return 1;

    else if(n%2 == 0)        //n is even

        return exp((x*x)%M,n/2,M);

    else                             //n is odd

        return (x*exp((x*x)%M,(n-1)/2,M))%M;

}

আজকে এই পর্যন্তই  হ্যাপি কোডিং 😊😊

UVA 10324 - Zeros and one

প্রব্লেম ঃ প্রবলেমটাতে  বলা হয়েছে আমাদের স্ট্রিং অথবা ক্যারেক্টার  অ্যারে সাইজটা ১০০০০০০  হতে পারবে । স্ট্রিংটাতে শুধুমাত্র '০' এবং '১' ক্যারেক্টার থাকতে পারবে। মূলত আমাদের ক্যারেক্টার থেকে  চেক করতে হবে মিনিমাম নাম্বার i এবং j এর মাজে min(i,j) এবং ম্যাক্সিমাম নাম্বার  i এবং j এর মাজে
 max (i,j) ।
সল্ভিং টেকনিক ঃ
এই প্রব্লেমটাতে টাইমের কথা চিন্তা করলে আমি ১. ৩১০ সেকেন্ডের আনতে পারি নাই। আরও ভালো  সল্যুশন হয়তো সম্ভব । প্রথমে আমরা ধরে নেই সবগুলা ক্যারেক্টার একই অর্থাৎ আমরা একটা ফ্ল্যাগ নিতে পারি এবং ফ্ল্যাগের মান ০ দেই। তারপর আমরা লুপের মাধ্যমে চেক করি  i থেকে j পর্যন্ত ক্যরেক্টার গুলো একই কিনা? যদি একই না হয় তাহলে আমরা ফ্ল্যাগের মান ১ করে দেই।  এখন ফ্ল্যাগের মান যদি ১ হয় তাহলে প্রিন্ট করি No আর যদি ফ্ল্যাগের মান ০ ই থাকে তাহলে প্রিন্ট করি Yes ।
ওকে তাহলে কোডিং শুরু করে দেন সল্ভ করার জন্য ।
আমার কোড নিচে দেওয়া আছে। আমি সি++ এ প্রব্লেমটা সল্ভ করছি। একান্ত চেষ্টা করার পরই কোডটা দেখতে পারেন।

কোড ঃ
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  int cnt=1;
  while(cin>>s)
  {
      if(s.size()==0)
        break;
   int a,b,c,flag;
   cin>>a;
   cout<<"Case "<<cnt<<":"<<endl;
   while(a--)
   {
       flag=0;
       cin>>b>>c;
       if(b>c)
         swap(b,c);
       for(int j=b+1;j<=c;j++)
       {
           if(s[b]!=s[j])
            flag=1;
       }
       if(flag==0)
        cout<<"Yes"<<endl;
        else
        cout<<"No"<<endl;
   }
   cnt++;
  }
   return 0;
}

UVA 10302 solve:

10302 - Summation of Polynomials

#include<bits/stdc++.h>

using namespace std;

int main()

{

    long  long int n;

        while(scanf("%lld",&n)==1)

        {

        printf("%lld\n",(n*n*(n+1)*(n+1))/4);

        }

    return 0;

}