Archive for the ‘UVA’ 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

NIM Game   Leave a comment


In NIM Game you have n piles each contains ai (0≤i<n) stones, two players alternate turns in each turn a player may remove any positive number of stones from a single pile, the player who cannot make a move loses the game.

Here’s an example n = 1,a0 = 30

First player take 29 stones.

Second player take 1 stone.

First player loses (a0 = 0).

However First player could’ve won if he took 30 stones in the first turn.

Another example n = 2,a0 =3,a1 = 3.

First player take 3 stones from a0.

Second player take 3 stones from a1.

Try playing the game here Stone game reading the next part

If both players play optimally who will win the game?

We can easily find who will win the game by calculating the bitwise XOR of all pile sizes(NIM sum) if this number is zero then second player wins otherwise first player wins.

So why does this work ? You can spend sometime trying to get some intuition by applying this rule on games with N ≤ 2, however when n grows a mathematical proof works best.

Here’s a sketch of a proof (Note: ^ is the bitwise xor)

lets assume we have piles a0,a1,…,an we prove that if a0^a1^…^an = 0 then we are in a losing position, otherwise we are in a winning position.

we prove the following

  • A-base case if all piles contain 0 stones then we are in a losing state (0 ^ 0 ^ .. ^ 0 = 0)
  • B-being in a losing state means that any move we make will put the opponent in a winning state

proof:

first being in a losing state means

a0 ^ a1 ^ a2 … ^ an = 0

lets assume without the loss of generality that we picked pile a0 to make our move and removed k (0<k≤an) stones from it

we need to prove that

(a0 – k) ^ a1 ^ a2 … ^ an != 0

starting from

a0 ^ a1 ^ a2 … ^ an = 0 xor both sides by a0 ^ (a0 – k)

we get

(a0 – k) ^ a1 ^ a2 … ^ an = a0 ^ (a0 – k)

but a0 ^ (a0 – k) will always be non zero for positive values of k.

  • C-being in a wining state means that there exists a move that will put the opponent in a losing state

proof:

assume that

a0 ^ a1 ^ a2 … ^ an = x

lets write x in binary, and look at the highest bit set there exists at least one pile that has that bit set assume without the loss of generality that this pile a0

we need to prove that there’s some POSITIVE k such that

(a0-k) ^ a1 ^ a2 … ^ an = 0

but (a0-k) ^ a1 ^ a2 … ^ an = x ^ a0 ^ (a0 – k)

thus we need to solve x ^ a0 ^ (a0 – k) = 0

xor both sides by a0 – k

we get

x ^ a0 = a0 – k which means

k = a0 – (x ^ a0) and with the assumption that a0 has the highest bit in x means that x ^ a0 is strictly less than a0 thus k is positive and we’re done.

using A,B,C we can use induction to obtain the complete proof.

Useful links

Play NIM game

Sample Problems

Stone game

Exclusively Edible

Box Game (Not direct NIM but try to get an observation and prove it in a similar way)

Posted June 25, 2013 by epicrado in Mathematics, Tutorials

UVa – 10714 – Ants   1 comment


The problem here is asking us to calculate the minimum,maximum time it would take all ants to fall off from the stick, lets focus on the maximum time first
That maximum time would be the maximum time that would take the last ant to fall from the stick.
So how do we make this time maximum if we had one ant at position x, simply the time would be max(x,L-x) where L is the length of the stick.
What makes the problem harder is the collision, so lets focus on what happens when 2 ants collide

