Archive for the ‘Dynamic programming’ Category

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 – 11468 – Substring   Leave a comment


Dynamic Programming + Aho Corasik String matching

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

public class UVa11468 {
	class AhoCorasik {
		Node root;

		class Node {
			Node next[];
			Node fail;
			boolean flag;// true iff current prefix matched ANY string in the
							// set
			int label;

			public Node() {
				next = new Node[128];
			}
		}

		AhoCorasik(char[][] patterns) {
			root = new Node();
			for (int i = 0; i < patterns.length; i++)
				TrieInsert(patterns[i]);
			Queue<Node> Q = new ArrayDeque<Node>();
			Queue<Character> Q2 = new ArrayDeque<Character>();
			root.fail = root;
			Q.add(root);
			while (!Q.isEmpty()) {
				Node current = Q.poll();
				for (int i = 0; i < current.next.length; i++)
					if (current.next[i] != null) {
						Q.add(current.next[i]);
						Q.add(current);
						Q2.add((char) i);
					}
				if (current == root)
					continue;
				Node parent = Q.poll();
				Character last = Q2.poll();
				Node cfail = parent.fail;
				while (cfail != root && cfail.next[last] == null)
					cfail = cfail.fail;
				current.fail = cfail.next[last];
				if (current.fail == null || current.fail == current)
					current.fail = root;
				current.flag = current.flag || current.fail.flag;
			}
		}

		void TrieInsert(char[] pattern) {
			Node current = root;
			for (int i = 0; i < pattern.length; i++) {
				if (current.next[pattern[i]] == null)
					current.next[pattern[i]] = new Node();
				current = current.next[pattern[i]];
			}
			current.flag = true;
		}

		Node next(Node current, char c) {
			while (current.next[c] == null && current != root)
				current = current.fail;
			return current.next[c] == null ? root : current.next[c];
		}
	}

	double[][] dp = new double[105][20 * 25];
	AhoCorasik.Node[] nodes = new AhoCorasik.Node[20 * 25];
	double[] prob = new double[128];
	char[] chr = new char[128];
	int all;
	AhoCorasik tree;

	public double f(int l, int state) {
		if (nodes[state].flag)
			return 0.0;
		else if (l == 0)
			return 1;
		else if (dp[l][state] != -1)
			return dp[l][state];
		else {
			double res = 0;
			for (int i = 0; i < all; i++)
				res += prob[i]
						* f(l - 1, tree.next(nodes[state], chr[i]).label);
			return dp[l][state] = res;
		}
	}

	public void run() throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		int cc = 1;
		while (tc-- > 0) {
			int patterns = in.nextInt();
			char[][] pat = new char[patterns][];
			for (int i = 0; i < pat.length; i++)
				pat[i] = in.next().toCharArray();
			tree = new AhoCorasik(pat);
			Queue<AhoCorasik.Node> Q = new ArrayDeque<AhoCorasik.Node>();
			Q.add(tree.root);
			int top = 0;
			while (!Q.isEmpty()) {
				AhoCorasik.Node cur = Q.poll();
				cur.label = top;
				nodes[top] = cur;
				top++;
				for (int j = 0; j < cur.next.length; j++)
					if (cur.next[j] != null)
						Q.add(cur.next[j]);
			}
			top = 0;
			all = in.nextInt();
			for (top = 0; top < all; top++) {
				char c = in.next().charAt(0);
				double d = Double.parseDouble(in.next());
				chr[top] = c;
				prob[top] = d;
			}
			int l = in.nextInt();
			for (int i = 0; i <= l; i++)
				Arrays.fill(dp[i], -1);
			System.out.printf("Case #%d: %.6f\n", cc++, f(l, 0));
		}
	}

	static class InputReader {
		private BufferedReader reader;
		private StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}
	}

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

Posted November 15, 2012 by epicrado in Dynamic programming, String Processing

Spoj – MREPLBRC   Leave a comment


easy with dp on substrings.

