Sane

The SMAC Challenge is back again for a third time. The number of submissions has increased since the first month, along with the number of people completing the most challenging problems. I hope to see this trend continue into the summer.

I've designed 4 programming challenges 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 recursive and algorithmic 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.

--------------
If you want some practice and exposure to the types of programming challenges you will see here, along with data to test your solutions, please have a look at some of the previous SMAC challenges here at PFO.
--------------

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. The challenges have been attached to the bottom of this post. Submission deadline is July 31, 2008.

At the end of the month, the best solutions, winners, test data, results, statistics, and explanations of all challenges will be posted in separate threads.

The ultimate goals of SMAC are to increase enthusiasm about problem solving and algorithms in computer science, to challenge even the most experienced coders, to increase community involvement in PFO, and to have fun.

Thanks and good luck to all who participate!


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

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, “cipher.in”). Output is written to the specified file (for example, “cipher.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 Advanced level problems.

6) E-mail your submissions to dr.sane@gmail.com with “SMAC” in the subject line before the submission deadline. Also make sure to include your PFO handle!

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 allotted 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: July 31

Attached Files

SMAC_3_July.pdf (125.7 KB, 42 views)

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

OpenLoop

for the Stocks problem, are you looking for the maximum profit single transaction?

Jimbo

Preceeding OpenLoop's question, are you only buying a total of 1000 shares during the day? Or can you only have 1000 at a time? If the former, then the problem seems to end up as OpenLoop asked...

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

Sane

A total of 1000 shares bought during the day. So a single-transaction. Or else the question would be much too difficult for Junior. The question is already pretty difficult if n=1,000,000.

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

Jessehk

There is a particular algorithm that Boost offers that would really help in the Junior class. Do you have Boost installed?

EDIT: Nevermind; ignore the question. I'll keep my post intact for clarity, though.

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

Sane

External libraries aren't allowed, mostly because it's already time consuming enough for me to do all of this. Sorry.

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

Jessehk

Anyone want to share test cases (pipe maps) for the advanced problem?

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

Sane

For senior? Yes, I've got one for you. Hopefully it is not too detailed.

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

Jessehk

I was so proud that I had a working algorithm and now you've gone and crushed my spirits.

Are we supposed to be able to handle that?

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

Sane

It's important to read everything, especially the "notes".

Your solution will get almost everything, but you will need to change something (do some Wikipedia'ing and perhaps reading of #2 SMAC solutions) to get it all.

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

Note To All Seniors:

I realized there's an ambiguity in Senior. The answer should be the number of spaces the water visits. Not the number of pipes it travels through. This is because it does not need to travel through the bottom-right pipe. In fact, there does not even need to be a pipe in the bottom-right corner (water just needs to be able to get there). The sample test data is still correct, but the correction is "number of spaces" as opposed to "number of pipes" for clarity since the water doesn't need to go anywhere once it gets to the bottom-right space.

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