Archive for the ‘Problem solving paradigms’ Category

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 – 11262 – Weird Fence   Leave a comment


Basic idea is binary search on the max allowed distance between two poles and build a graph using this distance, and do maximum matching to see where the binary search should go.

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

public class WeirdFence {
	public static int bfs(int s, int t, int[][] res, int[] parent) {
		Queue<Integer> Q = new LinkedList<Integer>();
		Q.add(s);
		Q.add(Integer.MAX_VALUE);
		while (!Q.isEmpty()) {
			int n = Q.poll();
			int flow = Q.poll();
			if (n == t)
				return flow;
			for (int j = 0; j < res[n].length; j++) {
				if (res[n][j] != 0 && parent[j] == -1) {
					Q.add(j);
					Q.add(Math.min(flow, res[n][j]));
					parent[j] = n;
				}
			}
		}
		return 0;
	}

	public static void augmentPath(int s, int t, int flow, int[] parent,
			int[][] res) {
		int cur = t;
		while (cur != s) {
			res[parent[cur]][cur] -= flow;
			res[cur][parent[cur]] += flow;
			cur = parent[cur];
		}
	}

	public static int maxFlow(int s, int t, int[][] res) {
		int[] parent = new int[res.length];
		Arrays.fill(parent, -1);
		int flow, maxflow = 0;
		while ((flow = bfs(s, t, res, parent)) != 0) {
			maxflow += flow;
			augmentPath(s, t, flow, parent, res);
			Arrays.fill(parent, -1);
		}
		return maxflow;
	}

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int n = in.nextInt();
			int k = in.nextInt();
			int[] x = new int[n];
			int[] y = new int[n];
			boolean[] col = new boolean[n];
			for (int i = 0; i < n; i++) {
				x[i] = in.nextInt();
				y[i] = in.nextInt();
				String s = in.next();
				col[i] = s.equals("red");
			}

			int l = 0;
			int h = 3000;
			boolean ok = false;
			while (h > l) {
				int mid = (l + h) / 2;
				int[][] g = new int[n + 2][n + 2];
				for (int i = 0; i < n; i++) {
					if (col[i])
						g[0][i + 1] = 1;
					else
						g[i + 1][n+1] = 1;
				}
				for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						if (col[i]
								&& !col[j]
								&& (x[i] - x[j]) * (x[i] - x[j])
										+ (y[i] - y[j]) * (y[i] - y[j]) <= mid
										* mid) {
							g[i + 1][j + 1] = 1;
						}
					}
				}
				int max = maxFlow(0, n+1, g);
				if (max >= k) {
					h = mid;
					ok = true;
				} else
					l = mid + 1;
			}
			if (ok)
				System.out.println(h);
			else
				System.out.println("Impossible");
		}
	}

	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 13, 2012 by epicrado in Binary search, Graphs, Maxflow

UVA – 714 – Copying Books   Leave a comment


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

public class CopyingBooks {

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int books = in.nextInt();
			int writers = in.nextInt();
			int[] b = new int[books];
			for (int i = 0; i < b.length; i++)
				b[i] = in.nextInt();
			long high = 1L << 33;
			long low = 1;
			while (high > low) {
				long mid = (high + low) / 2;
				long accu = 0;
				int j = 0;
				for (int i = 0; i < books && j < writers; i++) {
					while (b[i] + accu > mid && j < writers) {
						accu = 0;
						j++;
					}
					accu += b[i];
				}
				if (j >= writers)
					low = mid + 1;
				else
					high = mid;
			}
			long copy = high;
			int[] start = new int[writers];
			Arrays.fill(start, -1);
			long accu = 0;
			int current = writers - 1;
			for (int i = books - 1; i >= 0; i--) {
				if (accu + b[i] > copy) {
					start[current] = i + 1;
					accu = 0;
					current--;
				}
				accu += b[i];
			}
			start[current] = 0;
			int top = 0;
			for (int i = 0; i < start.length; i++)
				if (start[i] == -1)
					start[i] = top++;
			for (int i = 0; i < start.length - 1; i++) {
				if (start[i] >= start[i + 1])
					start[i + 1] += (start[i] - start[i + 1] + 1);
			}
			StringBuilder out = new StringBuilder();
			for (int i = 0; i < start.length; i++) {
				int next = books;
				if (i + 1 < start.length)
					next = start[i + 1];
				for (int j = start[i]; j < next; j++) {
					out.append(b[j] + " ");
				}
				out.append("/ ");
			}
			out.deleteCharAt(out.length() - 1);
			out.deleteCharAt(out.length() - 1);
			out.deleteCharAt(out.length() - 1);
			System.out.println(out);
		}
	}

	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 May 25, 2012 by epicrado in Binary search

UVA – 10041 – Vito’s Family   Leave a comment


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

public class VitosFamily {

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {
			int[] a = new int[in.nextInt()];
			for (int i = 0; i < a.length; i++)
				a[i] = in.nextInt();
			int min = 500 * 30000;
			for (int i = 0; i < a.length; i++) {
				int sum = 0;
				for (int j = 0; j < a.length; j++)
					sum += Math.abs(a[i] - a[j]);
				min = Math.min(min, sum);
			}
			System.out.println(min);
		}

	}

	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 April 30, 2012 by epicrado in Iterative

UVA – 10102 – The path in the colored field   Leave a comment


import java.io.*;
import java.util.*;

public class ThePathColoredField {
	public static int abs(int a) {
		return (a < 0) ? -a : a;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		while (true) {
			String s = in.readLine();
			if (s == null)
				break;
			int m = Integer.parseInt(s);
			char[][] a = new char[m][];
			for (int i = 0; i < a.length; i++)
				a[i] = in.readLine().toCharArray();
			int maximin = 0;
			for (int i = 0; i < m; i++)
				for (int j = 0; j < m; j++) {
					if (a[i][j] == '1') {
						int min = 2 * m;
						for (int k = 0; k < m; k++)
							for (int l = 0; l < m; l++)
								if (a[k][l] == '3'
										&& abs(k - i) + abs(l - j) < min)
									min = abs(k - i) + abs(l - j);
						if (min > maximin)
							maximin = min;
					}
				}
			System.out.println(maximin);
		}
	}
}

Posted April 30, 2012 by epicrado in Iterative

UVA – 11059 – Maximum Product   Leave a comment


import java.util.*;

public class MaximumProduct {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int cc = 1;
		while (in.hasNext()) {
			int n = in.nextInt();
			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				a[i] = in.nextInt();
			}
			long max = 0;
			for (int i = 0; i < a.length; i++)
				for (int j = i; j < a.length; j++) {
					long cur = 1;
					for (int k = i; k <= j; k++)
						cur = cur * a[k];
					max = Math.max(max, cur);
				}
			System.out.printf("Case #%d: The maximum product is %d.\n\n", cc++,
					max);
		}
	}
}

Posted April 27, 2012 by epicrado in Iterative

UVA – 10365 – Blocks   Leave a comment


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

public class Blocks {

	public static void main(String[] args) throws Exception {
		InputReader in = new InputReader(System.in);
		int tc = in.nextInt();
		while (tc-- > 0) {

			int v = in.nextInt();
			int min = Integer.MAX_VALUE;
			for (int i = 1; i <= v; i++)
				if (v % i == 0)
					for (int j = 1; j <= v / i; j++)
						if ((v / i) % j == 0) {
							int area = i * j + v / i + v / j;
							area <<= 1;
							min = Math.min(min, area);
						}
			System.out.println(min);
		}
	}

	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 April 27, 2012 by epicrado in Iterative