1 Title : Guidelines for ioi competitions 2 Author : ioi scientific Committee

828

829 Each deliverable should be authored by at least two persons, one

831 is intimately known by more than one person and, hence, that the loss

832 of an author will not jeopardize the timely delivery.

833

835 This reduces the impact of losing an author, and also helps ensure

836 diversity. For instance, it makes it impossible that all three tasks

837 in a Competition Round are authored by one and the same person.

838

839 Persons cannot act as a reviewer for the tasks they author. A reviewer

841

843 ----------- -----

844 The IOIn Competition Rules must provide a complete description of all

845 those general aspects of the competition at IOIn that are relevant for

846 the participating delegations and that are not already explained in the

847 IOI Regulations. The term "general aspects" is intended to cover those

848 aspects that are independent of the specific competition tasks posed at

849 IOIn. A checklist for the contents appears in the Appendix.

850

851 Examples of questions that need to be answered in the Competition Rules

853 programming tasks, and through which compilers? What other tools are

854 available? What is the interface to the grading system? What needs to

855 be submitted for a task, and in what format? How is the grading done?

856

857 Schedule

859 The following MILESTONES must be incorporated into the schedule.

860

861 Deliver description and examples of new TYPES of tasks

863 IC (during site visit)

864 5 months prior to IOIn: for delegations (via web & IOI mailing list)

865

867 5 months prior to IOIn: for review by IOI SC (via e-mail)

868 4 months prior to IOIn: for delegations (via web & IOI mailing list)

869

871 3 months prior to IOIn: for review by IOI SC (preferably during site

872 visit, or via e-mail)

873 in GA meeting at IOIn: for review by GA

874

875 Deliver Grading System and Grading Support Material

877 visit, or via e-mail)

878

879 Deliver Final Results and List of Delegations

881

883 1 month after IOIn: for review to IOI SC and IOIn Host Team

884 2 months after IOIn: for public (via web and IOI mailing list)

885

887 ------------- ----------

888 The organization of an IOI competition involves a large number of

889 documents, forms, files, software programs, etc. Borrowing a term

890 from Software Engineering, each such item is referred to as a

891 CONFIGURATION ITEM (CI). Configuration management concerns the

892 identification, storage, change, and release of configuration items.

893

895 and must be subjected to configuration management. They must be

896 identified and stored in such a way that their status is clear and that

897 all approved versions, including older ones, can be retrieved later.

898

899 Approved CIs are under CHANGE CONTROL. This means that changes can only

901 afterwards it can be verified that the changes have indeed been made as

902 agreed.

903

905 the schedule.

906

907 Appropriate backup measures must be taken to ensure that CIs are never

909 development. Approved CIs must also be stored by the Chair of the IOI SC.

910

911 Confidentiality

913 The Project Plan, Progress Reports, and other deliverables are

914 CONFIDENTIAL documents up to the moment of their public release.

915 Confidential documents, whether printed or in electronic form, must be

916 handled, stored, and transmitted in a secure manner to ensure that

917 unauthorized persons have no access to their contents.

918

919 During the life-time of a document, the set of authorized persons can

921 developed in a small group, then released to the IOI SC for review, then

922 released to the GA members at IOIn prior to the competition proper of round

923 X, and, finally, they are released to the competitors at the start of

924 the competition on day X and made publicly available to guests

925 and other interested persons, e.g. back home (in printed form and

926 via the IOIn web site).

927

929 networked systems, it suffices to use appropriate read/write permissions

930 of the file system in a password-protected user account. Encryption is

931 not required for storage, as long as limited access is guaranteed.

932

933 For electronic transmission, confidential documents should be encrypted.

935 delivery by regular mail directly to an authorized recipient is

936 acceptable.

937

939 ----------- --------------

940 There are a number of requirements on the competition accommodations.

941 These are listed in the Appendix. Their supervision is mostly a

942 concern of the IOI IC.

943

945

947 * GA meeting room, with at least two seats per delegation, and

948 seats for the various committee members

949 * GA computer room, with one computerized workplace per delegation

