Sane

PDF Updated: July 12 6:00 PM (GMT -6). Beginner and Senior clarifications. Guru input/output modified.

Problem Update: You may assume that Red Beard always has a way home. See Post #17.

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

Welcome back to the 9th month-long Algorithms Challenge.

SMAC is a set of programming challenges, written and released on a monthly basis, with the ultimate goals to increase enthusiasm about problem solving and algorithms in computer science, provide a convenient environment for learning enriched material, to challenge even the most experienced coders, to increase community involvement in PFO, and to have fun.

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

Past SMAC Challenges
Past SMAC Results
Past Beginner Solutions
Past Junior Solutions
Past Senior Solutions
Past Advanced Solutions
Past Guru Solutions
Past Time Trial Solutions

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

Newcomers should read the "How to Write a Solution". All returning veterans can skip most of this post.

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. Advanced requires a deeper level of problem solving skills.

Guru is the trickiest difficulty level, which measures up to the IOI and tough ACM problems. If you can do this level, you should consider winning some other competitions.

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 August 1, 2009.

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.

Thanks and good luck to all who participate!

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

Notes to New and Returning Participants

Rule (3) has been changed. No file input/output. Now it is standard input/output.

Rule (6) has been elaborated. Send your source code!

See the new section “How to Test a Solution” for some helpful information.

The usage of cin/cout in C++ is slow when used to read and write very large files. If doing Senior, Advanced, or Guru, it is highly recommended that you use scanf/printf for file IO with large files.

Do not assume any input files end with a newline, or end without a newline.

Please end your output to all files with a newline ('\n') after the last “meaningful” character (this makes it easier for the auto-judger). See the code under “How to Write a Solution” for an example.

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

How to Write a Solution

In a typical SMAC there are 5 programming challenges ranging from “Beginner” to “Guru”.

Each challenge is proposed in the exact same format. Here is a simple challenge, involving calculating the sum of two integers, and some code demonstrating how to write a solution.


Example Challenge:

Problem Statement:

You will be given two integers, a and b, and you are to report the sum of the two integers.

Input Format (Standard Input):

On the first line is the first integer, a (1 < a < 1,000).
On the second line is the second integer, b (1 < b < 1,000).

Output Format (Standard Output):

On a single line, output the sum of the two integers.

Sample Input:

5
7

Sample Output:

12



Example Solution in C:


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

How to Test a Solution

Learning how to test your solution is a very important tool in both software development and problem solving. Many mistakes that people have made in SMAC are the result of not making good test files to validate their solutions. This is often half the challenge.

At the end of the month I will be making anywhere between 5 and 30 test files for each problem to grade your submission. Some of these will be randomly generated, and some will be testing specific “corner cases” that you may not expect, yet were never ruled out by the problem statement. These test cases are hidden until after the submission deadline, because that is how it works in the real world. Your user will specify program requirements and the input/output format, but very rarely will your user tell you the exact input to your program in advance. Nevertheless, this does not prevent you from being able to correctly test your own solution before submission.

To run your solution on a test case, simply run the following commands from the command-line:


If you are not using Unix, then you will not have access to the diff command. Use FC on Windows, compare the two files manually, or write your own diff.exe.


To create test files, I have identified three different tiers of testing, ordered as follows:

1. Testing by Hand

The first thing you should always do, before writing any code, is devise some test cases manually and solve them by hand. This will not only get you thinking about the problem, but also give you some simple test cases and corner cases to sanity-check your solution.

2. Fast-Slow Checking

Write a computer program to generate a greater variety of test cases. Then write a slower solution (sometimes brute force) to solve each test case by letting it run overnight. This should give you a correct test suite to compare your faster solution against.

3. Speed, Memory, and Stability Testing

If you are good, you will be able to recognize the test cases that make your solution run the slowest. You can almost be sure that these are in the official test suite. Generate them, and then make sure they run within the time limit. Generate other tests which maximize the constraints listed in the problem statement, to make sure that your solution runs within the memory limit and does not encounter any runtime errors.