Assume we have 2 ants A,B in those directions —A—><—B— and they collided at point z, what happens that
before collision B should walk distance z, A should walk distance L-z
after collision A should walk distance z, B should walk distance L-z
so they just exchanged roles here, i.e before collision we were going to wait max(z,L-z) for both ants to fall (if they didn't collide and just shook hands 🙂 )
after collision we're also going to wait max(z,L-z), so collision doesn't change the result.
Knowing this the problem becomes direct, here's solution.

#include <stdio.h>
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int main()
{
	int tc,i,n,c,l,h;
	scanf("%d",&tc);
	while(tc--){
		scanf("%d %d",&c,&n);
		l = h = 0;
		while(n--){
			scanf("%d",&i);
			l = max(l,min(c-i,i));
			h = max(h,max(c-i,i));
		}
		printf("%d %d\n",l,h);
	}
	return 0;
}

Posted May 21, 2013 by epicrado in Greedy

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 – 1214 – Manhattan Wiring   1 comment


Well this might be one of the hardest problems I’ve solved so far, so I decided to write some little words about how to solve it, First the contest analysis for this problem said that It should be solved using search but excessive pruning is needed I’ve tried this approach but It failed and it took much time to solve those cases which had no solution.

Before seeing the analysis I’ve thought about dynamic programming with layer count + layer profile, but It couldn’t be that hard, but it actually was 🙂
So if you’re going to attempt this problem and you’re not pretty good with pruning search space in backtracking problems, I suggest understanding those first
commonly used DP state domains[read layer count+layer profile]
profile dynamics by emaxx[russian only you may use google translate]

Now I’ll assume you understand those well and we’re ready to rock, first imagine we have only cells marked with 2, and we want to solve the problem (i.e find the shortest path between those cells having 2) using dynamic programming ?
we may keep generating all possibilities for each layer (all binary numbers of size 2^m), the number of 1’s in each row will be the cost paid in this row then but how do we ensure that this actually forms a path? this is the problem to solve it we’ll need to understand paths.

Imagine a graph that is a simple path or a chain, what is special in this graph is that all nodes except possible start and end have degree = 2, start and end have exactly degree 1.
Now if we force this rule we’ll sure get a path so for each cell in the grid it should have degree 0 if this is not on the selected path, 1 if it’s a start or end, 2 if it’s an intermediate cell on the path.
but selecting only the degree is not enough we must also select neighbors not only the degree and selecting neighbor should also affect the neighbor’s degree each cell might look like one of those.

Note that this approach may generate also closed cycles that doesn’t contain start or end however because this is a minimization problem cycles wouldn’t exist in the optimal solution we find, If this was a maximization problem then it would be harder.

first node has degree 0 (empty), then 4 nodes that have a source or a destination with degree 1, all others have degree 2

cell-neighbor combinations

To apply this using dynamic programming we’d use a state of (current row, columns in current row that share an edge with the row above as a set(bitmask))
Transitions would be trying to put any of the cell-neighbor combinations but keep them consistent, handling blocks would be easy as a blocked cell should always be assigned degree = 0,
Now to solve the problem when we have both cells marked with 2 and cells marked with 3, the solution won’t differ much but we won’t be able to do it with a binary number, as paths are colored now each path has either color 0 (no path entering this cell), 1(path that starts and ends at a 2 entering this cell) or 2(path that starts and ends at 3 entering this cell) and choose the path color also for each cell-neighbor combination of cell

Here’s the source code

import java.util.Arrays;
import java.util.Scanner;
import static java.lang.Math.*;

public class ManhattanWiring {
	int[][] arr;
	int n, m;
	int[] power = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683 ,59049,177147,531441};
	int[][] dp = new int[10][19683];

	public int get(int a, int i) {
		return (a / power[i]) % 3;
	}

	public int set(int a, int i, int v) {
		return a + ( v - get(a, i) ) * power[i];
	}

	//search function to generate all transitions reachable from current state
	public int search(int i, int j, int must, int state, int next) {
		if (j == m)
			return must == 0 ? solve(i + 1, next) : 1023;
		int ret = 1023,x = get(state, j);
		if((must!=0 && (arr[i][j-1]==-1||arr[i][j]==-1)) || (get(state,j)!=0 && arr[i][j]==-1))ret = 1023;
		else if(arr[i][j]!=-1 && arr[i][j]!=0){
			if(x!=0 && must!=0)ret =  1023;
			else if(x==0 && must==0)ret = 1 + min(search(i, j+1, arr[i][j], state, next),
											 search(i,j+1,0,state,set(next,j,arr[i][j])));
			else if(x!=0 && x==arr[i][j])ret=search(i, j+1, 0, state, next);
			else if(must!=0 && must==arr[i][j])ret=search(i, j+1, 0, state, next);
			else ret = 1023;
		}
		else if (must == 0) {
			if (x == 0)//add none or add an arc    --
								  	  //          |
				ret = min(
								search(i, j + 1, 0, state, next),
						2 + min(search(i, j + 1, 1, state, set(next,j,1)),
							    search(i, j + 1, 2, state, set(next,j,2))));
			else
				//add | or add |
				//	  |        --
				ret = 1 + min(search(i, j+1, must, state, set(next,j,x))
						     ,search(i, j+1, x, state, next));
		}else
		{
			//add --  or -- --
 			//	  	|
			if((x = get(state,j))==0)
				ret = 1 + min(search(i, j+1, must, state, next)
							 ,search(i, j+1, 0, state, set(next,j,must)));
			//complete the	  |
			//			 	--
			else if(x == must)
				ret = search(i, j+1, 0, state, next);
		}
		return ret;
	}
	//dynamic programming function all.
	public int solve(int row, int state) {
		if (row == n)
			return state == 0 ? 0 : 1023;
		if(dp[row][state]==-1) dp[row][state] = search(row, 0, 0, state, 0);;
		return dp[row][state];
	}

	public void run() {
		Scanner in = new Scanner(System.in);
		while (true) {
			n = in.nextInt();
			m = in.nextInt();
			if(n==0 && m==0)return;
			arr = new int[n][m];
			for (int i = 0; i < arr.length; i++)
				for (int j = 0; j < arr[i].length; j++)
					arr[i][j] = (char) (in.next().charAt(0) - '0');

			for(int i = 0;i<arr.length;i++){
				for(int j = 0;j<arr[i].length;j++){
					if(arr[i][j]==1)arr[i][j]=-1;
					if(arr[i][j]==2)arr[i][j]=1;
					if(arr[i][j]==3)arr[i][j]=2;
				}
			}
			for(int i = 0;i<n;i++)
					Arrays.fill(dp[i],0,power[m],-1);
			int ret = solve(0, 0);
			if(ret>=1023)
				System.out.println(0);
			else
				System.out.println(ret);

		}
	}
	public static void main(String[] args){
		(new ManhattanWiring()).run();
	}
}

