JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
3.1 Dissecting Problem Statement | Reply
I have tried to keep the same style used by Nickolas here and grab it the part of constraints that was applicable to MM

Problem

Marathon Match problems have template format which consist of several parts and which often has a visualizer tool. Usually the problem statement is large and requires to be read carefully to fully understand it. Knowing the parts of the problem statement will allow you to understand it faster.

Solution

The problem statement consists in a set of sections, given always in the same order. Sometimes can be omitted due to the complexity of problem description and the writer's preferences.

Introduction: usually the first paragraph will give you an introduction to the problem, it will talk about the background of the problem and will give you a general idea of what the problem is about and what you will need to accomplish. Following paragraphs explain in detail what methods your code must implement in order to achieve a valid submission. This section will tell you the methods you will need to implement, the input and output parameters of those methods and the format that those parameters must have.

Scoring: the scoring part explains how your solution will be evaluated, here is explained how your output will be scored for each test case and how your final score will be calculated. It also establishes if the scoring system will be absolute or relative.

Test Case Generation: in this section is defined how the test cases will be generated. It defines exactly how each of the input parameter of each method will be generated, telling you in detail how the algorithm to create each test case works and what probability distributions has been chosen for each parameter of the input.
You can usually omit this section and you will also able to submit a valid solution but you will be given an advantage to other competitors, because you can find very important details here that can help you to improve your solution.

Visualizer: the visualizer tool is a program that allows you to test locally in your computer and obtain the same scores that you would get if you submit a test submission to the TopCoder server. The source code of the visualizer is also provided and this is extremely important because that is the exact and complete definition of the problem expressed in a formal language, Java. If you have any doubt about the problem statement or you want to know minor details that aren’t in the problem statement the source code of the visualizer will give the answer.

Definition: is the exact definition of the Classes, Methods, Parameters of each method, Returns of each method and the Method signature of each class and method that you must implement.

Available Libraries: in some problems you will find that you will need to use available libraries that will be specified in this section.

Notes: here you will find the memory limit, the time limit, the code size limit. You will also find the number of example test cases and the number of test cases for a full submission as well as other notes specific to the problem.

Contraints: provide the constraints on the input parameters.

Examples: provides a list of examples. Usually you can generate this examples by using the visualizer tool with the seeds indicated in each example.
Re: 3.1 Dissecting Problem Statement (response to post by amiune) | Reply
Re: 3.1 Dissecting Problem Statement (response to post by amiune) | Reply
Looks good to me. A few minor fixes:

- parts which you listed as separate ones before Definition are not technically necessary but rather writer-chosen. I'd say that in "Solution" we say that Introduction gives you the actual problem to solve, and can be broken to smaller logical parts as the writer sees fit, and in "Discussion" we expand it to the typical logical parts used.

- The omitted parts are due to complexity of problem description (and somewhat writer's preferences), not problem itself.

- Visualizer isn't usually in Java, it's always in Java - visualizer is created from MPSQAS solution (or vice versa), and MPSQAS works only with Java.

- Don't forget to add Available Libraries to discussion - autogenerated as well.

- On the other hand, we don't need much detail about Constraints section, as it's often neglected and never describes everything in such detail as in Algo.

- It would be really good to stress the differences and similarities with Algo statements - MM Introduction tends to be less formal and sometimes relies on visualizer for details, MM Notes are usually present, though limits and numbers of tests are related not to the problem itself but rather to organizing the testing process, MM Constraints give less detail, and MM examples are not annotated and tend to be pretty useless without the visualizer.
Re: 3.1 Dissecting Problem Statement (response to post by Nickolas) | Reply
Constraints list the limitations that apply to input parameters as well as your solution’s answer. Due to the complexity of the description of Marathon Matches problems it is possible that the author omits some constraints or doesn't describe them in complete detail, in those cases you can always relay on the visualizer source code.

It worth noting that compared with Algorithm problem statements Marathon Matches Introduction tends to be less formal and sometimes relies on visualizer for details, Notes are usually present, though limits and numbers of tests are related not to the problem itself but rather to organizing the testing process, Constraints give less detail, and Examples are not annotated and tend to be pretty useless without the visualizer.

A final recommendation: be sure to read the problem statement very carefully, it seems obvious but this is the most important step, take your time and read the problem statement carefully and entirely. Read the problem statement as many times as you need to perfectly understand what is the task that you need to accomplish is and how it will be scored.
Re: 3.1 Dissecting Problem Statement (response to post by Nickolas) | Reply
Thanks for the feedback, agree with all, I wanted to add some comparison with algo but didn't know if it was ok. I think I've patched those minor issues now.
RSS