Algorithms for Dummies : By Dummies

UVa 10432

2010-03-09T03:52:00.000-08:00

Finding the area of a polygon in a circle is fairly trivial if you remember basic trigonometry or you can make use of Wikipedia (like I did). The solution here uses the fact that a polygon is made up of many triangles and the area for a triangle whose SideAngleSide are known can be obtained using area = 1/2 * side * side * sin(angle). Initially I had gone for Law of Cosines and the Heron's formula but I could not get an AC so here is the code...

#include<iostream>
#include <vector>
#include <cmath>
#include <cstdio>
using namespace std;
int main()
{
  double r,n;
 while(scanf("%lf%lf",&r,&n)!=EOF) {
   double res = n*.5*r*r*sin((2*M_PI/n));

  printf("%.3lf\n",res);
 }
  return 0;

}

Graham Scan

2010-03-06T10:09:00.000-08:00

This is a standard computational geometry algorithm. It is used to find the convex hull of a set of points on a plane in O(n*log(n)). For more info check this out http://en.wikipedia.org/wiki/Graham_scan . The following is an implementation of the same :

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

class Point
{
    public:
        // (x, y)
        double first,second;
        Point():first(.0),second(.0){}
        Point(double _x,double _y):first(_x),second(_y){}
        friend ostream& operator << (ostream& os, const Point & ref);
};

// printer for Point
ostream& operator << (ostream& os, const Point & ref) {
    return os<<"("<<ref.first<<", "<<ref.second<<")"<<endl;
}


// lowest and the eft-most point
Point p1;

// comparator for the points -- sorts according to polar angles wrt to p1
class comparatorOfPoints
{
    public:
        bool operator () (const Point& p2, const Point& p3) const
        {
            // assuming three points p1,p2,p3
            // vector v1 = p2 - p1 and v2 = p3 - p1
            // vector cross product of v1*v2 > 0 iff p3 lies on left of v1
            return (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first) >= 0;
        }
};

// USAGE
// 1) feed all points --> GrahamScan(deque<Point> _listOfPoints)
// 2) sort all the points --> deque<Point> buildSortedListOfPoints();
// 3) build convex hull --> deque<Point> buildConvexHull();
class GrahamScan
{
    private :

        // holds all the points in the plane
        deque<Point > listOfPoints;
    public:

        GrahamScan(deque<Point> _listOfPoints):listOfPoints(_listOfPoints){}
        GrahamScan(const GrahamScan & ref):listOfPoints(ref.listOfPoints){}

        // sorts the points using the comparator
        deque<Point> buildSortedListOfPoints();

        // finds the convex hull
        deque<Point> buildConvexHull();
};

deque<Point> GrahamScan::buildSortedListOfPoints() {
    // Sanity check
    if(listOfPoints.size()<3) return listOfPoints;

    // finds p1
    p1 = listOfPoints[0];
    int positionOfP1 = 0;
    for(int i = 1; i < listOfPoints.size(); ++i) {
        if(listOfPoints[i].second < p1.second) {
            p1 = listOfPoints[i];
            positionOfP1 = i;
        }
        else if(listOfPoints[i].second == p1.second) {
            if(listOfPoints[i].first < p1.first) {
                p1 = listOfPoints[i];
                positionOfP1 = i;
            }

        }
    }

    // leave p1 and sort the rest
    swap(listOfPoints[0], listOfPoints[positionOfP1]);

    sort(listOfPoints.begin()+1, listOfPoints.end(), comparatorOfPoints());

    return listOfPoints;
}


// utility function to print the stack
void printStack(stack<Point> sp) {
    cout<<"__STACK__"<<endl;
    while(!sp.empty()) {
        Point temp = sp.top();
        sp.pop();
        cout<<temp<<endl;

    }
    cout<<"-----------"<<endl;
}


