UVA 12748 - Wifi Access

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
int main()
{
    int t;
    scanf("%d",&t);
    int I=1;
    int n,y;
    float x,Y,dis;
    while(t--)
    {
        printf("Case %d:\n",I++);
        scanf("%d%d",&n,&y);
        float xx[n],yy[n],rr[n];
        for(int i=0; i<n; i++)
        {
            scanf("%f%f%f",&xx[i],&yy[i],&rr[i]);
        }
        for(int i=0; i<y; i++)
        {
            scanf("%f%f",&x,&Y);
            long flag=0;
            for(int k=0; k<n; k++)
            {
                dis=sqrt(((x - xx[k])*(x - xx[k]))+((Y - yy[k])*(Y - yy[k])));
                if(dis<=rr[k])
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

UVA 531 - Compromise

PROBLEM TOPICS: LCS_LENGTH & PATH PRINT

#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>
#include <vector>
#define MX 210
using namespace std;

int dp[MX][MX], s[MX][MX];
vector<string> v1, v2;
int m, n;
int flag;
void lcsprint(int i, int j)
{
    if(i == 0 || j == 0)
        return;
    if(s[i][j] == 1)
    {
        lcsprint(i-1, j-1);
        if(flag == 0)
            cout << v1[i-1];
        else
            cout <<" " << v1[i-1];
        flag = 1;
    }
    else if(s[i][j] == 2)
    {
        lcsprint(i-1, j);
    }
    else
        lcsprint(i, j-1);
}


void LCSLength()
{
    int i, j;

    for (i = 0; i <= m; ++i)
        dp[i][0] = 0;

    for (j = 0; j <= n; ++j)
        dp[0][j] = 0;

    for (i = 1; i <= m; ++i)
    {
        for (j = 1; j <= n; ++j)
        {
            if (v1[i-1] == v2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
                s[i][j] = 1;
            }
            else if (dp[i-1][j] >= dp[i][j-1])
            {
                dp[i][j] = dp[i-1][j];
                s[i][j] = 2;
            }
            else
            {
                dp[i][j] = dp[i][j-1];
                s[i][j] = 3;
            }
        }
    }
    lcsprint(m, n);
    return;
}


int main()
{
    string s1, s2;

    while(getline(cin, s1))
    {
        // strcpy(a[length1++],temp);
        v1.clear();
        v2.clear();
        istringstream is(s1);
        while(is>>s2)
            v1.push_back(s2);
        while(getline(cin, s1))
        {
            if(s1 == "#")
                break;
            istringstream is(s1);
            while(is>>s2)
                v1.push_back(s2);
        }
        while(getline(cin, s1))
        {
            if(s1 == "#")
                break;
            istringstream is(s1);
            while(is>>s2)
                v2.push_back(s2);
        }
        flag = 0;
        m = v1.size();
        n = v2.size();
        LCSLength();
        printf("\n");
    }
    return 0;
}

UVA 10285 - Longest Run on a Snowboard

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
long dp[105][105],ar[105][105],r,c;
long call(long i1,long j1)
{
    if(dp[i1][j1]!=-1)
        return dp[i1][j1];
    long up=0,down=0,left=0,right=0;
    if(i1!=0&&ar[i1-1][j1]<ar[i1][j1])
    {
        up=call(i1-1,j1)+1;
    }
    if(i1!=r-1&&ar[i1+1][j1]<ar[i1][j1])
    {
        down=call(i1+1,j1)+1;
    }
    if(j1!=0&&ar[i1][j1-1]<ar[i1][j1])
    {
        left=call(i1,j1-1)+1;
    }
    if(j1!=c-1&&ar[i1][j1+1]<ar[i1][j1])
    {
       right=call(i1,j1+1)+1;
    }
    return max(up,max(down,max(left,right)));
}
main()
{
    timesave;
    long ts;
    cin>>ts;
    while(ts--)
    {
       string s;
       long i,j,mx=0;
        memset(dp,-1,sizeof(dp));
        cin>>s>>r>>c;
        for(i=0; i<r; i++)
        {
            for(j=0; j<c; j++)
            {
                cin>>ar[i][j];
            }
        }
        for(i=0; i<r; i++)
        {
            for(j=0; j<c; j++)
            {
                long len=call(i,j);
                mx=max(mx,len);
            }
        }
        cout<<s<<": "<<mx+1<<endl;
    }
}

Find the lexicographically smallest LCS (Longest Common Subsequence)

IF the lcs length is 0 then print :(
INPUT:
3
ab
ba

zxcvbn
hjgasbznxbzmx

you
kghs

OUTPUT:
a
zxb
:(

CODE
///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
string a,b;
long cs=1,n,m;
void call()
{
    long dp[n+1][m+1],i,j;
    string s[n+1][m+1];
    for(i=0; i<=n; i++)
    {
        dp[i][0]=0;
        s[i][0]="";
    }
    for(i=0; i<=m; i++)
    {
        dp[0][i]=0;
        s[0][i]="";
    }
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=m; j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=1+dp[i-1][j-1];
                s[i][j]=s[i-1][j-1]+a[i-1];
            }
            else if(dp[i-1][j]>dp[i][j-1])
            {
                dp[i][j]=dp[i-1][j];
                s[i][j]=s[i-1][j];
            }
            else if(dp[i][j-1]>dp[i-1][j])
            {
                dp[i][j]=dp[i][j-1];
                s[i][j]=s[i][j-1];
            }
            else
            {
                dp[i][j]=dp[i-1][j];
                s[i][j]=min(s[i-1][j],s[i][j-1]);
            }
        }
    }
    if(dp[n][m]==0)
        cout<<"Case "<<cs++<<": :("<<endl;
    else
        cout<<"Case "<<cs++<<": "<<s[n][m]<<endl;
}
main()
{
    timesave;
    long ts;
    cs=1;
    cin>>ts;
    while(ts--)
    {
        cin>>a>>b;
        n=a.size(),m=b.size();
        call();
    }
}