Archive for the ‘Data structures and libraries’ Category

UVA – 11297 – Census   Leave a comment


A 2D Segment tree would finish pretty fast,however M Segment trees also should pass the time limit.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Census {
	public static int indexOf(int i, int l, int u, int tind) {
		if (l == u)
			return tind;
		int mid = (l + u) >> 1;
		if (i <= mid)
			return indexOf(i, l, mid, (tind << 1) + 1);
		else
			return indexOf(i, mid + 1, u, (tind << 1) + 2);
	}

	public static void update(int i, int val, int[] tree, int len, int q) {
		int tar = indexOf(i, 0, len - 1, 0);
		tree[tar] = val;
		do {
			tar = (tar - 1) >> 1;
			if (q == 0)
				tree[tar] = Math
						.max(tree[(tar << 1) + 1], tree[(tar << 1) + 2]);
			else
				tree[tar] = Math
						.min(tree[(tar << 1) + 1], tree[(tar << 1) + 2]);
		} while (tar > 0);
	}

	public static int query(int i, int j, int len, int[] tree, int q) {
		return query(i, j, 0, 0, len - 1, tree, q);
	}

	public static int query(int i, int j, int tind, int ti, int tj, int[] tree,
			int q) {
		if (i == ti && j == tj)
			return tree[tind];
		int mid = (ti + tj) >> 1;
		if (j <= mid)
			return query(i, j, (tind << 1) + 1, ti, mid, tree, q);
		if (i > mid)
			return query(i, j, (tind << 1) + 2, mid + 1, tj, tree, q);
		else {
			if (q == 0)
				return Math
						.max(query(i, mid, (tind << 1) + 1, ti, mid, tree, q),
								query(mid + 1, j, (tind << 1) + 2, mid + 1, tj,
										tree, q));
			else
				return Math
						.min(query(i, mid, (tind << 1) + 1, ti, mid, tree, q),
								query(mid + 1, j, (tind << 1) + 2, mid + 1, tj,
										tree, q));
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer strtok = new StringTokenizer(in.readLine());
		int n = Integer.parseInt(strtok.nextToken());
		int m = Integer.parseInt(strtok.nextToken());
		int[][] min = new int[n][4 * m];
		int[][] max = new int[n][4 * m];
		for (int[] a : min)
			Arrays.fill(a, Integer.MAX_VALUE);
		for (int[] a : max)
			Arrays.fill(a, Integer.MIN_VALUE);
		for (int i = 0; i < n; i++) {
			strtok = new StringTokenizer(in.readLine());
			for (int j = 0; j < m; j++) {
				int k = Integer.parseInt(strtok.nextToken());
				update(j, k, max[i], m, 0);
				update(j, k, min[i], m, 1);
			}
		}
		int q = Integer.parseInt(in.readLine());
		while (q-- > 0) {
			String[] arr = in.readLine().split(" ");
			if (arr[0].equals("q")) {
				int a = Integer.parseInt(arr[1]) - 1;
				int b = Integer.parseInt(arr[2]) - 1;
				int c = Integer.parseInt(arr[3]) - 1;
				int d = Integer.parseInt(arr[4]) - 1;
				int r1 = Integer.MIN_VALUE;
				int r2 = Integer.MAX_VALUE;
				for (int i = a; i <= c; i++) {
					r1 = Math.max(r1, query(b, d, m, max[i], 0));
					r2 = Math.min(r2, query(b, d, m, min[i], 1));
				}
				System.out.println(r1 + " " + r2);
			} else {
				int a = Integer.parseInt(arr[1]) - 1;
				int b = Integer.parseInt(arr[2]) - 1;
				int c = Integer.parseInt(arr[3]);
				update(b, c, max[a], m, 0);
				update(b, c, min[a], m, 1);
			}
		}
	}
}

Posted April 19, 2012 by epicrado in Data structures and libraries

UVA – 11235 – Frequent values   Leave a comment


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

public class FrequentValues {
	static int[] freq = new int[200001];
	static int[] start = new int[200001];
	static int[] input = new int[200001];

	static class SegmentTree {
		private int[] tree;
		private int length;

		public SegmentTree(int[] a) {
			length = a.length;
			int len = a.length - 1;
			int pow = 1;
			while (len != 0) {
				pow = len & -len;
				len -= pow;
			}
			if (pow != length)
				pow <<= 1;
			tree = new int[pow | (pow - 1)];
			build(a, 0, 0, a.length - 1);
		}

		public int build(int[] a, int i, int s, int t) {
			if (s == t)
				return tree[i] = a[s];
			else
				return tree[i] = func(build(a, 2 * i + 1, s, (s + t) / 2),
						build(a, 2 * i + 2, (s + t) / 2 + 1, t));
		}

		public int query(int lo, int hi) {
			return query(0, 0, length - 1, lo, hi);
		}

		public int query(int i, int s, int t, int lo, int hi) {
			if (s == lo && t == hi)
				return tree[i];
			int mid = (s + t) / 2;
			if (lo > mid)
				return query(i * 2 + 2, mid + 1, t, lo, hi);
			else if (hi <= mid)
				return query(i * 2 + 1, s, mid, lo, hi);
			else
				return func(query(i * 2 + 1, s, mid, lo, mid),
						query(i * 2 + 2, mid + 1, t, mid + 1, hi));
		}

		public int func(int a, int b) {
			return Math.max(a, b);
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader inp = new BufferedReader(
				new InputStreamReader(System.in));
		StringBuilder out = new StringBuilder();
		while (true) {
			String t = inp.readLine();
			StringTokenizer st = new StringTokenizer(t, " ");
			int n = Integer.parseInt(st.nextToken());
			if (n == 0)
				break;
			int q = Integer.parseInt(st.nextToken());
			Arrays.fill(freq, 0);
			st = new StringTokenizer(inp.readLine(), " ");
			for (int i = 0; i < n; i++) {
				int k = Integer.parseInt(st.nextToken());
				if (freq[k + 100000] == 0) {
					start[k + 100000] = i;
				}
				freq[k + 100000]++;
				input[i] = k;
			}
			SegmentTree s = new SegmentTree(freq);
			for (int i = 0; i < q; i++) {
				st = new StringTokenizer(inp.readLine(), " ");
				int a = Integer.parseInt(st.nextToken()) - 1;
				int b = Integer.parseInt(st.nextToken()) - 1;
				int k1 = input[a];
				int k2 = input[b];
				int optimal;
				if (k1 == k2) {
					optimal = b - a + 1;
				} else {

					int k1Val = (freq[k1 + 100000] == 0) ? 0
							: freq[k1 + 100000] - (a - start[k1 + 100000]);
					int k2Val = (freq[k2 + 100000] == 0) ? 0 : b
							- start[k2 + 100000] + 1;
					optimal = Math.max(k1Val, k2Val);
				}
				k1++;
				k2--;
				if (k1 <= k2) {
					optimal = Math.max(optimal,
							s.query(k1 + 100000, k2 + 100000));
				}
				out.append(optimal + "\n");
			}
		}
		System.out.print(out);
	}
}

Posted January 6, 2012 by epicrado in Data structures and libraries

UVA – 11610 – Reverse Prime   Leave a comment


Solution is based onĀ 
used
1.modified sieve to have a prime factor for each number, see the fsum function which calculates the number of prime factors.
2.Binary Indexed trees to sum factors of reverse primes and delete
3.binary search + additional binary indexed tree to get index of the nth prime after doing deletions
, and binary search to get the index of some prime for deletions.

#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXN 1000005
#define MAXR 78500
int pfactor[MAXN] = { 0 };
int bit[2][MAXR + 5];
int rev[MAXR + 5];
char str[10];
int top = 1;
int query(int b, int i) {
	int ret = 0;
	while (i > 0) {
		ret += bit[b][i];
		i -= i & -i;
	}
	return ret;
}
void update(int b, int i, int val) {
	while (i <= MAXR) {
		bit[b][i] += val;
		i += i & -i;
	}
}
int fsum(int i) {
	int sum = 0;
	int j = 2;
	while (i >= MAXN) {
		while (i % j == 0) {
			i /= j;
			sum++;
		}
		j++;
	}
	while (i > 1) {
		sum++;
		i /= pfactor[i];
	}
	return sum;
}
void precalc() {
	int i, j;
	pfactor[0] = pfactor[1] = -1;
	for (i = 2; i * i < MAXN; i++)
		if (!pfactor[i])
			for (j = i * i; j < MAXN; j += i)
				pfactor[j] = i;
	for (i = 2; i < MAXN; i++)
		pfactor[i] = (pfactor[i]) ? pfactor[i] : i;
}
int reverse(int i) {
	int digits = 7;
	int res = 0;
	while (digits--) {
		res = res * 10 + i % 10;
		i /= 10;
	}
	return res;
}
int bs1(int t) {
	int l = 1, h = top;
	while (h > l) {
		int mid = (l + h) / 2;
		if (rev[mid] >= t)
			h = mid;
		else
			l = mid + 1;
	}
	return h;
}
int bs2(int t) {
	int l = 1;
	int h = top;
	while (h > l) {
		int mid = (l + h) / 2;
		if (query(1, mid) >= t)
			h = mid;
		else
			l = mid + 1;
	}
	return h;
}
int main(int argc, char **argv) {
	precalc();
	int num = 0;
	int cnt = 0;
	for (int i = 0; i < 1000000; i++)
		if (pfactor[i] == i) {
			rev[cnt + 1] = reverse(i);
			cnt++;
		}
	top = cnt;
	sort(rev + 1, rev + cnt + 1);
	for (int i = 0; i < MAXR; i++)
		bit[0][i] = bit[1][i] = 0;
	for (int i = 1; i <= cnt; i++) {
		update(0, i, fsum(rev[i]));
		update(1, i, 1);
	}
	while (scanf("%s %d", str, &num) == 2)
		if (str[0] == 'q')
			printf("%d\n", query(0, bs2(num + 1)));
		else {
			int k = bs1(num);
			update(0, k, -fsum(num));
			update(1, k, -1);
		}
	return 0;
}

Posted September 2, 2011 by epicrado in Data structures and libraries, Prime numbers

UVA – 10226 – Hardwood Species   Leave a comment


#include <map>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
	char buffer[40];
	int cases;
	cin>>cases;
	getchar();
	getchar();
	while(cases--)
	{
		map<string,int> m;
		vector<string> trees;
		int total = 0;
		while(gets(buffer)&&buffer[0])
		{
			string in(buffer);
			if(!m[in])
			{
				m[in]=1;
				trees.push_back(in);
			}
			else
				m[in]++;
			total++;
		}
		sort(trees.begin(),trees.end());
		for(int i =0 ;i<(trees.size());i++)
		{
			cout<<trees[i]<<' ';
			printf("%.4lf\n",m[trees[i]]*100.00/total);
		}
		if(cases)
			putchar('\n');
	}
}

Posted August 28, 2011 by epicrado in Data structures and libraries

UVA – 599 – The Forrest for the Trees   Leave a comment


Solved using union find
#include <stdio.h>
int set[26];
int getParent(int i,int *set)
{
	if(i==set[i])
		return i;
	else
		return (set[i]=getParent(set[i],set));
}
void makeUnion(int a,int b,int* set)
{
	set[getParent(a,set)] = getParent(b,set);
}
int main()
{
	int t,u;
	int cases = 0;
	int i,count[26];
	char letters[100],buffer[100];
	scanf("%d",&cases);
	getchar();
	while(cases--)
	{
		for(i=0;i<26;i++)
		{
			set[i]=i;
			count[i]=0;
		}
		while(gets(buffer)&&buffer[0]!='*')
			makeUnion(buffer[1]-'A',buffer[3]-'A',set);
		gets(letters);
		for(i=0;letters[i];i++)
			if(letters[i]!=',')
				count[getParent(letters[i]-'A',set)]++;
		t = u = 0;
		for(i=0;i<26;i++)
			if(count[i]>1)
				t++;
			else if(count[i]==1)
				u++;
		printf("There are %d tree(s) and %d acorn(s).\n",t,u);
	}
	return 0;
}

Posted August 22, 2011 by epicrado in Graph related, Union find

UVA – 11503 – Virtual Friends   Leave a comment


The trick is to cache the sum to avoid iteration over the disjoint set multiple times

#include <iostream>
#include <map>
#include <string>
#include <stdio.h>
using namespace std;
int getParent(int i, int *set) {
	if (i == set[i])
		return i;
	else
		return (set[i] = getParent(set[i], set));
}
int main() {
	int set[200005];
	int sum[200005];
	int cases;
	scanf("%d\n", &cases);
	while (cases--) {
		int n;
		scanf("%d\n", &n);
		int top = 1;
		for (int i = 1; i <= 2 * n; i++) {
			set[i] = i;
			sum[i] = 1;
		}
		map<string, int> hashmap;
		while (n-- > 0) {
			string s1, s2;
			cin >> s1 >> s2;
			int a, b;
			if (!hashmap[s1]) {
				a = top++;
				hashmap[s1] = a;
			} else
				a = hashmap[s1];
			if (!hashmap[s2]) {
				b = top++;
				hashmap[s2] = b;
			} else
				b = hashmap[s2];
			int p1 = getParent(a, set);
			int p2 = getParent(b, set);
			if (p1 != p2) {
				sum[p1] = sum[p1] + sum[p2];
				set[p2] = p1;
			}
			cout << sum[p1] << endl;
		}
	}
	return 0;
}

Posted August 22, 2011 by epicrado in Union find

UVA – 10685 – Nature   Leave a comment


import java.util.HashMap;
import java.util.Scanner;

public class Nature {
	static class DisjointSet {
		int[] set;

		DisjointSet(int n) {
			set = new int[n];
			int i = 0;
			while (i < n)
				set[i] = i++;
		}

		public int getParent(int i) {
			if (set[i] == i)
				return i;
			else
				return set[i] = getParent(set[i]);
		}

		public boolean isUnion(int a, int b) {
			return getParent(a) == getParent(b);
		}

		public void makeUnion(int a, int b) {
			set[getParent(a)] = getParent(b);
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();
		int n = in.nextInt();
		while (n != 0 || m != 0) {
			HashMap<String, Integer> map = new HashMap<String, Integer>();
			for (int i = 0; i < m; i++)
				map.put(in.next(), i);
			DisjointSet set = new DisjointSet(m);
			int[] count = new int[m];
			while (n-- > 0)
				set.makeUnion(map.get(in.next()), map.get(in.next()));
			for (int i = 0; i < m; i++)
				count[set.getParent(i)]++;
			int max = 0;
			for (int i : count)
				max = Math.max(max, i);
			System.out.println(max);
			m = in.nextInt();
			n = in.nextInt();
		}
	}
}

Posted August 21, 2011 by epicrado in Union find