Almost Daily Contest #1

[vasanth]

i submmited the first and the third.. but did not understand the 2nd question..

[Prelude]

>Could you re-explain the intermediate problem?
You have 8 sticks of any length (though you can assume that the shortest sticks possible are 1. A triangle cannot be made with any three of these 8 sticks if the length of the third is greater than or equal to the sum of the first two. Find the shortest possible length of the longest stick out of all 8.

[vasanth]

could you give an example please.. it is still confusing.. i dont get it.. the question


edited
--------

and what ever the question menas.. it is better you also give the function prototype......

[Prelude]

>could you give an example please..
I'm afraid I can't do that. Any example would tell you what the solution is, that's why I didn't give one to begin with.

>it is better you also give the function prototype......
Whatever you want is fine, but if you need a function definition:

int stickLen(int n); /* Variant number of sticks */

or

int stickLen(void); /* Hard code the number of sticks */

[FillYourBrain]

hmmm... not even matched? I wonder why. I couldn't think of anything faster. But then I did only spend 5 minutes on it. Oh well. First contest anyway.

[Prelude]

>hmmm... not even matched? I wonder why. I couldn't think of anything faster.
I used a sneaky optimization, you'll see when I post the results. I'll include my test functions. Your mileage may vary though depending on the profiler, compiler, and settings you use.

[FillYourBrain]

is inline assembler allowed?

[-KEN-]

Having a complexity of O(n) would mean that it only loops through the entire string once, right?

If so, darn. What I was thinking of would have to loop twice.

[Speedy5]

No, it can loop over it twice and still be O(N). Remember that the coefficients are taken off.

[FillYourBrain]

-KEN-, your algorithm is no doubt the same as mine which is O(n) even though it steps through 2 times. Prelude apparently has an optimization on that or a single loop method ( I couldn't come up with one ).

[ygfperson]

Mine's pretty efficient... I hope. I loop through once and then through a list of the possible characters. It can never go up to 2n, but it has to be at least n.

Meh... I'll work on the other two.

[FillYourBrain]

well I guess we're giving too much of our algorithms away, so we should probably shut up about that.

I want to just say thanks to Prelude for taking over the contest master role. I haven't done this before but it looks like it should be a lot of fun.

[ygfperson]

Question on the beginner:

for the prototype, I assume you mean just a 'long' and not a 'long double'?

[*ClownPimp*]

long double because the reversed number might overflow an int or a long

[ygfperson]

Hmm... too bad I submitted mine with just a long.