10088 – Trees on My Island

Given a polygon whose vertices are of integer coordinates (lattice points), count the number of lattice points within that polygon.
Pick’s theoreom states that
Where

• is the number of lattice points in the interior (this is our program’s output).
• is the area of the polygon.
• is the number of lattice points on the exterior.

All the reqired quantities are easily computable, however, needs some extra work. To find the number of lattice points on line segment , we simply calculate .
C++ implementation with rank 329:

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

typedef long long gtype;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )

long double polArea(vector<point> & p) {
	long double area = 0;
	for (size_t i = 0; i < p.size() - 1; ++i)
		area += crs(p[i], p[i + 1]);
	return abs(area) * 0.5;
}

long long gcd(long long a, long long b) {
	long long t;
	while (b)
		t = b, b = a % b, a = t;
	return a;
}

long long polLatticeB(vector<point> & p) {
	long long b = 0;
	for (size_t i = 1; i < p.size(); ++i)
		b += gcd(abs(p[i].y - p[i - 1].y), abs(p[i].x - p[i - 1].x));
	return b;
}

int main() {
	int n;
	while (cin >> n && n) {
		// polygons
		vector<point> p(n + 1);
		for (int i = 0; i < n; ++i)
			cin >> p[i].x >> p[i].y;
		p[n] = p[0];
		// is convex
		cout << (long long) (polArea(p) - polLatticeB(p) * 0.5l + 1) << endl;
	}
	return 0;
}

530 – Binomial Showdown

This problem is identical to 369 – Combinations.

369 – Combinations

A combinations problem. Given N and R, find NCR.
There’s a variety of ways; The first two solutions are straight-forward computation of . The last two have some tricks:

A naive Java solution that uses big arithmetic:

import java.math.*;
import java.util.*;

public class Main {

	private static BigInteger C(BigInteger n, BigInteger r) {
		r = (r.compareTo(n.subtract(r)) > 0) ? n.subtract(r) : r;
		BigInteger num = BigInteger.ONE, den = BigInteger.ONE;
		while (!r.equals(BigInteger.ZERO)) {
			num = num.multiply(n); den = den.multiply(r);
			r = r.subtract(BigInteger.ONE); n = n.subtract(BigInteger.ONE);
		}
		return num.divide(den);
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while (s.hasNext()) {
			BigInteger n = s.nextBigInteger(), r = s.nextBigInteger();
			if (n.equals(BigInteger.ZERO) && r.equals(BigInteger.ZERO))
				break;
			System.out.printf("%s things taken %s at a time is %s exactly.\n", n, r, C(n, r));
		}
	}
}

A similar C++ solution:

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

unsigned long long C(int n, int r) {
	r = min(n - r, r);
	long long out = 1;
	for (int i = 1; i <= r; ++i) {
		out *= n - r + i;
		out /= i;
	}
	return out;
}

int main() {
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, C(n, r));
	return 0;
}

A slower, but totally accepted, solution reduces the computations as you were doing it by hand; We have two arrays, one for the numerator and another for the denominator. We do a 2D loop to reduce the numerator with respect to the denominator and hence the answer. C++ implementation:

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

#define REDUCE(a, b) { int g = gcd(a, b); a /= g; b /= g; }

int num[100], den[100];
int numI, denI;

long long gcd(long long a, long long b) {
	long long t;
	while (a) { t = a; a = b % a; b = t; }
	return b;
}

long long C(int n, int r) {
	// fill arrays
	r = min(n - r, r);
	numI = denI = 0;
	while (r) { num[numI++] = n--; den[denI++] = r--; }
	// reduce & compute
	long long out = 1;
	for (int i = 0; i < numI; ++i) {
		for (int j = 0; j < denI; ++j)
			REDUCE(num[i], den[j]);
		out *= num[i];
	}
	return out;
}

int main() {
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, C(n, r));
	return 0;
}

The last solution has the same complexity as the first two. It uses Pascal’s Triangle for computing combinations. C++ implementation:

#include <cstdio>
using namespace std;

#define N 128

long long pascalTri[N * (N + 1) / 2];

void fillPascal() {
	for (int l = 0, lStart = 0; l < N; ++l, lStart += l) {
		pascalTri[lStart] = pascalTri[lStart + l] = 1;
		for (int i = 1; i < l; ++i)
			pascalTri[lStart + i] = pascalTri[lStart + i - l] + pascalTri[lStart + i - l - 1];
	}
}

int main() {
	fillPascal();
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, pascalTri[n * (n + 1) / 2 + r]);
	return 0;
}

10814 – Simplifying Fractions

A simple math GCD problem with big arithmetic.

• Get fraction a / b.
• Find g : GCD(a, b).
• Divide both a, b by g.
• Output.

Rank 461 Java code:

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	private static BigInteger gcd(BigInteger a, BigInteger b) {
		BigInteger t;
		while (a.compareTo(BigInteger.ZERO) != 0) {
			t = a;
			a = b.mod(a);
			b = t;
		}
		return b;
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		BigInteger a, b, g;
		while (n-- > 0) {
			a = s.nextBigInteger();
			s.next();
			b = s.nextBigInteger();
			g = gcd(a, b);
			System.out.println(a.divide(g) + " / " + b.divide(g));
		}
	}
}

11621 – Small Factors

A –supposed– math problem. But it turns out to be an ad-hoc problem.
Given an integer n, find the next integer m that’s in the set :
. In other words, the factors of m are only 2’s and 3’s.
A brute-force solution loops from n and onwards until it finds m. m is the first integer that after factorization with respect to 2 and 3, becomes 1 (no other factors remain). This gets a time limit exceeded.
Another brute-force solution does the same, however, for every input, it generates valid m‘s (by successive multiplications by 2 and 3) until one of them exceeds or equals n. After all possible optimizations that I could think of, this solution, also, gets a time limit exceeded.
After some thought, since m is only composed of 2’s and 3’s, for a number to match m‘s criterion, it must have
gcd(m, 2 * 2 * 2 ... * 2) * gcd(m, 3 * 3 * 3 ... * 3) = m
So, i did the same loop but with the former stopping condition. Still, a time limit exceeded. Anyways, here’s the C++ implementation:

#include <cstdio>
using namespace std;

#define P2 1073741824
#define P3 1162261467

int gcd(int a, int b) {
	int t;
	while (b) { t = a; a = b; b = t % b; }
	return a;
}

int n, m;

int main() {
	while (scanf("%d", &n) == 1 && (m = n)) {
		while(gcd(m, P2) * gcd(m, P3) != m)
			++m;
		printf("%d\n", m);
	}
	return 0;
}

Ironically, the only accepted solution I could get was to pre-calculate the set ! Then you have to find m that’s larger than or equal to input (n). Pre-calculation it is! C++ rank 58:

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

typedef long long int64;

int64 p2[32] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
		8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
		16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648ll };
int64 p3[21] = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323,
		4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401ll };
int64 n;
vector<int64> q;

int main() {
	// pre-calculate
	for (int i = 0; i < 32; ++i)
		for (int j = 0; j < 21; ++j)
			q.push_back(p2[i] * p3[j]);
	sort(q.begin(), q.end());
	// solve
	while (scanf("%lld", &n) == 1 && n)
		printf("%lld\n", q[lower_bound(q.begin(), q.end(), n) - q.begin()]);
	return 0;
}