Archive for the ‘Combinatorics’ Category

Combinations with repetitions   Leave a comment


Let the number of ways to choose R objects from N objects be C(N,R) where the order does not matter, which has the famous closed form N!/(R! * (N-R)!).
Let the number of ways to choose R times from N objects with repetition be S(N,R) where the order of choosing does not matter.
for example if we were to choose from A,B and C four times A,B,C,C is the same as A,C,B,C so we should not count this twice in S(N,R)
S(N,R) turns also to be the number of solutions of
a1 + a2 + … + aN = R, where ai ≥ 0, and R is some non negative integer, simply imagine ai’s as objects the number of time an object is chosen is it’s value, and we choose from those objects R times so the sum would be equals R.
The question is how do we calculate S(N,R) using C(N,R) and this is the only reason for writing this post.
Lets try to solve an instance of the problem
lets assume N = 3 , R = 4
here are some possible solutions
a1 = 0, a2 = 2, a3 = 2
a1 = 1, a2 = 2, a3 = 1
a1 = 2, a2 = 2, a3 = 0
basically we are assigning a value to each variable such that their sum is 4 (youdon’tsay!)
but lets try to interpret this using binary numbers somehow, we can somehow write a solution using a binary number of length N + R – 1 bits as the following
a zero means move on to next variable
a one means increment current variable by 1
we can write a1 = 0, a2 = 2, a3 = 2 as 011011
at the beginning we have a1 = 0, we encounter a 0 so we move on to a2 increment it twice, then move on to a3 increment it twice.
similarly we can write a1 = 1, a2 = 2, a3 = 1 as 101101
since in any solution we need to move on to next variable N-1 times (N variables), and we have to increment all variables R times then from any binary number of N-1 zeroes, R ones we can construct a valid solution.
And if we have a solution we can construct a binary number.
Then there’s a one to one correspondence between the set of solutions and the set of binary numbers with N+R-1 bits where N-1 of them are zeroes and R of them are ones.
Counting those can be easily done using normal combinations so S(N,R) = C(N+R-1,R).
Update: it turns out that this post has a similar content to whats written here at topcoder tutorial :(, so you might want to check it out.

Advertisements

Posted August 14, 2013 by epicrado in Combinatorics, Mathematics

UVA – 11732 – “strcmp()” Anyone?   Leave a comment


At first I thought this problem can be solved using trie, which would be an easy way however the simple trie would use a lot of memory 4000 * 1000 * 26 integers or so, Then I had to use another way which would be sorting, using any comparison based sorting algorithm as quick sort or merge sort would also cause Time limit exceeded so instead I used my not-so-efficient radix sort which runs in O(num_words*max_length), then using the sorted words you can easily calculate the result, see the solution for more information.

#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
char words[4005][1005];
int len[4005];
int loc[4005];
int temp[4005];
int word_count;
int freq[128];

int charAt(int i, int j) {
	return (j < len[loc[i]]) ? words[loc[i]][j] : 0;
}
void count_sort(int j) {
	memset(freq, 0, sizeof freq);
	for (int i = 0; i < word_count; i++)
		freq[charAt(i, j)]++;
	for (int i = 1; i < 128; i++)
		freq[i] += freq[i - 1];
	for (int i = word_count - 1; i >= 0; i--)
		temp[--freq[charAt(i, j)]] = loc[i];
	memcpy(loc, temp, word_count * 4);
}
void radix_sort() {
	int max_len = 0;
	for (int i = 0; i < word_count; i++) {
		loc[i] = i;
		if (len[i] > max_len)
			max_len = len[i];
	}
	for (int i = max_len - 1; i >= 0; i--)
		count_sort(i);
}
int main(int argc, char *argv[]) {
	int cc = 1;
	while (scanf("%d", &word_count) && word_count) {
		getchar();
		for (int i = 0; i < word_count; i++) {
			gets(words[i]);
			len[i] = strlen(words[i]);
		}
		radix_sort();
		stack<int> s;
		s.push(0);
		s.push(word_count - 1);
		s.push(0);
		ll res = 0;
		memset(freq, 0, sizeof(freq));
		while (s.size()) {
			int j = s.top();
			s.pop();
			int r = s.top();
			s.pop();
			int l = s.top();
			s.pop();
			int all = r - l + 1;
			for (int i = l; i <= r; i++)
				freq[charAt(i, j)]++;
			res += freq[0] * (freq[0] - 1);
			res += freq[0] * (all - freq[0]);
			freq[0] = 0;
			for (int i = l; i <= r; i++) {
				char c = charAt(i, j);
				if (!c)
					continue;
				if ((i > l && c == charAt(i - 1, j)) || !c)
					continue;
				res += freq[c] * (freq[c] - 1);
				res += freq[c] * (all - freq[c] - i + l);
				s.push(i);
				s.push(i + freq[c] - 1);
				s.push(j + 1);
				freq[c] = 0;
			}
		}
		printf("Case %d: %lld\n", cc++, res);
	}
	return 0;
}

Posted May 7, 2013 by epicrado in Combinatorics, String Processing

UVA – 11282 – Mixing Invitations   1 comment


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class MixingInv {
	public static long[][] C(int MAX) {
		long C[][] = new long[MAX + 1][MAX + 1];
		for (int i = 0; i < C.length; i++)
			C[i][0] = 1;
		for (int i = 1; i < C.length; i++)
			for (int j = 1; j < C[i].length; j++)
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
		return C;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		long[] dp = new long[21];
		long[][] C = C(21);
		dp[0] = 1;
		dp[1] = 0;
		for (int i = 2; i < dp.length; i++)
			dp[i] = (i - 1) * (dp[i - 2] + dp[i - 1]);

		while (true) {
			String s = in.readLine();
			if (s == null)
				return;
			String[] arr = s.split(" ");
			int a = Integer.parseInt(arr[0]);
			int b = Integer.parseInt(arr[1]);
			long res = 0;
			for (int i = 0; i <= b; i++)
				res += C[a][i] * dp[a - i];
			System.out.println(res);
		}
	}
}

Posted July 5, 2012 by epicrado in Combinatorics

UVA – 1224 – Tile Code   Leave a comment


Using recurrence formula W1 it has repetitions as turning a tag upside down doesn’t make a different tag,so we use another recurrence relation W2 where W2[i] is the number of symmetric 2xi tags
and the final result for a 2xn tag is (W1[n]-W2[n])/2 + W2[n]

#include <stdio.h>
#define MAXN 31
int main()
{
    int W1[MAXN],W2[MAXN],i,tc;
    W1[0]=1;
    W1[1]=1;
    for(i=2;i<MAXN;i++)
        W1[i]=2*W1[i-2]+W1[i-1];
    W2[0]=1;
    W2[1]=1;
    W2[2]=3;
    W2[3]=1;
    for(i=4;i<MAXN;i++)
        W2[i]=W2[i-2]+2*W2[i-4];
    scanf("%d",&tc);
    while(tc-->0)
    {
        scanf("%d",&i);
        printf("%d\n",(W1[i]-W2[i])/2 + W2[i]);
    }
    return 0;
}


Posted May 1, 2012 by epicrado in Combinatorics

UVA – 10219 – Find the ways !   1 comment


#include <stdio.h>
#include <math.h>
int main()
{
	unsigned long long int a, b;
	long double res;
	unsigned long long int i;
	while(scanf("%llu %llu",&a,&b)==2)
	{
		res = 0;
		for(i=a;i>a-b;i--)
			res+=log10(i);
		for(i=b;i>0;i--)
			res-=log10(i);
		printf("%d\n",(int)floor(res)+1);
	}
	return 0;
}

Posted September 22, 2011 by epicrado in Combinatorics

UVA – 11554 – Hapless Hedonism   Leave a comment


#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define N 1000001
unsigned long long int dp[N];
unsigned long long int sum(int s,int t,int shift)
{
	return (unsigned long long int)(abs(t-s)/shift+1)*(s+t)/2;
}
int main()
{
	int i,n;
	for(i=0;i<N;i++)
		dp[i]=0;
	dp[4]=1;
	for(i=5;i<N;i++)
	{
		n = i / 2 + 1;
		dp[i]=dp[i-1]+sum(1,n-2,1)+sum(i-n-1,1,1);
	}
	scanf("%d",&i);
	while(i--)
	{
		scanf("%d",&n);
		printf("%llu\n",dp[n]);
	}
	return 0;
}

Posted September 13, 2011 by epicrado in Combinatorics

UVA – 11401 – Triangle Counting   7 comments


Problem:
suppose we have sticks 1,2,3….,n
find the number of possible triangles that can be formed any of those sticks such that each stick can only be used once per triangle
first if we have a triangle with sides a,b,c therfore this must be true a+b>c , a+c>b , b+c>a

if n = 3
we have 3 sticks
1 2 3
we can’t form any triangles with this
if n = 4
1 2 3 4
we can form 1 triangle
(2,3,4)
if n = 5
1 2 3 4 5
we can form 3 triangles

(2,3,4)
——-
(2,4,5)
(3,4,5)

we can form the same number of triangles using four sticks + the number of triangles
that can be formed using the new stick as one side of the triangle (stick with length 5)

let nTri(n) is the number of triangles that can be formed using n sticks 1,2,3,4..n
so nTri(n) = nTri(n-1) + X
where X is the number of triangles having the nth side
now we need to calculate X
to figure this quickly we’ll use n=6
1 2 3 4 5 6
we already have 6 as the largest side we’ll choose x the smallest side
let y be the third side
so choosing x=2 yields
(2,y,6) y=5
choosing x=3 yields
(3,y,6) y=4 or 5
choosing x=4 yields
(4,y,6) y=5

2,n can pair with y=n-1 for 2+y>n to be true
3,n can pair with y=n-1,n-2 for 3+y>n to be true
4,n can pair with y=n-1,n-2,n-3 for 4+y>n to be true

for n=6 the sequence is 1,2,1
for n=7 the sequence is 1,2,2,1
thus
for any even n>=4 the sequence will be
1,2,..,(n/2-1),..,2,1
for any odd n>4 the sequence will be
1,2,..,(n/2-1),(n/2-1),..,2,1

X is the sum of this sequence
X can be easily calculated using the arithmatic sequence sum rule
then nTri(n) = nTri(n-1) + X


#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define N 1000001
unsigned long long int dp[N];
//Returns sum between integers 1 to n inclusive
unsigned long long int sum(int n)
{
    return	(unsigned long long int)n*(n+1)/2;
}
int main()
{
    int i,n;
    for(i=0;i<N;i++)
        dp[i]=0;
    dp[4]=1;
    for(i=5;i<N;i++)
    {
        n = i/2 -1;
        dp[i]=dp[i-1]+2*sum(n)-((!(i&1))*n);
        //((!(i&1))*n) if i is even this evaluates as n else it evaluates as 0
    }
    scanf("%d",&n);
    while(n>=3)
    {
        printf("%llu\n",dp[n]);
        scanf("%d",&n);
    }
    return 0;
}

Posted September 13, 2011 by epicrado in Combinatorics