#include <stdio.h>
#define MOD 100000
typedef long long ll;
ll dp[205][205];
char str[205];
ll refresh(ll k) {
	return k % MOD + ((k >= MOD) ? MOD : 0);
}
bool pair(char a, char b) {
	return ((a == '(' || a == '[' || a == '{') && b == '?')
			|| (a == '?' && (b == ']' || b == '}' || b == ')'))
			|| (a == '(' && b == ')') || (a == '{' && b == '}')
			|| (a == '[' && b == ']');

}
ll ways(int a, int b) {
	if (str[a] == str[b] && str[a] == '?')
		return 3;
	return pair(str[a], str[b]);
}
ll f(int l, int r) {
	if (l > r)
		return 1;
	else if (dp[l][r] != -1)
		return dp[l][r];
	ll res = 0;
	for (int k = l + 1; k <= r; k++) {
		res += ways(l, k) * f(l + 1, k - 1) * f(k + 1, r);
		res = refresh(res);
	}
	return dp[l][r] = res;
}

int main() {
	int n;
	char out[7];
	scanf("%d", &n);
	scanf("%s", str);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			dp[i][j] = -1;
	out[6] = 0;
	int top = 5;
	ll result = f(0, n - 1);
	do {
		out[top--] = result % 10 + '0';
		result /= 10;
	} while (result > 0);
	top++;
	while (top < 1)
		top++;
	puts(out + top);
	return 0;
}

Posted October 24, 2012 by epicrado in Dynamic programming

UVA – 481 – What Goes Up   1 comment


O(nlogk) LIS 😉

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;
import java.util.TreeSet;

public class UVa481 {

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		LinkedList<Integer> lst = new LinkedList<Integer>();
		while (true) {
			String s = in.readLine();
			if (s == null)
				break;
			s = s.trim();
			if (s.length() == 0)
				continue;
			int n = Integer.parseInt(s);
			lst.add(n);
		}
		int[] arr = new int[lst.size()];
		int top = 0;
		for (int i : lst)
			arr[top++] = i;
		int[] best = new int[arr.length];
		int[] index = new int[arr.length];
		int[] parent = new int[arr.length];
		Arrays.fill(best, Integer.MAX_VALUE);
		for (int i = 0; i < arr.length; i++) {
			int l = 0;
			int len = arr.length - 1;
			while (len > 0) {
				len /= 2;
				if (best[l + len] < arr[i])
					l += len + 1;
			}
			if (best[l] > arr[i]) {
				index[l] = i;
				best[l] = arr[i];
				parent[i] = (l - 1 < 0) ? -1 : index[l - 1];
			}
		}
		Stack<Integer> rev = new Stack<Integer>();
		for (int i = arr.length - 1; i >= 0; i--) {
			if (best[i] != Integer.MAX_VALUE) {
				int ind = index[i];
				while (ind != -1) {
					rev.push(arr[ind]);
					ind = parent[ind];
				}
				break;
			}
		}
		System.out.println(rev.size());
		System.out.println("-");
		while (!rev.isEmpty())
			System.out.println(rev.pop());

	}
}

Posted August 29, 2012 by epicrado in Dynamic programming

UVA – 12274 – Jumping monkey   Leave a comment


