Solve Of UVA 13152 (Balanced String)

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

sample ভ্যালিড স্ট্রিংঃ
( )
( ( ) )
( ) ( )
( ( ) ) ( )
( ( ) ) ( ( ) )

এই ভ্যালিড স্ট্রিংগুলোকে আমি যদি নাম্বারের সাহায্যে প্রকাশ করিঃ
তাহলেঃ
( )                        -> ১,০
( ( ) )                   -> ১,২,১,০
( ) ( )                   -> ১,০,১,০
( ( ) ) ( )              -> ১,২,১,০,১,০
( ( ) ) ( ( ) )         -> ১,২,১,০,১,২,১,০

( ( ) ( ) ) ( )         -> ১,২,১,২,১,০,১,০

আমাকে ভ্যালিড স্ট্রিং এর মধ্যে যেটা লেক্সিকোগ্রাফিক্যালি ছোট সেটা প্রিন্ট করতে হবেঃ
সুতরাংঃ
( ( ) ) ( ( ) )         -> ১,২,১,০,১,২,১,০

( ( ) ( ) ) ( )         -> ১,২,১,২,১,০,১,০

এই ২টা স্ট্রিং এর মধ্যে আমাকে ২য় টা প্রিন্ট করতে হবে।

যদি ২য় স্ট্রিং এর নাম্বার সিকুয়েন্স খেয়াল কর, তাহলে দেখবে নাম্বার ছোট থেকে বড় হচ্ছে, যখন আর বড় নাম্বার পাচ্ছে না, তখন আবার ১ ছোট হয়ে সেইম কাজ করতেসে। যখন আর বড় নাম্বার পাবে না তখনই ১ ছোট হচ্ছে, তাই একসময় ছোট হতে হতে ০ হওয়ে যাবে। এখানেই আমার মেইন array টা পেয়ে যাব।

আশা করি বুঝতে পারস array টা কে কি করতে হবেঃ

স্টেপসঃ

প্রথমত ১টা ডায়নামিক array রাখব।

১। আমি যে নাম্বার টা পাইসি সেটার থেকে ১ বড় নাম্বার খুজব ( অর্থাত নাম্বার+১ ) । পেলে স্টেপ ২ তে যাব। না পেলে স্টেপ ৩ এ যাব।

২। আমি যে নাম্বার টা পাইসি সেটা ডায়নামিক array তে পুশ করব।

৩। নাম্বার থেকে ২ বিয়োগ করে আবার স্টেপ থেকে চেক করব। ২ বিয়োগ করব কারন স্টেপ ১ এ আমি ১ যোগ করেই কিন্তু চেক করতেসি।

এরপর ডায়নামিক array থেকে স্ট্রিং টা প্রিন্ট করব।

কোডঃ

#include<bits/stdc++.h>using namespace std;
map<int,int>mp;
int arr[100009];
vector<int>v;
void cas(int i)
{
    printf("Case %d: ",i);
    return;
}
int main()
{
    int n,i,j,k,l,m,tst;
    cin>>tst;
    for(int t= 1; t<=tst; t++)
    {
        cin>>n;
        int mx = -1;
        mp.clear();
        v.clear();
        for(i=0; i<n; i++)
        {
            cin>>arr[i];
            mp[arr[i]]++;
            mx = max(mx,arr[i]);
        }
        int indx=0;
        for(i=0; i<2*n; i++)
        {
            if(mp[indx+1]>0)
            {
                v.push_back(indx+1);
                indx++;
                mp[indx]--;
            }
            else
            {
                indx-=2;
            }
        }
        cas(t);
        if(v.size() != n)
        {
            cout<<"invalid"<<endl;
            continue;
        }
        int ck = 2;
        for(i=0; i<=mx; i++)
        {
            if(mp[i]>0)
            {
                ck=3;
                break;
            }
        }
        string st="(";
        indx=v[0];
        int res = 1;
        for(i=1; i<n; i++)
        {
            if(v[i]>indx)
            {
                st+='(';
                res++;
            }
            else if(v[i]<indx)
            {
                st+=')';
                res--;
            }
            else
                ck=3;
            indx=v[i];
        }
        if(ck==3 || res != 0)
            cout<<"invalid"<<endl;
        else
            cout<<st<<endl;
    }
    return 0;
}

কোন ভুল থাকলে বললে খুশি হব। :)