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

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

884 – Factorial Factors

What is required is that we sum up the numbers of prime factors for all integers <= integer (n).
We modify Sieve of Eratosthenes so that instead of filling a boolean array isPrime, we fill an integer array nFactors that holds the number of factors for each integer. We accumulate the total number of factors below each integer.
So, we pre-calculate all 1000001 values and print the one corresponding to the input. The following C++ code got rank 345.

#include <iostream>
#include <limits.h>
#include <cmath>
using namespace std;

const int N = 1000001;

// SIEVE
unsigned long long nFactors[N];

void sieve() {
	int i, j, t;
	// reset
	for (i = 0; i < N; ++i)
		nFactors[i] = 0;
	// sieve
	unsigned long long cum = 0;
	for (i = 2; i < N; ++i) {
		// prime: update next integers
		if (nFactors[i] == 0) {
			nFactors[i] = 1;
			if (i < INT_MAX / 2)
				for (j = 2 * i; j > 0 && j < N; j += i) {
					t = j;
					do
						++nFactors[j];
					while ((t /= i) % i == 0);
				}
		}
		// accumulate
		nFactors[i] = (cum += nFactors[i]);
	}
}

// MAIN
int main() {
	// init
	sieve();
	// solve
	int n;
	while (cin >> n)
		cout << nFactors[n] << endl;
	return 0;
}