SPOJ 18963. Bhagat The Bit Man – cpp solution

It was a nice problem. I think this should count as one of my first bitmask problems.

#include <cstdio>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    long long number =0;
    long long mask=0;
    long long val;
    mask = ~(0LL);
    for (int i =0; i < n; ++i) {
        scanf("%lld", &val);
        number |= val;
        mask = mask&val;
    }
    number ^= mask;
    printf("%lldn", number);
    return 0;
}

SPOJ 3878. Rectangles Perimeter – CPP solution

Another nice dp problem though quite easy.

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

long dp[1001][2];

 long max(long a, long b) {
    if (a < b) return b;
    return a;
}

long abs(long a) {
    return a > 0 ? a : -a;
}

int main() {
    int n;
    scanf("%d", &n);
    int a,b;
    int preva,prevb;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d",&a,&b);
        if (i == 0) {
            dp[i][0]=a;
            dp[i][1]=b;
        } else {
            dp[i][0]=max(dp[i-1][1]+abs(b-preva),dp[i-1][0]+abs(b-prevb))+a;
            dp[i][1]=max(dp[i-1][1]+abs(a-preva),dp[i-1][0]+abs(a-prevb))+b;

        }
        preva=a;
        prevb=b;
    }
    printf("%ldn", max(dp[n-1][0],dp[n-1][1]));
    return 0;
}

Spoj 1871. Making A Budget – CPP solution

A nice dp problem though the description of it could be better. I had to assume that the number of workers is 300 (could not pass with 1000).

#include <iostream>
using namespace std;

// dp[month][workers] = current sum
#define INF 99999999
#define MAX 300

int main () {
    for (int t=1;1;++t) {
        int months, hire, salary, severe;
        cin >> months;
        if (months==0)break;
        cin >> hire >> salary >> severe;
        int dp[24][MAX]={INF};
        for (int i = 0;i<months;++i) {
            for (int j = 0;j<MAX;++j) dp[i][j]=INF;
        }
        int needed;
        int prev;
        for (int i = 0; i < months; ++i) {
            cin >> needed;
            if (i == 0) {
                for (int k = 0;k < MAX; ++k) {
                    dp[i][k] = k*(salary+hire);
                }
            } else {
                for (int k=0; k < MAX; ++k) {
                    for (int j = prev; j < MAX; ++j) {
                        if (k<j) {
                            dp[i][k] = min(dp[i][k], dp[i-1][j]+(j-k)*severe + k*salary);
                        } else {
                            dp[i][k] = min(dp[i][k], dp[i-1][j]+(k-j)*hire + k*salary);
                        }
                    }
                }
            }
            prev = needed;
        }
        int ans = INF;
        for (int i = MAX-1; i>=needed; --i) {
            ans = min(ans, dp[months-1][i]);
        }
        cout << "Case " << t << ", cost = $"<< ans << endl;
    }
    return 0;
}

SPOJ 8725. Closest Point Pair – CPP solution

A relatively straightforward divide and conquer problem.

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

#define INF 9999999999.9

struct Point {
    long double x;
    long double y;
    int index;
};

bool xComp(Point a, Point b) {
    return a.x < b.x;
}

bool yComp(Point a, Point b) {
    return a.y < b.y;
}

Point makePoint(double a, double b, int index) {
    Point tmp;
    tmp.x = a;
    tmp.y = b;
    tmp.index = index;
    return tmp;
}