Update
pure dynamic programming solution is almost twice faster here’s the source code

import java.util.Arrays;
import java.util.Scanner;
import static java.lang.Math.*;

public class ManhattanWiring {
	int[][] arr;
	int n, m;
	int[] power = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683 ,59049,177147,531441};
	int[][][][] dp_ = new int[3][9][9][19683];
	public int get(int a, int i) {
		return (a / power[i]) % 3;
	}

	public int set(int a, int i, int v) {
		return a + ( v - get(a, i) ) * power[i];
	}
	
	//dynamic programming
	public int solve(int i, int j, int must, int state) {
		if(i == n)
			return (state == 0) ? 0 : 1023;
		else if (j == m)
			return must == 0 ? solve(i + 1,0,0,state) : 1023;
		else if(dp_[must][i][j][state]!=-1)return dp_[must][i][j][state];
		int ret = 1023,x = get(state, j);
		if((must!=0 && (arr[i][j-1]==-1||arr[i][j]==-1)) || (get(state,j)!=0 && arr[i][j]==-1))ret = 1023;
		else if(arr[i][j]!=-1 && arr[i][j]!=0){
			if(x!=0 && must!=0)ret =  1023;
			else if(x==0 && must==0)ret = 1 + min(solve(i, j+1, arr[i][j], set(state,j,0)),
											 solve(i,j+1,0,set(state,j,arr[i][j])));
			else if(x!=0 && x==arr[i][j])ret=solve(i, j+1, 0, set(state,j,0));
			else if(must!=0 && must==arr[i][j])ret=solve(i, j+1, 0, set(state,j,0));
			else ret = 1023;
		}
		else if (must == 0) {
			if (x == 0)//add none or add an arc    --
								  	  //          |
				ret = min(
								solve(i, j + 1, 0, set(state,j,0)),
						2 + min(solve(i, j + 1, 1, set(state,j,1)),
							    solve(i, j + 1, 2, set(state,j,2))));
			else
				//add | or add |
				//	  |        --
				ret = 1 + min(solve(i, j+1, must, set(state,j,x))
						     ,solve(i, j+1, x, set(state,j,0)));
		}else
		{
			//add --  or -- --
 			//	  	|
			if((x = get(state,j))==0)
				ret = 1 + min(solve(i, j+1, must, set(state,j,0))
							 ,solve(i, j+1, 0, set(state,j,must)));
			//complete the	  |
			//			 	--
			else if(x == must)
				ret = solve(i, j+1, 0, set(state,j,0));
		}
		return dp_[must][i][j][state]=ret;
	}

	public void run() {
		Scanner in = new Scanner(System.in);
		while (true) {
			n = in.nextInt();
			m = in.nextInt();
			if(n==0 && m==0)return;
			arr = new int[n][m];
			for (int i = 0; i < arr.length; i++)
				for (int j = 0; j < arr[i].length; j++)
					arr[i][j] = (char) (in.next().charAt(0) - '0');
			
			for(int i = 0;i<arr.length;i++){
				for(int j = 0;j<arr[i].length;j++){
					if(arr[i][j]==1)arr[i][j]=-1;
					if(arr[i][j]==2)arr[i][j]=1;
					if(arr[i][j]==3)arr[i][j]=2;
				}
			}
			for(int i = 0;i<3;i++)
				for(int a = 0;a<n;a++)
					for(int b = 0;b<m;b++)Arrays.fill(dp_[i][a][b],0,power[m],-1);
			int ret = solve(0,0,0,0);
			if(ret>=1023)
				System.out.println(0);
			else 
				System.out.println(ret);

		}
	}
	public static void main(String[] args){
		(new ManhattanWiring()).run();
	}
}

