Minimum cost of a friend circle by using UNION FIND

এইটা Union Find টপিকস রিলেটেড

প্রবলেম লিঙ্কঃ http://codeforces.com/contest/893/problem/C

পুরো কোড সবার নিচে

দেখা যাবে দেওয়া থাকলো ৫ টা মান

ইনপুটঃ-

৫ ২           //৫ হল ৫ টা মান আর ২ হল ২ টা বন্ধুর লিস্ট

৮ ৫ ৩ ৪ ২   // এইগুলো হল পজিশন অনুযায়ী এদের ওয়েট যেমন ১ এর ৮,২ এর ৫ ,৩ এর ৩ ,৪ এর ৪ ,৫ এর ২

১ ৪          // ৪ ও ১ বন্ধু

৪ ৫         // ৪ ও ৫ বন্ধু

আউটপুটঃ-১০

এখন ১ ৪ ৫ একটা দল ,২ একটা দল,৩ একটা দল

এদের মধ্যে সব গুলো দলের মিনিমাম ওয়েট এর যোগফল কত?

উত্তর=১০

কারণ ১,৪,৫ এই দলের মিনিমাম ২+২ এর দলের ৫+৩ এর দলের ৩=১০

একটা কোড যদি করা থাকে সবার প্যারেন্ট কে এইবার মিনিমাম ওয়েট কিভাবে পাবো?

সেইটার কোডঃ

for(i=1;i<=n;i++)

        {

            par[i]=Find(i);

            st.insert(par[i]);

            mn[par[i]]=min(mn[par[i]],ar[i]);

            cout<<mn[par[i]]<<endl;

        }

set<long long >::iterator it;

        for(it=st.begin(); it!=st.end(); it++)

        {

            ans+=mn[*it];

        }

        cout<<ans<<endl;

পুরো কোডঃ-

#include <bits/stdc++.h>

using namespace std;

//long long vis[100010],ar[100010];

//vector<long long>vec[100010];

long long n,k;

long long par[100010],ar[100010],mn[100005];

long long Find(long long xx)

{

    if(par[xx]==xx)

        return xx;

    return par[xx]=Find(par[xx]);

}

void make_union(long long x,long long y)

{

    par[Find(y)]=Find(x);

}

set<long long>st;

main()

{

    //long k;

    cin>>n>>k;

    {

        long long i,u1,v1,ans=0;

        for(i=1; i<=n; i++)

        {

            cin>>ar[i];

            mn[i]=ar[i];

            par[i]=i;

        }

        for(i=1; i<=k; i++)

        {

            cin>>u1>>v1;

            make_union(u1,v1);

        }

        for(i=1;i<=n;i++)

        {

            par[i]=Find(i);

            st.insert(par[i]);

            mn[par[i]]=min(mn[par[i]],ar[i]);

            cout<<mn[par[i]]<<endl;

        }

        set<long long >::iterator it;

        for(it=st.begin(); it!=st.end(); it++)

        {

            ans+=mn[*it];

        }

        cout<<ans<<endl;

    }

}

Print 1 to 100 without for loop

#include<bits/stdc++.h>
using namespace std;
int i=1;
class A
{
    //int i=1;
public:
    A()
    {
        printf("%d\n",i++);
    }
};
//int A:: i=1;
main()
{
    A obj[100];
}

UVA 443 - Humble Numbers

#include<bits/stdc++.h>
using namespace std;
vector<long long>vec;
void calc()
{
    long i,i1,i2,i3;
    for(i=0;i<31;i++)
    {
        for(i1=0;i1<20;i1++)
        {
            for(i2=0;i2<14;i2++)
            {
                for(i3=0;i3<12;i3++)
                {
                    long long ans=pow(2,i)*pow(3,i1)*pow(5,i2)*pow(7,i3);
                    if(ans>0)
                        vec.push_back(ans);
                }
            }
        }
    }
    sort(vec.begin(),vec.end());
}
main()
{
    calc();
    long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        printf("The %d", n);
        if(n%10 == 1 && n%100 != 11)
            printf("st");
        else if(n%10 == 2 && n%100 != 12)
            printf("nd");
        else if(n%10 == 3 && n%100 != 13)
            printf("rd");
        else
            printf("th");
        printf(" humble number is %d.\n",vec[n-1]);
    }
}

UVA 12582 - Wedding of Sultan