double dist(Point a, Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

int indexa,indexb;
double ans = 999999999;

double closestBrute(Point points[], int n) {
    double d = INF;
    for (int i = 0; i < n; ++i) {
        for (int j = i+1; j < n; ++j) {
            double dTemp = dist(points[i], points[j]);
            if (dTemp < d) {
                d = dTemp;
                if (d < ans) {
                    ans = d;
                    indexa = points[i].index;
                    indexb = points[j].index;
                }
            }
        }
    }
    return d;
}

double closest(Point points[], int n) {
    if (n <= 3) return closestBrute(points, n);
    int mid = n/2;
    double left = closest(points, mid);
    double right = closest(points+mid, n-mid);
    double d = min(left, right);
    Point strip[n];
    int stripSize = 0;
    Point midPoint = points[mid];
    for (int i = 0; i < n; ++i) {
        if (abs(points[i].x - midPoint.x) < d) {
            strip[stripSize++] = points[i];
        }
    }
    sort(strip, strip+stripSize, yComp);
    for (int i = 0; i < stripSize; ++i) {
        for (int j = i+1; j < stripSize; ++j) {
            double tempDist = dist(strip[i], strip[j]);
            if (tempDist >= d) break;
            d = tempDist;
            if (d < ans) {
                ans = d;
                indexa = strip[i].index;
                indexb = strip[j].index;
            }
        }
    }
    return d;
}

int main() {
    int n;
    Point points[50001];
    scanf("%d",&n);
    for (int i =0; i < n; ++i) {
        double a,b;
        scanf("%lf%lf", &a,&b);
        points[i] = makePoint(a,b,i);
    }
    sort(points, points+n, xComp);
    double ans = closest(points, n);
    if (indexa > indexb) {
        int tmp = indexa;
        indexa = indexb;
        indexb = tmp;
    }
    printf("%d %d %.6lfn", indexa, indexb, ans);
    return 0;
}

SPOJ Wise And Miser – CPP solution

A very basic dynamic programming problem. Basically:
for the kth city you see see what is the best possible time using each of the buses based on the best time for the (k-1)-th city.

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

#define INF 99999999

int min(int a, int b) {
      return a < b ? a : b;
}

int main() {
    int n,m;
    int g[101][101];
    int dp[101][101];
    scanf("%d%d",&n,&m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {             scanf("%d", &g[i][j]);         }         if (i > 0) {
            for (int j = 0; j < m; ++j) {                 dp[i][j] = INF;                 if (j>0) {
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1] + g[i][j]);
                }
                if (j < m-1) {
                    dp[i][j] = min(dp[i][j], dp[i-1][j+1] + g[i][j]);
                }
                dp[i][j] = min(dp[i][j], dp[i-1][j] + g[i][j]);
            }
        } else {
            for (int j = 0; j < m; ++j) {
                dp[i][j] = g[i][j];
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < m; ++i) {
        ans = min(dp[n-1][i], ans);
    }
    printf("%dn", ans);
    return 0;
}

SPOJ Transform the Expression – CPP solution

The idea is very simple – just like traversing a binary tree (from in-order to post-order). There are two ways to solve it – either recursion or keeping a stack.

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

bool in(char sign, char * signs, int length) {
    for (int i = 0; i < length; ++i) {
        if (signs[i] == sign) return true;
    }
    return false;
}

char signs[] = "+-*/^";

char * ans;
int ansL=0;

void construct (char * buf, int from, int to) {
    int open = 0;
    if (from == to) {
        ans[ansL++]=buf[from];
    }
    for (int i = from; i <= to; ++i) {
        if (buf[i] == '(') {
            ++open;
        } else if(buf[i] == ')') {
            --open;
        } else if (open == 1 && in(buf[i],signs,5)) {
            construct(buf, from+1, i-1);
            construct(buf, i+1, to-1);
            ans[ansL++] = buf[i];
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        char buf[401];
        cin >> buf;
        int length = strlen(buf);
        ansL = 0;
        ans = new char[length];
        construct(buf, 0, length-1);
        ans[ansL] = '\0';
        cout << ans << endl;
    }
    return 0;
}

Spoj 394. Alphacode – CPP solution

An easy DP problem. The only thing you have to be careful is a 0 somewhere in between. An example of the idea. Let
the number be 25114.
We can construct sets (codes) by either appending (if possible) or by adding the number as a new element. Adding as a new element is only possible when the number is not 0.
For the upper number we have
Till 1st letter: {2}
Till 2nd letter: {2,5}, {25}
Till 3rd letter: {2,5,1}, {25, 1} -> observe that 51 is not a valid letter
Till 4th letter: {2,5,1,1}, {2,5,11}, {25, 1, 1}, {25, 11}
Till 5th letter: {25,1,14}, {25,1,1,4}, {25,11,4}, {2,5,11,4}, {2,5,1,14}, {2,5,1,1,4}

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

#define MAX 26

bool ok(char a, char b) {
    return (a-'0')*10 + (b-'0') < = MAX;
}

int main() {
    while (true) {
        char s[5001];
        cin >> s;
        if (strcmp(s, "0")==0) break;
        int l = strlen(s);
        int dp[5001][2];
        // 0 append, 1 new element
        dp[0][0] = 0;
        dp[0][1] = 1;
        for (int i = 1; i < l; ++i) {

            if (!ok(s[i-1], s[i])) {
                dp[i][0] = 0;
            } else {
                dp[i][0] = dp[i-1][1];
            }
            dp[i][1] = dp[i-1][0] + dp[i-1][1];
            if (s[i] == '0') {
                dp[i][1]=0;
            }
        }
        cout << dp[l-1][0] + dp[l-1][1] << endl;
    }
    return 0;
}

Spoj STONE – CPP solution

I just found a problem I wasn’t able to solve in the past. It seams I have tried to solve it by summing all of the x coordinates and then dividing them by the number of points.

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

#define pii pair<int,int>

vector<pii> points;

double round2(double number) {
    number *= 100;
    return round(number)/100.0;
}

double crossProduct(pii a, pii b) {
    return a.first * b.second - b.first*a.second;
}

double signedArea() {
    double area = 0.0;
    int n = points.size();
    for (int i = 0; i <n; ++i) {
        area += crossProduct(points[i], points[(i+1)%n]);
    }
    return 0.5*area;
}

double sigmaX() {
    double sum = 0.0;
    int n = points.size();
    for (int i = 0; i < n; ++i) {
        sum += (points[i].first + points[(i+1)%n].first)*crossProduct(points[i], points[(i+1)%n]);
    }
    return sum;
}

double sigmaY() {
    double sum = 0.0;
    int n = points.size();
    for (int i = 0; i < n; ++i) {
        sum += (points[i].second + points[(i+1)%n].second)*crossProduct(points[i], points[(i+1)%n]);
    }
    return sum;
}

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; ++i) {
        int n;
        points.clear();
        scanf("%d",&n);
        int a,b;
        double sumx=0,sumy=0;
        for (int k=0; k < n; ++k) {
            scanf("%d%d",&a,&b);
            points.push_back(make_pair(a,b));
        }
        double area = signedArea();
        double cx = (sigmaX()/6.0)/area;
        double cy = (sigmaY()/6.0)/area;
        printf("%.2f %.2fn", round2(cx), round2(cy));

    }

}