deque<Point> GrahamScan::buildConvexHull() {
    // Sanity Check
    if(listOfPoints.size()<=3) return listOfPoints;

    stack<Point> stackOfPoints;
    stackOfPoints.push(listOfPoints[0]);
    stackOfPoints.push(listOfPoints[1]);

    for(int index = 2 ; index<listOfPoints.size(); ++ index) {
        // printStack(stackOfPoints);
        Point p2 = stackOfPoints.top();
        stackOfPoints.pop();
        Point p1 = stackOfPoints.top();
        stackOfPoints.pop();
        Point p3 = listOfPoints[index];
        int turn = (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first);
        if(turn == 0) {
            // ignore intermediate collinear points
            stackOfPoints.push(p1);
            stackOfPoints.push(p3);
            continue;
        }
        else if(turn > 0) {
            stackOfPoints.push(p1);
            stackOfPoints.push(p2);
            stackOfPoints.push(p3);
            continue;
        }
        else if(turn < 0) {
            // cout<<"encountered a right turn for " <<p3;
            stackOfPoints.push(p1);
            Point p2,p1;
            int _turn = turn;
            while(stackOfPoints.size() >= 2 && _turn <= 0) {
                printStack(stackOfPoints);
                p2 = stackOfPoints.top();
                stackOfPoints.pop();
                p1 = stackOfPoints.top();
                stackOfPoints.pop();
                _turn = (p2.first - p1.first)*(p3.second - p1.second) - (p2.second - p1.second)*(p3.first - p1.first);
                cout<<"turn = "<<_turn<<endl;
            }
            if(_turn > 0) {
                cout<<"right turn resolved for " <<p3;
                stackOfPoints.push(p1);
                stackOfPoints.push(p2);
                stackOfPoints.push(p3);
                printStack(stackOfPoints);
                continue;
            }

            // Sanity check
            else if(stackOfPoints.size()<2) {
                cout<<"can not from a convex hull due to stack underflow"<<endl;
                return deque<Point>();
            }
        }
    }
    deque<Point> convexHull;
    while(!stackOfPoints.empty()) {
        convexHull.push_front(stackOfPoints.top());
        stackOfPoints.pop();
    }
    return convexHull;
}


// driver
int main() {
    deque<Point> pointsOnPlane;
    pointsOnPlane.push_back(Point(5,5));
    pointsOnPlane.push_back(Point(1,-1));
    pointsOnPlane.push_back(Point(0,0));
    pointsOnPlane.push_back(Point(2,2));
    pointsOnPlane.push_back(Point(-1,-1));
    pointsOnPlane.push_back(Point(-5,4));
    GrahamScan grahamScan(pointsOnPlane);
    grahamScan.buildSortedListOfPoints();
    deque<Point> convexHull=grahamScan.buildConvexHull();
    for(int i=0;i<convexHull.size();i++) {
        cout<<convexHull[i];
    }

    return 0;
}

UVa 357

2010-02-27T14:22:00.000-08:00

Its basically a variation of the famous "Coin Change" problem. The code is pretty much self-explanatory. Here it is:

#include<stdio.h>
unsigned long tab[6][30001];
int denom[]={0,1,5,10,25,50};
int main()
{
    // tab[denom][val]
    // tab[i][j] = no of ways we can pay value j using upto ith denominations
    for(int i=0;i<6;++i)
    {
        tab[i][0]=1;
    }
    for(int i=0; i<30001;++i )
    {
        tab[0][i]=0;
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(tab[5][n]!=0)
        {
            if(tab[5][n]==1) printf("There is only 1 way to produce %d cents change.\n",n);
            else printf("There are %lu ways to produce %d cents change.\n",tab[5][n],n);
            continue;
        }
        bool found =false;
        for(int i=1;i<=n;++i)
        {
            if(found) break;
            for(int j=1;j<=5;++j)
            {
                if(!tab[j][i])
                {
                    if(denom[j]>i) tab[j][i]=tab[j-1][i];
                    else
                    {
                        tab[j][i]=tab[j-1][i]+tab[j][i-denom[j]];
                    }
                }
                if(j==5 && i==n)
                {
                    if(tab[5][n]==1) printf("There is only 1 way to produce %d cents change.\n",n);
                    else printf("There are %lu ways to produce %d cents change.\n",tab[5][n],n);
                    found =true;

                }
            }
        }

    }
    return 0;
}