Spotting corner cases and recognizing worst case tests takes experience. Writing a correct fast-slow checker can also be very difficult. So keep practicing and good luck!

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

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 always obeys the format specified in the problem, and will be given through standard input (normal console input). Output is written to standard output (normal console output).

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 20 seconds to execute (unless otherwise specified). Also, your program must never use more than 64 MB of memory (unless otherwise specified).

6) E-mail your source code to dr.sane@gmail.com with “SMAC” in the subject line before the submission deadline. Remember 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 hidden 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. This contest is intended to be very difficult. The point of this is to push your brain to its limit, but also learn and have fun. So, if you would like me to refrain from posting your results or solutions in the analysis thread after the contest, please note that in your submitted e-mail(s). Good luck and happy coding!

12) I encourage the sharing of test files and the open discussion of broad principles and topics mentioned in each problem! However, in anticipation that this might get out of hand, please only share trivial test files (something that anyone could have easily randomly generated), and please do not explain why your answer to a trivial test file must be the correct answer. Finally, please do not discuss any specific aspects of a problem or possible test files which could give something away-- even if you are simply seeking clarification (if you aren't sure, e-mail me!).

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

Submission Deadline: August 1

Attached Files

SMAC_9_July.pdf (299.1 KB, 50 views)

__________________
|¯_/ . /¯\ . |¯\|¯| |_¯ PFO's Folding@Home Team
/¯_| /_/\_\ |_|\_| |__ Sane's Monthly Algorithms Challenges

S.I

Sane, I read it good, and started at beginner problem. I have to ask, There are so many ways to get from point a to point b, Does only the shortest way counts, or any way is good ? I am asking this because I'm not sure should I use some Graph theory algorithms like Dijaktra's or Floyd Warshall, or just move around a matrix trying to find that letter ...

Tnx.

__________________
--
Mathematics is the language of nature.

LarryC

I agree; it is unclear. It appears that one can move only up, down, left and right. Wouldn't someone go roughly in a straight line in which case Pythagoras' theorem would be useful? IE: the time taken to go from A to W would be .

Sane

Infer from the examples: Only up, down, left, and right. Also, the shortest path. If you infer "shortest path algorithm" from "shortest path", though, you are making things 100x more difficult than they need to be.

Rewriting the calculation to use Pythagoras' theorem would be trivial, and wasn't done to avoid nitpicking over floating points.

__________________
|¯_/ . /¯\ . |¯\|¯| |_¯ PFO's Folding@Home Team
/¯_| /_/\_\ |_|\_| |__ Sane's Monthly Algorithms Challenges

Sane

Guru has been altered. Apologies to anyone who had already started it.

__________________
|¯_/ . /¯\ . |¯\|¯| |_¯ PFO's Folding@Home Team
/¯_| /_/\_\ |_|\_| |__ Sane's Monthly Algorithms Challenges

Arla

Once again Sane, thanks for running this.

__________________
I can remember, back in '22
They changed the law - came knocking on the door
In that same moment, the broadband seemed to go..
Phones all dead. Gone dizzy in the head..

Arla

Nevermind, going to go with my gut instinct

__________________
I can remember, back in '22
They changed the law - came knocking on the door
In that same moment, the broadband seemed to go..
Phones all dead. Gone dizzy in the head..

Sane

Unfortunately I cannot see past revisions of posts.

If you were confused about something in a problem statement, you might as well ask in case others were wondering about it too?

__________________
|¯_/ . /¯\ . |¯\|¯| |_¯ PFO's Folding@Home Team
/¯_| /_/\_\ |_|\_| |__ Sane's Monthly Algorithms Challenges

Sane

In case any of you get bored and finish early on, there is an algorithm to Traffic Lights that will take <= 0.5 seconds on any test file.

__________________
|¯_/ . /¯\ . |¯\|¯| |_¯ PFO's Folding@Home Team
/¯_| /_/\_\ |_|\_| |__ Sane's Monthly Algorithms Challenges

Arla

Feh, can't even do senior this month (yet, I'm sure I'll get somewhere!) so getting bored and doing an that for guru, well, will only work if I happen to figure that out as my single solution to Guru.

__________________
I can remember, back in '22
They changed the law - came knocking on the door
In that same moment, the broadband seemed to go..
Phones all dead. Gone dizzy in the head..