Programming Challenge

[Jonathan Birch]

For those of you who don't know, the ACM holds a yearly international programming competition that SIUE participates in. The last couple years we've had some difficulty finding interested students though, and we've actually had to almost conscript people in order to get together the six people needed for two teams.

So, the other day Andrew Garrison sent me a link to this problem on a site set up by the ACM to allow people to practie for the competition. It struck me as being particularly interesting, so it thought I would post it here in case it might inspire some interest in the contest itself:

http://acm.uva.es/p/v1/108.html

I haven't actually tested it, but I'm pretty certain I've figured out an efficient solution to this problem. Anything that you can come up with that will run in polynomial time should be good enough though. Feel free to post any solution ideas you have (undrgraduate students only). It would be neat to get a discussion going about this, and I could post more problems later if people are actually interested.

And if you're actually interested in the contest, contact Dr. Bythe. The regional competitions are generally held in mid fall, and the last couple of years we've been organizing teams around the beginning of the fall semester.

[William Grim]

I took a look at this as well.  It's a good problem and has a much more straightforward answer than it first appears.  I didn't implement the solution either, but I did try it out on paper.  There is one trick that I did to make finding the answer a scaling factor faster, which may be the difference between getting a correct solution or not on ACM.

Also, I encourage others to take part in the ACM competitions.  It's really fun and is a good way to test your abilities and teamwork.

[EvilAndrew]

I implemented two solutions.  The first one ran in O(N^4) time and it took 6 of the maximum 10 seconds.  So I tried again and made one that runs O(N^3).  This ran in a small fraction of a second so it should be safe from the notorious re-judging that seems to kill efficient but not completely correct solutions.

I am eager to hear if anyone can write one that runs faster.  Since my 'N' is the edge length of the number square you should not be able to run faster than O(N^2) because it takes N*N operations just to read in the data.

P.S. You can submit your code to the Judge here (UVa Online Judge) and you can see the problems I have answered here (Andrew Lamonica’s ACM Statistics)

[EvilAndrew]

Regarding the ACM competition, I highly encourage any students who might be interested to join the team (contact Dr. Blythe).  The first year I competed (2000 I think) my team solved only one problem (of 6) but we got better and better and by the last year I competed we solved 5 (of 7) problems and had won the local competition twice and placed 8th (of about 110) in the region. The team with Jonathan Birch (greyblue) did even better placing 5th in the region.

I am sure that any of the past team members would be glad to tell you about the competition if you are interested.  So don’t let lack of knowledge about he ICPC be a deterrent to your participation.

One side note, if you cannot solve the problem that greyblue posted here don’t let that discourage you from competing.  Many of the problems used in past competitions are much easier to solve than it is.  

[Jonathan Birch]

I have to admit that the first "solution" I had for this doesn't work...

I've thought about it more since then though, and it is possible to do this in O(N^2) time (I might post how to do that a bit later). Also, I expect Andrew is right about the O(N^4) time solution being too slow. You usually can't get away with that sort of answer on these.

OK, the best solution I have is O(N^3), I wasn't thinking about that quite right...

[William Grim]

I'd like to see your solution some time.  Mine ended up not being too great either... but it seemed good at first.

[William Grim]

Well, I found out I was on the right track.  I know this, because since I don't have much time right now I looked up a solution to it, and I wasn't far away.

I would like to say I did have the O(N^4) solution.

[Alex Towell]

for (int x = 0; x < height; x++) {
    for (int y = 0; y < width; y++) {
        for (int h = 1; h <= height - x; h++) {
            for (int w = 1; w <= width - y; w++) {
                sum = add(array, x, y, w, h);
                if (sum > h_sum)
                    h_sum = sum;
            }
        }
    }
}

The add function returns the rectangular sum of array elements starting at x, y and ending at x+h, y+w.

This would appear to be a really inefficient solution.

Alex Towell
Student, SIUE

[EvilAndrew]

Spinoza’s solution is somewhere between O(N^4) and O(N^6) depending on what his â€Ã...“add()â€Ã, function does.  An O(N^4) solution to this problem can be written this way using dynamic programming to calculate the information needed to quickly ( = constant time ) produce the sums returned by the add() function.  The dynamic programming solution creates an array of partial sums as the data is read in and then uses these sums to produce an arbitrary sum when needed.

However, this solution does not really use the â€Ã...“hintâ€Ã, given at the beginning of the problem.  The real trick to making a fast version of this program is to condense the 2-Dimensional problem into 1-Dimensional problems.

P.S. Anyone who wants to see how to do "add()"  in constant time can e-mail me.  I don’t want to post it here because despite the fact that it is not the best solution the online judge will take an efficient O(N^4) solution.

[Alex Towell]

>>Spinoza’s solution is somewhere between O(N^4) and O(N^6) depending on what his â€Ã...“add()â€Ã, function does.<<

