-
Notifications
You must be signed in to change notification settings - Fork 0
/
Problem_Format_2012.mw
308 lines (241 loc) · 14.3 KB
/
Problem_Format_2012.mw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
=== Overview ===
This document describes a standard for distributing and sharing problems for algorithmic programming contests. It is primarily designed for the ACM ICPC but is applicable also to other contests.
All problems must have a "short name" consisting solely of lower case letters a-z and digits 0-9. All files related to a given problem are provided in a directory named after the short name of the problem.
All file names must match the following regexp
[a-zA-Z0-9][a-zA-Z0-9_.-]*[a-zA-Z0-9]
I.e., it must be of length at least 2, consist solely of lower or upper case letters a-z, A-Z, digits 0-9, period, dash or underscore, but must not begin or end with period, dash or underscore.
All text files for a problem should be UTF-8 encoded.
=== Problem Metadata ===
Metadata about the problem (e.g., source, license, limits) are provided in a file <tt><short-name>/problem.yaml</tt>. The format of this file is defined in the Appendix.
=== Problem Statements ===
The problem statement of the problem is provided in the directory <tt><short_name>/problem_statement/</tt>.
This directory must contain one LaTeX file per language, named <tt>problem.<language>.tex</tt>, that contains the problem text itself, including input
and output specifications, but not sample input and output. Language must be given as an ISO 639-1 alpha-2 language code. Optionally, the language code can be left out, the default is then English.
A template will be provided that \imports this file as well as the sample input
and output. The format of the problem statement is described in [[Problem Statement Template]]. Files needed by this file must all be in
<tt><short_name>/problem_statement/</tt> , problem.tex should reference auxiliary files as if the
working directory is <tt><short_name>/problem_statement/</tt>.
=== Test data ===
The test data are provided in subdirectories of <tt><short_name>/data/</tt>. The sample data in <tt><short_name>/data/sample/</tt> and the secret data in <tt><short_name>/data/secret/</tt>.
All input and answer files have the filename extension .in and .ans respectively. Optionally a text file (with filename extension .txt) describing the purpose of an input file may be present. Input, answer and description files are matched by the base name.
=== Example Submissions ===
Correct and incorrect solutions to the problem are provided in a directory <tt><short_name>/submissions/</tt>. The submissions/ directory has subdirectories corresponding to the judgement that the programs are supposed to receive:
# <tt>submissions/accepted/</tt>: Solutions correctly solving the problem
# <tt>submissions/wrong_answer/</tt>: Submissions producing incorrect answers
# <tt>submissions/time_limit_exceeded/</tt>: Submissions that are supposed to be too slow
# <tt>submissions/run_time_error/</tt>: Submissions that are supposed to crash
Every file or directory in these directories represents a separate
solution. Same requirements as for submissions with regards to
filenames. It is mandatory to provide at least one accepted solution. Everything else is optional, and empty subdirectories can be omitted.
==== Input/Output Methods ====
Submissions must operate in such a way that they receive problem input data on their standard input stream, and write to their standard output stream.
=== Validators ===
==== Input Format Validators ====
Input Format Validators, for verifying the correctness of the input files, are provided in <tt><short_name>/input_format_validators/</tt>. They must adhere to the [[Input format validator]] standard.
==== Output Validators ====
Output Validators are used if the problem requires more complicated output validation than what is provided by the default diff variant described below. They are provided in <tt><short_name>/output_validators/</tt>, and must adhere to the [[Output validator| Output Validator]] standard.
==== File Conventions For Validators ====
A validator is either a file or a directory. A validator in the form of a directory may include two scripts "build" and "run". Either both or none of these scripts must be included. If the scripts are present, then:
* validator must be compiled by executing the build script.
* the validator must be run by executing the run script.
Otherwise, the validator will be compiled and run as if it was a submission (except that it is given the command-line arguments specified in problem.yaml, if there are any).
==== Default Validator Capabilities ====
The default validator is essentially a beefed-up diff. In its default mode, it
tokenizes the files to compare and compares them token by token. It supports the
following command-line arguments to control how tokens are compared.
{| class="wikitable"
! Arguments !! Description
|-
| <tt>case_sensitive</tt> || indicates that comparisons should be case-sensitive.
|-
| <tt>space_change_sensitive</tt> || indicates that changes in the amount of whitespace should be rejected (the default is that any sequence of 1 or more
whitespace characters are equivalent).
|-
| <tt>float_relative_tolerance ε</tt> || indicates that floating-point tokens should be accepted if they are within relative error ≤ ε (see below for details).
|-
| <tt>float_absolute_tolerance ε</tt> || indicates that floating-point tokens should be accepted if they are within absolute error ≤ ε (see below for details).
|-
| <tt>float_tolerance ε</tt> || short-hand for applying ε as both relative and absolute tolerance.
|}
When supplying both a relative and an absolute tolerance, the semantics are that a token is accepted if it is within either of the two tolerances.
When a floating-point tolerance has been set, any valid formatting of floating point numbers is accepted for floating point tokens. So for instance if a token in the answer file says <tt>0.0314</tt>, a token of <tt>3.14000000e-2</tt> in the output file would be accepted. If no floating point tolerance has been set, floating point tokens are treated just like any other token and has to match exactly.
=== Determination of Time Limit ===
The execution time limit for the problem is determined as follows. First, all the provided <tt>accepted/</tt> solutions are run. Let ''t<sub>max</sub>'' be the maximum running time of these solutions on any of the input files. The time limit is then set to be ''t<sub>lim</sub>'' = ⌈''t<sub>max</sub> · M''⌉ where ''M'' is the value of the time multiplier parameter from the [[#limits|limits configuration of problem.yaml]].
Furthermore, it is required that all of the provided time limit exceeded submissions run for at least ''t<sub>lim</sub> · S'' seconds, where S is the value of the time safety margin parameter from the [[#limits|limits configuration]].
=== Verification ===
Solutions or validators in languages that are not supported by the CCS
should be ignored and a warning to that effect shown.
Verification Checks (in order)
# Check files (all files present as required + check problem.yaml)
# Check compile (check that all programs compile)
# Check input (run input validators)
# Check solutions (run all solutions check that they get the expected verdicts)
Warn if:
there are no *.in in data/sample/
Error if:
there is no problem.yaml
there is no problem statement (i.e., a problem*.tex file)
any value in problem.yaml is invalid
there are no *.in in data/secret/
there are .in files without corresponding .ans files in data/*/
there are .ans files without corresponding .in files in data/*/
there are no solutions in submissions/accepted/
there are no validators in input_format_validators/
validator begins with "custom" and there are no validators in output_validators/
there are validators in output_validators/ and validator does not begin with "custom"
any validator (input format or output) does not compile
For each *.in in public_data and judge_data:
For each validator in input_format_validators/:
If the validator does not accept the input file: Error!
For each solution in test_submissions/accepted/:
For each *.in in data/*/:
Run the solution on the input
For the built-in validator if corrector is "diff" or each validator in output_validators/:
If the validator does not accept the output of the solution: Error!
Let t be the longest time any of the solutions ran on any of the inputs.
For each solution in submissions/time_limit_exceeded/:
For each *.in in data/*/:
Run the solution on the input for at least t * time_limit_safety_margin seconds.
Let t_slow be the shortest time any of the solutions ran on any of the inputs.
If t_slow is less than t * time_limit_safety_margin: Error!
For each solution in submissions/wrong_answer/:
For each *.in in data/*/:
Run the solution on the input
For the built-in validator if corrector = "diff" or each validator in output_validators/:
If the validator accepts the output of the solution: Error!
For each solution in submissions/run_time_error/:
For each *.in in data/*/:
Run the solution on the input
If the solution is not judged Run-Time Error: Error!
=== Appendix ===
==== Configuration file format ====
problem.yaml is a UTF-8 encoded YAML file consisting of a mapping with the following keys:
{| class="wikitable"
! Key !! Comments !! Example
|-
| source || optional || ICPC World Finals 2011
|-
| author || optional, defaults to "Unknown" ||
|-
| license || optional, defaults to "cc by-sa" ||
|-
| rights_owner || mandatory || ICPC
|-
| keywords || optional ||
|-
| difficulty || optional ||
|-
| limits || Sequence of mappings with keys as defined below ||
|-
| validator
| optional, set of values from the following (delimited by spaces):
* "case_sensitive" - upper/lower case differences are significant. If this parameter is not specified, any changes in case are to be ignored.
* "space_change_sensitive" - whitespace differences are significant. If this parameter is not specified, any non-zero amounts of whitespace are considered identical.
* "float_relative_tolerance X" - accepts token if it is a floating point number and the relative error is <= X
* "float_absolute_tolerance X" - accepts token if it is a floating point number and the absolute error is <= X
* "float_tolerance X" - accepts token if either "float_relative_tolerance X" or "float_absolute_tolerance X" would accept
* "custom" - use a custom output validator. Must be the first value. All following values will be passed as command-line arguments to each of the output validators
|
|}
==== limits ====
A sequence of mappings with the following keys:
{| class="wikitable"
! Key !! Comments !! Example
|-
| time_multiplier || optional, defaults to 5 ||3.5
|-
| time_safety_margin || optional, defaults to 2||1.5
|-
| memory || optional, in Mb, defaults to 2048 || 3072
|-
| output || optional, in Mb, defaults to 8 || 4
|-
| compilation_time || optional, in seconds, defaults to 60 || 120
|-
| validation_time || optional, in seconds, defaults to 60 || 120
|-
| validation_memory || optional, in Mb, defaults to 2048 || 3072
|-
| validation_output || optional, in Mb, defaults to 8 || 4
|}
===== Sample problem.yaml =====
Typical problem.yaml:
# Problem configuration
source: ICPC Mid-Atlantic Regional Contest
author: John von Judge
rights_owner: ICPC
Maximal problem.yaml:
# Problem configuration
source: ICPC Mid-Atlantic Regional Contest
author: John von Judge
license: cc by-sa
rights_owner: ICPC
limits:
time_multiplier: 5
time_safety_margin: 2
memory: 4096
output: 16
compilation_time: 240
validation_time: 240
validation_memory: 3072
validation_output: 4
validator: space_change_sensitive float_absolute_tolerance 1e-6
==== Directory structure ====
<short_name>/
problem.yaml - problem configuration file
problem_statement/
problem.tex - problem statement
- any files that problem.tex needs to include, e.g. images
data/
sample/
*.in - sample input files
*.ans - sample answer files
secret/
*.in - input files
*.ans - answer files
*.txt - optional data file description
submissions/
accepted/
- single file or directory per solution
wrong_answer/
- single file or directory per solution
time_limit_exceeded/
- single file or directory per solution
run_time_error/
- single file or directory per solution
input_format_validators/
- single file or directory per validator
output_validators/
- single file or directory per validator
===== Sample Directory / Filenames =====
This is a sample list of directories/files for a problem named ''squares''
squares/problem.yaml
squares/problem_statement/problem.en.tex
squares/problem_statement/problem.sv.tex
squares/problem_statement/square1.png
squares/problem_statement/square2.png
squares/data/sample/squares_sample1.in
squares/data/sample/squares_sample1.ans
squares/data/sample/squares_sample2.in
squares/data/sample/squares_sample2.ans
squares/data/secret/squares1.in
squares/data/secret/squares1.ans
squares/data/secret/squares1.txt
squares/data/secret/squares2_cornercases.in
squares/data/secret/squares2_cornercases.ans
squares/data/secret/squares3_bigcases.in
squares/data/secret/squares3_bigcases.ans
squares/submissions/accepted/squares.cpp
squares/submissions/accepted/Squares.java
squares/submissions/accepted/squares.c
squares/submissions/wrong_answer/wrong.cpp
squares/submissions/time_limit_exceeded/tle.c
squares/submissions/run_time_error/rte.c
squares/input_format_validators/squares_input_checker1.py
squares/input_format_validators/squares_input_checker2/check.c
squares/input_format_validators/squares_input_checker2/data.h
squares/output_validators/squares_validator/validator.f
squares/output_validators/squares_validator/build
squares/output_validators/squares_validator/run
==Source==
* [https://clics.ecs.baylor.edu/index.php?title=Problem_format&oldid=1606 Problem Format history March 2012]