Archive for the ‘Recursive Backtracking’ Category

UVA – 165 – Stamps   Leave a comment


Simple backtracking + dp to find n for a given coin domination

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

public class Stamps {
	static int optimal;
	static Stack<Integer> best;

	public static int func(Stack<Integer> s, int h) {
		int max = s.peek() * h + 1;
		int[] count = new int[max];
		Arrays.fill(count, Integer.MAX_VALUE);
		count[0] = 0;
		for (int i = 0; i < max; i++) {
			if (count[i] > h) {
				return i - 1;
			}
			for (int j : s)
				if (i + j < max)
					count[i + j] = Math.min(count[i + j], 1 + count[i]);
		}
		return max - 1;
	}

	public static void n(int h, int k, Stack<Integer> s) {
		if (k == 0) {
			int current = func(s, h);
			if (current > optimal) {
				optimal = current;
				best = (Stack<Integer>) s.clone();
			}

		} else {
			int current = func(s, h);
			for (int j = s.peek() + 1; j <= current + 1; j++) {
				s.push(j);
				n(h, k - 1, s);
				s.pop();
			}
		}
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		while (true) {
			int h = in.nextInt(), k = in.nextInt();
			if (h == 0 && k == 0)
				break;
			Stack<Integer> S = new Stack<Integer>();
			S.push(1);
			optimal = 1;
			n(h, k - 1, S);
			for (int i : best)
				System.out.printf("%3d", i);
			System.out.printf(" ->%3d\n", optimal);

		}
	}

	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());
		}
	}
}

Advertisements

Posted June 20, 2012 by epicrado in Recursive Backtracking

UVA – 193 – Graph Coloring   3 comments


Simple back tracking without any pruning passes in 0.36 sec

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class GraphColoring {
	static int min;
	static int n;
	static boolean[][] g;
	static int[] col;
	static int[] chosen;

	public static void color(int i, int wc) {
		if (i > n) {
			if (wc < min) {
				min = wc;
				chosen = col.clone();
			}
		} else {
			boolean black = true;
			for (int j = 0; j < g.length; j++)
				if (g[i][j])
					black = black && col[j] != 2;
			if (black) {
				col[i] = 2;
				color(i + 1, wc);
				col[i] = 0;
			}
			col[i] = 1;
			color(i + 1, wc + 1);
			col[i] = 0;
		}
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			n = in.nextInt();
			int m = in.nextInt();
			g = new boolean[n + 1][n + 1];
			for (int i = 0; i < m; i++) {
				int a = in.nextInt();
				int b = in.nextInt();
				g[a][b] = g[b][a] = true;
			}
			col = new int[n + 1];
			min = n;
			color(1, 0);
			System.out.println(n - min);
			int cnt = 0;
			for (int i = 1; i < chosen.length; i++) {
				if (chosen[i] == 2) {
					if (cnt != 0)
						System.out.print(" " + i);
					else
						System.out.print(i);
					cnt++;
				}
			}
			System.out.println();
		}
	}

	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());
		}
	}
}

Posted June 20, 2012 by epicrado in Recursive Backtracking

UVA – 11742 – Social Constraints   Leave a comment


#include <stdio.h>
#include <algorithm>
using namespace std;
int abs(int a){return (a<0)?-a:a;}
int main()
{
	int n,m,a[20],b[20],con[20],perm[8],pos[8],i;
	while(1)
	{
		scanf("%d %d",&n,&m);
		if(n==0 && m==0)
			break;
		for(i=0;i<m;i++)
			scanf("%d %d %d",a+i,b+i,con+i);
		for(i=0;i<n;i++)
			perm[i]=i;
		int count = 0;
		int incr;
		do
		{
			for(i=0;i<n;i++)
				pos[perm[i]]=i;
			incr = 1;
			for(i=0;i<m && incr;i++)
				if((con[i]>0 && abs(pos[a[i]]-pos[b[i]])>con[i]) || (con[i]<0 && abs(pos[a[i]]-pos[b[i]])<-con[i]))
					incr = 0;
			count+=incr;
		}while(next_permutation(perm,perm+n));
		printf("%d\n",count);
	}
	return 0;
}

