## Solution to the ACM Programming Problem 1

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.

- Get q.
- Start n=1. Discard as UpperBound(n)<q.
- n=2. Discard as UpperBound(n)<q.
- n=3,4, discard as UpperBound(n)<q.
- n=5, discard as UpperBound(n) and q are not both divisible by 2.
- n=6, discard as UpperBound(n) and q are not both divisible by 2.
- 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. ðŸ˜‰

good job! I will go through it!