Dynamic Programming - 1 ( Coin change )

একটা বড় problem কে ছোট ছোট ভাগে ভাগ করে সেগুলো solve করার মাধ্যমে বড় problem টাকে solve করাই হচ্ছে Dynamic programming এর কাজ। আমরা প্রথমে কিছু সহজ DP প্রবলেম শিখব। আমরা আজকে যা শিখব তা হল coin change টাইপ প্রবলেম।

Type -1 ( Unlimited Coin )

শিখব কই থেকেঃ

See this slide

#define MAX 10000

vector<int>coin; // contains coin value
int is_possible[MAX];
int coin_need[MAX];

int coin_change(int need_to_make) // need_to_make < MAX
{
    // fill coin_need with INF value here

    is_possible[0] = 1;
    coin_need[0] = 0;

    for(int i=0;i<coin.size();i++)
    {
        for(int j=0;j+coin[i]<MAX;j++)
        {
            if(is_possible[j])
            {
                int next = j+coin[i];

                is_possible[ next ] = 1;
                coin_need[ next ] = min( coin_need[j]+1 , coin_need[ next ] );
            }
        }
    }
    return coin_need[need_to_make];
}

Type - 2 ( Limited Coin )

এখন তোমাকে যদি কিছু coin দেয়া হয় এবং বলে দেয়া হয় কোন coin টা maximum কয়বার ব্যবহার করতে পারবে তখন কি করবে?

আমরা unlimited  coin  এর জন্যে যেভাবে বাম থেকে ডানে লুপ চালিয়েছি, এবার একই ভাবে ডান থেকে বামে লুপ চালাব। তাহলেই limited coin এর জন্যে answer পেয়ে যাব।

#define MAX 10000

struct coin{
    int val,how_many;
};

vector<coin>has_coin;
bool is_possible[MAX];
int minimum_coin_need[MAX];


int limited_coin_change(int need_to_make)
{
    is_possible[0] = true;
    minimum_coin_need[0] = 0;

    for(int i=0;i<has_coin.size();i++)
    {
        for(int j= MAX-1 ; j>=0 ; j--)
        {
            if(is_possible[j] == true)
            {
                int value = has_coin[i].val;
                int next = j + value;
                int curent = j;

                for(int k=0;k<has_coin[i].how_many;k++)
                {
                    is_possible[next] = true;
                    minimum_coin_need[next] = min(minimum_coin_need[curent]+1,minimum_coin_need[next]);

                    curent = next;
                    next = next+value;
                }
            }
        }
    }

    return minimum_coin_need[need_to_make]; // return desire result
}

Problem

UVA - 147, 166, 357, 674, 10313, 10306, 11137, 11517, 562

Lightoj - 1231, 1232, 1233

Recursion & Backtracking

Recursion, programming এর জন্যে খুব গুরুত্বপূর্ণ। recursion প্রথম দিকে শেখার সময় অনেকের কাছে কঠিন লাগে। কিন্তু একবার শিখে ফেলতে পারলে এর থেকে সহজ আর কিছু নেই। শুধু শেখার আগ পর্যন্ত লেগে থাকতে হবে।

কোথা থেকে শিখব?

দেখতেই হবেঃ

1. ফাহিম ভাইয়ের ব্লগ। খুবই সুন্দর করে লিখেছেন। 
2. যোবায়ের ভাইয়ের ব্লগ। Attacking recursion.

আরো কিছু দেখতে পারোঃ

1. Topcoder
2. আর একটা...

করতেই হবেঃ

Problems of recursion.  এখানে ২০ টা problem দেয়া আছে। এই ২০ টা অবশ্যই করতে হবে। এই গুলো নিজে যখন বুঝে করতে পারবে তখনি শুধু নিচের গুলো করার চেষ্টা করবে।

Problem

এখানে যে problem গুলো দেয়া হয়েছে তা ফরহাদ ভাই ( 07 Batch, SUST & WF of 11,12 ) আমাদের training camp এ করিয়েছিলেন। সেখান থেকে সবগুলো problem দিয়ে দিলাম।

Lightoj - 1023, 1117

Uva - 195, 10696, 10776, 11753, 624

TopCoder - SRM 491 Div 2 1000, TCHS SRM 16 1000, TCHS SRM 55 1000, SRM 273 div 2 1000, TCHS SRM 2 1000, SRM 449 Div 2 500, TCCC06 online Round 2A Div 1 250, SRM 275 Div 2 500, TCHS SRM 26 500

TJU - 1306, 2893

All Pairs Shortest Path (Floyd–Warshall)

Floyd Warshall একটা গ্রাফের প্রতিটা নোড থেকে প্রতিটা নোডের দূরত্ব বের করে। খুব সহজ। এখনি নেটে সার্চ দাও। একবার দেখলেই পেরে যাবে। :)

#define MAX 100
#define INF (1<<30) // 2^30

int dis[MAX][MAX]; // distance

