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.