#include<bits/stdc++.h>
using namespace std;
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        string s;
        long i,x;
        stack<char>st;
        cin>>s;
        st.push(s[0]);
        st.push(s[1]);
        long sz=s.size(),ar[100]={0};
        printf("Case %ld\n",cs++);
        for(i=2;i<sz-1;i++)
        {
            if(s[i]==st.top())
            {
                x=s[i]-'A';
                ar[x]++;
                st.pop();
                x=st.top()-'A';
                ar[x]++;
            }
            else
                st.push(s[i]);
        }
        for(i=0;i<26;i++)
        {
            if(ar[i]!=0)
            cout<<(char)(i+65)<<" = "<<ar[i]<<endl;
        }
    }
}

UVA 12583 - Memory Overflow

#include<bits/stdc++.h>
using namespace std;
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long n,sz,i,cnt=0;
        char ch;
        string s;
        map<char,long>mp;
        queue<char>q;
        cin>>n>>sz>>s;
        for(i=0;i<sz;i++)
        {
            q.push(s[i]);
            if(mp[s[i]]!=0)
                cnt++;
            mp[s[i]]++;
        }
        for(i=sz;i<n;i++)
        {
            ch=q.front();
            if(mp[s[i]]!=0)
                {
                    cnt++;
                }
            mp[ch]--;
            mp[s[i]]++;
            q.pop();
            q.push(s[i]);
        }
        printf("Case %ld: %ld\n",cs++,cnt);
    }
}

UVA 12898 - And Or

Explaintion:
Step 1: Count bit length of a and b
step 2: if lenb>lena then OR = 2^lenb - 1 and And = 0*/
step 3: find/count not change bits between a and b, from MSB to LSB
        Or = b | R
         And = b | ~R  where R contain's 1 (total 1 = count)

Example:
[1]a = 7  b = 8

lena = 3 , Lenb = 4

 so Or = 2^lenb - 1 = 16 - 1 = 15

And = 0

[2] Let a = 12 , b =15

lena = 4, len b = 4
a = 1100 , b = 1111

start j = 3 and break when j = 1

R = 1LL<<(j+1) - 1 = (11)2
unchanged first 2 bits
Or = b | R = (1111) = 15
And = b & ~R = (1100) = 12

Source Code:
#include<bits/stdc++.h>
using namespace std;
#define maxlen 61
typedef long long ll;
int main()
{
    int n,c,i,lena,lenb,j;
    int a1[maxlen],b1[maxlen];
    ll Or,And,x,a,b,R;
    const ll one = 1;
    scanf("%d",&n);
    for(i = 1; i <= n; i++)
    {
        scanf("%lld %lld",&a,&b);
        /*Step 1: Count bit length of a and b*/
        c = 0;
        x = a;
        while(x)
        {
            a1[c] = x&1;
            x >>= 1;
            c++;
        }
        lena = c;
        c = 0;
        x = b;
        while(x)
        {
            b1[c] = x&1;
            x >>= 1;
            c++;
        }
        lenb = c;
        /*step 2: if lenb>lena then OR = 2^lenb - 1 and And = 0*/
        /*step 3: find/count not change bits between a and b, from LSB to MSB
                  Or = b | R and And = b | ~R  where R contain's 1 (total 1 = count)
         */
        if(lenb>lena)
        {
            Or =(one<<lenb)-1;
            And = 0;
        }
        else
        {
            for( j = lenb-1; j >= 0; j--)
            {
                if(a1[j]!=b1[j]) break;
            }
            R = (one<<(j+1))-1;
            Or = b|R;
            And = b&~R;
        }
        printf("Case %d: %lld %lld\n",i,Or,And);
    }
    return 0;
}

UVA 1726 - Automatic Cheater Detection

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
#define nl         printf("\n")
#define case(a,b)  printf("Case %lld: %lld\n",a,b)
#define P(a)       printf("%lld\n",a)
#define SP(a)      printf("%lld ",a)
#define G(a)       scanf("%lld",&a)
#define GG(a,b)    scanf("%lld %lld",&a,&b)
#define pb         push_back
#define DB         printf("I WAS HERE\n")
#define SPP(a,b)   printf("%lld %lld\n",a,b)
#define LL         long long
int main()
{
    long long t;
    G(t);
    while(t--)
    {
        LL n;
        G(n);
        long long ar[12]={0},ar2[12]={0};
        char r[10];
        long long i,j,d,s,cnt=0;
        for(i=1;i<=n;i++)
        {
            scanf("%lld %lld %s",&d,&s,r);
            if(s==0 && r[0]=='i')
            {
                ar[d]++;
            }
            else if(s==1 && r[0]=='c')
            {
                ar2[d]++;
            }
        }
        cnt=0;
        for(i=1;i<=9;i++)
        {
            for(j=i+1;j<=10;j++)
            {
               LL x=ar[i]*ar2[j];
                cnt+=x;
            }
        }
        P(cnt);
    }

return 0;
}