freopen vanish

আমরা প্রায়ই আমাদের online judge গুলোতে প্রবলেম submit করার সময় freopen comment করতে ভুলে যাই। ফলে আমাদের একটা অনাকাঙ্খিত একটা verdict দেখতে হয়। খুবই pathetic একটা জিনিস। accepted বাদের অন্য কোন verdict দেখলেই বুকের ভেতরটা কেমন করে ওঠে। তারপর বসে বসে error খোজ critical test case বের করো। অনেক ঝামেলা। তাই গুলো থেকে মুক্তি দিতে আমাদের ছোট খাট একটা tricks করতে হবে।
তবে এখানে আমি শুধু freopen থেকে মুক্তির উপায় বলবো। আমরা যদি কোডে ছোট্ট একটা tag যোগ করি তাহলে freopen আর submit করার সময় comment করা লাগবে না। খুব সহজেই কাজ হয়ে যাবে। আমাদের online judge জানবেও না যে tag এ ভিতরে একটা freopen আছে। আর তার জন্য আমাদের freopen টাকে এই tag এর মধ্যে লিখতে হবে।

#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif

তুমি চাইলে তোমার কোডের ভিতরে secret কিছু করতে চাইলে যেটা online judge কে দেখাতে চাও না সেটা এভাবে লিখতে পারো। online judge বুঝতেও পারবে না তুমি তোমার কোডে কি কি করেছো। কাজটা তুমি করতে পারো এভাবেঃ

int main(){
#ifndef ONLINE_JUDGE
	READ("in.txt");
#endif
    bktk(0);
    int cas=1,a[10],sum,ans;
    while(SDi(a[0])==1){
        repl(i,7) SDi(a[i]);
        pf("Case %d: ",cas++);
        ans = 1<<28;
        rep(j,cnt){
            sum = 0;
            rep(i,8){
                sum += (a[i] != (v[j][i]+1));
                #ifndef ONLINE_JUDGE
                    cout<<v[j][i]<<" ";
                #endif
            }
            ans = min(ans,sum);
            #ifndef ONLINE_JUDGE
                puts("");
            #endif
        } pf("%d\n",ans);
    }
    return EXIT_SUCCESS;
}

এখানে আমি প্রত্যেকটা test case নিয়ে কাজ করার সময় সেগুলো প্রিন্ট করে দেখেছি। কিন্তু এই কোডটা যখন online judge এ run করবে তখন এই tag এর ভিতরের কোন কিছু সে execute করবে না।
দারুণ জিনিস তাই না। এটা আমি জোগার করেছি codeforces এ একজনের কোড থেকে। কোডগুলো আমার কিন্তু technique টা তার কাছ থেকে ধার করা।
technique টা apply করতে কোন ঝামেলা হলে comment এ জানানোর জন্য অনুরোধ করছি। হ্যাপি প্রোগ্রামিং ! 🙂

গ্রাফ থিওরি এবং একটি রুপকথার গল্প

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

