[UVa] 531 - Compromise

Critical case: Normally you'd just check Part 1 against Part 2. But checking Part 2 agianst Part 1 might yield a better result.

#include <cstdio>
#include <iostream>
#include <map>
#include <string>
using namespace std;

int c[300][300], b[300][300], print1[300], print2[300];
int printer(int i, int j, int *x, int *print)
{
    int k=0;
    while (i>0 || j>0)
    {
        if (b[i][j]==1)
        {
            print[k++]=x[i];

            i--; j--;
        } else if (b[i][j]==2)
        {
            i--;
        } else
        {
            j--;
        }
    }
    return k;
}
int lcs(int *x, int *y, int size_a, int size_b)
{


    int m = size_a, n = size_b, i, j;
    for (i=0 ; i<=m ; i++)
    {
        for (j=0 ; j<=n ; j++)
        {
            c[i][j]=b[i][j]=0;
        }
    }

    for (i=1 ; i<m ; i++)
    {
        for (j=1 ; j<n ; j++)
        {
            if (x[i]==y[j])
            {
                c[i][j] = c[i-1][j-1]+1;
                b[i][j]=1;
            } else {
                if (c[i-1][j]>=c[i][j-1])
                {
                    c[i][j]=c[i-1][j];
                    b[i][j]=2;
                } else
                {
                    c[i][j]=c[i][j-1];
                    b[i][j]=3;
                }
            }
        }
    }
    return c[i-1][j-1];
}

class v
{
    public:
    string word;
    int id;
};

string s;
int main()
{
    while (1)
    {
        if (cin >> s)
        {
            map<string,int>l1;
            v wordList[300]={"",0};
            int i, l1_count=1, seq1_len=1, seq2_len=1, sizer, size1, size2, *print;
            int seq1[200], seq2[200];
            l1[s]=l1_count;
            wordList[l1_count].id = l1_count;
            wordList[l1_count].word=s;
            seq1[ seq1_len++ ] = l1_count++;
            while (cin >> s && s!="#")
            {
                if (l1[s])
                {
                    seq1[ seq1_len++ ] = l1[s];
                } else {
                    l1[ s ] = l1_count;
                    wordList[l1_count].id = l1_count;
                    wordList[l1_count].word = s;
                    seq1[ seq1_len++ ] = l1_count++;
                }
            }
            while (cin >> s && s!="#")
            {
                if (l1[s])
                {
                    seq2[ seq2_len++ ] = l1[s];
                } else {
                    l1[ s ] = l1_count;
                    wordList[l1_count].id = l1_count;
                    wordList[l1_count].word = s;
                    seq2[ seq2_len++ ] = l1_count++;
                }
            }
            size1 = lcs(seq1,seq2,seq1_len,seq2_len);
            printer(seq1_len-1,seq2_len-1, seq1, print1);
            size2 = lcs(seq2,seq1,seq2_len,seq1_len);
            printer(seq2_len-1,seq1_len-1, seq2, print2);

            if (size1>size2)
            {
                print = &print1[0];
                sizer=size1;
            } else
            {
                print = &print2[0];
                sizer=size2;
            }

            for (i=sizer-1 ; i>0 ; i--)
            {
                cout << wordList[print[i]].word << " ";
            }
            cout << wordList[print[i]].word << endl;

        } else {
            break;
        }
    }
    return 0;
}

[UVa] 10004 - Bicoloring

Method:

First color the whole graph using DFS

Then recheck the given edge list for common colors in vertexes.

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;
bool state;
int c[1000], color[1000], clr, n, adj[1000][1000], list[1000][2];
void dfs_core(int i, int n, int p)
{
    int j;

    color[i]=true;
    if (p<0) c[i]=0;
    else c[i]=(p+1)%2;

    FOR(j, 0, n)
    {
        if (!color[j] && adj[i][j])
        {
            dfs_core(j,n,c[i]);
        }

    }
}
void dfs_shell(int n)
{
    int i;

    clr=0;
    FOR(i, 0, n)
    {
        color[i]=false;
        c[i]=-1;
    }
    FOR(i, 0, n)
    {
        if (!color[i])
            dfs_core(i,n,c[i]);
    }
}