void floyd_warshall()
{
    for(int i=0;i<MAX;i++)
    {
        for(int j=0;j<MAX;j++)
        {
            if(i==j) dis[i][j] = 0; // distance from a node to itself is 0
            else dis[i][j] = INF; // initially distance from node i to j is INF
        }
    }

    /*

    here construct the graph with distance
    If a connection exists between node 2 and 5 with distance 8, update

    dis[2][5] = 8;
    dis[5][2] = 8;

    */
    
// ****************  Floyd Warshall *******************
    for(int k=0;k<MAX;k++)
    {
        for(int i=0;i<MAX;i++)
        {
            for(int j=0;j<MAX;j++)
            {
                dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    return ;
}

Problem

UVA - 821, 341, 534, 10048, 544

Single source shortest path ( SSSP - Dijkstra )

কোন গ্রাফের একটা নোড থেকে আরেকটা নোড এর মিনিমাম দূরত্ব বের করাই  dijkstra এর কাজ।
অনলাইনে সার্চ দিলেই ভাল ভাল টিওটোরিয়াল পাবে শেখার জন্যে।
Dijkstra animation

শিখতে হবেঃ

• STL
  1. Priority Queue ( push, pop, top, size, empty )
  Priority Queue একটি Data structure যেখানে element গুলো সবসময়  sorted থাকে।
  Priority Queue কি ও কি করে শুধু সেটা জানলেই হবে আপাতত। Data structure কোর্স করার সময় বিস্তারিত তখন জানতে পারবে।
  

#define SZ(a) (int)a.size()

#define MAX 1000
#define INF (1<<30) // 2^30

struct data{
    int v,w;

    // how the data'll be sorted in priority queue
    bool operator<(const data &p)const
    {
        return p.w<w; // in ascending order
    }
};

/*
You don't need to understand how does the following function work in the
structure right now.

bool operator<(const data &p)const
{
    return p.w<w;
}

You'll understand it later. Only remember if you write
return p.w<w; // It'll sort in ascending order of w
return p.w>w; // It'll sort in descending order of w
*/

vector<data>con[MAX]; // graph connection
int dis[MAX]; // distance from the start node

int dijkstra(int start,int end)
{

    priority_queue<data>Q;
    for(int i=0;i<MAX;i++) dis[i] = INF; 
    // at first set infinite distance from start node to every node 

    data tmp;
    tmp.v = start;
    tmp.w = 0;
    pq.push(tmp);
    dis[start] = 0;

    while(!Q.empty())
    {
        int u = Q.top().v;
        int w_u = Q.top.w;
        Q.pop();

        // if(u==end) return dis[end]; It works also;

        for(int i=0;i<SZ(con[u]);i++)
        {
            int v = con[u][i].v;
            int w_v = con[u][i].w;

            if( w_u+w_v < dis[v] )
            {
                dis[v] = w_u + w_v;

                tmp.v = v;
                tmp.w = dis[v];

                pq.push(tmp);
            }
        }
    }

    return dis[end];
}

Problem

UVA - 341, 920, 10801, 10986, 10000

BFS

গুগ্লিং করেই BFS শিখে ফেলতে পারবে। তেমন কঠিন না। গুগ্লিং করার সময় BFS ppt  লিখে সার্চ দিলে power point এর স্লাইড আসবে। স্লাইড দিয়ে শেখাটা অনেক সহজ।

BFS from shafaetsplanet

#define MAX 1000

vector<int>con[MAX]; // graph representation
bool color[MAX];

void bfs(int start,int end)
{
    queue<int>Q;
    Q.push(start);
    color[start] = true;

    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();

        for(int i=0;i<con[u].size();i++)
        {
            int v = con[u][i];
            if(color[v] == false)
            {
                Q.push(v);
                color[v] = true;
            }
        }
    }

    return ; // return result
}

কিছু লজিকঃ

1. co-ordinate move এর ক্ষেত্রে manually move  গুলো না দিয়ে একটা array এর মধ্যে move গুলো রেখে সবগুলো move বের করা যায়।

int rrr[]={1,0,-1,0};
int ccc[]={0,1,0,-1};
// left, down, up, right

int x = 3,y = 5; // initial position

for(int i=0;i<4;i++)
{
    int u = x+rrr[i];
    int v = y+ccc[i];
    
    // u,v will contain new cordinate
}

Problem

UVA - 572, 469, 439, 532, 336, 260, 10004, 11080, 10336, 11518
Lightoj - 1012,1039
HDU - 4171

Graph basic, STL

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

শিখতে হবে

• How to represent a graph.
  1. Adjacency Matrix
  2. Adjacency List
• Data structure
  1. Queue
  2. Stack
• STL
  1. vector ( push_back, pop_back, size, clear, operator[] )
  2. queue ( push, pop, front, size, clear, empty )

শুরুর কথা...

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

এখানে কিছু শিখিয়ে দেয়ার চেয়ে অনলাইনে পাওয়া যায় এমন রিসোর্স বেশি দেয়া হবে। নিজেকেই তা থেকে শিখে নিতে হবে। সবথেকে ভাল হয় যদি নিজেদের বন্ধুদের নিয়ে একটা গ্রুপ করে নেয়া যায়। তাহলে শেখাটা অনেক সহজ ও দ্রুত হবে। নিজে নতুন কিছু শিখলে সাথেসাথে পাশের বন্ধুকে তা শিখিয়ে দিতে হবে। এভাবে knowledge share এর অভ্যাস গড়ে তুলতে হবে। প্রতিটা পোস্ট এর নিচে কমেন্ট এ সবাই আলোচনা করতে পার যাতে তোমার পাশাপাশি অন্যরাও শিখতে পারে।

নতুন কিছু শেখার জন্যে সবথেকে ভাল যা পারতে হয় তা হল ভাল গুগ্লিং করা। :) কিছু সার্চ করার সময় তার শেষে ppt লিখে সার্চ দিও, তাহলে power point এর slide গুলো প্রথমে আসবে। স্লাইড দিয়ে শেখা কিছুটা সহজ।

যে যে প্রবলেম গুলো দেয়া হবে তার সবগুলো সময়মত করতে হবে। প্রয়োজনে বন্ধুর সাহায্য নাও, অনলাইনে আলোচনা কর, কিন্তু সময়মত সবগুলো শেষ করতে হবে।

সবশেষে প্রোগ্রামিংটাকে fun হিসেবে নাও। Happy coding. :)