আমাদের সবার অবস্থা সেই রাজকন্যার মত। আমাদের ভেতরে এক ডাইনি বুড়ি সব সময় যে গ্রাফ থিওরি হল এক বিভিষীকাময় জায়গা আর আমরা ভয়তে সেদিকে ফিরেও তাকাই না।
Back to the story: ধীরে ধীরে রাজকন্যার বয়স বাড়তে থাকলো আর সে বাইরের জগতের প্রতি আগ্রহী হয়ে উঠলো। এমন সময় তার ঘরে আসলো এক চোর যে কিনা তার মুকূট চূরি করে পালিয়েছে। রাজকন্যা বাইরের দুনিয়া দেখার কিঞ্চিত ভরসা পেল। আর নিজেকে বোঝাল যে বাইরের দুনিয়া যতই খারাপ সে একবার সেখানে যাবেই যাবে।
আর আমাদের জন্য সেই বার্তা বয়ে এনেছে আমাদের সবার প্রিয় সবচেয়ে সমৃদ্ধ বাংলা ব্লগ শাফায়েতের ব্লগ। বর্তমান সময়ের সব থেকে সমৃদ্ধ বাংলা টিউটোরিয়াল ব্লগ।
এতটুকু পড়ার পর তোমার মনে যদি একটু সাহস সঞ্চার হয়ে থাকে তাহলে গ্রাফ কি জেনে আসতে পারো এখান থেকে। তারপর গ্রাফ কিভাবে variable এ store করতে হয় তা জানতে পারো এখান থেকে আর এখান থেকে ।
back to story : রাজকন্যা চোরের সাথে বের হবার পর তার তো মাথা খারাপ অবস্থা সে বাইরের দুনিয়া দেখে পুরো পুরি বিস্মিত আর হতভম্ব সে নিজে বুঝতে পারলো যে তার তার মা তার সাথে যা বলেছে যা সে যা জেনেছে তা পুরোপুরি মিথ্যা।
তুমি যদি গ্রাফের আগের দুটো টিটোরিয়াল পড়ে থাকো তাহলে নিশ্চয় বুঝে গেছো যে তুমি যা জানতে তাও প্রায় পুরোপুরি মিথ্যা আর গ্রাফ খুব সহজ জিনিস। এখন তুমি যদি গ্রাফের দুনিয়া ঘুরে দেখতে চাও তাহলে তোমাকে গ্রাফ ট্রার্ভাস জানতে হবে আর তার জন্য আছে দুটো পদ্ধতি সে দুটো হল BFS আর DFS আর এদুটো আসলে কি তা জানতে তোমাকে BFS এর জন্য এখান থেকে আর DFS এর জন্য এখান তেকে ঘুরে আসতে হবে।আর যদি BFS কোড জানতে চাও তাহলে এখানে ছোট্ট একটা উকি দিয়ে আসো।
এখন তুমি গ্রাফের মোটামুটি expert বলা যায় এখন নিজের যোগ্যতা প্রমাণের জন্য হোক আর বন্ধুদের তাক লাগানোর জন্য হোক তুমি জলদি কয়েকটা problem solve করে ফেলতে পারো যদি জানতে চাও কোন গুলো তাহলে দেখ এই পোষ্টের শেষে অথবা uvatoolkit এ গিয়ে BFS লিখে একটা search মারো তুমি যত বেশি problem solve করবে তোমার লজিক তত develop করবে আর তুমি তত বড় মাপের problem solver হিসাবে আত্মপ্রকাশ করবে যদি ওয়া খাও তাহলে খুব খুশির কথা কারণ তুমি একটা নতুন জিনিস শেখার সুযোগ পেলে যা আগে জানতে না।
এখন যদি আবার গল্পের কথা মনে পড়ে তাহলে চল বাকিটুকু শুনে আসা যাক । রাজকন্যা পৃথিবী ঘোরা শুরু করার পর সে বুঝতে পারলো যে সে আসলে এত দিন মিথ্যার মধ্যে ছিল তারপর সে এক বিশাল adventure এর মধ্যে দিয়ে তার মা বাবাকে আবিষ্কার করে আর জানতে পারে তার আসল পরিচয় শেষ হয় এক শ্বাসরুদ্ধকর গল্পের। যারা আমার মত একটু হালকা পাতলা মুভি দেখ তারা নিশ্চয় বুঝে গেছ আমি কোন ছায়াছবির কথা বলতে চাইছি আমি আসলে Tangled এর গল্প বললাম যার মুল নাম রুপাঞ্জেল আর এটা একটা Spanish রুপকথা।
আমি যত সহজে গল্পটা শেষ করে দিলাম আমাদের আসল গ্রাফ থিওরি শেখা কিন্তু এতটা সহজে শেষ হবে না আমাদের আরো অনেক পথ যেতে হবে আর আমাদের adventure টাও রুপাঞ্জেলের থেকে কোন অংশে কম হবে না। এখনো তোমাকে গ্রাফ থিওরির অনেক অ্যালগো জানতে হবে।
MST গ্রাফের খুব গুরুত্বপূর্ণ একটা জিনিস তোমাকে MST কি জানতে উকি দিতে হবে এখানে আর কিভাবে MST বের করা যায় তা জানতে দেখতে হবে এখানে আর এখানে। MST এর বেলায়ও BFS এর মত একই কথা প্রযোজ্য uvatoolkit গিয়ে MST লিখে একটা search মারো যা আসবে solve করা শুরু করে দাও এখানে তোমাকে প্রত্যেক problem এর জন্য অ্যালগোটাকে অনেক ভাবে modify করা লাগবে যার মধ্যে দিয়ে তুমি গ্রাফ থিওরিতে হালকা পাতলা বস হতে শুরু করবে।

