SPOJ Problem ULM02

THE SIERPINSKI FRACTAL

Explanation:

This problem requires you to print the Sierpinski triangle of size n (1 <= n <= 10).

The problem can be solved using simple recursion technique. Below is my approach to the problem.

First, print the triangle of size n, then 3 triangles of size (n-1), one is the top one, second on the bottom-left, third on the bottom-right.

Below is the solution for the problem.

Solution:

#include<cstdio>
#define SIZE 1500
using namespace std;

char mat[SIZE][SIZE * 2];

void display(int maxRow, int maxCol){
    for(int i=0;i<maxRow;i++){
        for(int j=0;j<maxCol;j++)
            printf("%c", mat[i][j]);
        printf("\n");
    }
}

void prepareTraingleUtil(int startRow, int endRow, int startCol, int endCol, int size){
    if(size == 0)
        return;
    int startX = startRow;
    int startY = (startCol + endCol) / 2;
    for(int x = startX, y = startY, z = startY + 1;x <= endRow;x++, y--, z++){
        mat[x][y] = '/';
        mat[x][z] = '\\';
    }
    int midRow = (startRow + endRow) / 2;
    int rowDiff = midRow - startRow;
    for(int y = startCol + 1;y < endCol;y++)
        mat[endRow][y] = '_';

    //  top triangle
    prepareTraingleUtil(startRow, midRow, startY - rowDiff, startY + 1 + rowDiff, size - 1);

    //  left triangle
    prepareTraingleUtil(midRow + 1, endRow, startCol, startY, size - 1);

    //  right triangle
    prepareTraingleUtil(midRow + 1, endRow, startY + 1, endCol, size - 1);
}

void prepareTriangle(int n){
    int maxRow = 1 << n;
    int maxCol = maxRow << 1;
    for(int i=0;i<maxRow;i++)
        for(int j=0;j<maxCol;j++)
            mat[i][j] = ' ';
    prepareTraingleUtil(0, maxRow - 1, 0, maxCol - 1, n);
    display(maxRow, maxCol);
}

