Contest 36 results

[Ryan]

An Olympic-style result in anticipation of Athens 2004...

Gold medal ( for O(n) )

• Alvaro
• Beer Hunter
• Wizard
• Animatronic
• Norman
• Dudi Hatotah

Silver medal ( for O(n^2) or thereabouts )

• DannyBoy

Bronze medal ( for O(n^3) or thereabouts )

• thompsok
• t i l e x

Notes
Thank you all for participating! I ran the contests several times, and every time all the O(n) submissions were very close to one another. In fact, each time I ran it, a different entry won. To the winners, congratulations, and try contest 37 on for size!

[Ryan]

Here's one run through:

Code: Select all

alvaro
------
Test 1: result=7 expected=7 cycles=240
Test 2: result=15 expected=15 cycles=220
Test 3: result=58 expected=58 cycles=312
Test 4: result=187 expected=187 cycles=460
Test 5: result=460 expected=460 cycles=1180
Test 6: result=429 expected=429 cycles=2300
Test 7: result=455 expected=455 cycles=24628
Test 8: result=691 expected=691 cycles=118768
Test 9: result=679 expected=679 cycles=242364
Total cycles: 390472


beer_hunter
-----------
Test 1: result=7 expected=7 cycles=172
Test 2: result=15 expected=15 cycles=208
Test 3: result=58 expected=58 cycles=304
Test 4: result=187 expected=187 cycles=588
Test 5: result=460 expected=460 cycles=956
Test 6: result=429 expected=429 cycles=1744
Test 7: result=455 expected=455 cycles=19520
Test 8: result=691 expected=691 cycles=82500
Test 9: result=679 expected=679 cycles=182092
Total cycles: 288084


DannyBoy
--------
Test 1: result=7 expected=7 cycles=6400
Test 2: result=15 expected=15 cycles=6180
Test 3: result=58 expected=58 cycles=10256
Test 4: result=187 expected=187 cycles=15364
Test 5: result=460 expected=460 cycles=30512
Test 6: result=429 expected=429 cycles=66232
Test 7: result=455 expected=455 cycles=4097148
Test 8: result=691 expected=691 cycles=144333728
Test 9: result=679 expected=679 cycles=590857120
Total cycles: 739422940


DudiHaTotah
-----------
Test 1: result=7 expected=7 cycles=332
Test 2: result=15 expected=15 cycles=196
Test 3: result=58 expected=58 cycles=296
Test 4: result=187 expected=187 cycles=548
Test 5: result=460 expected=460 cycles=912
Test 6: result=429 expected=429 cycles=1692
Test 7: result=455 expected=455 cycles=23592
Test 8: result=691 expected=691 cycles=82820
Test 9: result=679 expected=679 cycles=171284
Total cycles: 281672


fred_bob
--------
Test 1: result=7 expected=7 cycles=188
Test 2: result=15 expected=15 cycles=228
Test 3: result=58 expected=58 cycles=340
Test 4: result=187 expected=187 cycles=464
Test 5: result=460 expected=460 cycles=972
Test 6: result=429 expected=429 cycles=1832
Test 7: result=455 expected=455 cycles=22244
Test 8: result=691 expected=691 cycles=81940
Test 9: result=679 expected=679 cycles=185424
Total cycles: 293632


matrix_overloading
------------------
Test 1: result=7 expected=7 cycles=280
Test 2: result=15 expected=15 cycles=240
Test 3: result=58 expected=58 cycles=464
Test 4: result=187 expected=187 cycles=720
Test 5: result=197 expected=460 cycles=1692
Test 6: result=262 expected=429 cycles=3508
Test 7: result=401 expected=455 cycles=33768
Test 8: result=602 expected=691 cycles=153092
Test 9: result=585 expected=679 cycles=315396
Total cycles: 509160


norman
------
Test 1: result=7 expected=7 cycles=180
Test 2: result=15 expected=15 cycles=212
Test 3: result=58 expected=58 cycles=212
Test 4: result=187 expected=187 cycles=568
Test 5: result=460 expected=460 cycles=852
Test 6: result=429 expected=429 cycles=1628
Test 7: result=455 expected=455 cycles=15560
Test 8: result=691 expected=691 cycles=76736
Test 9: result=679 expected=679 cycles=161020
Total cycles: 256968


wizard
------
Test 1: result=7 expected=7 cycles=236
Test 2: result=15 expected=15 cycles=168
Test 3: result=58 expected=58 cycles=232
Test 4: result=187 expected=187 cycles=388
Test 5: result=460 expected=460 cycles=1044
Test 6: result=429 expected=429 cycles=1824
Test 7: result=455 expected=455 cycles=19080
Test 8: result=691 expected=691 cycles=97240
Test 9: result=679 expected=679 cycles=177980
Total cycles: 298192


