Get Time
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


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.


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

Now let’s see some examples in more detail:

The Introduction is a short paragraph that helps you to understand the context of the problem, it is the less formal part of the problem statement. If you were a robot you will probably automatically discard this part but as a human it makes a lot of sense to read it and helps you to know why you will be solving the problem. Take as example this introduction from the problem StreetSales

“You work as a retail dealer at a certain district, and you sell goods of several types. Each morning you buy goods from the warehouse, set your prices for each type of goods and start your journey to the customers. You visit houses in the district at most once per day, and customers of each house you visit might want to buy some of your goods.”

Here the writer puts you in a real life situation, this not only helps you to understand the next parts of the problem statement but also give you an extra motivation for solving the problem besides the one of winning the contest.
Some contests are actually real life problems and were your solution will be actually used to solve that problem and this gives you and extra extra motivation, you can see examples of that in the following problems: SpaceMedkit,J2KDecode

The introduction will finalize with the exact description of your task. Let’s see some examples:
Problem StreetSales:Your task is to maximize your average daily profit over the time of your work.
Problem Planarity: Your task is to arrange the vertices of the graph so that the number of intersecting pairs of edges is minimized.
Problem EnclosingCircles: Your task is to minimize the sum of areas of the circles you use.
In some problems the writer omits the introduction and goes directly to the task you need to accomplish.

The Implementation section describes in detail the meaning of each parameter and return of each method and how they will be formatted. Take as example the implementation details of the problem EnclosingCircles

“Your code should implement one method placeCircles. int[]s pointX and pointY give you the coordinates of the points on the plane, and M is the maximal number of circles you can use.
You must return the list of the circles you'll use to enclose these points. Each element of your return describes one circle and should be formatted as "CENTERX CENTERY RADIUS" (quotes for clarity only). CENTERX and CENTERY specify x- and y-coordinates of the circle's center, and RADIUS specifies its radius. RADIUS must be strictly greater than 0.1. All values are double precision.”

Here you can see exactly what each input parameter means and how you must format your return.
Sometimes this section starts with the title “Implementation” o “Implementation Details” like in the previous example, sometimes it just follows the introduction like in SubgraphIsomorphism

The Scoring section is an extremely important section, you need to read this section carefully because your score depends on it. Sometimes can be very straightforward like in StreetSales or Epidemic and sometimes it will involve some formula like in PolygonArea

The Test Case Generation Section tells you in detail how each parameter of the input is generated for each test case. This section can contain an algorithm that describes how each test case is generated like in Epidemic , Textures and WatermarkSequences or simply the description of how each parameter is generated from a random distribution like you can see in FactoryManager and EnclosingCircles

The Visualizer section, usually posted in a different page than the problem statement, will have a link to the visualizer program (a .jar file), a link to the source code (a .java file), a pseudocode of what you need to implement in order to use it and a brief description of how to use it and the parameters that it can take. See an example from the problem FlockingBehaviour here

The Definition section is automatically generated and is has the structure of classes and methods that you need to implement.

Example from the Problem Street Sales:

Class: StreetSales
Method: dayTrade
Parameters: int[]
Returns: string[]
Method signature: string[] dayTrade(int[] visitedHouses)

Method: init
Parameters: string[], int[], int, int
Returns: int
Method signature: int init(string[] districtMap, int[] warehousePrices, int C, int S)
(be sure your methods are public)

In some problems you will find the Available Libraries section. This section is autogenerated as well as the definition and has the definition of extra classes and methods available for solving the problem that you can call from your code. You can find an example of this in the problem PolygonArea

Class: Polygon
Method: isInside
Parameters: double, double
Returns: bool
Sample Call: val = Polygon.isInside(x, y);

In this example you will be able to call the method Polygon.isInside(x, y); from your code and the TopCoder server will execute the method and give you an answer.

In Notes you will always find:

-the memory limit,
-the time limit,
-the code size limit.
-the number of example test cases
-the number of test cases for a full submission

Optionally you can find:

-problem statement clarifications: KnightsMoveCipher, Epidemic
-invalid return score: MegaParty
-implementation suggestions: WatermarkSequence
-external sources used to the test case generation: OneTimePad
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.