SPOJ LOOPEXP

Link : LOOPEXP

Category : Maths, Expectation

Hint : Consider the smallest element of the array. Consider the two cases of it being the first element of the array and not being the first element of the array.

Code:

	var arr:array[1..1000000] of double;
	i,ii,t:longint;
	begin
	arr[1]:=1;
	for i:=2 to 1000000 do begin
	arr[i]:=arr[i-1]+(1.0/i);
	end;
	readln(t);
	for ii:=1 to t do begin
	readln(i);
	writeln(arr[i]:0:14);
	end;
	end.

view raw loopexp.pas hosted with ❤ by GitHub

SPOJ AMR12H

Link : AMR12H

Category : Maths, probability and expectation

Solution : If f(x) is the Random Distribution Function of a random variable X and g(x) is the RDF of RV Y then
RDF of min(X,Y) is f(x)*g(x)
RDF of max(X,Y) is f(x)+g(x)-f(x)*g(x)
Then the expected value of the expression formed is integral over [0,1]

Code:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <queue>
	#include <stack>
	#include <map>
	#include <set>
	#include <utility>
	#include <climits>
	#include <cfloat>
	#include <cassert>
	using namespace std;
	#define readint(n) scanf("%d",&n)
	#define readull(n) scanf("%llu",&n)
	#define readll(n) scanf("%lld",&n)
	#define readf(n) scanf("%f",&n)
	#define readlf(n) scanf("%lf",&n)
	#define init(mem) memset(mem,0,sizeof(mem))
	#define ull unsigned long long int
	#define ll long long int
	#define setmax(a,b) a=max(a,b)
	#define setmin(a,b) a=min(a,b)
	#define ld long double
	#define poly vector<ld>
	poly mult(poly& p1,poly& p2){
	poly ret(p1.size()+p2.size()-1,0);
	for(int i=0;i<p1.size();i++){
	for(int j=0;j<p2.size();j++){
	ret[i+j]+=p1[i]*p2[j];
	}
	}
	return ret;
	}
	poly add(poly p1,poly p2){
	if(p1.size()>=p2.size()){
	for(int i=0;i<p2.size();i++){
	p1[i]+=p2[i];
	}
	return p1;
	}
	else{
	for(int i=0;i<p1.size();i++){
	p2[i]+=p1[i];
	}
	return p2;
	}
	}
	poly subt(poly p1,poly p2){
	if(p1.size()>=p2.size()){
	for(int i=0;i<p2.size();i++){
	p1[i]-=p2[i];
	}
	return p1;
	}
	else{
	for(int i=0;i<p1.size();i++){
	p2[i]=p1[i]-p2[i];
	}
	for(int i=p1.size();i<p2.size();i++){
	p2[i]=-p2[i];
	}
	return p2;
	}
	}
	poly X;
	int ptr;
	char* str;
	poly solve(){
	if(str[ptr]=='\0') assert(false);
	if(str[ptr]=='m'){
	ptr++;
	poly left=solve();
	poly right=solve();
	return mult(left,right);
	}
	else if(str[ptr]=='M'){
	ptr++;
	poly left=solve();
	poly right=solve();
	return subt(add(left,right),mult(left,right));
	}
	else{
	ptr++;
	return X;
	}
	}
	ld integrate(poly p){
	ld res=0;
	for(int i=0;i<p.size();i++){
	res+=(p[i]/(i+1));
	}
	return res;
	}
	int main(){
	X.push_back(0);
	X.push_back(1);
	str=new char[101];
	int t;
	readint(t);
	while(t--){
	scanf("%s",str);
	ptr=0;
	poly res=solve();
	printf("%.19Lf\n",integrate(res));
	}
	return 0;
	}

view raw AMR12H.cpp hosted with ❤ by GitHub

UVA 12356 : Army Buddies

Link : UVA12356

Category : Data Structure

Solution : Simple segment tree data structure suffices. Each node of the tree has a boolean variable indicating if at all it is possible to find an alive soldier in this range of soldiers.