If my understanding of big O is correct, it's O(N^6). The add function has two for loops in it.

>>An O(N^4) solution to this problem can be written this way using dynamic programming to calculate the information needed to quickly ( = constant time ) produce the sums returned by the add() function.  The dynamic programming solution creates an array of partial sums as the data is read in and then uses these sums to produce an arbitrary sum when needed.<<

Correct me if my interpretation is wrong. By this, do you mean create sums for regions of the array and adding those pre-calculated sums whenever possible instead of summing by adding each individual element each time?

>>However, this solution does not really use the â€Ã...“hintâ€Ã, given at the beginning of the problem.  The real trick to making a fast version of this program is to condense the 2-Dimensional problem into 1-Dimensional problems.<<

I had been thinking about that. If nothing else, simply having to use multiplication to get to elements in a 2D array would seem to make it worthwhile to condense it to 1D. But I'm sure there are far greater advantages to doing it this way than I'm able to realize in my ignorance.

When I have the time, I'm going to try to implement the 1D approach, then, if I'm feeling spunky, see if I can also do the sum of sums thing.

[Jonathan Birch]

To be fair, getting the O(N^3) solution to this almost requires that you've taken CS456, although I've heard that they sometimes teach the relevant concept in 240/340.

So, to expand on Andrew's hint a bit, try finding an efficient solution to this problem first:

Given an array of length N consisting of integers between -100 and 100, find the sum of the consecutive sub-sequence with the highest sum. So, for example, given

-1, 5, 27, 2, -35, 14, 9

The sub-sequence [5, 27, 2] has the highest sum, so the answer would be 5 + 27 + 2 = 34.

[blacklee]

So, to expand on Andrew's hint a bit, try finding an efficient solution to this problem first:

Given an array of length N consisting of integers between -100 and 100, find the sum of the consecutive sub-sequence with the highest sum. So, for example, given

-1, 5, 27, 2, -35, 14, 9

The sub-sequence [5, 27, 2] has the highest sum, so the answer would be 5 + 27 + 2 = 34.

max_sum = array[0]
last_sum = array[0]

for (int i=1; i < n; i++)

     if (last_sum > 0)
          last_sum=last_sum+array
     else
          last_sum = array

     if (max_sum < last_sum)
           max_sum = last_sum

//////////

Is this right? If yes, give me another hint please. How do I use it to solve the original 2D problem?  :-?

[blacklee]

I think I figured it out!

I want to code it and submit to the Judge, but I haven't used ACM for some time and lost my password. Their password and ID recovery system is not working at this time.

Andrew, are you using C++ ? What is the compiler most compatable with the Online Judge and where can I download it? I only have Visual Studio 2003, and I remember some things can compile in VS, but not in ACM's system.

Speaking of Visual Studio, I have a question. Are there any problems with running VS 2003 projects in VS 2005? (VB and C++).

[R. Andrew Lamonica]

Question 1:[/u] I use Visual Studio 2005, but I have used many versions of g++ and Visual Studio to submit to the online judge.  They seem to use g++ so your code should compile with it to be sure.  The differences that have popped up seem to be of the following:  

(a) Some versions of Visual Studio have a â€Ã...“for-loop scope problemâ€Ã,.  You can avoid thisproblem my declaring your iteration variable before the for-loop (Example: int i; for(i=0; i<10; i++) should be used instead of  for(int i=0; i<10; i++); if you want both g++ and VS to act the same).
(b) Templates classes act diffrent in some versions of Visual Studio.  This should not be a big deal for these competitions, however, since template classes are mostly just for reusability.
(c) Do not use char* itoa(int,char*,int) use sprintf() or a variant instead. (I think even new versions of visual studio have scrapped/renamed this function.)
(d) Manually #include Visual Studio includes it when you #included but g++ does not.  In fact, it is a good idea to manually include all the headers that you use functions from.  You can use the MSDN Library or a c++ reference book to see where each function resides.
(e) Do not assume that arrays or constants have a starting value.  This is good practice anyway, but it is a particularly bad mistake to assume an initial value when writing cross-platform software because the implementation’s initial values are different.
(f) Beware of 64 bit integers.  In g++ they are called â€Ã...“long longâ€Ã, in Visual Studio version they can have many different names.  In most ACM problems, if you feel that you need to use a 64 bit integer to avoid an overflow then you should probably rethink the problem.
(g) There are probably other differences I have forgotten, but I believe that the online judge gives you the compiler errors.  This is not the case with the real judges at the ACM competitions.

[R. Andrew Lamonica]

Question 2:
I have not had many problems making that perticualr switch.  However, I only write code in Visual Studio using  c++ and c# so I am not sure about vb.NET.  The c# code occasionally needs a little upgrade to use .NET 2.0 but even complicated programs like my Game Playing Interface required very few changes to make that switch.