Implementation of Kruskal using a disjoint-set forest C++

The implementation is actually a solution to the problem CSTREET on Spoj

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


struct Tree
{
    Tree * parent;
    int rank;
    int value;
};

struct Edge
{
    Tree * from;
    Tree * to;
    int weight;
};

int n,m,cost;
vector<Tree*> trees;
vector<Edge*> edges;

Tree * makeSet(int value)
{
    Tree * tmp = new Tree[1];
    tmp->parent = tmp;
    tmp->value = value;
    tmp->rank = 0;
    return tmp;
}

Edge * makeEdge(int from, int to, int weight)
{
    Edge * tmp = new Edge[1];
    tmp->from = trees[from];
    tmp->to = trees[to];
    tmp->weight = weight;
    return tmp;
}

Tree * findSet(Tree * node)
{
    if (node->parent != node)
    {
        node->parent = findSet(node->parent);
    }
    return node->parent;
}

void link(Tree * a, Tree * b)
{
    if (a->rank > b->rank)
    {
        b->parent = a;
    }
    else
    {
        a->parent = b;
        if (a->rank == b->rank) ++(b->rank);
    }
}

void unionSet(Tree * a, Tree * b)
{
    link(findSet(a), findSet(b));
}

bool comparator(Edge * a, Edge * b)
{
    return a->weight < b->weight;
}

void build()
{
    sort(edges.begin(), edges.end(), comparator);
    int value = 0;
    for (int i = 0; i < edges.size(); ++i)
    {
        Tree * firstSet = findSet(edges[i]->from);
        Tree * secondSet = findSet(edges[i]->to);
        if (firstSet->value != secondSet->value)
        {
            unionSet(firstSet, secondSet);
            value += edges[i]->weight;
        }
    }
    printf("%dn", value*cost);
}

int main()
{
    int t;
    scanf("%d", &t);
    trees.clear();
    edges.clear();
    for (int i = 0; i < t; ++i)
    {
        scanf("%d%d%d", &cost, &n, &m);
        int a,b,c;
        for (int i = 0; i < n; ++i)
        {
            trees.push_back(makeSet(i));
        }
        for (int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &a,&b,&c);
            edges.push_back(makeEdge(a-1,b-1,c));
        }
        build();
    }
    return 0;
}