int main()
{
    int i, j, x, y, e;
    while (scanf("%d",&n) && n)
    {
        FOR(i, 0, n)
        {
            FOR(j, 0, n)
            {
                adj[i][j]=0;
            }
        }
        scanf("%d",&e);
        FOR(i, 0, e)
        {
            scanf("%d %d",&x,&y);
            adj[x][y]=adj[y][x]=1;
            list[i][0]=x;
            list[i][1]=y;
        }
        dfs_shell(n);

        state=true;
        FOR(i, 0, e)
        {
            if (c[list[i][0]]==c[list[i][1]])
            {
                state=false;
                break;
            }
        }

        if (state)
        {
            printf("BICOLORABLE.\n");
        } else
        {
            printf("NOT BICOLORABLE.\n");
        }
    }
    return 0;
}

[UVa] 495 - Fibonacci Freeze

import java.util.Scanner;
import java.math.BigInteger;
/**
 *
 * @author Tafhim
 */
public class Main {

    
    public static void main(String[] args) {
        
        BigInteger[] fibs = new BigInteger[5004];
        fibs[0] = BigInteger.ZERO;
        fibs[1] = BigInteger.ONE;
        for (int i=2 ; i<=5000 ; i++)
        {
            fibs[i] = fibs[i-1].add(fibs[i-2]);
        }
        Scanner input = new Scanner(System.in);

        int q;

        while (input.hasNext())
        {
            q = input.nextInt();
            System.out.printf("The Fibonacci number for %d is %d\n",q,fibs[q]);
            
        }
    }
}

Important links

Mathematics:
Series and Sums

Programming help [Algorithms, Codes, Links]:
Mehadi Bhai's Blog
Shafaet's Blog
Fahim Bhai's Site
Fahim Bhai's Page

Online Judge [Contest, Problems, Virtual Contests]
TopCoder
Codeforces
Codechef

[UVa] 10642 - Can you solve it?