Code:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <queue>
	#include <stack>
	#include <map>
	#include <set>
	#include <utility>
	#include <climits>
	#include <cfloat>
	#include <cassert>
	using namespace std;
	#define read(n) scanf("%d",&n)
	#define read2(n,m) scanf("%d%d",&n,&m)
	#define read3(n,m,l) scanf("%d%d%d",&n,&m,&l)
	#define readull(n) scanf("%llu",&n)
	#define readll(n) scanf("%lld",&n)
	#define ull unsigned long long int
	#define ll long long int
	#define vi vector<int>
	#define vs vector<string>
	bool *mem;
	void init(int l,int h,int pos){
	if(l==h) mem[pos]=true;
	else{
	mem[pos]=true;
	init(l,(l+h)/2,2*pos);
	init(1+(l+h)/2,h,2*pos+1);
	}
	}
	void remove(int l,int h,int pos,int x,int y){
	if(y<l or x>h) return;
	if(l>=x and h<=y){
	mem[pos]=false;
	return;
	}
	remove(l,(l+h)/2,2*pos,x,y);
	remove(1+(l+h)/2,h,2*pos+1,x,y);
	mem[pos]=mem[2*pos] or mem[1+2*pos];
	}
	int get(int l,int h,int pos,int x,int y){
	if(y<x) return -1;
	if(y<l or x>h) return -1;
	if(mem[pos]==0) return -1;
	if(l==h) return l;
	int ret=get(1+(l+h)/2,h,2*pos+1,x,y);
	if(ret==-1) ret=get(l,(l+h)/2,2*pos,x,y);
	return ret;
	}
	int get1(int l,int h,int pos,int x,int y){
	if(y<x) return -1;
	if(y<l or x>h) return -1;
	if(mem[pos]==0) return -1;
	if(l==h) return l;
	int ret=get1(l,(l+h)/2,2*pos,x,y);
	if(ret==-1) ret=get1(1+(l+h)/2,h,2*pos+1,x,y);
	return ret;
	}
	int main(){
	mem=new bool[1000000];
	int s,b,x,y;
	while(1){
	read2(s,b);
	if(b==0 and s==0) return 0;
	init(1,s,1);
	while(b--){
	read2(x,y);
	remove(1,s,1,x,y);
	int left=get(1,s,1,1,x-1);
	int rght=get1(1,s,1,y+1,s);
	if(left==-1) printf("* ");
	else printf("%d ",left);
	if(rght==-1) printf("*\n");
	else printf("%d\n",rght);
	}
	printf("-\n");
	}
	return 0;
	}

view raw UVA12356.cpp hosted with ❤ by GitHub

Codechef ARIGEOM

Link : ARIGEOM

Category : Pigeonhole principle

Solution : Consider the first three terms. Some two of them have to be in AP or both in GP, thus giving 6 possible cases. Eg, let a,b,and c be first three terms. If a and b form an AP, then common difference of the AP must be b-a. Now mark all elements falling in this AP as apmarked (remember, all elements must be present in this AP starting from a and ending at some end point within the array). Now for remaining elements, find the common ratio that would mark all remaining elements, and possibly some apmarked elements too. Similarly for other 5 cases too.

