Tuesday, March 9, 2010

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;

}

Saturday, March 6, 2010

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;
}


Saturday, February 27, 2010

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;
}

Friday, February 26, 2010

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;
}
}
}
}
}

Wednesday, February 24, 2010

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;
}

Tuesday, February 23, 2010

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;
}

Monday, February 22, 2010

Posting Code Snippets on Blogger

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:

SPOJ PRIME1

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

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.