950 and for various other individuals

951

953 APPENDICES

954

955 Checklists

957

959 ---- ---- ------------

960 * A general description of the type of task, including grading

961 information

962 * At least one complete example of a task description for this type

963 of task

964 * Complete documented solutions for the examples

965

967 ----------- -----

968 * Dates and times for practicing and for the Practice, First, and

969 Second Competition

970 * Dates and times for the competition-related GA Meetings, especially

971 - an Introduction Meeting, before the Practice Competition, where the

972 entire competition procedure is (again) briefly explained;

973 questions must be restricted to those that are urgent before the

974 Practice Competition takes place; other questions should be posed

975 at the following Questions Meeting

976 - a Questions Meeting, after the Practice Competition; there must be

977 time after this meeting for delegations to report to the

978 competitors before the First Competition

979 - a meeting before the First Competition, where the tasks are

980 presented and afterwards translated; the delegation members in

981 this meeting must not communicate with the competitors until

982 the First Competition is over

983 - a meeting where the results of the First Competition are

984 finalized; there must be time after this meeting for delegations

985 to report to the competitors before the Second Competition

986 - a meeting before the Second Competition, where the tasks are

987 presented and afterwards translated; the delegation members in

988 this meeting must not communicate with the competitors until

989 the Second Competition is over

990 - a meeting where the results of the Second Competition are

991 finalized

992 - a meeting where the final results of both competitions are

993 approved and where medals are assigned

994 - at least two meetings with ample opportunity to present, discuss,

995 and approve changes in the IOI Competition

996

997 * Hardware specifications:

999 keyboard, pointing device

1000 * Software specifications:

1001 - Operating System, compilers, editors, etc. (exact versions)

1002 * Directory structure and other environment/setup info

1003 * Backup measures (e.g. do-it-yourself on diskette)

1004 * Printing facility

1005 * Task description general info, such as I/O format restrictions

1006 (also see below)

1007 * Auxiliary material

1008 - What is supplied, e.g. paper, diskette, special helper progs

1009 - What competitors may bring (pen), what not (calculators, books)

1010 * Outline of each Competition Round:

1011 - presentation of the Competition Tasks at the GA meeting

1012 - translation

1013 - preparation: competitors enter competition room(s), go to their

1014 assigned workplace without touching the competition

1015 material or competition equipment

1016 - start (competitors open envelope with competition material)

1017 - clarification requests (restricted to first hour; competitors

1018 may ask one questions per form; if this question is not understood

1019 by the organizing committee, then the competitor's delegation

1020 leader is requested to help interpret the question; the ONLY

1021 answers are YES, NO, and NO COMMENT)

1022 - what to do in case of systems trouble, restrooms, eating/drinking,

1023 - 15 minutes, 5 minutes, and 1 minute before-end announcements

1024 - end (stop working, power off)

1025 - grading of competitors' work

1026 - delegations have the opportunity to verify the results

1027 - appeals (through Grading Appeal Form)

1028 - finalization at GA meeting

1029 * Interface to grading system, additional details

1030

1031 Competition Tasks

1033 * General requirements:

1034 the IOI Competition

1035 - must focus on problem solving in Computer Science

1036 - must emphasize fundamental, long-lasting concepts

1037 - must aim to interest and challenge all competitors

1038 - must offer a sufficiently diverse set of tasks,

1039 avoiding a one-sided view on Computer Science;

1040 not only should there be diversity within a single IOI,

1041 but also from one IOI to the next

1042 - must not require special skills or knowledge outside

1043 the approved areas of Computer Science (currently,

1044 computer programming, algorithms, data structures, but

1045 NOT speed typing or familiarity with computer architecture)

1046 - must have an effective way to overcome the language

1047 barrier, both to and from the competitors

1048 - must allow objective grading of the competitors' work;

1049 the grading process shall be developed together with the tasks

1050 (and not as an afterthought)

1051 - must be politically, culturally, and gender neutral;

1052 it must not favor any competitor

1053 - must present high-quality solutions for all Competition Tasks

