![]() |
#1 |
Free Software Terrorist
Technical Director
|
![]() Rules
Problem #2: Sequence I have a global integer array udg_input and udg_count , udg_input contains udg_count elements, if udg_count is 7 then udg_input has the indexes 0..6 assigned. udg_count is a number between 2 and 200 udg_input contains postive integer numbers not greater than 10000000 . No element appears in the list more than once. (no repetitions) The objective is to make a function: function Consecutive takes nothing returns boolean It returns true if and only if the elements of the array can form a sequence of consecutive numbers. Examples To make the examples, I will use [i0 i1 i2 ...] notation to abbreviate the array. Then Consecutive([4 5 6]) means: ![]() set udg_count=3 set udg_input[0]=4 set udg_input[1]=5 set udg_input[2]=6 set b=Consecutive() All right: Consecutive( [1 2 3 4 5 6] ) : returns true Consecutive( [1 2 3 4 5 7] ) : returns false Consecutive( [6 2 5 4 3 1] ) : returns true Consecutive( [3 2 4 5 6 1] ) : returns true Consecutive( [3 2 4 5 6 1] ) : returns true Consecutive( [102 103 104 105 106 107 108 109 110 111 112 113] ) : returns true Consecutive( [100013 100002 100003 100004 100005 100006 100007 100008 100009 100010 100011 100012] ) : returns true Consecutive( [100013 100002 12 100004 100005 100006 100007 100008 100009 100010 100011 100012] ) : returns false The results
Other submissions:
disqualified:
The solution It was really easy, there are no repetitions, then you can just get min and max values of the array and check if their substraction matches (count-1) There was an alternative solution in which you only get the minimum and the sum then check with Gauss' formula for sum of consecutive numbers. Both solutions ended up being as efficient, but the min/max version has an advantage and it is that with little changes you can make it stop the iteration when you can be sure it is wrong. Otherwise, when 2 persons submitted the same algorithm, little details in the implementation decided who wins. emjrl3 is the only person who used a different, heavier algorithm that didn't get to the op limit/had issues. Extra Kudos go to anitarf for being the first person to submit a O(n) algorithm, the rest eventually updated theirs later. So here is a solution: ![]() function Consecutive takes nothing returns boolean local integer c = udg_count local integer i = c-2 local integer t local integer l = udg_input[c-1] local integer m = l loop set t = udg_input[i] if l > t then if t + c > m then set l = t else return false endif elseif m < t then if l + c > t then set m = t else return false endif endif set i = i - 1 exitwhen i == -1 endloop return true endfunction |
![]() |
![]() |
Sponsored Links - Login to hide this ad! |
|
![]() |
#2 |
Oh for the sake of fudge
Respected User
|
![]() Heh, looks like fun.
__________________Are use lazy types who didn't bother with contest #1 allowed in? |
![]() |
![]() |
![]() |
#3 |
Free Software Terrorist
Technical Director
|
![]() Each quicksilver round is independent of the others.
__________________ |
![]() |
![]() |
![]() |
#4 | |
SpeakerGames.com
|
![]() Quote:
Thats a sequence? How'd you get that? |
|
![]() |
![]() |
![]() |
#5 |
Oh for the sake of fudge
Respected User
|
![]() Rearrange it: 1,2,3,4,5,6
__________________Edit: Good, this one looks like fun(by which I mean easy:)) so I think I will do it. Last edited by Chuckle_Brother : 10-27-2006 at 01:40 AM. |
![]() |
![]() |
![]() |
#6 |
xyzi - our universe
Join Date: May 2005
Posts: 742
![]() ![]() ![]() ![]() |
![]() No big deal, took me some minutes.
__________________ |
![]() |
![]() |
![]() |
#7 |
Oh for the sake of fudge
Respected User
|
![]() Yeah, same. I think Vex is losing it. It being his edge.
__________________Edit: Where be your entry? Even if this is an easy problem you may as well scoop up some rep while you can. Last edited by Chuckle_Brother : 10-26-2006 at 07:05 PM. |
![]() |
![]() |
![]() |
#8 | |
xyzi - our universe
Join Date: May 2005
Posts: 742
![]() ![]() ![]() ![]() |
![]() Quote:
|
|
![]() |
![]() |
![]() |
#9 |
Nonchalant
Respected User
|
![]() Note: The challenge may not be simply solving the problem, but doing so in the fastest possible time. Algorithm efficiency is important.
__________________Chuckle: Check your link, it has a message. The whole point isn't to post your solution for everyone to see, which was an absolutely marvelous idea there, because it's a competition. Everyone is supposed to submit a solution alone, without any help from other people so that it can be judged as a representation of your abilities. |
![]() |
![]() |
![]() |
blu_da_noob |
This message has been deleted by blu_da_noob.
Reason: bah, vex
|
![]() |
#10 |
Free Software Terrorist
Technical Director
|
![]() yes?
|
![]() |
![]() |
![]() |
#11 |
Nonchalant
Respected User
|
![]() We keep doing stuff at the same time which confuses the others' action >.<
__________________So thanks for the 'apparently' psychic answer :P (Question was: can we modify the data in udg_input in our function) Last edited by blu_da_noob : 10-26-2006 at 07:38 PM. |
![]() |
![]() |
![]() |
#12 | |
Dread Lord of the Cookies
Content Director
|
![]() Submitted.
__________________
|
|
![]() |
![]() |
![]() |
#13 |
Procrastination Incarnate
Development Director
|
![]() Submitted.
__________________I had to edit it just a few minutes afterwards, serves me right for not testing it. I hope Vex has the latest version. Anyway, this one was almost absurdly simple. |
![]() |
![]() |
![]() |
#14 | |
Oh for the sake of fudge
Respected User
|
![]() I thought we were supposed to put it in the pastebin, no?
__________________Quote:
Last edited by Chuckle_Brother : 10-27-2006 at 01:39 AM. |
|
![]() |
![]() |
![]() |
#15 |
Free Software Terrorist
Technical Director
|
![]() Yes, you were supposed to put it in the pastebin, but not link it.
__________________ |
![]() |
![]() |
![]() |
Thread Tools | Search this Thread |
|
|