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:
-1+2-3-4+5+6+7=12
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).
About the Author
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
-
Flax HTML5 Game Engine Development Diary Part 11
Well it’s that time again, it’s been just about three weeks since the first iteration of the Flax HTML5 Game Engine 0.1 and as promised […]
Catch up with the Flax Project – Busy times!
Hey everyone, so it’s been nearly 5 weeks since we last posted. It’s been a crazy 5 weeks and it’s not over just yet. Unfortunately we […]
17 Comments
Trackbacks for this post
-
[…] This post was mentioned on Twitter by HN Firehose, Dr Carl Lange, Flax.ie, Dr Carl Lange, Dr Carl Lange and others. Dr Carl Lange said: I just wrote blog post about a cool logic problem. RT for giant space lobsters! http://flax.ie/two-hour-acm-programming-problem-the-first/ […]
-
[…] then ever we need practice. If you’re not up to speed on what it’s all about check out Carl’s first post on another ACM problem. So let’s get straight to the problem. I will present the problem in […]
For 7 wouldn’t the quickest way be:
– 1 – 2 + 3 + 4 = 7
or am I reading the problem the wrong way
No that makes 4!
Ignore me I’m tired LOL
Nice one! (solution takes 10-15 minutes)
– sum of first n numbers [SOFnN] is n*(n+1)/2
– given the integer w find first SOFnN that is >= w and with same odd/even quality
– return n
in C#
public static int ICPC(int wanted) {
if (wanted sum || (sum – wanted) % 2 == 1) {
i++;
sum += i;
}
return i;
}
Don’t know why, part of code was lost 🙁 here I try it again.
public static int ICPC(int wanted) {
if (wanted sum || (sum – wanted) % 2 == 1) {
i++;
sum += i;
}
return i;
}
Something wrong with page submission!!
last try
//public static int ICPC(int wanted) {
// if (wanted sum || (sum – wanted) % 2 == 1) {
// i++;
// sum += i;
// }
// return i;
//}
another try to submit code, last one I promise! 🙂
public static int ICPC(int wanted) {
if (wanted [less RuntimeTypeHandle or equal] 0) return 0;
int i = 1;
int sum = 1;
while (wanted [greater than] sum || (sum – wanted) % 2 == 1) {
i++;
sum += i;
}
return i;
}
I think the pre tag may work in this comments system. Testing..
public static int ICPC(int wanted) { if (wanted [less RuntimeTypeHandle or equal] 0) return 0; int i = 1; int sum = 1; while (wanted [greater than] sum || (sum - wanted) % 2 == 1) { i++; sum += i; } return i; }Yep, but I not sure was that your problem.
Here’s my very quick solution in Java:
public static long acm(long n) {
if (n == 0) return 0L;
n = Math.abs(n);
long group = (iSqrt((n <>> 1;
switch ((int) (group & 3L)) {
case 0: return group + (n & 1L);
case 1: return group – ((n & 1L) << 1) + 2L;
case 2: return group – (n & 1L) + 1L;
case 3: return group + ((n & 1L) <>> 2) < n ? low : high;
}
Here’s my super-fast solver in Java. It looks like my last solution was inaccurate for large numbers and had bad markup for this blog.
public static long acm(long n) {
if (n == 0) return 0L;
n = Math.abs(n);
long group = (long) ((Math.sqrt(8.0*n – 1.0) + 1.0)/2.0);
switch ((int) (group & 3L)) {
case 0: return group + (n & 1L);
case 1: return group – ((n & 1L) << 1) + 2L;
case 2: return group – (n & 1L) + 1L;
case 3: return group + ((n & 1L) << 1);
}
return -1;
}
Mr. Olathe, would you mind explaining the process by which you arrived at this solution? This is extremely elegant!
Thank you for sharing!
I just wanted to report a typo in the problem quote where it says “Given an number”.
Ah, thanks very much. Corrected.
Here’s what I came up with. http://snipt.org/nppJ/
This is a brute force solution, as I didn’t see a pattern in these values until I saw the other solutions that had already been shared here. Works for small values, at least.
Quick and dirty bruteforce in Factor: https://gist.github.com/717457