1054 before the end of IOIn

1055

1057 - Competition Tasks

1058 o must be new, that is, must not have appeared in earlier

1059 competitions or in the published literature

1060 o should contain some innovative element

1061 o must have been completely solved by the IOIn CC:

1062 * preferably in all allowed programming languages;

1063 * knowing the time and space complexity of the solutions

1064 * with a proof that the solutions meet the specified

1065 resource limits (time, memory) for all allowed inputs

1066 o must be effectively and efficiently gradable

1067 o must allow for partial credit to be awarded, that is,

1068 each task allows a, preferably wide, range of resulting

1069 scores; in particular, it is not 0% or 100% only.

1070 There are various ways to accomplish this, such as multiple

1071 test cases or the distinction of subtasks, each of which

1072 can be credited independently.

1073 - Task descriptions

1074 o must be written in correct and simple English,

1075 keeping in mind that the text needs to be translated

1076 o must be presented in a consistent layout and style

1077 o must be precise, complete, and unambiguous,

1078 paying special attention to

1079 * constraints (bounds) on input parameters

1080 (precondition)

1081 * input-output relationship (postcondition)

1082 * illustrations

1083 * input and output format (syntax)

1084 * resource limits (time, memory, or others)

1085 * file names and locations

1086 * library routine headers and parameter meanings

1087 * example(s)

1088 * grading details (what the scoring function is, e.g.

1089 the number of test cases and the number of points per

1090 test case for each subtask)

1091 o should be no longer than two printed pages at 12 point

1092 including illustrations, and preferably fit on ONE page

1093 o must include at least one non-trivial example

1094 o must be available in electronic form during translation

1095 - Additional task material accompanying the task description:

1096 o example input and output data in electronic form,

1097 must include all examples in the task description and

1098 also some larger cases

1099 o output format checker utility

1100

1101 * The set of Competition Tasks:

1103 o Practice Competition (one or two)

1104 o Two Competition Rounds (typically, three each)

1105 o reserve (at least one per round)

1106 - must be of an appropriate level of difficulty:

1107 o the First Competition is somewhat easier than the Second

1108 o the set contains tasks of various difficulty levels,

1109 taking into account the considerable variation in skills

1110 of the competitors and ensuring more spread in the total

1111 score

1112 - must be accompanied by a Task Overview sheet, summarizing

1113 the key information of each task in the set, including

1114 o Task number, title, input file names, output file

1115 names, maximum total number of points

1116

1117 * Background info (as given to GA when deciding on tasks):

1119 - intended challenge (what are the major difficulties to overcome)

1120 - how will imperfect submissions score (receive partial credit);

1121 details of the test data need not be presented, but it should

1122 be explained what the design criteria of the test data were

1123

1125 - test data:

1126 o with motivation (what is the purpose of each test case)

1127 o with scoring details (how is score derived from the test

1128 result)

1129 o sufficient number of test cases to ensure effective grading

1130 o reasonable distribution of size and difficulty, covering

1131 the entire spectrum allowed by the task description

1132 o testing all requirements (functionality and performance)

1133 - input validators:

1134 o that reads the test input data and checks that it agrees

1135 with the task description

1136 - output checkers:

1137 o for tasks where the correct output is uniquely determined

1138 by the input, a kind of file comparison utility can be used

1139 o for tasks where the correct output is not uniquely

1140 determined by the input, it will be necessary to develop

1141 a special-purpose output checker that reads the input and

1142 the captured output, and reports the result

1143 - grading scripts

1144

