UVa 10432

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

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

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

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

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

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

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;

}