zen
---
Test 1: result=7 expected=7 cycles=216
Test 2: result=15 expected=15 cycles=200
Test 3: result=51 expected=58 cycles=280
Test 4: result=187 expected=187 cycles=504
Test 5: result=460 expected=460 cycles=1196
Test 6: result=429 expected=429 cycles=2832
Test 7: result=401 expected=455 cycles=27124
Test 8: result=602 expected=691 cycles=122892
Test 9: result=535 expected=679 cycles=256500
Total cycles: 411744


zmg
---
Test 1: result=263136 expected=7 cycles=256
Test 2: result=4103 expected=15 cycles=184
Test 3: result=58 expected=58 cycles=204
Test 4: result=187 expected=187 cycles=540
Test 5: result=460 expected=460 cycles=992
Test 6: result=429 expected=429 cycles=1960
Test 7: result=455 expected=455 cycles=17992
Test 8: result=691 expected=691 cycles=87760
Test 9: result=679 expected=679 cycles=177176
Total cycles: 287064


thompsok
--------
Test 1: result=7 expected=7 cycles=1152
Test 2: result=15 expected=15 cycles=740
Test 3: result=58 expected=58 cycles=2920
Test 4: result=187 expected=187 cycles=12904
Test 5: result=460 expected=460 cycles=129992
Test 6: result=429 expected=429 cycles=883336
Test 7: result=455 expected=455 cycles=689280940
(timeout)


tilex
-----
Test 1: result=7 expected=7 cycles=1328
Test 2: result=15 expected=15 cycles=804
Test 3: result=58 expected=58 cycles=2932
Test 4: result=187 expected=187 cycles=14480
Test 5: result=460 expected=460 cycles=143032
Test 6: result=429 expected=429 cycles=865332
Test 7: result=455 expected=455 cycles=685741188
(timeout)


[Ryan]

And a sample of winning code, this one from Wizard:

Code: Select all

#include <vector>

int largestSum(const std::vector<int>& list) {
    int sum, maxSum, size;
    size = list.size();
//    if (size == 0) return 0; //Comment if size is guaranteed to be greater than 0
    sum = list[0]; maxSum = sum;
    for (int i = 1; i < size; ++i) {
        sum += list[i];
        if (sum > maxSum) maxSum = sum;
        if (sum < 0) sum = 0;
    }
    return maxSum;
};


[Dudi Hatotah]

Yey! I got the gold medal!

Congratulations to everyone who won the gold medal with me! And congratulations to those who won silver and bronze medals - these are good too.

There are 11 entries so far, and the results will come tomorrow says Ryan who runs the contests.

How come there were 11 entries for this contest when the last "News" item was written on the main page of cpp-home (which was before I submitted), and now there are only 10? How is that possible?...

And a sample of winning code, this one from Wizard:

Code: Select all

#include <vector>

int largestSum(const std::vector<int>& list) {
    int sum, maxSum, size;
    size = list.size();
//    if (size == 0) return 0; //Comment if size is guaranteed to be greater than 0
    sum = list[0]; maxSum = sum;
    for (int i = 1; i < size; ++i) {
        sum += list[i];
        if (sum > maxSum) maxSum = sum;
        if (sum < 0) sum = 0;
    }
    return maxSum;
};


Shouldn't this code work slowly due to using list[i] instead of using a pointer to the list?...
It seems to be one of the best codes, so I wonder how can it work so fast...

Well, at any rate...
Thank you, Ryan, for making this contest.
And I am looking forward for future contests! (I will try to participate in contest 37, too...)

[Alvaro]

Shouldn't this code work slowly due to using list[i] instead of using a pointer to the list?...
It seems to be one of the best codes, so I wonder how can it work so fast...

If list were a pointer to int, list[i] would just be *(list+i). The processor has addressing modes that do that as fast as you can dereference a pointer. The fact that list is a vector doesn't change things much, since the address of the first element of the vector won't change, so the optimizer can load it in a register. And of course, the call to operator[] is inlined.

My code even calls list.size() in each iteration. A decent implementation of vector should make that as cheap as a variable access.

Anyway, I didn't micro-optimize my solution, so probably others were marginally better than mine.

Congratulations to everyone!

[Ryan]

How come there were 11 entries for this contest when the last "News" item was written on the main page of cpp-home (which was before I submitted), and now there are only 10? How is that possible?...

You had to get the right answers to get a medal... There ended up being more than 11.

Anyway, I didn't micro-optimize my solution, so probably others were marginally better than mine.

Perhaps, but marginally is the key word there. I'd rather not encourage that kind of code twiddling.

It seems we're in need of more difficult contests, but maybe not one so heavy as contest 37.. I'll see if I can come up with an intermediate one.

[Blueteeth]

Hey thnx Ryan , but just wanna know why my answers deviate from the expected value in large lists ?!
my code is

Code: Select all

// Made by: MatRiX_OvErLoadiNg
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int LargestSum (vector<int>& list)
{
   int largest = *max_element( list.begin(),list.end() );
   int RunSum=0;
   for (int i=0 ; i<list.size() ; i++)
   {
      RunSum += list[i];
      if (RunSum > largest)
      {
         largest = RunSum;
         RunSum = 0;
      }

      else if (RunSum < 0)
      {
         RunSum = 0;
      }
   }

   return largest;
}



