Abracadabra

I’ve always be longing to own a blog of my own, but I am never able to deal with the annoying hosting stuff. And today, I finally decided to use wordpress – use money to fill the emptiness of knowledge. That’s fair.

 

Anyway, I am having this very own blog now. I’m using it to record my coding training for programming contests. I had been using github but… it’s just not the same and you have no idea how I envied others for their blogs.

 

Hopefully I’ll truly “knee the way to my chosen dream”, and I hope you enjoy reading my tiny steps.

post

POJ 2528

8/18/2017
Problem: http://poj.org/problem?id=2528
Solution: Segment tree, obviously. But since there’re 10^7 bricks, segment tree
only would bring up a MLE. That’s why we are using hashing: if no
endpoints of posters lie on segment a-b, it doesn’t really matter how
long this segment is. We can simply map it to a segment of length 2.
Note: In regard to the expression “a||b”, if a is already true then b would not
be checked. That’s where I spent two days debugging..


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

struct poster {
	int l, r;
} p[10100];

int x[20200] = {0};
int hash[10000010] = {0};
int nodecnt = 0;

struct node {
	int l, r;
	bool c;
	node *pl, *pr;
};

node tree[1000005];

void build (node *root, int l, int r) {
	root->c = false;
	root->l = l;
	root->r = r;
	if (l == r) {
		return;
	}
	nodecnt++;
	root->pl = tree + nodecnt;
	nodecnt++;
	root->pr = tree + nodecnt;
	int mid = (l + r) / 2;
	build(root->pl, l, mid);
	build(root->pr, mid + 1, r);
}

bool post (node *root, int l, int r) {
	// cout << root->l << ' ' << root->r << ' ' << root->c << endl;
	if (root->c) {
		return false;
	}
	if (root->l == l && root->r == r) {
		root->c = true;
		return true;
	}
	bool b = false;
	int mid = (root->l + root->r) / 2;
	if (r <= mid) {
		b = post(root->pl, l, r);
	} else if (l > mid) {
		b = post(root->pr, l, r);
	} else {
		bool b1 = post(root->pl, l, mid);
		bool b2 = post(root->pr, mid + 1, r);
		b = b1 || b2;
	}
	if (root->pl->c && root->pr->c) {
		root->c = true;
	}
	return b;
}

int main() {
	int c;
	scanf("%d", &c);
	while (c--) {
		memset(x, 0, sizeof(x));
		memset(hash, 0, sizeof(hash));
		memset(p, 0, sizeof(p));
		memset(tree, 0, sizeof(tree));
		nodecnt = 0;
		int n;
		scanf("%d", &n);
		// cout << n << endl;
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &p[i].l, &p[i].r);
			x[cnt++] = p[i].l;
			x[cnt++] = p[i].r;
		} 
		sort(x, x + cnt);
		cnt = unique(x, x + cnt) - x;