আজ এ পর্যন্তই আগামীতে আরো নতুন কিছু নিয়ে আসবো নতুন কোন অ্যালগো বা টিউটোরিয়াল সে পর্যন্ত সবাই ভাল থাকবেন। খোদা হাফেজ।

STL : vector

ভেক্টর হল স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরীর একটা element. স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরী হল c++ এর একটা ফিচার যেখানে অনেক Data Structure built-in দেওয়া আছে। আমরা চাইলে সেখান থেকে আমাদের পছন্দমত element নিয়ে কাজ করতে পারি। তবে শর্ত হল আমাদের ওদের operation গুলো জানতে হবে। বর্তমান সময়ের কনটেস্ট প্রোগ্রামারদের মধ্যে স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরী খুবই জনপ্রিয় আর TopCoder এ প্রোগ্রামিং কনটেস্ট এর পূর্ব শর্ত হল তোমাকে অবশ্যই স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরী সম্পর্কে ধারণা থাকতে হবে।ভবিষ্যতে স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরীর আরো element নিয়ে আলোচনা করা হবে। আজকের আলোচ্য বিষয় হল ভেক্টর।
ভেক্টর জানার আগে তোমাকে একটু টেমপ্লেট সম্পর্কে জানতে হবে। সাধারণ কথায় টেমপ্লেট হল একটা কমন ফরম্যাট যা সব কিছুতে ব্যবহার করা যাবে। ভেক্টর
এর template হল এরকম

vector< datatype > objects/variables;

এখানে datatype হল তুমি কোন type এর ডাটা ব্যবহার করতে চাও। যদি integer type এর ডাটা হয় তাহলে deceleration হবে এরকমঃ

vector< int > v;

এখানে V হল ভেক্টর ডাটা টাইপের একটা variable. ভেক্টর হল অনেকটা array এর মত। তবে এর অনেক সুবিধা আর ফিচার আছে যা ভেক্টরকে অ্যারে থেকে আলাদা করে তুলেছে।আমি যদি ভেক্টরের ভেতর ডাটা ঢুকাতে চাই তাহলে array এর মত indexing ছাড়াও আর একটা মজার বিষয় আছে সেটা হল push_back(); আমি যদি ডাট ঢুকাতে চাই আর push_back(); দিয়ে ডাটা ঢুকাই তাহলে ১ম ডাটার index হবে ০, ২য় ডাটার ১ এভাবে ডাটা ঢুকতে থাকবে।জিনিসটা হবে এরকমঃ

vector< int > v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

তাহলে আমদের ভেক্টরে ডাটা ঢুকান শেষ এবার আমরা একটু এটা নিয়ে খেলা করবো। আমাদের ডাটা ঢুকানোর পর মনে হল যে আমরা ৪ এর জায়গায় ভুল করে ২ ঢুকিয়ে ফেলেছি। কোন চিন্তা নেই। খালি লিখে দাওঃ

v[1] = 4;