int main(){
    int n;
    while(true){
        scanf("%d", &n);
        if(n == 0)
            break;
        prepareTriangle(n);
        printf("\n");
    }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem MKJUMPS

MAKING JUMPS

Explanation:

This problem requires us to find the minimum no. of cells which can not be visited by the knight among all the paths taken. Or, in other words, we can say, we need to find the maximum no. of cells (or longest path) which this knight can visit starting from cell (0, 0).

So, basically we can find the longest path using DFS (if you are not aware, below are the links provided to learn DFS).

Below is the solution provided. Happy coding!

DFS learning links.
1. http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

Solution:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define in_range(x, y, r, c) (x >= 0 && x < r && y >= 0 && y < c)
#define INF 100000000
#define SIZE 11

using namespace std;
char maze[SIZE][SIZE];
int a[] = {-2, -2, -1, 1, 2, 2, 1, -1}, b[] = {-1, 1, 2, 2, 1, -1, -2, -2}, visitedNodes;

void init(){
    //  Fill the chessboard with #s.
    for(int i=0;i<SIZE;i++)
        for(int j=0;j<SIZE;j++)
            maze[i][j] = '#';
}

void dfs(int x, int y, int r, int c, int cntNodes){
    //  Mark current cell as 'v' which denotes this cell is visited.
    maze[x][y] = 'v';
    bool noRoute = true;
    for(int i=0;i<8;i++){
        //  Find next cell to be visited.
        int tmpX = x + a[i];
        int tmpY = y + b[i];
        //  If the cell lies within the chessboard and is not visited.
        if(in_range(tmpX, tmpY, r, c) && maze[tmpX][tmpY] == '.'){
            noRoute = false;
            //  Run dfs on that cell.
            dfs(tmpX, tmpY, r, c, cntNodes + 1);
        }
    }
    /*  If no more cell can be visited from the current node,
        update maximum path length if current path length
        is greater than the maximum one.*/
    if(noRoute){
        if(visitedNodes < cntNodes)
            visitedNodes = cntNodes;
        //display();
    }
    //  Mark the cell as unvisited, as it might be a part of another path.
    maze[x][y] = '.';
}

int main(){
    int r, x, y, cnt, cas=1;
    while(true){
        scanf("%d", &r);
        if(r == 0)
            break;
        //  Initialize the chessboard.
        init();
        cnt = 0;
        visitedNodes = -INF;
        for(int i=0;i<r;i++){
            scanf("%d%d", &x, &y);
            for(int j=x;j<x + y;j++){
                //  Mark the cells in the chessboard with '.'s which can be visited.
                maze[i][j] = '.';
                //  Update the count of cells which can be visited.
                cnt++;
            }
        }
        //  Run a dfs on cell [0][0], which is the top-left cell.
        dfs(0, 0, SIZE, SIZE, 1);
        int res = cnt - visitedNodes;
        if(res == 1)
            printf("Case %d, 1 square can not be reached.\n", cas++);
        else
            printf("Case %d, %d squares can not be reached.\n", cas++, res);
    }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem SOLDIERS

SOLDIERS

Explanation:

The problem asks us to find the maximum no. of soldiers which can be placed on a m x n chessboard.
Here is the answer for the problem.

maximum (( m * (( n + 1 ) / 2 )), ( n * (( m + 1 ) / 2 ))).

But, here is the twist in the problem. 1 <= m <= 10^30 and 1 <= n <= 10^30. For this, we can simply use strings and we are done.

Below is the solution provided. Happy coding!

Solution:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

string add(string a, string b){
    //  Returns the sum of a and b.
    stack<int> st;
    string res = "";
    int i = a.length() - 1, j = b.length() - 1, carry = 0, sum;
    while(i >= 0 && j >= 0){
        sum = (a[i] - 48) + (b[j] - 48) + carry;
        st.push(sum % 10);
        carry = sum / 10;
        i--;j--;
    }
    while(i >= 0){
        sum = (a[i] - 48) + carry;
        st.push(sum % 10);
        carry = sum / 10;
        i--;
    }
    while(j >= 0){
        sum = (b[j] - 48) + carry;
        st.push(sum % 10);
        carry = sum / 10;
        j--;
    }
    while(carry){
        st.push(carry % 10);
        carry /= 10;
    }
    while(!st.empty()){
        res.append(1, st.top() + 48);
        st.pop();
    }
    return res;
}

string removeLeadingZeros(string s){
    //  Removes the leading zeros from the string.
    string res = "";
    int i;
    for(i=0;i<s.length() && s[i] == '0';i++);
    while(i<s.length()){
        res.append(1, s[i]);
        i++;
    }
    if(res == "")
        res = "0";
    return res;
}

string intMultiply(string a, int b){
    //  Returns the product of string a and a digit b.
    stack<int> st;
    string res = "";
    int i = a.length() - 1, carry = 0, sum;
    while(i >= 0){
        sum = (b * (a[i] - 48)) + carry;
        carry = sum / 10;
        st.push(sum % 10);
        i--;
    }
    while(carry){
        st.push(carry % 10);
        carry /= 10;
    }
    while(!st.empty()){
        res.append(1, st.top() + 48);
        st.pop();
    }
    return res;
}

string multiply(string s, string t){
    //  Returns the product of s and t.
    int power = 0;
    string res = "0", tmp = "";
    stack<int> st;
    for(int i=s.length() - 1;i>=0;i--){
        tmp = intMultiply(t, s[i] - 48);
        tmp.append(power, '0');
        power++;
        tmp = removeLeadingZeros(tmp);
        res = add(res, tmp);
    }
    return res;
}

string divide(string input, int n){
    //  Returns the integer quotient for 'input / n'.
    string tmp = "";
    int m = 0;
    bool first = true;
    for(int i=0;i<input.length();){
        m *= 10;
        m += (input[i] - 48);
        if(m / n > 0){
            first = false;
            tmp.append(1, (m/n)+48);
        }
        else{
            if(!first)
                tmp.append("0");
        }
        m %= n;
        i++;
    }
    if(tmp == "")
        tmp = "0";
    return removeLeadingZeros(tmp);
}

string myMaximum(string a, string b){
    //  Returns the maximum of a and b.
    if(a.length() > b.length())
        return a;
    if(b.length() > a.length())
        return b;
    for(int i=0;i<a.length();i++){
        if(a[i] == b[i])
            continue;
        else if(a[i] > b[i])
            return a;
        else
            return b;
    }
    return a;
}

int main(){
 
 int te;
 string s, t;
 scanf("%d", &te);
 while(te--){
  cin >> s >> t;
  cout << myMaximum(multiply(s, divide(add(t, "1"), 2)), multiply(t, divide(add(s, "1"), 2))) << endl;
 }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem BOGGLE

Boggle Scoring

Explanation:

This problem requires simple implementation of a hash, which maps string to number of times different players found it.

Here is the approach.

1. Take a map from string to int (you can use STL). Below are the links provided to learn, if you are not aware.

2. For different words found by multiple players, keep on storing the number of times each word is found, in the above map.

3. For each player, take the word found by him, check if it was also found by some other player. If yes, reject the word, else, calculate the score depending on the length of the word.

C++ Map links.
1. http://www.cplusplus.com/reference/map/map/

Solution:

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>

using namespace std;

vector<string> tokenize(string s, char c){
    //  Splits the string s into vector of words based on character c.
    vector<string> res;
    string tmp = "";
    for(int i=0;i<s.length();i++){
        if(s[i] == c){
            res.push_back(tmp);
            tmp = "";
        }
        else
            tmp.append(1, s[i]);
    }
    res.push_back(tmp);
    return res;
}

long long int findSize(string word){
    //  Returns the score of each word depending on its length.
    if(word.length() <= 4)
        return 1;
    if(word.length() == 5)
        return 2;
    if(word.length() == 6)
        return 3;
    if(word.length() == 7)
        return 5;
    return 11;
}

int main(){

    int n;
    vector< vector<string> > words;
    map<string, int> mymap;
    long long int result = 0;
    string s;

    scanf("%d", &n);
    words.resize(n);
    getline(cin, s);
    for(int i=0;i<n;i++){
        getline(cin, s);
        //  Split the string into different words for ith player.
        words[i] = tokenize(s, ' ');
        //  Increment the count of word found and store in mymap.
        for(int j=0;j<words[i].size();j++){
            mymap[words[i][j]]++;
        }
    }
    //  Traverse through each word found.
    for(int i=0;i<words.size();i++){
        long long int tmpVal = 0;
        for(int j=0;j<words[i].size();j++){
            //  If word not found by anyone else, add the score to ith player's score.
            if(mymap[words[i][j]] == 1)
                tmpVal += findSize(words[i][j]);
        }
        //  Update the maximum score found so far.
        result = max(tmpVal, result);
    }
    printf("%lld", result);
    return 0;
}

Any suggestions are welcome.

SPOJ Problem ADFRUITS

Advanced Fruits

Explanation:

This problem uses the concept of LCS (longest common subsequence). If you are not aware about LCS, below are the links provided. Nothing much to say on this, just try to find the longest common substring for the strings provided as input and then try to merge both the strings, make sure you include the matched character only once in the output. And you are good to go.

Below is my approach to find the resultant string.

1. Find out the LCS for two strings.
2. Take two arrays, sArr and tArr which stores the value true if the corresponding character is a part of LCS, else false.
3. Backtrack to find the matching characters in the LCS and mark corresponding positions in above array as true (below is an example provided).
4. Traverse two strings and merge them to find the resultant string.

Example:
apple peach

Here, s = apple, and t = peach. LCS will be 2 here. And corresponding characters are 'p' and 'e', as shown. apple and peach. Thus, the two arrays will have below value.
sArr = false | false | true  | false | true
tArr = true  | true  | false | false | false

LCS learning links.
1. https://www.youtube.com/watch?v=NnD96abizww&list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&index=27
2. http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

Solution:

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

bool sArr[105], tArr[105];
char s[105], t[105], res[210];
int sLength, tLength, matrix[105][105];

void prepareBoolArray(){
    //  Initialize sArr and tArr.
    fill(sArr, sArr + sLength, false);
    fill(tArr, tArr + tLength, false);
    //  Initialize the matrix to calculate LCS.
    for(int i=0;i<=sLength;i++)
        matrix[i][0] = 0;
    for(int j=0;j<=tLength;j++)
        matrix[0][j] = 0;
    //  Calculate the matrix for LCS.
    for(int i=1;i<=sLength;i++){
        for(int j=1;j<=tLength;j++){
            if(s[i-1] == t[j-1])
                matrix[i][j] = matrix[i-1][j-1] + 1;
            else
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1]);
        }
    }
    //  Backtrack to find the common characters.
    int x = sLength, y = tLength;
    while(true){
        if(x == 0 || y == 0)
            break;
        //  If two characters are equal, 
        //    move to diagonally opposite cell and mark the current position in sArr and tArr as true.
        //  else, move to the cell [x-1][y] or [x][y-1], whichever has the maximum value.
        if(s[x-1] == t[y-1]){
            sArr[x-1] = true;
            tArr[y-1] = true;
            x--;y--;
        }
        else
            (matrix[x-1][y] >= matrix[x][y-1]) ? (x--) : (y--);
    }
}

int main(){
    //  Take input till EOF.
    while(scanf("%s", s) != EOF){
        scanf("%s", t);
        sLength = strlen(s), tLength = strlen(t);
        //  Populate sArr and tArr.
        prepareBoolArray();
        //  Merge two strings together.
        int i = 0, j = 0, idx = 0;
        while(i < sLength && j < tLength){
            int k = i, l = j;
            //  Add the characters from first string to resultant string which are not part of LCS.
            for(;k < sLength && !sArr[k];k++)
                res[idx++] = s[k];
            //  Add the characters from second string to resultant string which are not part of LCS.
            for(;l < tLength && !tArr[l];l++)
                res[idx++] = t[l];
            //  Add the characters to resultant string which are part of LCS.
            while(k < sLength && l < tLength && sArr[k] && tArr[l]){
                res[idx++] = s[k];
                k++;
                l++;
            }
            i = k;
            j = l;
        }
        //  Add remaining characters from the first string, if any.
        while(i < sLength)
            res[idx++] = s[i++];
        //  Add remaining characters from the second string, if any.
        while(j < tLength)
            res[idx++] = t[j++];
        res[idx] = 0;
        printf("%s\n", res);
    }
}

Any suggestions are welcome.

SPOJ Problem M00PAIR

0 0 Pairs

Explanation:

This problem ask us to to find number of pair of consecutive zeros after 'n' steps. If you want to try the problem, I would give you one hint, it's a dynamic programming problem. Good luck!

Let's go through few values of n and the number of pair of consecutive zeros first to find out the dp pattern. 

n = 0.
pattern: 1(pattern0), no. of pairs: 0(output1)
Well, with one value, we won't be able to find out anything. Let's move to higher values.

n = 1.
pattern: 01(pattern1), no. of pairs: 0(output2)
Let's check for another value of n.

n = 2.
pattern: 10-01(pattern2), no. of pairs: 1(output2)
Here, the no. of pair gets incremented by 1, okay. Let's see what we can find in the pattern. We can see, that 01 at the end, is a pattern for n=1. Also, 1 at the beginning for n=2, is a pattern for n=0.
You can have similar observation for n=1.
So far, we found that, output2 will include sum of output1 and output0 as they are part of pattern for n=2. But, output2 = 1 != (output1 + output0). Let's move to next value and we will come back to this point.

n = 3.
pattern: 01-10-10-01(pattern3), no. of pairs: 1(output3)
Following pattern found above, we can see that, yes, pattern2 is part of pattern3. Now, 01(pattern1) at the beginning is also a part of pattern3, and last thing, 1(pattern0), is also a part of pattern3.
So, basically, we divided the whole pattern as shown below.
01 => (pattern1)
1 => (pattern0)
0
10-01 => (pattern2)
So, we can say that, output3 = output2 + output1 + output0, which is equal to 1 this time, and woah, formula worked.
We will come back to the point why the formula didn't work for n=2.

n = 4.
pattern: 10-01-01-10-01-10-10-01(pattern4), no. of pairs: 3(output4)
Let's straightaway divide the pattern.
10-01 => (pattern2)
01 => (pattern1)
1 => (pattern0)
0
01-10-10-01 => (pattern3)
Here, if we calculate (output0 + output1 + output2 + output3), we get 2, but output4 is 3. Now, where does this one more pattern comes into the picture. Okay, let's take a closer look at the pattern. One pair comes from pattern2, second comes from pattern3. The third one also comes from pattern3, but not completely from it. Hope you were able to find it by now. If not, you can give it a look, again.
Okay, there is a zero in our pattern which doesn't belong to any of the patterns defined above. This zero and the first zero in pattern3 add one more pair to the number of pairs. And now, you can scroll up and see if this was the same case for n=2.
Thus, we can say that, for some cases,
output(n) = output(n-1) + output(n-2) + ... + output1 + output0
and for some cases,
output(n) = output(n-1) + output(n-2) + ... + output1 + output0 + 1

So far, we have seen the latter case for n=2 and n=4.

n = 5.
pattern: 01-10-10-01-10-01-01-10-10-01-01-10-01-10-10-01(pattern5), no. of pairs: 5
Let's divide the pattern, as we have been doing.
01-10-10-01 => (patter3)
10-01 => (pattern2)
01 => (pattern1)
1 => (pattern0)
0
10-01-01-10-01-10-10-01 => (pattern4)
Here, we don't see that extra pair of zero adding up. Thus, we can say that, ouptut5 = output4 + output3 + output2 + output1 + output0, which is equal to 5 and thus the formula works.

Moving ahead, here is the pseudocode for above problem.

output(n) = output(n-1) + output(n-2) + ... + output1 + output0
if n is a multiple of 2.
   add 1 to output(n)

I will leave it to you to prove that we need to add 1 for patterns of even n's.

Simple, so far, there is one more twist to the problem. As you will move ahead, the value of output(n) overflows and won't fit into any basic data type for C++. So, just use string to store the sum.

Below is the solution provided. Happy coding!

Solution:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

string add(string a, string b){
    //  return a + b
    stack<int> st;
    string res = "";
    int i = a.length() - 1, j = b.length() - 1, carry = 0, sum;
    while(i >= 0 && j >= 0){
        sum = (a[i] - 48) + (b[j] - 48) + carry;
        st.push(sum % 10);
        carry = sum / 10;
        i--;j--;
    }
    while(i >= 0){
        sum = (a[i] - 48) + carry;
        st.push(sum % 10);
        carry = sum / 10;
        i--;
    }
    while(j >= 0){
        sum = (b[j] - 48) + carry;
        st.push(sum % 10);
        carry = sum / 10;
        j--;
    }
    while(carry){
        st.push(carry % 10);
        carry /= 10;
    }
    while(!st.empty()){
        res.append(1, st.top() + 48);
        st.pop();
    }
    return res;
}

int main(){

    string res[1000], total[1000];
    int n;
    /*  res[n] will store the result for nth step.
        total[n] will store the sum of res[0], res[1], ..., res[n-1], res[n] */
    res[0] = res[1] = total[0] = total[1] = "0";
    for(int i=2;i<1000;i++){
        res[i] = total[i-1];
        if(i % 2 == 0)
            res[i] = add(res[i], "1");
        total[i] = add(total[i-1], res[i]);
    }
    while(scanf("%d", &n) != EOF)
        cout << res[n] << endl;
    return 0;
}

Any suggestions are welcome.

SPOJ Problem EPALIN

Extend to Palindrome

Explanation:

This problem ask us to add minimum number of characters at the end of the string s to make it a palindrome. So, basically, we need to prepare a palindrome of minimum whose prefix should be s.

A very basic approach would be to take the reverse of the string and append it to the original string. Believe me, that's a correct solution. It would give you a palindrome, but not really a palindrome with minimum length. If still not sure, try examples 'abcd' & 'abcc'. Now, I will leave it to you to decide, if the approach is correct or not.

But, we will be working very close to the first approach we had. That is, we would be taking the reverse of original string s and appending it to the original one and then trying to form a palindrome of minimum length.

Let's take a few examples to get to a solution.

Example # 1.
original string: abcd
reverse string: dcba
palindrome after appending: abcddcba
minimum length palindrome: abcdcba

Here, we can say that, if we remove the first character from the reverse, it might work. Correct, but partially. Let's take another example.

Example # 2.
original string: abcc
reverse string: ccba
palindrome after appending: abccccba
minimum length palindrome: abccba

Looking at this example, first thing which came to my mind was, we could have had a palindrome of a smaller length, which is 'abcba'(isn't it a palindrome and also smaller than 'abccba'?). Then, what's the reason, we have 'abccba'. Just a hint. string s should be a part of palindrome.

Okay, now moving ahead, here we had to remove two characters from the reverse which contradicts the conclusions from example 1. So, there must be something else which we need to check. Let's take one more example, and we will be clear what needs to be done.

Example # 3.
original string: amanaplanacanal
reverse string: lanacanalpanama
palindrome after appending: amanaplanacanallanacanalpanama
minimum length palindrome: amanaplanacanalpanama

I guess, by now, you must have guessed, what we need to remove from the reverse string. Its the longest palindrome which is also suffix of original string or prefix of its reverse. So, going ahead with above examples.

Example # 1. Result would be 'd'.
Example # 2. Result would be 'cc'.
Example # 3. Result would be 'lanacanal'.

So, now we know what needs to be done. We need to find the longest palindrome of string s which is suffix of original string s. Now, how to find the longest suffix palindrome. We know, it would be the prefix of reverse of the string. So, do we have something which takes into consideration, the prefix as well as suffix. Yes, we do have, and that's KMP algorithm (those who are not aware, check the links provided below). Not exactly KMP algorithm, but its first part, which calculates the longest suffix which is also the prefix of the string.

So, to achieve our purpose,we take string "rev(s)+#+s" (adding a # because we only need the longest prefix of the reverse of the string and not the whole string "rev(s)+s"). The maximum length we receive is the length of palindromic suffix of the string. Now, things become easy, isn't it. I will leave further part to you to implement. You can refer the solution which I used.

KMP algorithm links.
1. Part-1: https://www.youtube.com/watch?v=GTJr8OvyEVQ&index=2&list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de
2. Part-2: https://www.youtube.com/watch?v=KG44VoDtsAA&index=1&list=PLrmLmBdmIlpvxhscYQdvfFNWU_pdkG5de
3. http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

Solution:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>
#define SIZE 100005

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

int prepareLPSArray(string pattern){
    /* Returns the length of longest suffix which is also prefix of the string.
       Since, we have appended original string to its reverse, we would be able
       to get the length of longest suffix of original string which is also a 
       palindrome. Below is the basic implementation of prefix array calculation 
       used in KMP algorithm. */

    int len = pattern.length();
    vector<int> lsp(len);
    lsp[0] = 0;
    for(int j=0, i=1;i<len;i++){
        if(pattern[i] == pattern[j]){
            lsp[i] = j + 1;
            j++;
        }
        else{
            while(true){
                if(j == 0 || pattern[j] == pattern[i])
                    break;
                j = lsp[j-1];
            }
            if(pattern[j] == pattern[i]){
                lsp[i] = j + 1;
                j++;
            }
            else
                lsp[i] = 0;
        }
    }
    return lsp[len - 1];
}

string findPalin(string s){
    string res = s;
    // Obtain the reverse of string.
    string revS = string(s.rbegin(), s.rend());
    // Find the no. of chars to be appended to original string.
    int noOfChars = s.length() - prepareLPSArray(revS + "#" + s);
    // Append noOfChars from original string to the result in reverse order.
    for(int i=noOfChars - 1;i>=0;i--)
        res.append(1, s[i]);
    return res;
}

int main(){
    char str[SIZE];
    // Take input until EOF.
    while(scanf("%s", str) != EOF){
        string s = str;
        // Find minimum length for s.
        cout << findPalin(s) << endl;
    }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem BOMARBLE

D - Playing with Marbles

Explanation:

A simple DP problem. I would suggest to work with pen and paper before reading the explanation.

For ith pentagon, we add three edges to the (i-1)th pentagon and for each edge added, we put i marbles. In total, we add (3 * i) marbles. Now remains 1 marble, which needs to be added to the intersection of two edges. Thus, finally we add (3 * i) + 1 to number of marbles in (i-1)th pentagon.

Example is shown for two pentagons.

• New edges added are shown in green.
• 3 * i marbles are shown in blue.
• 1 marble at the intersection is shown in red.

two pentagons

Solution:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#include<queue>
#include<stack>
#include<utility>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
#include<vector>
#include<fstream>
#include<map>
#include<list>
#include<algorithm>
#define SIZE 1001

typedef long long int LLD;
typedef unsigned long long int LLU;

using namespace std;

int main(){
 
    vector<LLD> num_of_marbles(SIZE);
    int n;

    // initialize number of marbles for first pentagon.
    num_of_marbles[1] = 5;

    // compute the no. of marbles from second pentagon to thousandth pentagon
    // by adding (3 * i) + 1 to num_of_marbles[i-1].
    for (int i=2;i<SIZE;i++)
        num_of_marbles[i] = num_of_marbles[i-1] + (3 * i) + 1;

    while(true){
        cin >> n;
        if(!n)
            break;
        cout << num_of_marbles[n] << endl;
    }

    return 0;
}

Any suggestions are welcome.