Posted April 25, 2013 by epicrado in Dynamic programming

UVA – 11534 – Say Goodbye to Tic-Tac-Toe   Leave a comment


grundy numbers + dynamic programming
you can read about grundy numbers here.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <set>
using namespace std;
char game[105];
int n;
int dp[3][3][105];
int grundy(int p, int len, int nx) {
	if (len == 0)
		return dp[p][nx][len] = 0;
	else if (dp[p][nx][len] != -1)
		return dp[p][nx][len];
	set<int> s;
	for (int k = 1; k <= len; k++) {
		if (!((k == 1 && p == 1) || (k == len && nx == 1)))
			s.insert(grundy(p, k - 1, 1) ^ grundy(1, len - k, nx));
		if (!((k == 1 && p == 2) || (k == len && nx == 2)))
			s.insert(grundy(p, k - 1, 2) ^ grundy(2, len - k, nx));
	}
	dp[p][nx][len] = 0;
	while (s.count(dp[p][nx][len]))
		dp[p][nx][len]++;
	return dp[p][nx][len];
}
int main(int argc, char **argv) {
	int tc;
	scanf("%d", &tc);
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			for (int k = 0; k < 105; k++)
				dp[i][j][k] = -1;
	getchar();
	while (tc--) {
		gets(game);
		n = strlen(game);
		int pl = 0;
		for (int i = 0; i < n; i++)
			if (game[i] != '.')
				pl ^= 1;
		int res = 0;
		for (int i = 0; i < n; i++) {
			if (game[i] != '.')
				continue;
			int pr = (i - 1 < 0) ? 0 : (game[i - 1] == 'X') ? 1 : 2;
			int j = i;
			while (j < n && game[j] == '.')
				j++;
			int nx = (j == n) ? 0 : (game[j] == 'X') ? 1 : 2;
			int len = j - i;
			res ^= grundy(pr, len, nx);
			i = j;
		}
		if ((!pl && res) || (pl && !res))
			puts("Possible.");
		else
			puts("Impossible.");
	}
	return 0;
}

Posted November 24, 2012 by epicrado in Dynamic programming, Mathematics

UVA – 1062 – Containers   Leave a comment


Minimum path cover on a dag, I believe it can be also solved using a greedy algorithm.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class UVa1062 {
	boolean[] v;
	int[] pair;
	LinkedList<Integer>[] G;

	public int path(int i) {
		if (v[i])
			return 0;
		v[i] = true;
		for (int j : G[i])
			if (pair[j] == -1 || path(pair[j]) != 0) {
				pair[j] = i;
				return 1;
			}
		return 0;
	}

	public int match() {
		int match = 0;
		Arrays.fill(pair, -1);
		for (int i = 0; i < G.length; i++) {
			Arrays.fill(v, false);
			match += path(i);
		}
		return match;
	}

	public void run() throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		v = new boolean[1005];
		pair = new int[1005];
		int cc = 1;
		while (true) {
			char[] arr = in.readLine().trim().toCharArray();
			if (arr.length == 3 && arr[0] == 'e' && arr[1] == 'n'
					&& arr[2] == 'd')
				return;
			G = new LinkedList[arr.length];
			for (int i = 0; i < G.length; i++) {
				G[i] = new LinkedList<Integer>();
				for (int j = i + 1; j < arr.length; j++)
					if (arr[j] <= arr[i])
						G[i].add(j);

			}
			System.out.printf("Case %d: %d\n", cc++, arr.length - match());
		}
	}

	public static void main(String[] args) throws Exception {
		(new UVa1062()).run();
	}
}

Posted November 15, 2012 by epicrado in DAG, Graphs