Code:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <queue>
	#include <stack>
	#include <map>
	#include <set>
	#include <utility>
	#include <climits>
	#include <cfloat>
	#include <cassert>
	using namespace std;
	#define readint(n) scanf("%d",&n)
	#define readull(n) scanf("%llu",&n)
	#define readll(n) scanf("%lld",&n)
	#define readf(n) scanf("%f",&n)
	#define readlf(n) scanf("%lf",&n)
	#define init(mem) memset(mem,0,sizeof(mem))
	#define ull unsigned long long int
	#define ll long long int
	#define setmax(a,b) a=max(a,b)
	#define setmin(a,b) a=min(a,b)
	inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
	struct frac{
	ll n,d;
	frac(){}
	frac(ll n1,ll d1){
	n=n1;
	d=d1;
	ll g=gcd(n,d);
	n/=g;
	d/=g;
	}
	};
	inline frac getcommonroot(frac a,frac b){
	//printf("%lld %lld %lld %lld\n",a.n,a.d,b.n,b.d);
	if(a.n*b.d>a.d*b.n) swap(a,b);
	if(a.n==1 and a.d==1) return b;
	if((b.n*a.d)%(b.d*a.n)!=0) return a;
	return getcommonroot(a,frac(b.n*a.d,b.d*a.n));
	}
	int t,n;
	ll arr[10001];
	bool apmarked[10001];
	bool gpmarked[10001];
	bool testAP(int ind1,int ind2){
	init(apmarked);
	init(gpmarked);
	int markcnt=0;
	apmarked[ind1]=1;
	apmarked[ind2]=1;
	markcnt=2;
	ll diff=arr[ind2]-arr[ind1];
	int ptr=ind2+1;
	ll next=arr[ind2]+diff;
	while(ptr<n){
	if(arr[ptr]==next){
	apmarked[ptr]=1;
	markcnt++;
	next+=diff;
	if(next>arr[n-1]) break;
	}
	ptr++;
	}
	if(markcnt==n or markcnt==n-1){
	int unmarked=0;
	for(int i=0;i<n;i++){
	if(!apmarked[i]){
	unmarked=i;
	break;
	}
	}
	for(int i=0;i<n;i++){
	if(apmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	if(unmarked==n-1){
	printf("%lld %lld\n",arr[unmarked-1],arr[unmarked]);
	}
	else{
	printf("%lld %lld\n",arr[unmarked],arr[unmarked+1]);
	}
	return true;
	}
	if(markcnt==n-2){
	for(int i=0;i<n;i++){
	if(apmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	for(int i=0;i<n;i++){
	if(!apmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	return true;
	}
	int prevunmarked=0;
	while(apmarked[prevunmarked]) prevunmarked++;
	frac ratio(1,1);
	for(int i=prevunmarked+1;i<n;i++){
	if(!apmarked[i]){
	ratio=getcommonroot(ratio,frac(arr[i],arr[prevunmarked]));
	prevunmarked=i;
	}
	}
	ptr=0;
	while(apmarked[ptr]) ptr++;
	gpmarked[ptr]=true;
	markcnt++;
	if((arr[ptr]*ratio.n)%ratio.d==0){
	next=(arr[ptr]*ratio.n)/ratio.d;
	ptr++;
	while(ptr<n){
	if(next>arr[n-1]) break;
	if(arr[ptr]==next){
	gpmarked[ptr]=true;
	if(!apmarked[ptr]) markcnt++;
	if((arr[ptr]*ratio.n)%ratio.d!=0) break;
	next=(arr[ptr]*ratio.n)/ratio.d;
	}
	ptr++;
	}
	if(markcnt==n){
	for(int i=0;i<n;i++){
	if(apmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	for(int i=0;i<n;i++){
	if(gpmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	return true;;
	}
	}
	return false;
	}
	bool testGP(int ind1,int ind2){
	init(apmarked);
	init(gpmarked);
	int markcnt=0;
	gpmarked[ind1]=1;
	gpmarked[ind2]=1;
	markcnt=2;
	bool justcheckap=false;
	frac ratio(arr[ind2],arr[ind1]);
	if(((arr[ind2]*ratio.n)%ratio.d)!=0){
	justcheckap=true;
	}
	ll ptr=ind2+1,next=(arr[ind2]*ratio.n)/ratio.d;
	if(!justcheckap){
	while(ptr<n){
	if(next>arr[n-1]) break;
	if(arr[ptr]==next){
	gpmarked[ptr]=true;
	if(((next*ratio.n)%ratio.d)!=0) break;
	next=(next*ratio.n)/ratio.d;
	markcnt++;
	}
	ptr++;
	}
	}
	if(markcnt==n or markcnt==n-1){
	int unmarked=0;
	for(int i=0;i<n;i++){
	if(!gpmarked[i]){
	unmarked=i;
	break;
	}
	}
	if(unmarked==n-1){
	printf("%lld %lld\n",arr[unmarked-1],arr[unmarked]);
	}
	else{
	printf("%lld %lld\n",arr[unmarked],arr[unmarked+1]);
	}
	for(int i=0;i<n;i++){
	if(gpmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	return true;
	}
	if(markcnt==n-2){
	// printing
	for(int i=0;i<n;i++){
	if(!gpmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	for(int i=0;i<n;i++){
	if(gpmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	return true;
	}
	int prevunmarked=0;
	while(gpmarked[prevunmarked]) prevunmarked++;
	ll diff=0;
	for(int i=prevunmarked+1;i<n;i++){
	if(!gpmarked[i]){
	diff=gcd(diff,arr[i]-arr[prevunmarked]);
	prevunmarked=i;
	}
	}
	ptr=0;
	while(gpmarked[ptr]) ptr++;
	apmarked[ptr]=1; // AP starter
	next=arr[ptr]+diff;
	while(ptr<n){
	if(next>arr[n-1]) break;
	if(arr[ptr]==next){
	apmarked[ptr]=1;
	next+=diff;
	}
	ptr++;
	}
	markcnt=0;
	for(int i=0;i<n;i++){
	if(gpmarked[i] or apmarked[i]) markcnt++;
	}
	if(markcnt==n){
	for(int i=0;i<n;i++){
	if(apmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	for(int i=0;i<n;i++){
	if(gpmarked[i]){
	printf("%lld ",arr[i]);
	}
	}
	printf("\n");
	return true;
	}
	return false;
	}
	int main(){
	readint(t);
	while(t--){
	readint(n);
	for(int i=0;i<n;i++){
	readll(arr[i]);
	}
	if(n==2){
	printf("%lld %lld\n",arr[0],arr[1]);
	printf("%lld %lld\n",arr[0],arr[1]);
	continue;
	}
	if(testAP(0,1)) continue;
	if(testGP(0,1)) continue;
	if(testAP(0,2)) continue;
	if(testGP(0,2)) continue;
	if(testAP(1,2)) continue;
	if(testGP(1,2)) continue;
	assert(false);
	}
	return 0;
	}

view raw ARIGEOM.cpp hosted with ❤ by GitHub

SPOJ DCEPC206

Link : DCEPC206

Category : Segment Tree

Code:

	#include <iostream>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <cmath>
	#include <algorithm>
	#include <vector>
	#include <list>
	#include <queue>
	#include <stack>
	#include <map>
	#include <ctime>
	#include <utility>
	#include <climits>
	#include <cfloat>
	#include <cassert>
	using namespace std;
	#define readint(n) scanf("%d",&n);
	#define readll(n) scanf("%lld",&n);
	#define readchar(n) scanf("%c",&n);
	#define readf(n) scanf("%f",&n);
	#define readd(n) scanf("%lf",&n);
	#define readstr(s) scanf("%s",&s);
	#define init(mem) memset(mem,0,sizeof(mem));
	int pabs(int n){return (n>0?n:-n);}
	int hcf(int a,int b){if(b==0){return a;} else{return hcf(b,a%b);}}
	long long int mem[4000004];
	int n;
	void update(int ind,int l,int u,int v){
	if(v<l or v>u)return;
	if(l==u){
	mem[ind]+=l;
	return;
	}
	int mid=(l+u)/2;
	update(2*ind,l,mid,v);
	update(2*ind+1,mid+1,u,v);
	mem[ind]=(mem[ind*2]+mem[2*ind+1]);
	}
	long long int query(int ind,int l,int u,int x,int y){
	if(u<x or l>y){
	return 0;
	}
	if(x<=l and u<=y){
	return mem[ind];
	}
	int mid=(l+u)/2;
	return query(2*ind,l,mid,x,y)+query(2*ind+1,mid+1,u,x,y);
	}
	int main(){
	int t,v;
	readint(t);
	while(t--){
	init(mem);
	readint(n);
	long long int sum=0;
	for(int i=1;i<=n;i++){
	readint(v);
	sum+=query(1,1,1000001,1,v-1);
	update(1,1,1000001,v);
	}
	printf("%lld\n",sum);
	}
	return 0;
	}

view raw DCEPC206.cpp hosted with ❤ by GitHub

SPOJ SKYLINE

Link : SKYLINE

Category :Maths

Solution : Recurrence works out to be Catalan number.

Code:

	var cat:array[1..1001] of int64;
	var n:longint;
	const md:int64=1000000;
	procedure prep();
	var i,j:longint;
	var tmp:int64;
	begin
	cat[1]:=1;
	for i:=2 to 1001 do begin
	cat[i]:=0;
	for j:=1 to i-1 do begin
	tmp:=(cat[j]*cat[i-j]) mod md;
	cat[i]:=cat[i]+tmp;
	end;
	cat[i]:=cat[i] mod md;
	end;
	end;
	begin
	prep();
	while true do begin
	readln(n);
	if n=0 then break;
	writeln(cat[n+1]);
	end;
	end.

view raw skyline.pas hosted with ❤ by GitHub

SGU 355 : Numbers Painting

Link : sgu355

Category : Simple number theory

Solution :  For every M in 2 to N, let prime factorization of M be M=product(p_i^e_i). Then M will be colored by color number sum(e_i). Eg, 12=2²x3¹, then color 12 by color number (2+1)=3. Additionally, number 1 will require a totally different color, since it divides all other numbers.

Code:

	var n,n0,n1,i,maxfacts,facts:longint;
	colors:array[1..10000] of longint;
	begin
	readln(n0);
	if n0=1 then
	begin
	writeln(1);
	writeln(1);
	exit;
	end;
	maxfacts:=1;
	for n1:=2 to n0 do
	begin
	n:=n1;
	facts:=0;
	i:=2;
	while i*i<=n do
	begin
	if n mod i=0 then
	begin
	while n mod i=0 do
	begin
	n:=trunc(n/i);
	inc(facts);
	end;
	end;
	inc(i);
	end;
	if n>1 then inc(facts);
	if facts>maxfacts then maxfacts:=facts;
	colors[n1]:=1+facts;
	end;
	writeln(maxfacts+1);
	write(1,' ');
	for i:=2 to n0 do
	write(colors[i],' ');
	end.

view raw sgu355.pas hosted with ❤ by GitHub