Posted April 27, 2012 by epicrado in Iterative, Recursive Backtracking

UVA – 10475 – Help the Leaders   Leave a comment


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

public class HelpTheLeaders {
	static class Str implements Comparable<Str> {
		String s;

		public Str(String s) {
			this.s = s;
		}

		public String toString() {
			return s;
		}

		@Override
		public int compareTo(Str o) {
			if (s.length() > o.s.length()
					|| (s.length() == o.s.length() && s.compareTo(o.s) < 0))
				return -1;
			if (s.compareTo(o.s) == 0)
				return 0;
			return 1;
		}
	}

	static class StrGrp implements Comparable<StrGrp> {
		Str[] grp;

		public StrGrp(Str[] g) {
			grp = g;
		}

		@Override
		public int compareTo(StrGrp o) {
			int k;
			for (int i = 0; i < grp.length; i++)
				if ((k = grp[i].compareTo(o.grp[i])) != 0)
					return k;
			return 0;
		}

		public String toString() {
			StringBuilder out = new StringBuilder();
			for (int i = 0; i < grp.length - 1; i++) {
				out.append(grp[i].s);
				out.append(' ');
			}
			out.append(grp[grp.length - 1].s);
			return out.toString();
		}
	}

	public static int count(int n) {
		int c = 0;
		while (n > 0) {
			c += n & 1;
			n >>= 1;
		}
		return c;
	}

	public static void main(String[] args) throws NumberFormatException,
			IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(in.readLine());
		int cc = 1;
		while (tc-- > 0) {
			String[] sp = in.readLine().split(" ");
			int n = Integer.parseInt(sp[0]);
			int m = Integer.parseInt(sp[1]);
			int b = Integer.parseInt(sp[2]);
			String[] inp = new String[n];
			int[] bad = new int[n];
			for (int i = 0; i < n; i++)
				inp[i] = in.readLine().toUpperCase();
			Arrays.sort(inp);
			for (int i = 0; i < m; i++) {
				String[] sp2 = in.readLine().split(" ");
				int x = Arrays.binarySearch(inp, sp2[0].toUpperCase());
				int y = Arrays.binarySearch(inp, sp2[1].toUpperCase());
				bad[x] |= (1 << y);
				bad[y] |= (1 << x);
			}
			PriorityQueue<StrGrp> Q = new PriorityQueue<StrGrp>();
			for (int i = 0; i < 1 << n; i++) {
				if (count(i) == b) {
					boolean ok = true;
					for (int j = 0; j < bad.length && ok; j++) {
						if (((i >> j) & 1) != 0) {
							int k = i & bad[j];
							if (k != 0)
								ok = false;
						}
					}
					if (ok) {

						Str[] arr = new Str[b];
						int t = 0;
						for (int j = 0; j < n; j++) {
							if (((i >> j) & 1) != 0)
								arr[t++] = new Str(inp[j]);
						}
						Arrays.sort(arr);
						Q.add(new StrGrp(arr));
					}
				}
			}
			System.out.println("Set " + (cc++) + ":");
			while (!Q.isEmpty())
				System.out.println(Q.remove());
			System.out.println();

		}
	}
}

UVA – 10344 – 23 out of 5   1 comment


#include <stdio.h>
int nums[5];
char inp[100];
int allperm[120][5];
int gen[5];
int perm;
int current = 0;
char* resstr[2]={"Impossible","Possible"};