UVa 113

2010-02-26T04:37:00.000-08:00

Basic formula but difficult constraints. The code I wrote was the first thought that came to my mind. I use binary search to correctly guess 'k' by using 1 to 10^9 as the range. This is my only Java submission, mainly because I did not have a pre-written BigInt class in C/C++. However later on I came across a neat mathematical way of doing it though I have not coded it yet. Here it is:

k^n = p

n*log(k) = log(p)

log(k) = log(p)/n

k = exp(log(p)/n)

My code is as follows:

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.math.BigInteger;

public class Main {

public static void main(String args[]) throws IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String str1 = "", str2 = "";

int n = 0;

BigInteger p = new BigInteger("0");

while (true) {

str1 = br.readLine();

if (str1 == null) {

break;

}

n = Integer.parseInt(str1);

str2 = br.readLine();

if (str2 == null) {

break;

}

p = new BigInteger(str2);

double lo = 0, hi = 10e9;

while (lo <= hi) {

boolean flag = false;

double mid = lo / 2 + hi / 2;

BigInteger temp = new BigInteger(Integer.toString((int) mid));

temp = temp.pow(n);

int comp = temp.compareTo(p);

switch (comp) {

case 0:

flag = true;

System.out.println((int) mid);

break;

case 1:

hi = (int) mid - 1;

break;

case -1:

lo = (int) mid + 1;

break;

}

if (flag) {

break;

}

SPOJ PROBTNPO

2010-02-24T07:37:00.000-08:00

When I saw this problem for the first time memoization was the word that came to my mind. And as usual, I jumped into coding it without giving it much thought before it struck me that a static memo is not a very good option as the numbers might go out of bounds because off the 3*n+1 step. Then I resorted to using map, a fancy but very useful data structure. But the "Man proposes, God disposes and I slog" rule came into play and I got some runtime errors, thanks to my flamboyant coding skills ;-) . Next came a tsunami of TLEs. After sometime i got really frustrated and started typing afresh right into the "code pasting" text field. It was the most naive solution I could think of and expected a TLE. But to my surprise, there it was smiling at me, a beautiful ACC.

#include <cstdio>

#include <algorithm>
using namespace std;

int f(int i)
{
    int cnt = 1;

    while(i != 1) {
        if(i&1) cnt+=2,i=(3*i+1)>>1;
        else ++cnt,i=i>>1;
    }

    return cnt;
}

int main()
{
    int i, j, a;
    int mx;

    while(scanf("%d%d", &i, &j)!=EOF) {
        mx = -1;
        for(a=min(i,j); a<=max(i,j); ++a)
            mx = max(mx, f(a));
        printf("%d %d %d\n", i, j, mx);
    }

    return 0;
}

SPOJ GOSSIPER

2010-02-23T10:52:00.000-08:00

This problem fooled me into thinking that it was all about transitive closure. So the first thing I did was to use Floyd-Warshall on it which failed miserably. But then with the help of Gowtham I could figure out that a meeting does not propagate the gossip back to the previous gossiper, a fact that I had clearly ignored even when it was screaming out in the sample input. Anyways couple of WAs, TLEs and SIGSEGVs later I finally got an AC. Phew...

#include<stdio.h>

#include<string>

#include<map>

#include<iostream>

using namespace std;

char tab[2100][2100];

map<string,int> name_map;

int main() {

int n,m;

while(scanf("%d%d",&n,&m)!=EOF) {

if(n==0 && m==0) return 0;

int _n=0,x,y;

string name1,name2;

name_map.clear();

while(_n<n) {

cin>>name1;

name_map.insert(make_pair(name1,_n++));

}

while(m--) {

cin>>name1>>name2;

x=name_map.find(name1)->second;

y=name_map.find(name2)->second;

for(_n=0;_n<n;++_n) {

if(tab[x][_n] && _n!=y) tab[y][_n]=1;

if(tab[y][_n] && _n!=x) tab[x][_n]=1;

}

tab[x][y]=tab[y][x]=1;

}

int cnt=0;

for(x=0;x<n;++x) {

for(y=0;y<n;++y) {

if(tab[x][y]) {

cnt++;

tab[x][y]=0;

}

if(cnt==n*n-n) printf("YES\n");

else printf("NO\n");

}

return 0;

}

UVa 108

2010-02-23T02:57:00.000-08:00

This is a well known problem. Also called Kadane's 2D problem, it asks to find the maximum sub matrix from a given matrix of integers. The theory is to reduce it to Kadane's 1D problem which aims at finding the maximum sub array in a given array of integers. How do we reduce, this is how:

1) First find the column sums, can be done on the fly. O(n^2)

2) Then just chose pair of rows from this table of column sums. O(n^2)

3) For each pair selected find the partial sum of each column from 1 to n

4) Run Kadane's 1D on the 1D array found above. O(n)