1145 * Documented solutions (to be disclosed to delegations after the start

1147 programs and how they would score

1148

1149 * Input-output shall be kept as simple as possible.

1151 items. Each item is either a number or a string:

1152 o Numbers are represented in the usual decimal format,

1153 so that they can be read in by a standard input routine.

1154 Unless specifically stated otherwise, number values are

1155 within the range supported by the programming languages.

1156 o A string is a non-empty sequence of printable characters

1157 (ASCII values in the range 32..126).

1158 - Items on the same line are separated by a single space character.

1159 There are no space characters at the beginning or end of a line.

1160 Strings only appear at the end of a line; consequently, there is

1161 at most one string per line.

1162 - The structure of input text files is always such that end-of-line

1163 and end-of-file recognition is not an issue. There are three ways

1164 to accomplish this:

1165 o The number of items (or lines) is the same for all instances

1166 (e.g. "the first line contains the three numbers a, b, and c")

1167 o The number of items (or lines) is given earlier in the input

1168 (e.g. "the first line gives the number n of nodes;

1169 the following n lines each describe one node")

1170 o The number of items (or lines) is implicitly defined, by

1171 including a special terminating item

1172 (e.g. "each line contains a sequence of positive numbers

1173 followed by 0")

1174 In particular, this excludes a description like "the i-th line

1175 contains the neighbors of node i" when the number of neighbors

1176 is not known in advance, because in that case, determining the

1177 number of neighbors requires the recognition of end-of-line.

1178 - All input data used in grading must agree with the task

1179 description. The competitor programs never need to validate

1180 the input data.

1181 - Before checking, output files are first filtered to

1182 o remove space characters at the beginning and end of a line

1183 o replace multiple space characters between items by a single

1184 space character

1185 o remove empty lines

1186

1187 Grading

1189 * General grading requirements for programming tasks:

1190 - the grading process must implement the following three

1191 (separate) phases:

1192 1st phase (execution): running the competitor's programs

1193 for all test cases, capturing the output; this requires

1194 compilation, when programs have been submitted in source form.

1195 2nd phase (evaluation): checking the captured output, and

1196 awarding points

1197 3rd phase (reporting): generating the reports

1198 - the 1st phase

1199 o must provide external timing

1200 o should provide automated abort of competitor's program

1201 when a resource limit (e.g. time) is exceeded

1202 o should detect competition rule violation

1203 o must detect and report run-time errors

1204 o must also capture standard output generated during execution

1205 o must provide a secure execution environment, especially

1206 for reactive tasks

1207 o must capture the dialog between the program and its

1208 environment for reactive tasks

1209 - the test cases (input, and how to check the output) must be

1210 developed in close cooperation with the task creator

1211 * Automated grading system (preferably defined by IOI Software Team)

1212 * Well-defined interfaces to

1213 - competitors, explaining

1214 o what source code restrictions apply (e.g. which

1215 compiler directives are permitted)

1216 o whether data files prepared during the competition can be

1217 used by the program when it is executed for grading, and

1218 if so, what restrictions apply

1219 o whether the program can read other (e.g. system) files

1220 when it is executed for grading

1221 o whether temporary files can be created and used by the

1222 program when it is executed for grading, and if so,

1223 what restrictions apply

1224 o what environment conditions hold during execution of

1225 the programs

1226 - task creators, explaining

1227 o in what format the correct and known-incorrect

1228 solutions are to be supplied

1229 o in what format the test cases are to be supplied

1230 (input files, input validators, output files or output

1231 checkers)

1232 o in what format the scoring details are to be supplied

1233 - system operators, explaining

1234 o how to set configuration files (to fill in details of

1235 each competition round)

1236 o how to operate the grading system

1237 * Grading schedule (if necessary: who is graded where at what time)

1238 * Appeal mechanism

1239 * After grading a competition, each delegation leader must receive:

1240 - A printed grading report, with total score and score break down

1241 (per test case and subtask), for each of their competitors

1242 - All submissions of each of their competitors (source and exe)

1243 - All output/log files produced by each of their competitors

1244 - All test data (input, and correct output if applicable)

1245 - Input validity checkers (source and exe)

1246 - File comparator (exe)

1247 - Output checkers used for grading, if applicable (source and exe)

1248 - All libraries and other support software (source and exe)

1249 - A grading appeal form, one for each of their competitors

1250

1251 NOTE: The availability of ALL relevant material (in source and exe

1253 confidence.

1254

1255 Scripts and agendas

1257 All competition activities, especially those involving many officials,