char can(int i,int res)
{
	if(i==5)
		return res==23;
	else
		return can(i+1,res*nums[allperm[perm][i]])||can(i+1,res+nums[allperm[perm][i]])||can(i+1,res-nums[allperm[perm][i]]);
}
void generate(int j,int v)
{
	int i;
	if(j==5)
	{
		for(i=0;i<5;i++)
			allperm[current][i]=gen[i];
		current++;
	}
	else
	{
		for(i=0;i<5;i++)
			if(!(v&(1<<i)))
			{
				gen[j]=i;
				generate(j+1,v|(1<<i));
			}
	}
}
int main()
{
	generate(0,0);
	scanf("%d %d %d %d %d",nums,nums+1,nums+2,nums+3,nums+4);
	while(nums[0]||nums[1]||nums[2]||nums[3]||nums[4])
	{
		char res = 0;
		for(perm=0;perm<120&&!res;perm++)
			res|=can(1,nums[allperm[perm][0]]);
		puts(resstr[res]);
		scanf("%d %d %d %d %d",nums,nums+1,nums+2,nums+3,nums+4);
	}
	return 0;
}

Posted October 2, 2011 by epicrado in Recursive Backtracking

UVA – 208 – Firetruck   1 comment


Regular backtracking but the idea here is to prune the branches which won’t lead us to the destination.

so simply run dfs from destination and mark all nodes that can lead us there.

And while backtracking if we’re a node that is not marked then we do nothing

import java.util.Scanner;

public class fire {
	static boolean[][] matrix;
	static boolean[] canVisit;
	static int counter;

	public static void dfs(int n, int max) {
		canVisit[n] = true;
		for (int i = 1; i <= max; i++)
			if (matrix[n][i] && !canVisit[i])
				dfs(i, max);
	}

	public static void generatePath(String path, int s, int e, int v, int max) {
		if (canVisit[s]) {
			if (s == e) {
				counter++;
				System.out.println(path);
			}
			for (int i = 1; i <= max; i++)
				if ((v & (1 << i)) == 0 && matrix[s][i])
					generatePath(path + " " + i, i, e, v | (1 << i), max);
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int index = 1;
		while (in.hasNext()) {
			int n = in.nextInt();
			int max = 0;
			matrix = new boolean[22][22];
			canVisit = new boolean[22];
			counter = 0;
			int e1 = in.nextInt();
			int e2 = in.nextInt();
			while (e1 != 0 || e2 != 0) {
				matrix[e1][e2] = matrix[e2][e1] = true;
				e1 = in.nextInt();
				e2 = in.nextInt();
				max = Math.max(Math.max(e1, e2), max);
			}
			dfs(n, max);
			System.out.println("CASE " + (index++) + ":");
			generatePath("1", 1, n, 2, max);
			System.out
					.println("There are " + counter
							+ " routes from the firestation to streetcorner "
							+ n + ".");
		}
	}
}

Posted September 20, 2011 by epicrado in Depth first search, Recursive Backtracking

UVA – 11085 – Back to the 8-Queens   Leave a comment


#include <stdio.h>
#define minimum(a,b) (a<b)?a:b
int d1,d2,row;
int pos[9];
int solve(int col)
{
	if(col==9)return 0;
	int r;
	int min = 8;
	for(r=1;r<=8;r++)
		if(!(d1&(1<<(r+col)))&&!(d2&(1<<(r-col+9)))&&!(row&(1<<r)))
		{
			d1^=(1<<(r+col));
			d2^=(1<<(r-col+9));
			row^=(1<<r);
			min = minimum((r!=pos[col])+solve(col+1),min);
			d1^=(1<<(r+col));
			d2^=(1<<(r-col+9));
			row^=(1<<r);
		}
	return min;
}
int main()
{
	char buffer[100];
	int i,j,c=1;
	while(gets(buffer))
	{
		for(j=0;j<9;j++)pos[j]=0;
		j = 1;
		for(i=0;buffer[i];i++)
			if(buffer[i]==' ')
				j++;
			else
				pos[j]=pos[j]*10 + buffer[i]-'0';
		printf("Case %d: %d\n",c++,solve(1));
	}
	return 0;
}

Posted September 13, 2011 by epicrado in Recursive Backtracking