11879 – Multiple of 17

You can either use the approach given or modular arithmetic. Both methods are of the same computational complexity, however, they differ in coding difficulty. A third solution is using big arithmetic which I won’t consider.

Given approach

The operation explained in the statement modifies at most 4 digits of the integer. 1 digit for by removing the last digit (d) and –at most– 3 digits for the subtraction of (5 * d).
This suggest that: we perform the operation on the first 4 rightmost digits (which reduces them to 2 or 3 digits) then concatenate the next rightmost digit and repeat until the string is processed.
A little bit hard to code, but it works! Coded in C++, rank 451:

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

char num[128], *numPtr;
int n, i;

int main() {
	while (scanf("%s", num) && !((numPtr = num + strlen(num) - 1) == num && *num == '0')) {
		for (n = 0, i = 1; numPtr >= num && i < 10000; i *= 10)
			n += (*(numPtr--) - '0') * i;
		while (numPtr >= num) {
			n = (n / 10) - (n % 10) * 5;
			if (n > 9999)
				n += (*(numPtr--) - '0') * 10000;
			else
				n += (*(numPtr--) - '0') * 1000;
		}

		printf("%d\n", (n % 17) == 0);
	}
	return 0;
}

Modular arithmetic

You parse the input like you would normally do for an integer, but you take modulo 17 as you compute. This utilizes addition and multiplication properties in modular arithmetic. C++ implementation with rank 456:

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

char num[128], *numPtr;
int n;

int main() {
	while (scanf("%s", num) && !(strlen(numPtr = num) == 1 && *num == '0')) {
		n = 0;
		do
			n = (n * 10 + (*numPtr - '0')) % 17;
		while (*++numPtr != '\0');
		printf("%d\n", (n % 17) == 0);
	}
	return 0;
}

469 – Wetlands of Florida

The problems is a Flood-Fill which is listed as a Depth First Search application. So, I decided to solve it as a Disjoint Sets problem. I used the code I wrote before for flood-fill with disjoint sets in Java and converted it to C++.
Here is the implementation:

#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;

struct group {
	group* parent;
	int area;

	group() {
		area = 1;
		parent = NULL;
	}

	group* getParent() {
		if (this->parent != NULL)
			return this->parent->getParent();
		else
			return this;
	}

	void setParent(group* parent) {
		if (this->parent != NULL)
			this->parent->setParent(parent);
		this->parent = parent;
	}

	void incrementArea(int incr) {
		if (this->parent != NULL)
			this->parent->incrementArea(incr);
		else
			this->area += incr;

	}

	int getArea() {
		if (this->parent != NULL)
			return this->parent->getArea();
		else
			return area;
	}

	group* merge(group* g) {
		if (g == NULL || g->getParent() == getParent())
			return this;
		group* newParent = g->getParent();
		newParent->incrementArea(this->getArea());
		this->setParent(newParent);
		return this;
	}

	int parentDepth() {
		return parent != NULL ? 1 + parent->parentDepth() : 0;
	}
};

#define N 100 + 1

char line[N], prevLine[N];
int nCases;
group g[N][N];
int width, height;

void resetLine() {
	for (int x = 0; x < width; x++) {
		g[height][x].parent = NULL;
		g[height][x].area = 1;
	}
}

void merge(int x, int y) {
	char thisChar = line[x];
	group* w = (x > 0 && thisChar == line[x - 1]) ? &g[y][x - 1] : NULL;
	group* n = (y > 0 && thisChar == prevLine[x]) ? &g[y - 1][x] : NULL;
	group* nw = (y > 0 && x > 0 && thisChar == prevLine[x - 1]) ? &g[y - 1][x - 1] : NULL;
	group* ne = (y > 0 && x < width - 1 && thisChar == prevLine[x + 1]) ? &g[y - 1][x + 1] : NULL;
	g[y][x].merge(w)->merge(n)->merge(nw)->merge(ne);
}

void print() {
	for (int y = 0; y < height; y++) {
		for (int x = 0; x < width; x++)
			printf("%3d", g[y][x].getArea());
		printf("\n");
	}
}

