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;
}

12149 – Feynman

A combinatorics problem.
You’re required to count the number of squares in an NxN square grid.
After observing some base cases you might recognize the formula if you’re familiar with it. However, let’s try a more systematic and intuitive way. In an NxN area, we’ll look into squares that inhibit this area with respect to their dimensions:

• 1x1 squares: each one of these can choose an x-position from 1 to N. Also, a y-position from 1 to N. Thus, it can choose out of NxN position.
• 2x2 squares: which are bigger by one. Thus, they can choose between N-1 x-positions and N-1 y-positions. That’s (N-1)x(N-1)
• 3x3 squares: using similar reasoning are (N-2)x(N-2).
• NxN squares: 1x1 (only one possible position).
• And so on…

Hence the formula we get is:

Which is the square pyramidal number. OEIS.
Coded in C++ with rank 574:

#include <cstdio>
using namespace std;

long long n;

int main() {
	while (scanf("%lld", &n) && n)
		printf("%lld\n", n (n + 1) (2 n + 1) / 6);
	return 0;
}

160 – Factors and Factorials

A simple math problem.
For , you’re required to find the number of its prime factors. The input space is n < 100 which is rather small. So, a pre-calculation will do. For each integer starting from 0 up to 100, calculate the number of prime factors and there repetition and store them in a 100×25 array (25 is the number of prime numbers under 100).
Now, for any input n, we iterate over all the numbers form 1 to n and accumulate their prime factors repetition in an array of length 25.
Caution!

• Output is tricky.

C++ code, rank 5311:

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

#define N 101

int nFactors[101][25] = {
	"http://pastebin.com/RAANwCY0#"
	};

int main() {
	int n;
	int nDiv[25];
	while(scanf("%d", &n) && n) {
		memset(nDiv, 0, sizeof nDiv);
		// add factors
		for (int i = 2; i <= n; ++i)
			for (int j = 0; j < 25; ++j)
			nDiv[j] += nFactors[i][j];
		// print
		printf("%3d! =", n);
		int nBlock = 0;
		for (int i = 0; i < 25; ++i)
			if(nDiv[i]) {
				if(nBlock == 15) {
					nBlock = 0;
					printf("\n      ");
				}
				printf("%3d", nDiv[i]);
				++nBlock;
			}
		printf("\n");
	}
	return 0;
}

10079 – Pizza Cutting

A combinatorics/math problem.
You’re required to output the maximum number of pieces obtainable by making n straight cuts in a pizza.
The answer is actually a sequence known as the lazy caterer’s sequence. Implementation is trivial. Coded in C++, rank 5355:

#include <cstdio>

long long n;

int main() {
	while (scanf("%lld", &n) && n >= 0)
		printf("%lld\n", n * (n + 1) / 2 + 1);
	return 0;
}