# Thread: Almost Daily Contest #1

1. ## Almost Daily Contest #1

To start of my tenure as contest master, I'll test the waters with some quick contests. If everyone likes them then I'll make some more on a (hopefully) almost daily basis. I say almost daily because it's not easy coming up with something good and my time is limited.

Please PM me with suggestions and comments so that I can adjust my methods to meet the demand.

The Almost Daily Contest will run for a set amount of time. Anyone may participate by emailing their submission to happyfrosty@hotmail.com with the subject "Almost Daily Contest Entry". Be sure to specify which difficulty level you're solving. There's no need to sign up ahead of time.

Almost Daily Contest #1

Beginner:

Write a function in C or C++:

long double digRev ( int val )

that takes any valid integer and reverses the digits. Your function should work for every valid int from INT_MAX to INT_MIN. Example:

digRev ( 12345 );

This should result in 54321. You will be graded on the following categories:

Speed: Nice and toasty.
Elegance: Easy on the eyes.
Portability: It needs to run wherever I test it.

Intermediate:

A triangle can be formed with side lengths 4, 5, and 8. It's not possible to form a triangle with side lengths of 4, 5, and 9.

You have eight sticks, no three of which can be used to form a triangle. Write a program to calculate the shortest possible length of the longest stick where the shortest stick is length 1.

Correctness: Does it work right?
Speed: Is efficient?
Elegance: Elegant solutions are most welcome

Hints: Triangle Inequality

Write a function in C or low level C++ (no STL):

char findFirstNonRepeat ( char *s );

that returns the first character that is not repeated in the string. For example, in "google", the first nonrepeated character is 'l', in "better", the first nonrepeated character is 'b'.

You may use any number and type of helper functions and data structures, but the algorithm must have a complexity of O(n) or better. Your function will be graded on:

Speed: Pedal to the metal
Elegance: Nifty algorithms are always good

Contest End: Tuesday, August 5, 2003

2. I have submitted my entries for all three.

3. >I have submitted my entries for all three.
Recieved and graded, thank you.

4. You have eight sticks, no three of which can be used to form a triangle. Write a program to calculate the shortest possible length of the longest stick.
I don't understand...The shortest length...So you want us to generate 7 random lengths that can't make a triangle and determine what the shortest length of the eighth would be assuming its the longest?

edit: Ok I think it makes more sense now...are we assuming no decimals?

5. >I don't understand...The shortest length...
Triangle Inequality: In order to be unable to make a triangle with three sticks, one has to be at least as long as the sum of the others.

What I want is a function that takes the number of sticks (in this case 8), where the shortest of them is 1. It then proceeds to calculate the shortest possible length of the longest stick. Keep in mind the rule of triangle inequality when doing this though.

>So you want us to generate 7 random lengths that can't make a triangle
You don't need any lengths at all except for the shortest, which is 1. Your program should be able to calculate the correct answer given the number of sticks and the assumption that the shortest stick is 1.

>are we assuming no decimals?
Use whatever helps you to get the answer, but you don't need decimals.

This task is dreadfully easy if you make the connection, but I'm thinking that maybe I should have swapped the intermediate and advanced tasks.

6. I think I understand now...I think your sneaky little edit made it a bit clearer

7. I would have liked a string size passed on on findFirstNonRepeat() but hey, can't have everything I guess. It would have been easier to do an O(n) anyway. But if I remember my order notation stuff correctly, walking through exactly twice is 2n which is O(n) right? ok, nevermind.

8. My entry is submitted...

9. submitted one, loads a fun, so quickly done, it means a ton.

10. Umm... whats this mean? --> O(n)

11. It's Big O notation, and is a measurement of the speed of the algorithm.

edit: well, sorta. Look it up on Google.

12. Update

The following people have submitted entries and been graded (in order of submission):

Speedy5 (Beginner, Intermediate, Advanced)
JaWiB (Intermediate)

Keep the entries coming, every task can still be won. So far nobody has matched or exceeded my test functions. Who's going to do it? Could it be you? We'll just have to wait and see, but if you don't enter, you won't win.

13. Originally posted by Prelude
Keep the entries coming, every task can still be won. So far nobody has matched or exceeded my test functions.[/B]
Huh? All my functions work and they are pretty partly optimized too (for speed).

14. >Huh? All my functions work and they are pretty partly optimized too (for speed).
You'll see when the winners are posted. Though I will tell you that your intermediate entry didn't solve the right problem. I'll accept an update if you want to send another attempt. This is because my description of the task was vague at best, my appologies.

15. Could you re-explain the intermediate problem? What I got out of it the first time was that there are 8 sticks. You have to use two of those eight for 2 sides of a triangle. The goal is to choose the correct sticks so that the third side is the smallest possible. Coming to think of it, my function does it in a kinda inefficient way...

Ok I think I got the new problem: You have 8 sticks, which one of them is 1. The other 7 can be any numbers in the world, and they can repeat in the list -- just as long as no trio of sticks can make a triangle. What you want is a function that'll find the shortest length so that all 9 sticks still can't make triangles. Right?

Popular pages Recent additions