So the other day month, I posted a programming problem from the ACM inter-collegiate programming competition that I did last year. Here’s my plain-English solution (with some code too). And yes. It is three months late.

Well, there were a large number of people who solved the problem in virtually no time (including a solution in Factor, which I’d never heard of), showing me just how bad I am at these things. Not only that, but they solved it using methods and shortcuts I’d never even dreamed of. My solution was a simple bruteforce, and it goes a little something like this:

“UpperBound(n)” here means every number (up to an including n) added together. q is the answer of the sum, that is, the input.

1. Get q.
2. Start n=1. Discard as UpperBound(n)<q.
3. n=2. Discard as UpperBound(n)<q.
4. n=3,4, discard as UpperBound(n)<q.
5. n=5, discard as UpperBound(n) and q are not both divisible by 2.
6. n=6, discard as UpperBound(n) and q are not both divisible by 2.
7. n=7, UpperBound(n) and q are both divisible by 2, an answer exists. Print n, end.

Didn’t make sense to you? That’s okay! I copied that verbatim from my whiteboard. Here’s some (C/C++) code, instead.

#include <iostream>

int getUpperBound(int n){
	int upperBound = 0;
	while (n > 0){
		upperBound += n;
		n--;
	}
	return upperBound;
}

bool getN(int q, int n){
	if (getUpperBound(n) < q) {
		return false;
	} else {
			//check for divisibility (if q/2 then upperbound of n _must_ also be /2
		if (((getUpperBound(n)%2==0) && (q%2==0)) || (!(getUpperBound(n)%2==0) && !(q%2==0))) {
			return true;
		} else {
			return false;
		}
	}
}

	//get q elsewhere, like a text file
int main (int q) {
	q = 12;

	if (q < 0){
			//should use absolute value here instead, not that it makes a difference
		q+=(0-q)*2;
	}

	int i = 1;
	while((getN(q, ++i)) != true); //prefix used so there's no off-by-one error
	std::cout << i << std::endl;
}

That code ought to compile in the majority of popular C/C++ compilers – I wrote it in XCode and compiled with GCC. However, the input doesn’t conform to the competition’s typical text-file input standards – in fact, there is no input. To check the algorithm with another number, just change q in the main method.

My apologies for the three months of delaying – although I’m sure nobody waited that long for the (probably inefficient, insufficiently-explained) answer.

Carl Lange

I'm currently a Computer Games Development student at Carlow IT. I love programming and all things technical, and I'll learn anything if it's interesting. I'm passionate about technical education, and naturally about games. Check out my resume, and follow me on Twitter!

Related posts:

1. Two-hour ACM Programming Problem, the first
2. ACM-ICPC 2010/2011 Programming Problem – High Score
3. ACM Irish Collegiate Programming Contest 2011 @UCC