The easiest DFS (depth first search) Problem: UVa 459

N:B First understand the core dfs algorithm and implement it in your own way.There are a lot of resources in online like GeeksForGeeks and in Wiki.


Problem Link: Graph Connectivity
For more practice : Go to here

Source code in C++:

#include<bits/stdc++.h>
#define lli long long int
#define file freopen("in.txt","rt",stdin)
using namespace std;
vector<int> node[101];
int vis[101];
void dfs(int n)
{
    for(int i=0; i<node[n].size(); i++)
    {
        if(vis[node[n][i]]==0)
        {
            vis[node[n][i]] = 1;
            dfs(node[n][i]);
        }
    }
}


int main()
{
    char str[3];
    int test,temp,sum=0;
    char f,s;
    cin>>test;
    scanf("\n");
    while(test--)
    {
        gets(str);
        sum=0;
        temp = str[0];
        memset(vis,0,sizeof vis);
        while(gets(str) and str[0])
        {

            node[str[0]].push_back(str[1]);
            node[str[1]].push_back(str[0]);
        }

        for(int i=65; i<=temp; i++)
        {
            if(vis[i]==0)
            {
                sum++;
                dfs(i);
            }
        }
        cout<<sum;
       if(test)
       {
           cout<<"\n\n";
       }
       else
        cout<<"\n";
       for(int i=65;i<=90;i++)
        node[i].clear();
    }
    return 0;
}

How to represent an odd number sum of any three prime numbers.

Codeforces Number Theory Problem: D - Dima and Lisa 

Tutorial:

There is a fact that the distance between adjacent prime numbers isn't big. For n = 10⁹ maximal distanse is 282. So let's find maximal prime p, such that p < n - 1 (we can just decrease n while it's not prime(we can check it in O(sqrt(n) complexity). We know that n - p < 300. Now we have even (because n and p are odd) number n - p and we should divide it into a sum of two primes. As n - p < 300, we can just iterate over small primes P and check if P is prime and n - p - P is prime. You can check that there is a solution for all even numbers less than 300 by bruteforce.

Source Code in C++:

#include<bits/stdc++.h>
using namespace std;
int mark[1000000],PrimeNumber[1000000];
int n = 1000,nprime,limit;
void PrimeNum()
{
    mark[1]=1;

    PrimeNumber[nprime++]=2;

    for(int i=4; i<=n; i+=2)
        mark[i]=1;

    for(int i=3; i<=n; i+=2)
    {
        if(!mark[i])
        {
            PrimeNumber[nprime++]=i;

            if(i<=limit)
            {
                for(int j=i*i; j<=n; j=j+i*2)
                {
                    mark[j]=1;
                }
            }
        }
    }
}
int main()
{
    limit = sqrt(n+1);
    PrimeNum();
    int a,b;
    bool ok=false;
    cin>>a;
    int prime;
    for(int i=a-1;; i--)
    {
        ok =true;
        for(int j=2; j*j<=i; j++)
        {
            if(i%j==0)
            {
                ok=false;
                break;
            }
        }
        if(ok)
        {
            prime=i;
            break;
        }
    }
    int need = a - prime,got;


    for(int i=0;; i++)
    {

        got = need - PrimeNumber[i];

        ok =true;
        for(int j=2; j*j<=got; j++)
        {
            if(got%j==0)
            {
                ok=false;
                break;
            }
        }
        if(ok)
        {
            b=PrimeNumber[i];
            break;
        }

    }
    if(a==3)
    {
        cout<<1<<"\n"<<3<<endl;
    }
    else if(got==0)
    {
        printf("2\n");
        cout<<prime<<" "<<b<<endl;
    }
    else
    {
        printf("3\n");
        cout<<prime<< " "<<got<< " "<<b<<endl;
    }

    return 0;
}

Easy topological sort problem in C++. UVa-10305

Please don't copy code.At first try to understand the topological sort algorithm.
Best explanation in Bangla Language টপোলজিকাল সর্ট.


Implementation in C++.

Source code:

#include<bits/stdc++.h>
using namespace std;
int result[101];
vector<int>ans;
int main()
{
    vector<int>G[101];

    int n,m;
    while(cin>>n>>m)
    {
        if(n==0 && m==0)
            break;
        ans.clear();
        memset(result,0,sizeof result);
        for(int i=0; i<m; i++)
        {
            int node1,node2;
            cin>>node1>>node2;
            G[node1].push_back(node2);
            result[node2]++;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(result[j]==0)
                {
                    for(int k=0; k<G[j].size(); k++)
                    {
                        int t = G[j][k];
                        result[t]--;
                    }
                    result[j]=-1;
                    ans.push_back(j);
                    break;
                }
            }

        }
        for(int i=0; i<n; i++)
        {
            cout<<ans[i];
            if(i!=n-1)
                cout<<" ";
        }
        cout<<endl;

        for(int i=0;i<=n;i++)
        {
            G[i].clear();
        }

    }
    return 0;
}