5) Voila sub matrix found in O(n^3)

Here it goes:

#include<stdio.h>

#include<algorithm>

using namespace std;

int tab[101][101];

int main() {

int n;

while(scanf("%d",&n)==1) {

for(int i=1;i<=n;++i) {

for(int j=1;j<=n;++j) {

scanf("%d",&tab[i][j]);

tab[i][j]+=tab[i-1][j];

}

int mx=tab[1][1];

for(int i=0;i<n;++i) {

for(int j=i+1;j<=n;++j) {

int temp=0;

for(int k=1;k<=n;++k) {

temp+=tab[j][k]-tab[i][k];

if(temp<0) temp=0;

mx=max(mx,temp);

}

printf("%d\n",mx);

}

return 0;

}

Posting Code Snippets on Blogger

2010-02-22T10:01:00.001-08:00

Well after some googling I found out the following "no fuss" code snippet transformers, good for casual bloggers like me. Hope it helps you too:

1) webformatter

2) formatmysourcecode

SPOJ PRIME1

2010-02-22T09:51:00.000-08:00

Here is another one of those problems that any wannabe programmer should solve to get initiated in the art of problem solving (trying to preach here ;)) . This code got me through, barely though.

It tends to be pretty slow, one must try segmented sieve for problems like this. But after I got an ACC I was not in a mood to dive into it again. Hopefully, someday I'll return to it and give it a second look. Till then ...

#include<cstdlib>

#include<iostream>

#include<string>

#include<fstream>

#include<cmath>

#include<cstring>

using namespace std;

#define SZ 32000

bool prime_tab[SZ];

int main(int argc, char** argv) {

int m, n, t;

prime_tab[0] = prime_tab[1] = 1;

for (int i = 2; i < SZ; i++) {

if (!prime_tab[i]) {

for (int j = 2; i * j < SZ; j++) {

prime_tab[i * j] = 1;

}

cin >> t;

while (t--) {

cin >> m >> n;

for (int i = m; i <= n; i++) {

bool pass = (i != 1);

for (int j = 2; j * j <= i; j++) {

if (!prime_tab[j]) {

if (i % j == 0) {

pass = 0;

break;

}

if (pass)

cout << i << endl;

}

cout << endl;

}

return 0;

}

SPOJ SUMITR

2010-02-22T09:19:00.000-08:00

This was good problem for people interested in pure algorithm and tweaking. I had to spend some time (read 2 hours) to come up with something that would satisfy the 256 bytes constraint. Luckily I happen to be a friend of a gifted individual (read one whose got an ACC) who had solved this problem before. With his tips I was able to to get an ACC finally :) So here it goes

#include<iostream>

#define f(a,b,c) for(a=b;a<=c;++a)

#define _ std::

int a[100][100],t,n,i,j,x;main(){_ cin>>t;while(t--){_ cin>>n;f(i,1,n)f(j,1,i)_ cin>>a[i][j],a[i][j]=_ max(a[i-1][j],a[i-1][j-1])+a[i][j],x=_ max(x,a[i][j]);_ cout<<x<<_ endl;x=0;}}

PS- I am open to criticism, please post any improvements that you can suggest.

Beginning of the Beginning...

2009-06-24T03:19:00.001-07:00

A Simple Hello World Program...

#include <iostream>
int main(){
std::cout<<"Hello World"<<std::endl;
return 0;
}