//		for (int i = 0; i < cnt; i++) {
//			cout << x[i] << ' ';
//		}
		int no = 0;
		for (int i = 0; i < cnt; i++) {
//			cout << no << ' ';
			hash[x[i]] = no;
			if (i < cnt - 1) {
				if (x[i + 1] - x[i] == 1) {
					no++;
				} else {
					no += 2;
				}
			}
		}
		build(tree, 0, no);
		int ans = 0;
		for (int i = n - 1; i >= 0; i--) {
			// cout << hash[p[i].l] << ' ' << hash[p[i].r] << endl; 
			if (post(tree, hash[p[i].l], hash[p[i].r])) {
				ans++;
				// cout << i << endl;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

POJ 4368 A Simple Problem with Integers

8/11/2017
Problem: http://poj.org/problem?id=3468
Solution: Record the sum for each segment. For time efficiency, here we do not
add immediately after an “add” operation. Instead, if reaching a
complete segment, simply record the inc value onto that exact point.
It would only be added to the individual points beneath when part of
the segment is queried.


#include<iostream>
#include<cstdio>
using namespace std;
int nodecnt = 0;

struct node{
	int l, r;
	node *pl, *pr;
	long long sum;
	long long inc;
};

node tree[200010];

void build (node *root, int l, int r) {
	root->l = l;
	root->r = r;
	root->sum = root->inc = 0;
	if (l == r) {
		return;
	}
	nodecnt++;
	root->pl = tree + nodecnt;
	nodecnt++;
	root->pr = tree + nodecnt;
	int mid = (l + r) / 2;
	build(root->pl, l, mid);
	build(root->pr, mid + 1, r);
}

void insert (node *root, int i, int v) {
	if (root->l == i && root->r == i) {
		root->sum = v;
		return;
	}
	root->sum += v;
	int mid = (root->l + root->r) / 2;
	if (i <= mid) {
		insert(root->pl, i, v);
	} else {
		insert(root->pr, i, v);
	}
}

void add (node *root, int l, int r, long long c) {
	// cout << l << ' ' << r << ' ' << c << endl;
	if (root->l == l && root->r == r) {
		root->inc += c;
		return;
	}
	root->sum += c * (r - l + 1);
	int mid = (root->l + root->r) / 2;
	if (r <= mid) {
		add (root->pl, l, r, c);
	} else if (l > mid) {
		add (root->pr, l, r, c);
	} else {
		add (root->pl, l, mid, c);
		add (root->pr, mid + 1, r, c);
	}
}

long long search (node *root, int l, int r) {
	// cout << l << ' ' << r << endl;
	if (root->l == l && root->r == r) {
		return root->sum + root->inc * (r - l + 1);
	}
	root->sum += (root->r - root->l + 1) * root->inc;
	int mid = (root->l + root->r) / 2;
	add (root->pl, root->l, mid, root->inc);
	add (root->pr, mid + 1, root->r, root->inc);
	root->inc = 0;
	if (r <= mid) {
		return search(root->pl, l, r);
	} else if (l > mid) {
		return search(root->pr, l, r);
	} else {
		return search(root->pl, l, mid) + search(root->pr, mid + 1, r);
	}
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	build(tree, 1, n);
	for (int i = 1; i <= n; i++) {
		int tmp;
		scanf("%d", &tmp);
		insert(tree, i, tmp);
	}
	for (int i = 1; i <= q; i ++) {
		char ch;
		cin >> ch;
		// scanf("%c", &ch);
		if (ch == 'Q') {
			int a, b;
			scanf("%d%d", &a, &b);
			printf("%lld\n", search(tree, a, b));
		} else {
			int a, b;
			long long c;
			scanf("%d%d%lld", &a, &b, &c);
			add(tree, a, b, c);
		}
	}
	return 0;
}


POJ 3264 Balanced Lineup

8/11/2017
Problem: http://poj.org/problem?id=3264
Solution: Record the max and min value for each segment.


#include<iostream>
#include<climits>
#include<cmath>
#include<cstdio>
using namespace std;
int mi = INT_MAX;
int ma = INT_MIN;

struct node{
	int l, r;
	int max;
	int min;
};

node t[800005] = {0};

void build (int root, int l, int r) {
	t[root].l = l;
	t[root].r = r;
	t[root].max = INT_MIN;
	t[root].min = INT_MAX;
	if (l != r) {
		build(root * 2 + 1, l, (l + r) / 2);
		build(root * 2 + 2, (l + r) / 2 + 1, r);
	}
}

void insert (int root, int i, int v) {
	if (t[root].l == t[root].r) {
		t[root].min = v;
		t[root].max = v;
		return;
	}
	t[root].min = min(t[root].min, v);
	t[root].max = max(t[root].max, v);
	if (i <= (t[root].l + t[root].r) / 2) {
		insert (root * 2 + 1, i, v);
	} else {
		insert (root * 2 + 2, i, v);
	}
}

void search (int root, int l, int r) {
	int mid = (t[root].l + t[root].r) / 2;
	if (mi <= t[root].min && ma >= t[root].max) {
		return;
	}
	if (t[root].l == l && t[root].r == r) {
		mi = min(mi, t[root].min);
		ma = max(ma, t[root].max);
		return;
	}
	if (r <= mid) {
		search (root * 2 + 1, l, r);
	} else if (l >= mid + 1) {
		search (root * 2 + 2, l, r);
	} else {
		search (root * 2 + 1, l, mid);
		search (root * 2 + 2, mid + 1, r);
	}
	return;
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	build(0, 1, n);
	int tmp;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &tmp);
		insert(0, i, tmp);
	}
	for (int i = 1; i <= q; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		mi = INT_MAX;
		ma = INT_MIN;
		search(0, a, b);
		printf("%d\n", ma - mi);
	}
	return 0;
}

