Binary Search Lower Bound and Upper Bound

#include<bits/stdc++.h>
#define N 100
using namespace std;

int ar[N+5];

int lowerBound(int itm , int sz)
{
    int lo=0, hi=sz-1 , mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2 ;

        if(ar[mid] == itm)
        {
            hi = mid-1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid-1 ;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

int upperBound(int itm, int sz)
{
    int lo=0, hi=sz-1, mid;

    while(lo <= hi)
    {
        mid = (lo+hi) / 2;

        if(ar[mid] == itm)
        {
            lo = mid+1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid - 1;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

int main()
{
    int n;

    cout << "Take array size: ";

    while(cin >> n)
    {
        int i;

        for(i=0;i<n;i++)
        {
            cin >> ar[i];
        }

        int q;
        cout << "Number of Query: ";
        cin >> q;

        while(q--)
        {
            int x;
            cin >> x;

            int lw,up;

            lw = lowerBound(x,n);

            cout << "index = " << lw << " value = " << ar[lw] << "\n";

            up = upperBound(x, n);

            cout << "index = " << up << " value = " << ar[up] << "\n";
        }

        cout << "Take array size: ";
    }

    return 0;
}

Upcomming_Eid_Ul_AZHA_Programmming_Contest Problem B. Even Digits

Link: Problem B - Even Digits Problem Link
AC Code Link: Problem B - Even Digits AC Code Link

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define high 10000

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

int main()
{
    fast;
    int t, tc=0;
    LL n, quotiant=0;
    string ans="";
    cin >> t;
    while(t--)
    {
        ans="";
        cin >> n;

        cout << "Case " << ++tc << ": ";

        if(n==1)
        {
            outn("0");
            continue;
        }

        quotiant = n-1;

        while(quotiant > 0)
        {
            ans+=((quotiant % 5) * 2) + 48;

            quotiant = quotiant / 5;
        }

        reverse(ans.begin(), ans.end());
        outn(ans);
    }

    return 0;
}

Machine Learning

মেশিন লার্নিং এ বড় ধরণের একটা সাফল্য দশটা মাইক্রোসফট এর সমান হবে। এটা আমার কথা না, বিল গেটস নিজের কথা।
কম্পিউটার সাইন্স এর দারুণ একটা সাবজেক্ট হচ্ছে মেশিন লার্নিং। সাধারণত আমরা কম্পিউটারকে কিছু ইন্সট্রাকশন দেই, কম্পিউটার সে অনুযায়ী কাজ করে। কিন্তু মেশিং লার্নিং এর ক্ষেত্রে আমরা কিছু প্রসেস বলে দেই, বাকিটা সে নিজে নিজে শিখে নেয় এবং সে অনুযায়ী কাজ করে। যেমন আবহাওয়ার কথাই ধরা যাক, আমরা একটা কম্পিউটার প্রোগ্রামকে পূর্বের সকল আবহাওয়ার ডেটা দিব। ঐ ডেটা এনালাইসিস করে আমাদের প্রোগ্রাম আবহাওয়ার পূর্বাবাস জানাবে। আমরা এখানে বলে দিচ্ছি না কি জানাতে হবে। প্রোগ্রাম আগের ডেটা এনালাইসিস করে বর্তমান আবহাওয়া দেখে আমাদের বলে দিচ্ছে আগামীকালকের আবহাওয়া কেমন হতে পারে। এটাই মেশিং লার্নিং।
কম্পিউটার প্রোগ্রামকে ডেটা দিলেই তা এনালাইসিস করতে পারবে না। আমাদের কিছু ইন্সট্রাকশন দিয়ে দিতে হবে কিভাবে ডেটা এনালাইসিস করতে হবে। কি কি অ্যালগরিদম কিভাবে ব্যবহার করতে হবে, ইত্যাদি। এসব করে দিলে বাকি কাজ মেশিন বা প্রোগ্রাম নিজে করবে। এখন ছোট খাটো অ্যাপেও মেশিন লার্নিং এর দরকার হয়। ডেটা মাইনিং, ন্যাচারাল ল্যাঙ্গুয়েজ প্রসেসিং, ইমেজ রিকগনিশন, এক্সপার্ট সিস্টেম সহ কম্পিউটার সাইন্স এবং আর্টিফিশিয়াল ইন্টীলিজেন্স এর অনেক জায়গায় মেশিন লার্নিং এর প্রয়োগ হয়।
অনেক গুলো উদাহরণ দেওয়া যাবে। হাতের কাছের একটা উদাহরণ দেই। Madviser নামে একটা অ্যান্ড্রয়েড অ্যাপ রয়েছে। এটার কাজ হচ্ছে আপনার জন্য কোন মোবাইল প্যাকেজ ভালো হবে, তা সাজেস্ট করা। আর তার জন্য এটি আপনার সকল ডেটা প্যাকেজ এবং ভয়েস কল এনালাইসিস করে। এই অ্যাপকে সরাসরি কি করতে হবে, তা বলে দেওয়া হয় নি। কিছু ডেটা দেওয়া হচ্ছে, ঐ ডেটা এনালাইসিস করে ব্যবহারকারীকে একটা প্যাকেজ সাজেস্ট করছে। এটাও মেশিং লার্নিং এর একটা প্রয়োগ। অ্যাপটা বাংলাদেশী ডেভেলপারদের তৈরি।
আরেকটা সিম্পল উদাহরণ হচ্ছে OCR বা Optical Charecter Recognition/Reader. ছবি থেকে লেখা গুলো পড়ার জন্য ব্যবহৃত হয়। আমরা অনেকে ব্যবহার করেছি হয়তো। এটিও মেশিং লার্নিং এর একটি প্রয়োগ। ইমেজ থেকে ক্যারেকটার গুলো দেখে তারপর কোনটা কি, তা ডিটেক্ট করে। আর এই মেশিং লার্নিং এ ব্যবহৃত হয় Classification Algorithm. ইমেলে আসা কোনটা স্প্যাম, কোনটা স্প্যাম না, তা বের করতেও মেশিন লার্নিং বা ক্লাসিফিকেশন অ্যালগরিদম ব্যবহৃত হয়। এরকম অনেক গুলো অ্যালগরিদম এর ব্যবহার মিলেই হচ্ছে মেশিং লার্নিং।
মেশিন লার্নিং অ্যালগরিদম গুলোকে প্রধানত দুই ক্যাটেগরিতে ভাগ করা যায়।
- Supervised Learning.
- Unsupervised learning.
Supervised Learning: কিছু প্রি ডিফাইন ডেটাসেট এর উপর প্রোগ্রামকে ট্রেইন করা হয়। ঐ ট্রেইন ডেটা এর উপর ভিত্তি করে প্রোগ্রাম ডিসিশন দেয়। এটা হচ্ছে সুপারভাইসড লার্নিং। যেমন মেইলটি কি স্প্যাম না কি স্প্যাম না, এই ডিসিশনটা আগের কিছু ডেটার উপর নির্ভর করে দেয়া হয়। এটা হচ্ছে সুপারভাইসড লার্নিং এর উদাহরণ।
Unsupervised learning: আনসুপারভাইসড লার্নিং এ প্রোগ্রামকে কিছু ডেটা দেওয়া হয়। প্রোগ্রাম ঐ ডেটার উপর নির্ভর করে ডিসিশন দেয়। যেমন এক ঝুড়ি ফল রয়েছে। প্রোগ্রাম ভিন্ন ভিন্ন ফল কে ভিন্ন ভিন্ন ক্যাটেগরিতে ভাগ করবে, এটা হচ্ছে আনসুপারভাইড লার্নিং এর উদাহরণ।
সিরি, কর্টনা এসব হচ্ছে মেশিং লার্নিং এর সফল প্রয়োগ। ফেসবুকে ইমেজ আপলোড করার পর অটোমেটিকেলি কার ছবি, তা ডিটেক্ট করে। এটাও মেশিন লার্নিং এর প্রয়োগ। বিল গেটস মিথ্যে বলে নি। মেশিন লার্নিং কে যদি আরো ইফিশিয়েন্টলি প্রয়োগ করা যায়, তাহলে আমাদের পুরো প্রযুক্তি দুনিয়াটাই পাল্টে যাবে। এমন না যে চেষ্টা করা হচ্ছে না। নিয়মিতই এই সেক্টরটি ডেভেলপ হচ্ছে।
দুই ধরনের মানুষ রয়েছে। Watcher & Player. আপনি কোন ধরণের হবেন? Player হলে এখন থেকেই এসব নিয়ে পড়ালেখা করতে পারেন। জানতে পারেন আস্তে আস্তে। ইন্টারনেটে প্রচুর রিসোর্স রয়েছে। মেশিন লার্নিং এর উপর এই কোর্স দুইটি দারুণ এবং জনপ্রিয়।
coursearemachinelearning
udacitymachinelearning
গুগলে একটু সার্চ করলেই দারুণ সব রিসোর্স পাওয়া যাবে। ML এক্সপার্ট এর অনেক চাহিদা রয়েছে। আর আমাদের দেশে রয়েছে অভাব। যেখানে অভাব, সেখানেই সুযোগ। কাজে লাগানো আপনার ইচ্ছে  :) :)

Upcomming_Eid_Ul_AZHA_Programmming_Contest A. Helping Tool

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<map>
//#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf

typedef long long LL;
typedef long L;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef map<char, int> mpcii;
typedef map<char , bool> mpcb;
typedef vector<char>vc;

int main()
{
    fast;
    string s;
    //mpcii mp;
    //mpcb mpc;
    vc v;
    while(cin >> s)
    {
        //mp.clear();
        //mpc.clear();
        v.clear();

        int len = s.length() , i=0;

        //int x = 200000; cout << x;

       for(i=0; i<len; i++)
       {
           v.push_back(s[i]);
       }

       i=0;

       len=v.size(); //cout << "len1 = " << len << "\n";

       for(; i<len-1; i++)
       {
           if(v[i] == v[i+1])
           {
               int j = i;

               len-=2;

               for(; j<len; j++)
               {
                   v[j] = v[j+2];
               }

//               if(!mpc[v[i]] and !mpc[v[i+1]])
//               {
//                   mpc[s[i]] = true;
//                   mpc[s[i+1]] = true;
//               }

               //for(int k=0; k<v.size()-2; k++) cout << v[k] << " ";
               //cout << "\n";

               i=-1;
           }
       } //cout << "len = " << len << "\n";

       if(len <= 0) cout << "-1";

       else
       {
           for(i=0 ; i<len; i++) cout << v[i];
       }

       cout << "\n";
    }

    return 0;
}

// xraccabccbry

Cube Root - Binary Search - Bisection Method

// Cube root
// Binary Search-Bisection Method

#include<bits/stdc++.h>
using namespace std;

#define out(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define ex 1e-6

typedef long long LL;

double diff(double n, double mid)
{
    if(n > (mid * mid *mid)) return n - (mid * mid *mid);
    else return (mid * mid *mid) - n;
}

double bisection(double n)
{
    double lo=0.0, hi=n, mid=0.0;

    while(true)
    {
        mid = (lo + hi) / 2.0;

        double d = diff(n,mid);

        if(d <= ex) return mid;

        if((mid * mid * mid) > n) hi = mid;
        else lo = mid;
    }
}

int main()
{
    double x;
    while(cin >> x)
    {
        cout << "Cube root of " << x << " is " << bisection(x) << "\n";
    }

    return 0;
}

Find the power by O(lgn)

#include<bits/stdc++.h>
using namespace std;

#define out(x) cout << x << "\n"

// O(n) solution

//int power(int x, int y)
//{
//    if(y == 0) return 1;
//
//    if(y % 2 == 0)
//    {
//        int r = power(x, y/2);
//        return r*r;
//    }
//
//    else
//    {
//        return x * power(x, y/2) * power(x, y/2);
//    }
//}
//
//int main()
//{
//    int x,y;
//
//    while(cin >> x >> y)
//    {
//        cout << power(x, y) << "\n";
//    }
//}


// O(lgN) Solution

// when y is positive
// the function can be optimized to O(logn) by calculating power(x, y/2) only once and storing it.

//int power(int x, int y)
//{
//    int temp;
//
//    if(y == 0) return 1;
//
//    temp = power(x, y/2);
//
//    if(y % 2 == 0) return temp * temp;
//
//    else
//    {
//        return x * temp * temp;
//    }
//}
//
//int main()
//{
//    int x,y;
//
//    while(cin >> x >> y)
//    {
//        cout << power(x, y) << "\n";
//    }
//}


// O(lgn), when y is negative

float power(int x, int y)
{
    float temp=0.0;

    if(y == 0) return 1;

    temp = power(x, y/2);

    if(y % 2 == 0) return temp * temp;

    else
    {
        if(y > 0) return x * temp * temp;

        else
        {
            return temp * temp / x;
        }
    }
}

int main()
{
    int x,y;

    while(cin >> x >> y)
    {
        cout << power(x, y) << "\n";
    }
}

Longest Decreasing Subsequence

#include<bits/stdc++.h>
using namespace std;

const int inf = 9999;

int n, seq[100], ldsseq[100], I[100], L[100];

int BINARY_SEARCH(int lo, int hi, int itm)
{
    int mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2;

        if(I[mid] < itm)
        {
            lo = mid + 1;
        }

        else
        {
            hi = mid - 1;
        }
    }

    return lo;
}

int LIS()
{
    int i, j , len=0 , r , Llen=0;

    for(i=0; i<n; i++)
    {
        r = BINARY_SEARCH(0, len, seq[i]);

        I[r] = seq[i];
        L[Llen++] = r;

        if(len < r)
        {
            len = r;
        }
    }

    //cout << "LDS Length: " << len;
    return len;
}

void find_squence( int mxlen)
{
    int i=0 , j;

    for(j=1; j<n; j++)
    {
        if(L[j] > L[i])
        {
            i = j;
        }
    }

    int top = L[i];

    top--;

    ldsseq[top] = seq[i];

    for(j=i-1; j>=0; j--)
    {
        if(seq[j] < seq[i] and L[j] == L[i]-1)
        {
            i=j;

            top--;

            ldsseq[top] = seq[i];
        }
    }

    cout << "Sequence: ";
    for(i=mxlen-1; i>=0; i--)
    {
        cout << ldsseq[i] << " ";
    }
}

int main()
{
    while(cin >> n)
    {
        int ilen=0;

        I[ilen++] = -inf;

        for(int i=0; i<n; i++)
        {
            cin >> seq[i];

            I[ilen++] = seq[i];
        }

        reverse(seq, seq+n);

        int rlen = LIS();

        find_squence(rlen);

        cout << "LDS Length = " << rlen << "\n";
    }

    return 0;
}