[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.