SPOJ Problem CCHESS

COSTLY CHESS

Explanation:

The problem requires to find the minimum cost for a knight in chess to reach (c, d), if it starts from (a, b). Cost to reach from (a, b) to (c, d) is calculated as (a * c) + (b * d).

Problem requires simple implementation of BFS. Take a cost matrix of 8x8, with cost of each block set to INFINITY and the cost(a, b) = 0. Using BFS, find the minimum cost of each block which can be reached starting from (a, b).

If the cost(c, d) is still infinity, that means the block (c, d) cannot be reached from (a, b) and hence we should return -1, or else, return the cost(c, d).

Below is the code for reference.

Solution:

#include <iostream>
#include <cstdio>
#include <queue>
#define INF 1000000000
#define inRange(x, y) (x >= 0 && x < 8 && y >= 0 && y < 8)
#define calculateDistance(a, b, c, d) (a * c) + (b * d)

using namespace std;

int mat[8][8];

int findMinimumPath(int a, int b, int c, int d){
    queue<int> q;
    q.push(a);
    q.push(b);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        int y = q.front();
        q.pop();
        int a[] = {-1, -2, -2, -1, 1, 2, 2, 1}, b[] = {-2, -1, 1, 2, 2, 1, -1, -2};
        for(int i=0;i<8;i++){
            int tmpX = x + a[i];
            int tmpY = y + b[i];
            if(inRange(tmpX, tmpY) && mat[tmpX][tmpY] > mat[x][y] + calculateDistance(x, y, tmpX, tmpY)){
                mat[tmpX][tmpY] = mat[x][y] + calculateDistance(x, y, tmpX, tmpY);
                q.push(tmpX);
                q.push(tmpY);
            }
        }
    }
    return ((mat[c][d] == INF) ? -1 : mat[c][d]);
}

void init(){
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
            mat[i][j] = INF;
}

int main(){
    int a, b, c, d;
    while(scanf("%d%d%d%d", &a, &b, &c, &d) != EOF){
        init();
        mat[a][b] = 0;
        printf("%d\n", findMinimumPath(a, b, c, d));
    }
    return 0;
}

Problem NAKANJ can also be solved using the same strategy. Just need to do few computations.

Any suggestions are welcome. 

SPOJ Problem CRZYSMKR

CRAZY SMOKER

Explanation:

A simple problem which requires li'l bit of modular arithmetics and we are done.
We just need to calculate the results of (34 ^ n) % 11 and (30 * n) % 11. Add 32 to it.

Once we have the result of above calculation, we need to find the minimum number to be added to the above result so that final result becomes equal to (0 % 11). We do it by subtracting it from 11 and taking a modulo 11. Taking modulo 11 helps for the case where n = 0.

Below is the code for reference.

Solution:

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

long long int mulMod(long long int a, long long int b, long long int c){
    // returns (a * b) % c.
    long long int x = 0, y = a % c;
    while (b) {
        if (b & 1)
            x = (x + y) % c;
        y = (y << 1) % c;
        b >>= 1;
    }
    return (x % c);
}

long long int modPower(long long int a, long long int b, long long int c){
    // returns (a ^ b) % c.
    long long int y = 1;
    while (b) {
        if (b & 1)
            // y = (y * a) % mod;
            y = mulMod(y, a, c);
        // a = (a * a) % mod;
        a = mulMod(a, a, c);
        b >>= 1;
    }
    return y;
}

long long int calculateCigarettes(long long int n){
    return (modPower(34, n, 11) + mulMod(30, n, 11) + 32) % 11;
}

int main() {
    int t;
    long long int n;
    scanf("%d", &t);
    while(t--){
        scanf("%lld", &n);
        printf("%lld\n", (11 - calculateCigarettes(n)) % 11);
    }
    return 0;
}

Any suggestions are welcome.

SPOJ Problem TMSUM

THE MAXIMIZE SUM

Explanation:

Given 'n' number of elements in a set, you need to find the subsets of the set containing maximum of two elements and minimum of one. Once, we have the subsets, we need to find the product of the elements in the subset containing two elements. And, then adding all the found products to the elements of set with size one. Following the process, we need to find the maximum sum at the end and then print. The problem requires li'l bit of recursion which later gets converted into a very simple DP problem. You can find the explanation below.

Now, since we are supposed to find the maximum sum, thus, we can say that the product of two numbers should be maximum (as we are adding the product of two numbers for a 2-element set to get the sum). For that, we need to multiply together, the largest numbers and hence, we can get maximum product. Thus, we can come to a conclusion that, sorting is required here. Once sorted, we have two options now, either we form a 2-element set or 1-element set containing this element.

Let's say, for example.

Set, S = {1, 3, 2}
Once, we have sorted this, we get S' = {1, 2, 3}.

Now, taking every element into consideration, we can have following possible subset combinations.

1. {1}, {2}, {3}
2. {1}, {2, 3}
3. {1, 2}, {3}

Calculating results for above possible combination, we get,

1. 6
2. 7
3. 5

And, as said above, we need to find the product of largest numbers to get the maximum sum, and thus, we can see, we get the maximum sum for case 2, where we find the product of two largest numbers.

Now, let's try to come up with the recursion formula.

Case 1.
Consider, we take ith element ai into a 1-element set, so the sum till ith index, say Si, will be, Si = Si-1 + ai, where Si-1 is the maximum sum till index (i-1).

Case 2.
Consider, we take ith element ai into a 2-element set, so the sum till ith index, say Si, will be, Si = Si-2 + (ai * ai-1), where Si-2 is the maximum sum till index (i-2).

So, the final formula becomes,

Si = max(Si-1 + ai, Si-2 + (ai * ai-1))

Below is the code for reference.

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;

int main(){
 
    int t, n, arr[100];
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i=0;i<n;i++)
            scanf("%d", &arr[i]);
        if(n == 1){
            printf("%d\n", arr[0]);
            continue;
        }
        if(n == 2){
            printf("%d\n", max(arr[0] * arr[1], arr[0] + arr[1]));
            continue;
        }
        sort(arr, arr + n);
        int sum[100];
        sum[0] = arr[0];
        sum[1] = max(arr[0] * arr[1], arr[0] + arr[1]);
        for(int i=2;i<n;i++)
            sum[i] = max(sum[i-1] + arr[i], sum[i-2] + (arr[i-1] * arr[i]));
        printf("%d\n", sum[n-1]);
    }
    return 0;
}

Any suggestions are welcome.