Sane

I've been thinking about doing this for a while now, and on queue with Grich's post, I've decided to go ahead with it.

I've designed 4 problems ranging from beginner to advanced difficulty.

Beginner and Junior are for those who haven't had much experience with contest-style challenges, but can still think logically and write good solid code.

Senior and Advanced are for those experienced with writing more complicated algorithms.

Guru will be the trickiest difficulty level which will measure up to the tough IOI and ACM problems. I have not included one in this problem set. I will save them for later once I see what skill level people enjoy doing.

But even for any difficulty, it will be challenging to attain 100%. You must make your solution work for every possible test file. And these test files will not be revealed until after the competition. So test your code inside and out until then.

Please read every rule. Submission deadline is May 31, 2008.

The challenges have been attached to the bottom of this post. As the month progresses, due to necessary clarifications, the rules and/or questions may be updated at any time. Sorry for any inconvenienes.

Thanks and good luck to all who participate! I hope this goes well.


-----------------------------------------------------------------------------------

Rules and General Information

1) Do not post or share any solutions!

2) You may ask questions and give simple hints and tips in the thread provided each month.

3) Input is always in the format specified in the problem, and will be read from the specified file (for example, “move.in”). Output is written to the specified file (for example, “move.out”).

4) You may use any language, but only C/C++/Java/Python will be graded by me (see rule 9).

5) Each solution must take no more than 10 seconds to execute. Also, your program must never use more than 64 MB of stack space (unless otherwise specified). These constraints should only be considered for Senior and Guru level problems.

6) E-mail your submissions to dr.sane@gmail.com with “SMAC” in the subject line before the submission deadline.

7) You have a month to write your solutions, and submissions are only made final after the deadline cutoff. Before then, if you would like to update your submission, just make sure you e-mail it to me and let me know.

8) It is recommended that you start at “Beginner” to familiarize yourself with the problems, and then work your way up. Even the most experienced programmers may find the last problem(s) very challenging.

9) Sometime after the deadline, results will be publicly posted showing how well each program performed on larger and more tricky data files (not the given sample data). Also, solutions and an analysis of each problem will be given. If your program was not written in C/C++/Java/Python, I will not be able to grade your submission. In this case, I will give you the test files and expect you to report back with your own score within the next couple days.

10) Every solution’s score will be based solely on its ability to solve the unknown test files. Points are awarded for every perfectly matching output file. No points are awarded for clarity, style, presentation, or execution speed (within the alloted time).

11) Don’t take the results (or expectations) of these challenges seriously. The point of this is to learn and have fun. If you would like me to refrain from posting your results or solutions in the analysis thread after the contest, please specify that in your submitted e-mail(s). Good luck and happy coding!

Submission Deadline: May 31

Attached Files

	SMAC_1_May_03.doc (54.0 KB, 32 views)
	SMAC_1_May_03.pdf (110.9 KB, 51 views)

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jessehk

PDF's instead of DOC's please.

EDIT: Also, while I've been programming for a while, I haven't had a lot of competition experience. I'll probably write the first two "classes" only.

__________________
Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

titaniumdecoy

I'm impressed. It looks like you put a lot of work into this, Sane. I'll take a closer look when I get the chance.

I converted the Word document to a PDF for those who prefer that format.

Attached Files

SMAC_1_May_03.pdf (110.9 KB, 24 views)

Sane

Thanks Titanium. That makes it look much better.

I'd be grateful if a mod could add that attachment to my first post. Or better yet, could a mod allow me to have editing privileges over 30 minutes for that one post?

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jimbo

To mods: Actually, could we get our own subforum for this, and have Sane as a moderator (kudos for putting forth the effort btw). That way we can have our own little corner to discuss these competitions

__________________
<insert disclaimer here>
<insert shameless plug for Visual Studio here>

Jessehk

Sane, I have a question. In the beginner class, you state that

Which to me implies that n must decrease by one except when it is prime. But your sample data seems to indicate otherwise.

For example,
You say a start of 2 2 should result in a chain of 2, 1.
However, 2 is prime. So it seems to me that the sequence should be 2 5.
When I change the rule to decrease by 1 only when n is prime, I can replicate your test case. Can you clarify please?

__________________
Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Sane

Sorry, I see why that's misleading. That sentence was intended to finish the sentence from rule 2.

It was to be read like:

"If n is positive, n will increase by 3, unless n is prime, then n must decrease by 1."

You are correct. Follow the test case. It should be "n must decrease by 1 if n is prime".

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Jessehk

Ah, sorry. One more question.

Can I write C99 (with stuff like stdbool.h, variables declared inside for loops, etc) or should I stick with C89?

Oh, and thanks for putting so much work into this, Sane. It's great.

__________________
Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Sane

I'm not going to be picky. If something doesn't compile, or something doesn't even work on the simple test files, I'll try to fix the minor problem. Same goes with typos and little output format mistakes. I won't count those as bad solutions. I want to keep this fun, and the rules lenient. Feel free to use C99, but avoid using anything that will be too difficult for me to test.

Thanks, glad you guys like it.

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Freaky Chris

This looks like you have put alot of effort into it and i hope i can get my tiny brain around it and come up with some form of a solution to the easy one's lol.

But it does look fun.
Chris

__________________
Steven Skiena - Algorithms