[Guest]

Hey thnx Ryan , but just wanna know why my answers deviate from the expected value in large lists ?!
my code is

Code: Select all

      if (RunSum > largest)
      {
         largest = RunSum;
         RunSum = 0;
      }



That would likely be the RunSum = 0; part of your code. That said, I'm surprised there were problems with determining a winner. If each of the code was run a few thousand time and the minimum of all those times taken a reasonable ranking should have been found. Isn't the minimum time out of all those test cases all we care about?

[Blueteeth]

That would likely be the RunSum = 0;

Yeah i think so , thnx
i don`t know why i put it there anyway !

[Dudi Hatotah]

Shouldn't this code work slowly due to using list[i] instead of using a pointer to the list?...
It seems to be one of the best codes, so I wonder how can it work so fast...

If list were a pointer to int, list[i] would just be *(list+i). The processor has addressing modes that do that as fast as you can dereference a pointer. The fact that list is a vector doesn't change things much, since the address of the first element of the vector won't change, so the optimizer can load it in a register. And of course, the call to operator[] is inlined.

Thanks. I guess the optimizer optimizes much better than I thought.
For some reason, though, loops in which I used list.end() instead of a variable which keeps the list end's address were many times slower. That's weird. list.end() should be fast, and with all those optimizations, I find it odd.

How come there were 11 entries for this contest when the last "News" item was written on the main page of cpp-home (which was before I submitted), and now there are only 10? How is that possible?...

You had to get the right answers to get a medal... There ended up being more than 11.

Oops, I looked at the medals instead of the actual checkings...
There were 12 participants, in the end.
That's alot!
There were only 2 participants on contest 34, then 4 on contest 35... now we're at 12!
Things are looking good!

I'm surprised there were problems with determining a winner. If each of the code was run a few thousand time and the minimum of all those times taken a reasonable ranking should have been found. Isn't the minimum time out of all those test cases all we care about?

Since all the "gold medal" codes were similiar, there is a very minor difference between them. None of them was better than the others significantly.
Thus, if a winner will be determained it will only be due to luck (I consider making the right micro-optimizations for the right compiler and system luck).
Since this contest should be (IMHO) about skill and not about luck, there is no point in determaining the winner in such a way.

[Animatronic]

Hi ryan,

one small thing, me and fred bob are different ppl ,

actually i didnt even put my alias on the submission, but i thought u would get it from the email addy.

and i finally registered, im sure ive registered in the past, oh well

[Zen]

And a sample of winning code, this one from Wizard:

Code: Select all

#include <vector>

int largestSum(const std::vector<int>& list) {
    int sum, maxSum, size;
    size = list.size();
//    if (size == 0) return 0; //Comment if size is guaranteed to be greater than 0
    sum = list[0]; maxSum = sum;
    for (int i = 1; i < size; ++i) {
        sum += list[i];
        if (sum > maxSum) maxSum = sum;
        if (sum < 0) sum = 0;
    }
    return maxSum;
};


Won't this produce wrong results when faced by a list like this: -5, 8, 2, -1, 3, -10?

At least it did when I used it to verify my fixed (?) code (I feel stupid )

Well, it was a fun contest. Thanks ryan

Anyway, I'm off hanging myself, (see results ) if I survive I'll participate in the next contest (not 37)

[Wizard]

Won't this produce wrong results when faced by a list like this: -5, 8, 2, -1, 3, -10?

At least it did when I used it to verify my fixed (?) code (I feel stupid )

Meep! You're right
A simple, one line fix.

Code: Select all

#include <vector>

int largestSum(const std::vector<int>& list) {
    int sum, maxSum, size;
    size = list.size();
//    if (size == 0) return 0; //Comment if size is guaranteed to be greater than 0
    sum = list[0]; if (sum < 0) sum=0; maxSum = sum;
    for (int i = 1; i < size; ++i) {
        sum += list[i];
        if (sum > maxSum) maxSum = sum;
        if (sum < 0) sum = 0;
    }
    return maxSum;
};

There, better.
Actually, now that I've thought of it, probably would have been better to use an iterator. That would be one of the "marginally" faster optimizations, I'd imagine.

[Dudi Hatotah]

Meep! You're right
A simple, one line fix.

Ryan, how come this code didn't fail on your checks?...
At any rate, since this code was declared as a winning one, and got a medal - I suggest to ignore the small bug, and not to take away the medal.

Anyway, I'm off hanging myself, (see results ) if I survive I'll participate in the next contest (not 37)

Don't be too hard on yourself.
Everyone makes some mistakes and some stupid bugs.
I got confused between west and east on the last contest... (Though the wrong code never got to be checked, so in the end a corrected code was checked for me)
Even Wizard made a stupid bug...

[Zen]

Because the highest sequence must consist of the second number while the first must be negative. I guess ryan used pretty large list so he would be able to measure the speed