Most easy Disjoint Set Union Problem. UVa-793-Network Connections.

C++ Source Code.
#include<bits/stdc++.h>
using namespace std;

int par[11111];

int find(int a)
{
    if(par[a]==a)
        return a;
    par[a] = find(par[a]);
    return par[a];
}

int main()
{
    int test,i;
    int n,m,computer,u,v;
    int ans1=0,ans2=0;

    char c;
    scanf("%d",&test);

    while(test--)
    {

        scanf("%d",&computer);
        getchar();
        for(i=1; i<=computer; i++)
        {
            par[i] = i;
        }
        ans1=0,ans2=0;
        while((c = getchar())&&isalpha(c))
        {

            scanf("%d%d",&n,&m);
            getchar();
            if(c=='c')
            {
                u = find(n);
                v = find(m);
                par[u] = v;
            }
            else
            {
                u = find(n);
                v = find(m);

                if(u==v)
                {
                    ans1++;
                }
                else
                    ans2++;
            }
        }

        printf("%d,%d\n",ans1,ans2);
        if(test)
            printf("\n");
    }

    return 0;
}

The easiest segment tree problem. Lightoj-1082

1082 - Array Queries  

First read about Segment tree in English or In Bangla ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি-১.

 Implemented in C:

#include<stdio.h>
#define mx 100009
int arr[mx];
int tree[mx*3];
void init(int NowNode,int L,int R) /** Building segment tree **/
{
    if(L==R)
    {
        tree[NowNode]=arr[L];
        return;
    }
    int left = NowNode*2;
    int right = NowNode*2+1;

    int mid = (L+R)/2;

    init(left,L,mid);
    init(right,mid+1,R);
    if(tree[left]<tree[right])
        tree[NowNode]=tree[left];
    else
        tree[NowNode]=tree[right];
}

int Query(int NowNode,int L,int R,int p,int q) /** Query **/
{
    if(p>R|| q<L)
    {
        return 9999999;
    }
    if(L>=p && R<=q)
        return tree[NowNode];

    int left = NowNode*2;
    int right = NowNode*2+1;
    int mid = (L+R)/2;
    int p1 = Query(left,L,mid,p,q);

    int p2 = Query(right,mid+1,R,p,q);
    if(p1<p2)
        return p1;
    else
        return p2;
}


int main()
{
    int n,j,m,k,p,q;
    int i,test;

    scanf("%d",&test);
    for(j=1;j<=test;j++)
    {
        getchar();
        scanf("%d%d",&n,&m);

        for(k=1;k<=n;k++)
        {
            scanf("%d",&arr[k]);
        }
        init(1,1,n);
        printf("Case %d:\n",j);
        for(k=1;k<=m;k++)
        {
            scanf("%d%d",&p,&q);
             printf("%d\n",Query(1,1,n,p,q));
        }
    }
    return 0;
}

Lightoj-1212 - Double Ended Queue

 
The simple deque implementation problem.

C++ Code (STL deque).

#include<bits/stdc++.h>
#define file freopen("lightoj.txt","rt",stdin)
using namespace std;

int main()
{
  //  file;
    deque<int>d;
    string str;
    int n,m,a,val,test;
    cin>>test;
    for(int j=1; j<=test; j++)
    {
        d.clear();

        printf("Case %d:\n",j);
        cin>>n>>m;

        for(int i=1; i<=m; i++)
        {
            cin>>str;
            if(str=="pushLeft")
            {
                cin>>a;
                if(d.size()<n)
                {
                    d.push_front(a);
                    cout<<"Pushed in left: "<<a<<endl;
                }
                else
                    cout<<"The queue is full"<<endl;
            }
            else if(str=="pushRight")
            {
                cin>>a;
                if(d.size()<n)
                {
                    d.push_back(a);
                    cout<<"Pushed in right: "<<a<<endl;
                }
                else
                    cout<<"The queue is full"<<endl;

            }
            else if(str=="popLeft")
            {

                if(!d.empty())
                {
                    val = d.front();
                    d.pop_front();
                    cout<<"Popped from left: "<<val<<endl;
                }
                else
                    cout<<"The queue is empty"<<endl;
            }
            else
            {
                if(!d.empty())
                {
                    val = d.back();
                    cout<<"Popped from right: "<<val<<endl;
                    d.pop_back();
                }
                else
                    cout<<"The queue is empty"<<endl;
            }
        }
    }
    return 0;
}

Lightoj 1305 - Area of a Parallelogram.

N:B Please don't copy source code.Try to find out the geometrical logic and work hard.

There are 2 or more solution of this problem. I have mentioned one by commenting by uses matrix formula for finding area of quadrilateral.

Or read again the problem.

 C program:

#include<stdio.h>
int main()
{

    double Ax,Ay,Bx,By,Cx,Cy,x,y;
    double a,b,c,ans,s,d,h;
    int i,test;
    scanf("%d",&test);
    for(i=1; i<=test; i++)
    {
        scanf("%lf %lf %lf %lf %lf %lf",&Ax,&Ay,&Bx,&By,&Cx,&Cy);
        x=Ax+Cx-Bx;
        y=Ay+Cy-By;
        a=sqrt((Ax-Bx)*(Ax-Bx)+(Ay-By)*(Ay-By));
        b=sqrt((x-Ax)*(x-Ax)+(y-Ay)*(y-Ay));
        c=sqrt((x-Bx)*(x-Bx)+(y-By)*(y-By));
        s=(a+b+c)/2.0;
        d = sqrt(s*(s-a)*(s-b)*(s-c));
       // ans = .5*fabs((Ax*By+Bx*Cy+Cx*y+x*Ay)-(Ax*y+x*Cy+Cx*By+Bx*Ay));/** Matrix solution **/

        printf("Case %d: %.0lf %.0lf %.0lf\n",i,x,y,2*d);
    }
    return 0;
}

Lightoj- 1338 - Hidden Secret!

Source code in C++.
-----------------------------
#include<bits/stdc++.h>
using namespace std;
int main()
{

    char str[109],str1[109];
    char arr[109],arr1[109];
    int n;
    scanf("%d ",&n);

    for(int k=1; k<=n; k++)
    {

        gets(str);
        gets(str1);
        int l=0;
        for(int i=0; i<strlen(str); i++)
        {
            if(str[i]>='A'&&str[i]<='Z')
            {
                str[i]=str[i]+' ';

            }
            if(str[i]!=' ')
            {
                arr[l]=str[i];
                l++;
            }
        }
        int m=0;
        for(int i=0; i<strlen(str1); i++)
        {
            if(str1[i]>='A'&&str1[i]<='Z')
                str1[i]=str1[i]+' ';
            if(str1[i]!=' ')
            {
                arr1[m]=str1[i];
                m++;
            }
        }
        sort(arr,arr+l);
        sort(arr1,arr1+m);
        bool ok= true;
        if(l==m)
        {

            if(ok)
                printf("Case %d: Yes\n",k);
            else
                printf("Case %d: No\n",k);
        }
        else
            printf("Case %d: No\n",k);
    }
    return 0;
}

lightoj-1020- A Childhood Game

Suggestion: Don's use or see any source code before you have tried enough.

It's a game theoretical basic problem.If you do not understand it please read first from Shafayater blog>game theory(1).
Source Code in C:

#include<stdio.h>
#include<string.h>
int main()
{
    long long int n,i,m,t;
    char str[10];
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld ",&t);
        scanf("%s",str);

        m=strcmp(str,"Alice");
        if(m==0)
        {
            if(t==1||(t-1)%3==0)
            {
                printf("Case %lld: Bob\n",i);
            }
            else
                 printf("Case %lld: Alice\n",i);
        }else
        {
            if(t%3==0)
            {
                printf("Case %lld: Alice\n",i);
            }
            else
                 printf("Case %lld: Bob\n",i);
        }
    }
    return 0;
}

 lightoj-1008-Fibsieve`s Fantabulous Birthday

Suggestion: Don's use or see any source code before you have tried enough.

#include<stdio.h>
#include<math.h>
#define lli long long int
int main()
{
    long long int test,i,mid,low,high,k,f,m;
    double n,l;
    scanf("%lld",&test);

    for(i=1; i<=test; i++)
    {
        scanf("%lf",&n);
        l=floor(sqrt(n));
        f = ceil(sqrt(n));
        if(n==1)
        {
            printf("Case %lld: 1 1\n",i);
        }
        else if(f==l)
        {
            if(f%2==0)
            {
                printf("Case %lld: %lld 1\n",i,f);
            }
            else
            {
                printf("Case %lld: 1 %lld\n",i,f);
            }
        }
        else
        {

            k=l+1;
            m=l;
            if(m%2==0)
            {
                low=(l*l)+1;
                high=(k*k);
                mid=(low+high)/2;
                if(n==mid)
                {
                    printf("Case %lld: %lld %lld\n",i,k,k);
                }
                else if(n<mid)
                {
                    printf("Case %lld: %lld %lld\n",i,k,llabs(low-n)+1);
                }
                else
                {
                    printf("Case %lld: %lld %lld\n",i,llabs(high-n)+1,k);
                }
            }
            else
            {
                low=(l*l)+1;
                high=(k*k);
                mid=(low+high)/2;
                if(n==mid)
                {
                    printf("Case %lld: %lld %lld\n",i,k,k);
                }
                else if(n>mid)
                {
                    printf("Case %lld: %lld %lld\n",i,k,llabs(high-n)+1);
                }
                else
                {
                    printf("Case %lld: %lld %lld\n",i,llabs(low-n)+1,k);
                }
            }
        }
    }
    return 0;
}