#include <stdio.h>
int q[1<<22];
int lg2[1<<22];
int g[22];
char v[1<<21];
int next[1<<21];
int parent[1<<21];
int choice[1<<21];
int out[1001];
int h,t;
int isEmpty()
{
	return (t-h+(1<<22))%(1<<22)==0;
}
void enq(int n)
{
	q[t]=n;
	t=(t+1)%(1<<22);
}
void clear()
{
	h = t = 0;
}
int deq()
{
	int res = q[h];
	h = (h+1)%(1<<22);
	return res;
}
int main()
{
	int n,m,i,j,k,l;
	for(i=0;i<22;i++)
		lg2[1<<i]=i;
	while(1)
	{
		scanf("%d %d",&n,&m);
		
		if(!n&&!m)break;
		
		for(i = 0;i<n;i++)g[i]=0;
		
		for(i = 0;i<m;i++)
		{
			scanf("%d %d",&k,&l);
			g[k]|=(1<<l);
			g[l]|=(1<<k);
		}
		
		for(i = 0;i<1<<n;i++)
			next[i]=v[i]=0;
		
		for(i = 1;i<1<<n;i++)
			next[i]=next[i-(i&-i)]|g[lg2[i&-i]];
		
		clear();
		
		enq((1<<n)-1);
		v[(1<<n)-1]=1;
		int f = 0;
		while(!isEmpty())
		{
			int current = deq();
			if(!current)
			{
				int top = 0;
				while(current!=(1<<n)-1)
				{
					out[top++]=choice[current];
					current = parent[current];
				}
				printf("%d:",top);
				--top;
				while(top>=0)
					printf(" %d",out[top--]);
				putchar('\n');
				f = 1;
				break;
			}
			int mask = current;
			while(mask!=0)
			{
				int nx = next[current^(mask&-mask)];
				if(!v[nx])
				{
					v[nx]=1;
					enq(nx);
					parent[nx]=current;
					choice[nx]=lg2[(mask&-mask)];
				}
				mask-=mask&-mask;
			}
		}
		if(!f)
			puts("Impossible");
	}
	return 0;
}

Posted July 29, 2012 by epicrado in Breadth first search, Dynamic programming

UVA – 12276 – Assembly line   Leave a comment


Like matrix chain multiplication however the state differs a bit since there may be multiple resulting characters from the same interval so we need to choose the optimal

#include <stdio.h>
#include <string.h>
int dp[201][201][26];
int calc[201][201];
int symb;
char s[201];
int comb[26][26];
char next[26][26];
char v[26];
int min(int a,int b)
{
	return (a<b)?a:b;
}
void go(int l,int r)
{
	if(calc[l][r])return;
	else if(l==r)
	{
		dp[l][r][s[l]]=0;
		calc[l][r]=1;
		return;
	}
	else
	{
		int i,j,k;
		for(i = l;i<r;i++)
		{
			go(l,i);
			go(i+1,r);
			for(j=0;j<symb;j++)
				for(k=0;k<symb;k++)
					dp[l][r][next[j][k]]=min(dp[l][r][next[j][k]],dp[l][i][v[j]]+dp[i+1][r][v[k]]+comb[j][k]);
		}
		calc[l][r]=1;
		return;
	}
}
int main()
{	
	int i,j,k,l,m;
	int cc = 0;
	while(1)
	{
		scanf("%d",&symb);
		if(!symb)break;
		if(cc++)putchar('\n');
		getchar();
		for(i = 0;i<symb;i++)
		{
			v[i]=getchar();
			getchar();
			v[i]-='a';
		}
		for(i = 0;i<symb;i++)
		{
			for(j = 0;j<symb;j++)
			{
				int x;
				char y;
				scanf("%d-%c",&x,&y);
				getchar();
				comb[i][j]=x;
				next[i][j]=y-'a';
			}
		}
		int q;
		scanf("%d",&q);
		getchar();
		for(i = 0;i<q;i++)
		{
			gets(s);
			k=strlen(s);
			for(j=0;j<k;j++)s[j]-='a';
			for(j=0;j<k;j++)
				for(l=0;l<k;l++)
				{
					calc[j][l]=0;
					for(m=0;m<26;m++)
						dp[j][l][m]=(int)1e8;
				}
			go(0,k-1);
			int best = 0;
			for(j =1;j<symb;j++)
				if(dp[0][k-1][v[j]]<dp[0][k-1][v[best]])
					best = j;
			printf("%d-%c\n",dp[0][k-1][v[best]],(char)(v[best]+'a'));
		}
	}
	return 0;
}

Posted July 29, 2012 by epicrado in Dynamic programming