My Weblog

Blog about programming and math

Project Euler Problem 307

Finally solved using this book. Project Euler problem 307 requires a bit knowledge of counting technique so i recommend you to read couple of chapters of An Introduction to Probability Theory and Its Applications by William Feller. The required probability will be 1.0-p(1)-p(2) where p(1) and p(2) are probability of chips having one and two defects per chip respectively. Calculation of p(1) is relatively easy but p(2) requires some trick. First defect can be put in any of N chips , second defect can be put in any of N chips …..Kth defect can be put in any of N chips so total number of ways = N^K. How many ways we can put K defects into N chips such that each chip has only one defect. First defect can be put into any of N chips , second can be put into any of (N-1) chips ………… Kth defect can be any of (N-K+1) chips so total number ways is N*(N-1)…….(N-K+1).Now things are bit complicated. We will try to mix 2 defects per chip and 1 defect per chip. How many ways we can chose 2 defects out of K defects and put it into one of N available chips[chip having two defect ] and remaining (K-2) defects into (N-1) available chips[one defect per chip]. Clearly its (K Chose 2) *N *[(N-1)(N-2)……(N-k+2)]. How many ways we can put 4 defects out of K defects in 2 chips [ 2 defects per chip ] and remaining (K-4) defects into (N-2) places [ one defect per chip].This would be (K Chose 2) *N ((K-2) Chose 2 )(N-1)*[(N-2)……(N-k+3)]. There is little catch in previous expression. Since ordering is not important so we have to divide it by 2![ 2 factorial]. We will continue till we haven’t distributed all K defects into K/2 chips [ 2 defects per chip]. It will be (K Chose 2) *N *((k-2) Chose 2) *(N-1)*((K-4) Chose 2 )*(N-2) ………… Since ordering is not important we have to divide it by factorial of Number of chips having 2 defects which is K/2[2 defects per chip]. So total probability will be 1.0-(favorable/total).
Favorable is N*(N-1)*(N-2)……..(N-k+1)+ (K Chose 2) *N*(N-1)…..(N-k+2)+ (K Chose 2) *((K-2) Chose 2)*N*(N-1)…(N-k+3)/2! + (K Chose 2) *((K-2) Chose 2)*((K-4) Chose 2)N*(N-1)…(N-k+4)/3! + ……….
Total is N^K. Hope i explained it. Source code for problem

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
typedef long double d64;
int main()
	{
		int n=1000000,k=20000,p,d;
		long double tot=k*logl(n*1.0),fav=0,ret=0,tmp=0,fact=0;
		for(int i=n-k+1;i<=n;i++) fav+=logl(i*1.0);
		ret+=expl(fav-tot);
		p=n-k+1,d=1;
		for(int i=0;i<k;i+=2)
		{
			tmp+=(logl((k-i)*1.0)+logl((k-i-1)*1.0)-logl(2.0));
			fav-=logl(p*1.0);
			fact+=logl(d*1.0);
			ret+=expl(tmp+fav-fact-tot);
			p++,d++;
		}
		printf("%.10llf\n",1.0-ret);
		
	}
Advertisements

December 24, 2010 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: