Codeforces Round 264(Problem D)

প্রবলেমঃ 

n টা নাম্বারের k টা permutation দেয়া হবে। আমাকে permutation গুলোর মধ্যে longest common subsequence বের করতে হবে।

যদি প্রথম চারটা নাম্বারের তিনটা permutation দেয়া থাকে এমনঃ

1 4 2 3
4 1 2 3
1 2 4 3

তাহলে উত্তর হবে ৩। কারণ, সব permutation এই ১>২>৩ subsequence টা কমন। আর যেহেতু এই কমন sequence এর length ৩ এবং এটিই longest length, তাই উত্তরও ৩, অর্থাৎ আউটপুট হবে ৩।

প্রবলেম লিঙ্কঃ D. Gargari and Permutations

কিভাবে করব ?

একটি 2D array নিই, যেটিতে প্রতিটা permutation এ কোন একটি value কততম পজিশনে আছে, সেটা থাকবে।

ধরি, integer টাইপ array টি হল pos[7][1010]। এই array এর pos[1][3] তে ১ নং permutation এ ৩ ভ্যালুটি কততম পজিশনে আছে, তা store করা হবে। যেমন, উপরে যে ইনপুট সেটটি দেয়া আছে, তার জন্য pos[1][3] তে থাকবে 4। কারণ ১ নং permutation এ ৩ আছে ৪ নং পজিশনে।

এবার আমি ডিপি চালাব। এই recursive dp এর স্টেট থাকবে একটি (ধরি, u)।  রিকার্সিব ফাংশনের নাম rec() হলে, rec(u) আমাকে sequence এ u রেখে প্রাপ্ত sequence length রিটার্ন করবে।

recursive ফাংশনঃ

#define fr(i,a,b) for(i=a;i<=b;i++)
int dp[si];
int rec(int u)
{
    int &ret=dp[u],i,j,cnt;
    if(ret!=-1)
    return ret;
    ret=0;
    fr(i,1,n)
    {
        cnt=0;
        fr(j,1,k)
        {
            if(pos[j][u]<pos[j][i])
            cnt++;
        }
        if(cnt==k)
        ret=max(ret,1+rec(i));
    }
    return ret;
}

main function টি হবে এমনঃ

while(~scanf("%d%d",&n,&k))
{
    mx=0;
    fr(i,1,k)
    {
        fr(j,1,n)
        {
            scanf("%d",&v);
            pos[i][v]=j;
        }
    }
    mem(dp,-1);
    fr(i,1,n)
    mx=max(mx,1+rec(i));
    printf("%d\n",mx);
}

main function থেকে প্রতিবার i দিয়ে rec() কল করছি। এর অর্থ হচ্ছে sequence এর প্রথম element i হলে প্রাপ্ত sequence length। এক যোগ করছি, কারণ i কে প্রথম element করে আমি already sequence এর length এক পেয়ে গিয়েছি। রিকার্সিব ফাংশনে আসার পর(i এখন u) u ভ্যালুটি আরেকটি ভ্যালু (ধরি i) খুজে যে প্রতিটি permutation এই তার পরে এসেছে। ব্যাপারটি উপরের উদাহরণ দিয়ে বলি। আমি যদি main function থেকে i=1 দিয়ে rec() কল দেই, তাহলে rec() এ u=1। এখন সে ১<=i<=n(সবসময় ১ থেকে n পর্যন্ত লুপ চলবে) এর জন্য চেক করে দেখবে, কোনটির জন্য সে max length পায়। আর আবার কল সে তখনই দিবে, যখন কোন একটি i সব permutation এই তার পরের যেকোন পজিশনে আসে। এটি চেক করা হয়েছে if(pos[j][u]<pos[j][i]) – এই কন্ডিশনের মাধ্যমে। কোন একটি permutation এর জন্য এই কন্ডিশন ট্রু হলে cnt এর মান increment করছি। আর cnt এর মান যখন total permutation এর সমান হবে, অর্থাৎ সব permutation এই u ভ্যালুটি i ভ্যালুর আগে এসেছে, তখনি আমি i দ্বারা আবার rec() কল দিয়েছি। সাথে sequence এ i যোগ হওয়ায় sequence length ১ যোগ করেছি।

Advertisements

মন্তব্য করুন

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / পরিবর্তন )

Twitter picture

You are commenting using your Twitter account. Log Out / পরিবর্তন )

Facebook photo

You are commenting using your Facebook account. Log Out / পরিবর্তন )

Google+ photo

You are commenting using your Google+ account. Log Out / পরিবর্তন )

Connecting to %s