POJ 2007

8/10/2017
Problem: http://poj.org/problem?id=2007
Solution: Sort all the points by cross product (of vectors). If v1 ^ v2 > 0,
then v1 can reach v2 rotating less than 180 degrees counter-clockwise.


#include<iostream>
#include<algorithm>
using namespace std;

struct node{
	double x, y;
	node(){}
	node(double xx, double yy):x(xx), y(yy){}
};

node n; 

bool cmp (node a, node b) {
	return (((a.x - n.x) * (b.y - n.y) - (a.y - n.y) * (b.x - n.x)) > 0);
}

int main() {
	double x, y;
	node p[105];
	int cnt = 0;
	cin >> n.x >> n.y;
	while (cin >> x >> y) {
		p[++cnt] = node(x, y);
	}
	sort(p + 1, p + cnt + 1, cmp);
	cout << "(0,0)" << endl;
	for(int i = 1; i <= cnt; i++) {
		cout << '(' << p[i].x << ',' << p[i].y << ")" << endl;
	} 
	return 0;
}

POJ 2349

8/8/2017
Problem: http://poj.org/problem?id=2349
Solution: The answer is just the length of the k-th largest edge in the MST.

#include<cstdio>
#include<iostream> 
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

struct point{
	int x, y;
	point(int xx, int yy):x(xx), y(yy){}
	point(){}
};

struct edge{
	int i, j;
	double w;
	edge(int ii, int jj, double ww):i(ii), j(jj), w(ww){}
	edge(){}
};

point p[5005];
edge e[251010];
int parent[5005];

double dist(int x1, int y1, int x2, int y2) {
	return sqrt((double)(x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

bool cmp(edge a, edge b) {
	return a.w < b.w;
}

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		parent[a] = find(parent[a]);
		return parent[a];
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p2] = p1;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int s, n;
		cin >> s >> n;
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		} 
		for (int i = 1; i <= n; i++) {
			cin >> p[i].x >> p[i].y;
		} 
		int cnt = 0;
		for (int i = 1; i < n; i++) {
			for (int j = i + 1; j <= n; j++) {
				double tmp = dist(p[i].x, p[i].y, p[j].x, p[j].y);
				e[++cnt] = edge(i, j, tmp);
				e[++cnt] = edge(j, i, tmp);
			}
		}
		int node = 0;
		sort(e + 1, e + cnt + 1, cmp);
		for (int i = 1; i <= cnt; i++) {
			if (find(e[i].i) != find(e[i].j)) {
				merge(e[i].i, e[i].j);
				node++;
				if (node == n - s) {
					printf("%0.2f\n", e[i].w);
					break;
				}
			}
		}
	}
	return 0;
}

POJ 1258 Agri-Net

8/8/2017
Problem: http://poj.org/problem?id=1258
Solution: I used Kruskal but Prim is the same. Nothing noteworthy.


#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> parent;

struct Edge{
	int s, e, w;
	Edge(int ss, int ee, int ww):s(ss), e(ee), w(ww){}
};

vector<Edge> edge;

bool operator<(Edge a, Edge b) {
	return a.w < b.w;
}

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (find(p1) != find(p2)) {
		parent[p2] = p1;
	}
}