Analysis:
Draw the coordinate system but start from 1 not 0, just to escape negative value problems. Draw it like a triangle where the top has 1. Now see that on the right side, every i-th number is the sum of all numbers till i.
1 = 1x(1+1)/2
3 = 2x(2+1)/2
6 = 3x(3+1)/2
10 = 4x(4+1)/2
15 = 5x(5+1)/2
So, given the x coordinate you can find the first number in that row using X*(X+1)/2, BUT make X=X+1 first.
To find the Y-th element (in my case (Y+1)-th, you can use the formula
S = a + (a+d) + (a+2d) + ... + [a + (n-1)d] = n[2a + (n-1)d]/2
But you have to modify it a bit first. This is derived from the analysis that every number in a row has some initial numbers lost except the first row. In X=2, 2 is not in the series, in X=3, 3 and 4 are not in the series. This keeps increasing by 1 at every i. So the series is
Y[0], Y[0]+1x1, Y[0]+1x2, Y[0]+1x3 ......
So you can simply use the formula with a=0 and n=Y+(X-1). Just add X to that.
Find both the numbers this way and print their difference. Done!!!.


A useful link for Summation formulas

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;
int sum(int a, int n)
{
    return n*(2*a+(n-1)*1)/2;
}
int main()
{
    int test, kase=1, x1, x2, y1, y2, num1, num2, temp, n, a;
    scanf("%d",&test);
    while (test--)
    {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        x1++; x2++; y1++; y2++;


        num1 = x1+(sum(0,y1+(x1-1)));
        num2 = x2+(sum(0,y2+(x2-1)));


        printf("Case %d: %d\n",kase++,num2-num1);
    }
    return 0;
}

[UVa] 11057 - Exact Sum

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;
int a[20000]={0};


bool cmp(int x, int y)
{
    return (x<y);
}
int cmp2(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}
int main()
{
    int n, i, val, *p, x, s, maxDiff, pX, pY;

    while (scanf("%d",&n)==1)
    {



        for (i=0 ; i<n ; i++)
        {
            scanf("%d",&a[i]);

        }
        scanf("%d",&val);
        QSORT(a,n,int,cmp2);
        maxDiff = 9999999;
        for (i=0 ; i<n-1 ; i++)
        {
            x=a[i];
            s = val-x;



            p = NULL;
            p = (int*)bsearch(&s,&a[i+1],n-i-1,sizeof(int),cmp2);
            if (p)
            {
                if (abs((*p)-x)<maxDiff)
                {
                    pX = x;
                    pY = (*p);
                    maxDiff = abs((*p)-x);

                }
            }

        }
        if (pX>pY) swap(pX,pY);
        printf("Peter should buy books whose prices are %d and %d.\n\n",pX,pY);

    }
    return 0;
}

Moving!!!

I'm making a shift to Wordpress from Blogger. It's disappointing how Blogger sucks so much after my being such a dedicated user for over 5 years. No more. I'm tired of downtimes and slow site access.

Please visit my new site at : http://www.tafhimui.wordpress.com

I'll still be updating this site in hopes of Blogger becoming a good host some day.

[UVa] 10191 - Longest Nap

A much complex and inefficient solution follows. This one is simpler and more efficient.

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;
char input[1000];

struct timex
{
    int start;
    int end;
} array[500];

bool cmp(timex x, timex y)
{
    return (x.start < y.start);
}

int main()
{
    int nTask, i, maxStart, maxInterval, interval;
    int hour1, hour2, minute1, minute2, hour, minute, j, day=1;
    while ( cin >> nTask )
    {
        getchar();
        i=0;
        array[i].start = 600;
        array[i].end = 600;
        for (i=1 ; i<=nTask ; i++)
        {
            gets(input);
            sscanf(input,"%d:%d %d:%d",&hour1,&minute1,&hour2,&minute2);



            array[i].start = hour1*60 + minute1;
            array[i].end = hour2*60 + minute2;
        }
        array[i].start = 1080;
        array[i].end = 1080;
        i++;

        sort(array,array+i,cmp);


        for (j=1, maxInterval=-1 ; j<=nTask+1 ; j++)
        {
            interval = array[j].start-array[j-1].end;
            if (interval > maxInterval)
            {
                maxStart = array[j-1].end;
                maxInterval = interval;
            }
        }

        hour = (int)maxStart/60;
        minute = maxStart%60;



        if (maxInterval>=60)
            printf("Day #%d: the longest nap starts at %d:%.2d and will last for %d hours and %d minutes.\n",day++,hour,minute,(int)maxInterval/60,maxInterval%60);
        else
            printf("Day #%d: the longest nap starts at %d:%.2d and will last for %d minutes.\n",day++,hour,minute,maxInterval);

    }
    return 0;
}

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;
char inp[10000];
int data[60][60];
struct time
{
    int h, m;
} initTime, maxInitTime;
int napTimer, maxNapTimer;

void setter(int hour1, int minute1, int hour2, int minute2)
{
    int i, j, jLimit;

    for (i=hour1 ; i<=hour2 ; i++)
    {
        if (i==hour1) j=minute1;
        else j=0;
        if (i==hour2) jLimit=minute2-1;
        else jLimit = 59;

        for ( ; j<=jLimit ; j++)
        {
            data[i][j]=1;
        }
    }
}

void parser(char *inp)
{
    int i, j, hour1, hour2, minute1, minute2;
    char h[10];

    for (i=0 ; !(inp[i]>='0') && !(inp[i]<='9') ; i++); // Skipping initial blanks
    for (i, j=0 ; inp[i]>='0' && inp[i]<='9' ; i++, j++)
    {
        h[j]=inp[i];
    }
    h[j]='\0';
    hour1 = atoi(h);
    for (i ; inp[i]!=':' ; i++);
    for (i ; inp[i]==':' ; i++);
    for (i ; !(inp[i]>='0') && !(inp[i]<='9') ; i++);
    for (i, j=0 ; inp[i]>='0' && inp[i]<='9' ; i++, j++)
    {
        h[j]=inp[i];
    }
    h[j]='\0';
    minute1 = atoi(h);

    //cout << " --> " << i << endl;
    for (i ; inp[i]==' ' ; i++); //Skipping spaces
    for (i, j=0 ; inp[i]>='0' && inp[i]<='9' ; i++, j++)
    {
        h[j]=inp[i];
    }
    h[j]='\0';
    hour2 = atoi(h);
    for (i ; inp[i]!=':' ; i++);
    for (i ; inp[i]==':' ; i++);
    for (i ; !(inp[i]>='0') && !(inp[i]<='9') ; i++);
    for (i, j=0 ; inp[i]>='0' && inp[i]<='9' ; i++, j++)
    {
        h[j]=inp[i];
    }
    h[j]='\0';
    minute2 = atoi(h);


    setter(hour1, minute1, hour2, minute2);
}

void initData()
{
    int i, j;
    for (i=10 ; i<=20 ; i++)
    {
        for (j=0 ; j<=60 ; j++)
        {
            data[i][j]=0;
        }
    }
}



void napFinder()
{
    bool napOpen;
    napTimer=0;
    maxNapTimer=-1;
    maxInitTime={-1,-1};
    initTime={-1,-1};
    int i, j;
    napOpen=false;
    if (data[10][0]==0)
    {
        //napOpen=true;
        initTime={10,0};
    }


    for (i=10 ; i<18 ; i++)
    {
        //cout << "\t" << i << endl;


        for (j=0 ; j<=59 ; j++)
        {

            if (data[i][j]==0)
            {
                if (napOpen)
                {
                    napTimer++;

                }
                else
                {
                    napOpen=true;
                    initTime={i,j};

                    napTimer=0;
                }
            }
            else
            {
                if (napOpen)
                {
                    napOpen=false;
                    if (napTimer>maxNapTimer)
                    {
                        maxNapTimer=napTimer;
                        maxInitTime=initTime;
                        //cout << " -> " << napTimer << endl;
                        napTimer=0;
                    }
                } else
                {
                    napTimer=0;
                }
            }

        }
    }
    if (napOpen)
    {
        napOpen=false;
        if (napTimer>maxNapTimer)
        {
            maxNapTimer=napTimer;
            maxInitTime=initTime;

            napTimer=0;
        }
    }
}

int main()
{

    //freopen("input.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);


    int nTask, i, hours, minutes, kase=1;
    char maxInitTimeHourPrint[100], maxInitTimeMinutePrint[100];
    while (cin >> nTask)
    {
        getchar();
        initData();
        for (i=0 ; i<nTask ; i++)
        {
            gets(inp);
            parser(inp);
        }
        napFinder();

        maxNapTimer++;
        hours = maxNapTimer / 60;
        if (maxNapTimer%60)
            minutes = maxNapTimer%60;



        if (maxInitTime.h>9)
            sprintf(maxInitTimeHourPrint,"%d",maxInitTime.h);
        else
            sprintf(maxInitTimeHourPrint,"0%d",maxInitTime.h);
        if (maxInitTime.m>9)
            sprintf(maxInitTimeMinutePrint,"%d",maxInitTime.m);
        else
            sprintf(maxInitTimeMinutePrint,"0%d",maxInitTime.m);

        printf("Day #%d: the longest nap starts at %s:%s and will last for ",kase++,maxInitTimeHourPrint,maxInitTimeMinutePrint);
        if (maxNapTimer>=60)
            printf("%d hours and %d minutes.\n",(int)maxNapTimer/60,maxNapTimer%60);
        else
            printf("%d minutes.\n",maxNapTimer);
    }
    return 0;
}

[UVa] 10591 - Happy Number

Method:
Kept a table of happy and unhappy numbers. Once a number is found to be unhappy/happy the whole sequence that is left behind has the same property. I tagged them out using a stack.

/* --------------------------> BISMILLAHIR RAHMANIR RAHIM <------------------------------ */
/* ------------------------> Tafhim Ul Islam [ CSE-09@IIUC ] <--------------------------- */
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <vector>
#include <climits>
#include <set>
#include <algorithm>
#define MI INT_MAX
#define ULONG unsigned long long
#define LLONG long long
#define swap(a,b) {int t=a ; a=b ; b=t; }
#define sz(a) sizeof(a)
#define FOR(i, a, b) for (i=a ; i<b ; i++)
#define QSORT(a,n,s,f) qsort(a,n,sizeof(s),f)
using namespace std;

map<int,int> ver;
int sqrs[10];

int digSum(int n)
{

    int sum=0;
    while (n)
    {
        sum+=sqrs[(n%10)];
        n/=10;
    }
    return sum;
}

int sqr()
{
    int i;
    for (i=0 ; i<=9 ; i++)
    {
        sqrs[i]=i*i;
    }
    return 0;
}

int findIf(int n)
{
    int j;
    int stat;

    if (ver[n]==3)
        return 3;

    map<int,bool> vis;
    stack<int> list;
    for (j=digSum(n) ; ; j=digSum(j))
    {
        list.push(j);
        if (vis[j] || ver[j]==1)
        {
            stat=1;
            break;
        }
        if (ver[j]==3)
        {
            ver[n]=3;
            stat=3;
            break;
        }
        if (j==1)
        {
            ver[n]=3;
            stat=3;
            break;
        }
        if (j==n)
        {
            stat=1;
            break;
        }
        vis[j]=true;
    }

    while (!list.empty())
    {
        ver[list.top()]=stat;
        list.pop();
    }

    return stat;
}

int main()
{

    sqr();


    int test, inp, kase=1;
    scanf("%d",&test);
    while (test--)
    {
        scanf("%d",&inp);

        printf("Case #%d: ",kase++);

        if (findIf(inp)==3)
            printf("%d is a Happy number.\n",inp);
        else
            printf("%d is an Unhappy number.\n",inp);
    }
    return 0;
}