int main() {
	scanf("%d", &nCases);
	getchar();
	getchar();
	while (nCases-- > 0) {
		// MAP
		height = 0;
		while (gets(line) && strlen(line) > 0) {
			// read map
			if (line[0] == 'W' || line[0] == 'L') {
				width = strlen(line);
				resetLine();
				// solve
				for (int x = 0; x < width; x++)
					if (line[x] == 'L')
						g[height][x].incrementArea(-1);
					else
						merge(x, height);
				height++;
				strcpy(prevLine, line);
			}
			// read test cases
			else {
				// print();
				int x = 0, y = 0;
				sscanf(line, "%d %d", &y, &x);
				// solve
				if (x <= 0 || x > width || y <= 0 || y > height)
					printf("0");
				else
					printf("%d", g[y - 1][x - 1].getArea());
				printf("\n");
			}
		}
		if (nCases > 0)
			printf("\n");
	}
}

The input is very tricky and I couldn’t get it right. You could see how messy it looks.
Rank 36.

10344 – 23 Out Of 5

Generate all orders/permutations of 5 integers before getting any input (you can even generate them before compiling!). That’s (5! = 120) permutations.

• Get input and store it.
• Order the input according to the previously generated permutations.
• Brute-force attack all the possible operations on the 5 integers until you get 23. Those are (34 = 81) permutations.
• If no permutation of integers and operations give 23, that’s "Impossible".

Recursive C++ implementation, 175 rank.

#include <iostream>
using namespace std;

const int target = 23;

// generate permutations for 5 elements
int genUsed, perm[120], permI, nPerm, thisPerm;
void generatePermutations() {
	if (permI == 5)
		perm[nPerm++] = thisPerm;
	else
		for (int i = 0; i < 5; ++i)
			if (~genUsed & (1 << i)) {
				genUsed ^= (1 << i);
				thisPerm = thisPerm * 5 + i;
				permI++;
				generatePermutations();
				permI--;
				thisPerm /= 5;
				genUsed ^= (1 << i);
			}
}

// generate operation and calculate
int in[5], operand[5];
bool isGood(int result, int opI) {
	if (opI == 5)
		return result == target;
	else
		return isGood(result - operand[opI], opI + 1) || isGood(result * operand[opI], opI + 1) || isGood(result + operand[opI], opI + 1);
	return false;
}

int main() {
	// generate
	genUsed = 0, nPerm = 0;
	generatePermutations();
	// input
	while (cin >> in[0] >> in[1] >> in[2] >> in[3] >> in[4]) {
		if (in[0] == 0 && in[1] == 0 && in[2] == 0 && in[3] == 0 && in[4] == 0)
			break;
		// permute
		int p, i;
		for (i = 0; i < 120; ++i) {
			p = perm[i];
			for (int i = 0; i < 5; ++i) {
				operand[i] = in[p % 5];
				p /= 5;
			}
			if (isGood(operand[0], 1))
				break;
		}
		if (i < 120)
			cout << "Possible" << endl;
		else
			cout << "Impossible" << endl;
	}
}

Integer Square Root

Occasionally, we’re faced with the problem of calculating the square root of an integer. Here are three algorithms:

• This method is the least efficient. It relies on the fact that the difference between consequent squares is the series of odd numbers.

i	0	1	2	3	4	5	6
sqr(i)	0	1	4	9	16	25	36
sqr(i) – sqr(i + 1)	1	3	5	7	9	11	…

So, given an input integer n what the algorithm does is:
It starts with square = 1 and keeps adding odd integers (delta) from the series until square reaches n(the input integer). The root is sqrt(n) = delta / 2 - 1.
Implementation in C++

template
type sqrt(type n) {
	type square = 1;
	type delta = 3;
	while (square 		square += delta;
		delta += 2;
	}
	return delta / 2 - 1;
}

• The second method to guesses a root (guess) and then tries to minimize the distance to the real root.

In C++:

template
type sqrt(type n) {
	type upperBound = n + 1;
	type guess = 0;
	type lowerBound = 0;
	type delta;
	while (delta = (guess = (upperBound + lowerBound) / 2) * guess - n)
		if (delta > 0)
			upperBound = guess;
		else
			lowerBound = guess;
	return guess;
}

• This method is similar to the previous. However, it has different logic. We’re trying to “build” the root bit-by-bit. It is the most efficient among them.

In C++:

template
type sqrt(type n) {
	type guess = 0;
	int newBit = 1 << (sizeof(type) * 4 - 1); 	while (newBit > 0) {
		if (n >= (guess + newBit) * (guess + newBit))
			guess += newBit;
		newBit >>= 1;
	}
	return guess;
}

Caution!

• C++’s <cmath> is faster!
• Results for non-integer squares are not reliable.