Friday, September 30, 2011

[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;
}

2 comments:

  1. Gobbasso7:25 PM

    I wish I could understand that code. :'(

    ReplyDelete
  2. Please point out which points confuse you so that I can help you. If you do not understand the coding language used here altogether, then you should first learn C/C++.

    ReplyDelete

Post your comment here. If you want to say something about programming problems, scripts, software etc, please try to be as descriptive as possible.

Connect Rapoo MT750S with Linux (Tested on Manjaro)

 I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...