int main() {
	int n;
	while (cin >> n) {
		parent.clear();
		edge.clear();
		for (int i = 0; i <= n; i++) {
			parent.push_back(i);
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				int w;
				cin >> w;
				edge.push_back(Edge(i, j, w));
			}
		}
		sort(edge.begin(), edge.end());
		int node = 0;
		int len = 0;
		for (int i = 0; i < edge.size(); i++) {
			if (find(edge[i].s) != find(edge[i].e)) {
				merge(edge[i].s, edge[i].e);
				node++;
				len += edge[i].w;
			}
			if (node == n - 1) {
				break;
			}
		}
		cout << len << endl;		
	}
	return 0;
} 

POJ 2236 Wireless Network

8/7/2017
Problem: http://poj.org/problem?id=2236
Solution: Still basic dsu..

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int x[1005];
int y[1005];
int parent[1005];
int ok[1005];
int d;

bool close(int a, int b) {
	if ((y[a] - y[b]) * (y[a] - y[b]) + (x[a] - x[b]) * 
						(x[a] - x[b]) <= d * d) {
		return true;					
	}
	return false;
}

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
	}
}

int main() {
	int n;
	cin >> n >> d;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
		parent[i] = i;
	} 
	string s;
	while (cin >> s) {
		if (s == "O") {
			int k;
			cin >> k;
			ok[k] = 1;
			for (int i = 1; i <= n; i++) {
				if (ok[i] && close(i, k) && find(i) != find(k)) {
					merge(i, k);
				}
			}
		} else if (s == "S") {
			int a, b;
			cin >> a >> b;
			if (find(a) == find(b)) {
				cout << "SUCCESS";
			} else {
				cout << "FAIL";
			}
			cout << endl;
		}
	}
	return 0;
}

POJ 2524 Ubiquitous Religions

8/7/2017
Problem: http://poj.org/problem?id=2524
Solution: Basic dsu, no explanation needed.

#include<iostream>
#include<cstring>
using namespace std;
int parent[50005];

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
	}
}

int main() {
	int n, m;
	int c = 0;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}
		for (int i = 1; i <= m; i++) {
			int p, q;
			cin >> p >> q;
			if (find(p) != find(q)) {
				merge(p, q);
				n--;
			}
		}
		c++;
		cout << "Case " << c << ": ";
		cout << n << endl;
	}
	return 0;
}

PKU 30 Find it, Catch it

Problem: http://acmicpc.openjudge.cn/practice/030/


#include<iostream>
#include<cstdio>
#include<ctype.h>
using namespace std;
int parent[200005] = {0};

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
	}
	return;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, m;
		scanf("%d%d", &n, &m);
		if (n == 2 && m == 1) {
			cout << "In different gangs." << endl;
			char ch = 0;
			int a, b;
			while(!isalpha(ch)) {
				ch = getchar();
			}
			scanf("%d%d", &a, &b);
			continue;
		}
		for (int i = 1; i <= 2 * n; i++) {
			parent[i] = i;
		}
		for (int i = 1; i <= m; i++) {
			char ch = 0;
			int a, b;
			while(!isalpha(ch)) {
				ch = getchar();
			}
			scanf("%d%d", &a, &b);
			if (ch == 'D') {
				merge(a, b + n);
				merge(b, a + n);	
			} else if (ch == 'A') {
				int aa = find(a);
				int bb = find(b);
				if (find(a) == find(b + n)) {
					cout << "In different gangs." << endl; 
				} else if (aa != bb) {
					cout << "Not sure yet." << endl;
				} else {
					cout << "In the same gang." << endl;
				}
			}
		}
	} 
	return 0;
} 


PKU 29 Religion

Problem: http://acmicpc.openjudge.cn/practice/029/


#include<iostream>
#include<cstring>
using namespace std;
int parent[50005] = {0};

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
	}
	return;
}

int main() {
	int n, m;
	int c = 0;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}
		c++;
		for (int i = 1; i <= m; i++) {
			int a, b;
			cin >> a >> b;
			if (find(a) != find(b)) {
				n--;
				merge(a, b);
			}
		}
		cout << "Case " << c << ": " << n << endl;
	}
	return 0;
}