Two-hour ACM Programming Problem, the first
So myself and Ciarán (and some other classmates, Kevin Beirne and Keith Cully) are in the ACM International Collegiate Programming Contest at University College Cork this year. We’d competed last year, but we were so unprepared that we didn’t even bring pen and paper. It was a spur of the moment thing (to drive halfway across the country and compete in a programming competition is a spur-of-the-moment decision for us, oh yes).
This year, we’re preparing something like six months in advance.
So, we’ve decided to write some articles as we complete some problems. The ICPC problems are very much logic-based questions, mostly centred on figuring out an algorithm to solve a problem. This week, we solved a problem that we were asked last year. Ciarán, apparently having incredible memory, remembered the basic premise of the question rather well, so here it is:
You are given an integer, either positive or negative. You can only add or subtract numbers, and every number before the highest number must be used. That is, if the highest number in your sum is 7, you must also use 1, 2, 3, 4, 5, 6. You can only use a number once, and you can only add or subtract it. The question is such: Given a number, what is the lowest number of integers in your sum needed to calculate that number?
So taking the number 12 as sample input, output would be 7. Input of 21 would give 6. Input of 7 would give 5.
This is demonstrated as such: Given the number 7, a sum is -1+2-3+4+5=7. 5 is the answer, as it’s the highest number in the sum, and this sum has the fewest possible integers in it. You could not, say, simply do 9-2=7; you would need to also use 1,3,4,5,6,7, and 8 in your sum. Any sum larger than that one (by larger, I mean that contains more integers) is also wrong, as -1+2-3+4+5=7 is the smallest possible sum.
Note that in further articles, we’ll be taking questions directly from sample problem sheets or previous competitions, so they might be more long-form.
My apologies if the question seems very hard to understand, as that’s probably my fault.
So, how do you get the smallest possible number of integers for any number, if that number has to be calculated as shown above? What’s the algorithm you go through?
In a few days, I’ll post the solution, but feel free to figure it out and post your solutions! I’m not looking for code – a plain English solution is as good as any C++ (though I’ll post my code solution as well).