ব্যস ডাটা ঠিক হয়ে গেল।
এবার মনে কর আমাদের ১০০ সাইজের একটা ভেক্টর লাগবে যাতে সবগুলো ০ থাকবে। তাহলে কোডটা হবে এরকমঃ

vector< int > v(100,0);

তুমি চাইলে -1 দিয়েও initialize করতে পার।সেক্ষেত্রে ০ এর জায়গায় -১ বসিয়ে দাও।

এবার ধরো একটা array আছে। তাকে ধরে নিয়ে ভেক্টরের ভেতর ঢুকাতে হবে। কাজটা হবে এরকমঃ

 int array [] = {5, 4, 1, 7, 9, 13, 32, 5, 71};
 unsigned int array_length=sizeof (array) /sizeof(int);
 vector <int> v ( array, array + array_length );

ব্যস কাজ হয়ে গেল।
এবার ভেক্টরের ভেতর অনেক element ঢুকে গেছে আমাদের মনে হল একটু সর্ট করা দরকার। খালি লিখে দাও।

sort(v.begin().v.end());

দেখ ম্যাজিক ডাটা সব sort হয়ে গেছে। কি মজা তাই না আগে ডাটা সর্ট অ্যালগোরিদম লিখতে হাত ব্যাথা হয়ে যেত আর complexity ছিল কত বেশি আর এখন কত মজা।
যদি ক্লান্ত হয়ে যাও তাহলে আর কষ্ট করো না খালি ভেক্টরটা পরিষ্কার করে ফেল। এভাবেঃ

v.clear();

তোমার ভেক্টর পরিষ্কার হয়ে গেছে। আর কোন চিন্তা নাই একে আবার নতুনের মত ব্যবহার করা যাবে।
এবার একটি মজা দেখ। মীরাক্কেলের ত্রাস রনি মাস্তান তোমাকে বলল তার কাছে ৫ টা ডাটা সেগুলোর যত গুলো permutation সম্ভব তোমাকে বের করে দেখাতে হবে। তুমি বেশি তাফালিং করলে তোমার স্ক্রু টাইট করে দিবে তাই অন্য উপায় বের করতে হবে। এখন যদি তুমি ভেক্টর জান তাহলে খালি লিখে দাওঃ

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

int main()
{
    vector<int> v;
    v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);
    do{
    for(int i=0;i<5;i++)
        cout<<v[i]<<" ";
        puts("");
    }while(next_permutation (v.begin(),v.end() ));
    return 0;
}

Sample কোডটা এরকম হবে তাই না। এখানে next_permutation algorithm হেডারের একটা প্রোপার্টি।

এবার ধর ভেক্টরের মধ্যে কোন ডাটা আছে কিনা তা খুজে বের করতে হবে সেক্ষেত্রে সবচেয়ে কাজের জিনিস হল binary search. এবার আমরা একটা ভেক্টরের ভেতর binary search চালাব। আর ডাটা খুজবো। (binary search কি সেটা নিয়ে আর একদিন আলোচনা করবো)
তবে binary search চালানোর একটা শর্ত আছে। তোমার ডাটাগুলো অবশ্যই ascending অথবা descending order এ sorted অবস্থায় থাকতে হবে। তা না হলে উত্তর ভুল আসতে পারে।
কোডাটা হবে এরকমঃ

int key = 9;
    if ( binary_search ( v.begin (), v.end (), key ) )
        printf ("key : %d found\n", key);
    else
        printf ("key : %d not found\n", key);

যদি আগের ভেক্টরের ডাটা ব্যবহার করি তাহলে output হবে key : 9 not found

কেউ টিউটোরিয়ালটা বুঝে থাকলে Age sort প্রবলেমটা solve করে ফেলতে পার।

আলী আকবরকে অসংখ্য ধন্যবাদ তার মূল্যবান পরামর্শ দিয়ে পোস্টটাকে আরো সমৃদ্ধ করার জন্য।

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