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