Форум DL

Мой профиль

(продолжение)

In fact, there are several pages with information about our UVa Online site (and maybe much more we don’t know about, as we can’t control every thing, of course). For example, one of the most popular pages dedicated to algorithms and programming contest (Pi
algorithmist) contains a section specifically dedicated to the UVa Online Judge with several links to some of those pages, as well as an open subsection about categories. The sites of Felix and Steven Halim are excellent, with a lot of interesting information, but
maybe the users like more the site managed by Igor Naverniouk (Igor’s UVa tools) where the problems are classified by difficulty level (trivial, easy, medium, hard, very hard, IMPOSSIBLE)
and it allows to compare with each other user as well as to get a tip about the following problems to try in function of the past history. Of course, we have this information and we check it from time to time, but they are not managed by us. Although we contact the responsible staff of these sites, and try to help them to develop their initiatives, they are independent. But all of them have some common characteristics. For example, there is almost general agreement about labeling only a few problems into each of the categories. At this moment there is not an ‘official’
categorization of the site even though the data base is ready to do it, and we hope that all these features will be included as a built-in feature in the UVa Online Judge with the collaboration of all these persons.

Мой профиль

Авторы поддерживают он-лайн-тестирование, на базе архива из 2500+ задач и кучу других сервисов. Есть намерение развернуть имеющееся средство в сторону ОБУЧЕНИЯ. Получена финансовая поддержка этого намерения от Евросоюза. Мне кажется идеологическая (методическая, педагогическая и т.д) платформа у них слабовата. В частности, среди рассматриваемых направлений развития в статье перечислены ТОЛЬКО:
- тестирование по баллам
- развитие ядра тестирования (например, турниры программ)
- автоматическая генерация тестов
- категоризация задач по темам и сложности (у которой есть и противники - те, кто соревнуется, кто больше задач решит - они считают категоризацию излишней подсказкой).

Мой профиль

What Do Olympiad Tasks Measure?
http://www.mii.lt/olympiads%5Fin%5Finformatics/pdf/INFOL032.pdf

Troy VASIGA, Gordon CORMACK
David R. Cheriton School of Computer Science,
University of Waterloo
Waterloo, Ontario, N2L 3G1 Canada

Graeme KEMKES
Department of Combinatorics and Optimization,
University of Waterloo
Waterloo, Ontario, N2L 3G1 Canada

... tasks should be attractive, approachable, challenging and practical (which we also mean generalizable or extendible).

Our thesis is that while it is tempting, one should avoid making problems hard by increasing the information processing aspects of the problem. Similarly it is common to create easy problems by removing the problem solving component, leaving information
processing or memorization of algorithms. Neither the information processing nor memorization should overwhelm the problem solving aspects.

By problem solving, we mean the use of creative, intelligent, original ideas in combination with prior knowledge when applied to a new situation.

In order to further clarify our definition of problem solving, we explicitly define what we do not mean by problem solving. For lack of a better term, we will classify the following concepts as problem solving distractors. To begin, we consider detailed information processing a distractor to problem solving. By detailed information processing, we wish to encompass knowing details of
• particular programming languages or libraries contained therein,
• tedious input/output formatting,
• optimizations that result in constant-factor time improvement in execution speed.

Another problem solving distractor is detailed esoteric knowledge of algorithms, by which we mean memorization of recent journal articles for leading edge algorithms (e.g., recent algorithms from such publications as ACM Symposium on Theory of Computing or IEEE Symposium on Foundations of Computer Science) or memorization of implementation details of complicated algorithms (e.g., implementing red-black trees).

What is the goal of an olympiad task?
Our view is that the goal of an olympiad task is to solve the task. By solving the task, we mean being able to communicate the underlying algorithmic process that will consume input in the desired way to produce the correct output. The core concept in solving a task is the application of problem solving skills.
Unfortunately, solving a task is conflated with the problem solving distractors outlined in Section 2. Specifically, students need to pay particular attention to information processing
details, such as
• whether to return 0 at the end of their main procedures in C/C++ ;
• dealing with newline characters in their input or output;
• dealing with file input and output nuances in particular languages;
• knowing particular libraries, and more specifically, the efficiency of particular libraries.
For example, knowing runtime differences between cin and printf
in C++.

This disproportionate focus on efficiency has led to
many concerns with IOI tasks, such as:
• competitors guessing what non-solutions get the most marks: see for example evaluation of IOI tasks (Forisek, 2006) that have allocated an inappropriate percentage of marks for incorrect algorithms;
• the speed of programming being a factor in the scores of IOI competitors;
• the competitor who has memorized the “correct” set of algorithms has a clear advantage over those competitors who have broader algorithmic abilities.

Minimizing Distractors
1. Provide feedback during the competition
2. Consider using output-only tasks.
- reduce the restrictions imposed by programming languages
- to solve some small or restricted case of a problem by hand
- to ask a theoretical question, such as what is the minimum number of times event X can occur if some other event Y must occur in some previous step
3. Provide a syllabus.
4. Provide a standard IOI library of tools(STL-like library).
5. Provide practice problems that test all input/output requirements.
6. Simplify the input format.
7. Simplify the output format.
8. Ensure the problem statement is short.
9. Ensure that solutions are short.
If the solution for a task is longer than 50 lines of C code or if it requires use of the STL or other library functions, the task should be met with great suspicion.
10. Attempt to make tasks practical, or show how they may be extended to practice.

Мой профиль

Коротко говоря, авторы ратуют за конвергенцию IOI задач к стилю "придумать", а не "знать" или "быстро кодировать".
В общем нашим олимпиадникам нужно
1. Быстро кодировать
2. Много знать (теорию по алгоритмам)
3. Уметь придумывать решения, где на первый, второй и несколько последующих взглядов НИКАКИЕ из известных стандартных алгоритмов не применимы.

В этих направлениях мы работали и будем работать дальше.

Мой профиль

Programming Task Packages: Peach Exchange Format
http://www.mii.lt/olympiads%5Fin%5Finformatics/pdf/INFOL019.pdf

Tom VERHOEFF
Department of Mathematics and Computer Science,
Technische Universiteit Eindhoven
P.O. Box 513, NL–5600 MB Eindhoven, The Netherlands

Programming education and contests have introduced software to help evaluation by executing submitted taskwork. We present the notion of a task package as a unit for collecting, storing, archiving, and exchanging all information concerning a programming task. We also describe a specific format for such task packages as used in our system Peach, and illustrate it with an example. Our goal is to stimulate the development of an international standard for packaging of programming tasks.

Using these task packages has helped us ensure completeness and correctness of task data. We will discuss the contents and format of task packages and also the interface and operations for task packages. Particular concerns are the support for
• multiple languages to express human readable texts (including, but not restricted to, the task description);
• multiple programming languages allowed for solving the task;
• multiple platforms to deploy tasks;
• diverse task styles;
• validation of package content;
• handling of relationships between tasks, e.g., where one task is a variant of another task;
• flexibility to allow easy incorporation

Мой профиль

Во время проведения IOI 2009 состоится международная конференция, посвященная подготовке и проведению олимпиад по информатике:

Все статьи уже опубликованы в специально издаваемом журнале
OLYMPIADS IN INFORMATICS
International Journal
http://www.mii.lt/olympiads%5Fin%5Finformatics/

Я намерен прочитать эти статьи и процитировать в ответах на это сообщение наиболее интересные материалы.

Вот содержание очередного (третьего) тома:

Contents Volume 3

Foreword (1-2)

Using Item Response Theory to Rate (not only) Programmers (3-16)
Michal FORISEK

Taking Kids into Programming (Contests) with Scratch (17-25)
Abdulrahman IDLBI

Tasks and Training the Intermediate Age Students for Informatics Competitions (26-37) Emil KELEVEDJIEV, Zornitsa DZHENKOVA

Infrastructure for Contest Task Development (38-59)
Rob KOLSTAD

Moe - Design of a Modular Grading System (60-66)
Martin MARES

Using a Linux Security Module for Contest Security (67-73)
Bruce MERRY

The Role of Reactive and Game Tasks in Competitions (74-79)
Ilia NINKA

Team Competition in Mathematics and Informatics ``Ugale'' - Finding New Task Types (80-100)
Martinc OPMANIS

Representational Means for Tasks in Informatics (101-112)
Pavel S. PANKOV, Kirill A. BARYSHNIKOV

Baltic Olympiads in Informatics: Challenges for Training Together (112-131)
Timo PORANEN, Valentina DAGIENE, Asmund ELDHUSET, Heikki HYYRO, Marcin KUBICA, Antti LAAKSONEN, Martins OPMANIS, Wolfgang POHL, Jurate SKUPIENE, Par SODERHJELM, Ahto TRUU

Improving the Automatic Evaluation of Problem Solutions in Programming Contests (132-143)
Pedro RIBEIRO, Pedro GUERREIRO

Using Subtasks (144-148)
Willem van der VEGT

20 Years of IOI Competition Tasks (149-166)
Tom VERHOEFF

jBOI - One More Possibility for Increasing the Number of Competitors in Informatics (167-173)
Biserka YOVCHEVA, Galina MOMCHEVA, Petar PETROV

Мой профиль

Во время проведения IOI 2010 состоится международная конференция, посвященная подготовке и проведению олимпиад по информатике:

Все статьи уже опубликованы в специально издаваемом журнале
OLYMPIADS IN INFORMATICS
International Journal
http://www.mii.lt/olympiads_in_informatics/

Вот содержание очередного (четвертого) тома вместе с моими краткими комментариями:

Encouraging Algorithmic Thinking Without a Computer
Benjamin A. BURTON
School of Mathematics and Physics, The University of Queensland
Brisbane QLD 4072, Australia
e-mail: bab@maths.uq.edu.au

Проблема - мало количество участников олимпиад по информатике
(и падает). В разных странах (Южной Африке, Литве, Болгарии)
вводят альтернативные олимпиады [для начинающих?]

В Австралии - соревнования без компьютеров, несколько задач на час:
- алгоритмические задачи
- логические задачи
- Tracing tasks - студент должен следовать набору инструкций
- Аналитические задачи - студент должен исследовать сильные
и слабые стороны данного алгоритма
- указать количество шагов алгоритма в худшем случае
- найти ошибку в алгоритме
- ?создать полное множество входных тестов

- Трехстадийные задачи
(три теста, нарастающей сложности/размерности данных)

Что делать?

1. Спросить у Бартона условия всех задач (с ответами) с 2005 года.
2. Поставить как математические на русском и английском языках
3. Подумать как ставить свои такие задачи (и на какие темы?)

==================================================================================================

Mutual Influence of the National Educational
Standard and Olympiad in Informatics Contents
Vladimir M. KIRYUKHIN
Department of Informatics and Control Systems,
National Research Nuclear University ”MEPhI”
Kashirskoe Shosse 31, 115409 Moscow, Russian Federation
e-mail: vkiryukhin@nmg.ru, msvm@lianet.ru

Cистема виртуальных лабораторий по информатике Задачник 2-6
http://school-collection.edu.ru/catalog/rubr/473cf27f-18e7-469d-a53e-08d72f0ec961/109594/

Что делать
1. Выкачать, развернуть и поработать с "Системой виртуальных лабораторий"
- "вытянуть" оттуда полезные идеи
2. http://www.journal.edusite.ru/p103aa1.html
описания учебников по "Информатике", очень похожих на наши "Учимся думать"

==================================================================================================

Strategy for ICT Skills Teachers and Informatics
Olympiad Coaches Development
Vladimir M. KIRYUKHIN
Department of Informaticss and Control Systems, National Research Nuclear University
Kashirskoe Shosse 31, Moscow 115409, Russian Federation
e-mail: vkiryukhin@nmg.ru , msvm@lianet.ru
Marina S. TSVETKOVA
Publishing House “BINOM. Knowledge Laboratory”
Proezd Aeroporta 3, Moscow 125167, Russian Federation
e-mail: tsvetkova@lbz.ru , msvm@lianet.ru

программа обучения тренеров к олимпиадам по информатике
- своеобразный Российский теор.минимум (?максимум) на английском языке.

==================================================================================================

Algorithms without Programming
Marcin KUBICA, Jakub RADOSZEWSKI
Institute of Informatics, University of Warsaw
Banacha 2, 02-097 Warsaw, Poland
e-mail: {kubica,jrad}@mimuw.edu.pl

Для привлечения интереса предлагается проводить соревнования
по решению задач без компьютеров. Фактически, чтобы можно было
вручную получить ответ, нужно придумать эффективный алгоритм
(иначе будет слишком много утомительных вычислений)
Приводятся примеры таких задач с подсказками, решениями и
методическими пояснениями.

UniColor Triangles                      - комбинаторика
Continuous Subsequences Divisible by 13 - ДП
Subsequences Divisible by 5             - ДП
Coins                                   - классическое ДП
Encyclopedia                            - классическое ДП
Heavy Encyclopedia                      - жадный + "разделяй и властвуй"    
Anti-Binary Sets                        - скрытый граф + жадный + ДП

Указываются обобщенные свойства таких задач:
- решение должно быть технически простым (из нескольких шагов)
- избегать задач, которые требуют знание классических алгоритмов
- должно существовать простое, но очень медленное (трудоемкое для ручного
просчета) решение задачи, очевидное любому, кто возьмется ее решать
(для гарантии понимания задачи)

Полезные ссылки на аналоги
www.bebras.org
www.mimuw.edu.pl/delta (на польском)
projecteuler.net

==================================================================================================

Indonesian Olympiad in Informatics
Ilham W. KURNIA
Computer Science Faculty, University of Kaiserslautern, TU Kaiserslautern
Fachbereich Informatik, Gebaude 34, Postfach, 30 49, D-67653 Kaiserslautern
e-mail: ilham@cs.uni-kl.de
Brian MARSHAL
School of Computer Engineering, Nanyang Technological University
Nanyang Avenue, Block N4, Singapore 639798
e-mail: brian.marshal@pmail.ntu.edu.sg

Организация национальных олимпиад в Индонезии
как и везде
- он-лайн обучение
- многоступенчатый отбор
- сборы
По утверждению авторов, Индонезия, участвуя в IOI только с 1995 года,
завоевала 2 золотых, 11 серебряных и 16 бронзовых медалей.
Население Индонезии - 213 миллионов на 2005 год.

==================================================================================================

Testing of Programs with Random Generated Test Cases
Krassimir MANEV
Department of Mathematics and Informatics, Sofia University
J. Bourchier blvd. 5, 1164 Sofia, Bulgaria
Institute of Mathematics and Informatics, Bulgarian Academy of Sciences
G. Bontchev str. 8, 1113 Sofia, Bulgaria
e-mail: manev@fmi.uni-sofia.bg
Biserka YOVCHEVA, Milko YANKOV, Peter PETROV
Department of Mathematics and Informatics, Shumen University
Universitetska str. 115, 9712 Shumen, Bulgaria
e-mail: bissy_y@yahoo.com, m.yankov@f5bg.net, peshoto_bg@yahoo.com

"масло масляное":
- надо использовать генераторы тестов
- надо, чтобы тесты хорошо разделяли правильные/неправильные,
эффективные/неэффективные решения

==================================================================================================

Performance Analysis of Sandboxes for Reactive Tasks
Bruce MERRY
ARM Ltd
110 Fulbourn Road, Cambridge, CB1 9NJ, United Kingdom
e-mail: bmerry@gmail.com

Сравнение производительности двух "песочниц", отслеживающих
запрещенные системные вызовы

==================================================================================================

Real Processes as Sources for Tasks in Informatics
Pavel S. PANKOV
International University of Kyrgyzstan
A. Sydykov str. 252, Apt. 10, 720001 Bishkek, Kyrgyzstan
e-mail: pps50@rambler.ru

Предлагается использовать естественные науки как источник задач.
(физика, химия, генетика, геология, астрономия).

Выделяется три класса задач:

- Комбинаторные: сколько существует различных объектов?

Важное значение имеет понятие различия объектов.
Часто чем больше объектов рассматриваются как эквивалентные,
тем более сложна задача, поскольку затрудняется применение
стандартных алгоритмов. Существует множество видов эквиалентности
для реальных объектов: вращение, отражение, трансляция эквивалентность.

- Оптимизация: найти максимальный/минимальный из всех объектов.

- Интерактивные: определить объект за минимальное или ограниченное
количество запросов.

==================================================================================================

The New Zealand Experience of Finding Informatics Talent
Margot PHILLIPPS
New Zealand Olympiad in Informatics
e-mail: margot.phillipps@gmail.com

"Ищут пожарные, ищет милиция" ...

==================================================================================================

Мой профиль

(продолжение)

Validating the Security and Stability of the Grader
for a Programming Contest System
Tocho TOCHEV, Tsvetan BOGDANOV
Sofia University, Bulgaria
J. Bourchier 5, 1164 Sofia, Bulgaria
e-mail: tocho.tochev@gmail.com, tsvetan.bogdanov@gmail.com

Предлагают набор тестов для систем тестирования программ:
https://svn.openfmi.net/pcms/trunk/test/grader/

==================================================================================================

The Olympiads in Informatics as a Part of the State
Program of School Informatization in Russia
Marina S. TSVETKOVA
Publishing House “BINOM. Knowledge Laboratory”
Proezd Aeroporta 3, 125167 Moscow, Russian Federation
e-mail: tsvetkova@lbz.ru, msvm@lianet.ru

Дается обзор развития изучения информатики в России с 1985 года.
Множество ссылок на федеральные и региональные образовательные ресурсы,
в том числе:

http://www.edu.ru
http://fcior.edu.ru
http://www.school.edu.ru
http://www.educom.ru/ru/nasha_novaya_shkola/
http://window.edu.ru
http://www.school-collection.edu.ru

==================================================================================================

An Enticing Environment for Programming

Tom VERHOEFF
Department of Mathematics and Computing Science, Eindhoven University of Technology
Den Dolech 2, 5612 AZ Eindhoven, The Netherlands
e-mail: t.verhoeff@tue.nl

- простая среда разработки программ на JavaScript
(даже для не изучавших ранее программирование)
www.win.tue.nl/~wstomv/edu/javascript (accessed April 2010)

==================================================================================================

Selection Mechanism and Task Creation of Chinese
National Olympiad in Informatics

Hong WANG
Department of Computer Science and Technology, Tsinghua University
100084 Beijing, China
e-mail: wanghong@tsinghua.edu.cn
Baolin YIN
School of Computer Science and Technology, Beihang University
100083 Beijing, China
e-mail: yin@nlsde.buaa.edu.cn
Rujia LIU
Eryiju Science and Technology Company Limited
100084 Beijing, China
e-mail: rujia.liu@gmail.com
Wenbin TANG, Weidong HU
Department of Computer Science and Technology, Tsinghua University
100084 Beijing, China
e-mail: tangwb06@gmail.com, wd.h@163.com

Они написали, что с 2009 года публикуют условия задач на английском языке
- где?

==================================================================================================

IOI Israel – Team Selection, Training, and Statistics

Ela ZUR, Tamar BENAYA
The Openu University of Israel, Computer Science Department
Ravutzky 108, 43107 Raanana, Israel
e-mail: {ela, tamar}@openu.ac.il
David GINAT
Tel-Aviv University, Science Education Department
Ramat Aviv, 699978 Tel-Aviv, Israel
e-mail: ginat@post.tau.ac.il

с 1997 года они взяли 4 золотых, 16 серебряных и 15 бронзовых медали.
Правда в 2008 не участвовали, а в 2009 взяли только одну медаль, и ту -
бронзовую.

4 стадии подготовки
- самоподготовка
- национальная олимпиада
- отбор
- подготовка сборной к IOI

==================================================================================================

Get Involved!
The IOI Workshop 2010, Its Goals and Results

2 главных вопроса

1) Как организовать сотрудничество (в том числе обмен задачами)
http://www.bwinf.de/ioi-cooperation

2) Как сделать визуализацию процесса IOI-олимпиады для наблюдателей

Мой профиль

Volume 5 (2011)
http://www.mii.lt/olympiads_in_informatics/contents.htm

Foreword (1-2)

David GINAT
Algorithmic Problem Solving and Novel Associations (3-11)

Lasse HAKULINEN
Survey on Informatics Competitions: Developing Tasks (12-25)

Kentaro IMAJO
Contest Environment Using Wireless Networks: A Case Study from Japan (26-31)

Grzegorz JAKACKI, Marcin KUBICA, Tomasz WALEN
Codility. Application of Olympiad-Style Code Assessment to Pre-Hire Screening of Programmers (32-43)

Vladimir M. KIRYUKHIN, Marina S. TSVETKOVA
Preparing for the IOI through Developmental Teaching (44-57)

Dennis KOMM
Teaching the Concept of Online Algorithms (58-71)

Tomasz KULCZYNSKI, Jakub LACKI, Jakub RADOSZEWSKI
Stimulating Students' Creativity with Tasks Solved Using Precomputation and VisualizationThe authors thank an anonymous referee for helpful suggestions on the presentation of the paper. (71-81)

Krassimir MANEV, Nikolai NIKOLOV, Minko MARKOV
Reconstruction of Trees Using Metric Properties (82-91)

Martin MARES
Fairness of Time Constraints (92-102)

Bruce MERRY, Carl HULTQUIST
Measuring the Startup Time of a Java Virtual Machine (103-112)

Pavel S. PANKOV, Kirill A. BARYSHNIKOV
Tasks of ``Mission Impossible'' and ``Mission Impeded'' Types (113-119)

Tom VERHOEFF
Beyond the Competitive Aspect of the IOI: It Is All about Caring for Talent (120-127)

Arturo CEPEDA, Margarita GARCIA
Mexican Olympiad in Informatics (128-130)

Sebastien COMBEFIS, Damien LEROY
Belgian Olympiads in Informatics: The Story of Launching a National Contest (131-139)

Mario ITALIANI
Italian Olympiad in Informatics: 10 Years of the Selection and Education Process (140-146)

Jari KOIVISTO
The National Computer Olympiads and the IOI Participation in Finland (147-149)

Kanchit MALAIVONGS
Preparing Students for IOI: Thailand Country Report (150-154)

Pavel S. PANKOV, Timur R. ORUSKULOV
Kyrgyzstan National Report on Olympiads in Informatics (155-160)

Ela ZUR, Tamar BENAYA, Oren BECKER, David GINAT
Israel: The Regional and National Competitions (161-168)
REVIEWS, COMMENTS (169-175)

Мой профиль

Algorithmic Problem Solving and Novel Associations
David GINAT, Tel-Aviv University, Israel

The less competent students do not recognize sufficient task characteristics.
This phenomenon may derive from lower competence in unfolding hidden
patterns; but may also due to the undesired problem solving discipline of hastily
“jumping” to the composition of an algorithm, without conducting a suitable, thorough
task analysis.

Survey on Informatics Competitions: Developing Tasks
Lasse HAKULINEN, Aalto University, Finland

Kubica and Radoszewsk (2010) ... suggest that problems that require the knowledge of classical algorithms and advanced techniques should be excluded from the competitions.

Features of a good informatics olympiad task:
• The problem statement should be short and easy to understand.
• The algorithms that solve the task should not directly resemble a classic algorithm
or a known problem. However, it can be a modification of a classic algorithm.
• There should be several different valid solutions of varying difficulty and efficiency
in order to allow weaker students to gain partial marks for the task.
• The official solution should be reasonably concise.
• In most cases (depending on the difficulty of the task), the official solution should
also be the best known solution for the task.
• For the experienced students, it is nice to have category the desired algorithm belongs to.

Preparing for the IOI through Developmental Teaching
Vladimir M. KIRYUKHIN, Marina S. TSVETKOVA
National Research Nuclear University ”MEPhI”, Russian Federation

There is no doubt that a significant success in the IOI can be achieved only by students
who are gifted by nature. Along with the necessary knowledge and the skills required
for solving non-standard tasks, such students have important personal qualities – selfimprovement
abilities, self-confidence, striving for success, etc.

Recently, widespread opinion has been that the more competition tasks a students have
solved in the preparation process, the more chances they have to succeed at the IOI.
Moreover, the process of preparation is structured in such way that, first, the student
solves the proposed tasks, and then, after evaluation of the solution, looks for mistakes
with the help of a coach or the available resources, including Internet resources. When
the students are not able to produce solution, the coach explains to them one possible
algorithm, and the student memorizes that algorithm.

This approach, founded on reproductive teaching, is popular due to habit. Its basic
disadvantage is the absence of a developmental aspect, as it is constructed on a reproduction
of patterns. Because of their extraordinarily ability, gifted child cram into memory
patterns for various difficult tasks and the techniques to solve them, subsequently reproducing
the stored solutions (Fig. 1). We will call such a model the “Reproduction of patterns
with support of memory”. In this case, development of theoretical knowledge and
technological abilities is subordinated to features of the tasks and aimed at accumulation,
not on discovering the underlying problem-oriented situation.

Creative Development of Students in Olympiad Preparation Environment

In Russia, for the development of creative abilities of students, the theory of developmental
teaching offered in the 30 years of the twentieth century (Vygotsky, 1991) is widely
used. According to this theory, the leading aspect of methods for development of creative
ability of children is the shift from a teaching process to a process of learning and development.
Another aspect of applying this theory, reflecting the orientation of modern
society to the knowledge processes, is the assimilation of new scientific and technological
achievements, particularly in the field of informatics and information technologies, and
their introduction into the context of the lives and studies of gifted students.

Model of training gifted students, based on anticipatory teaching

should be applied from early childhood. This will allow the building of the development horizon of
a gifted student, constantly expanding the area of the nearest development, solving dif-
ficult tasks, and even creative and research tasks, challenging unique student abilities to
apply the knowledge in practice. It is possible not only to solve competition tasks but also
to work with hypotheses, to explore different methods of getting knowledge, to feel the
necessity for the generation of ideas, for mastering unique technologies of working with
information.

It is important to note that the identification of gifted students in the domain of informatics
should begin as early as possible, and for that purpose contests in primary school
can be used, which also must be focused on the development of algorithmic thinking,
mathematical ingenuity, and the desire to use computer as an assistant in searching for
task solutions and implementing ideas.

2-6 grades - school winner
7-9 grades - RusOI winner
10-11 grades - IOI winner

The support on creative activity is based on the development of the students’ desire
to share their creative experience with others. It is possible to form such qualities on
the basis of student performances after competition with analyses of tasks solutions and
preparing lectures on topics which they have thought up creating their own tasks. But
most important is involving the students in scientific research where their talent could
be used in solving real research problems. Early entrance of the gifted students in the
scientific community, participation in research or other scientific work will enable them
to see themself in science and profession, find horizons for practically using their talent in
various fields of knowledge. Omission of such work with student leads to deformation of
their talent, concentrating only on competitions, solving problems in the name of gaining
points, which restricts the personal development of the gifted students and usage of their
talents in the profession. To assess the level of student creative activity it is possible to
use the traditional forms for the assessment of achievements of young scientist.

Beyond the Competitive Aspect of the IOI: It Is All about Caring for Talent
Tom VERHOEFF, Eindhoven University of Technology

The IOI is not just an informatics competition, but a means to care for talent in informatics. Caring for talent involves a broad range of issues, including identification of talent and education adjusted to that talent. There is (almost?)no generally accessible literature focusing on informatics talent. To show what such literature could offer, we review several books that address talent in mathematics. These books also contain much that is directly applicable to talent in informatics.

Note that not all talented pupils are motivated by a competition (Verhoeff, 1997).

In this article, we address various aspects related to the goals of discovering, encouraging,
challenging, and, in particular, developing talent.

We do so by reviewing six books about discovering, developing, training mathematical talent.

Our hope is that similar books will, one day, be published in the area of informatics, so that these can be
reviewed.

We have the impression that a lot of talent is already lost and wasted before secondary education starts.

Мой профиль

Volume 6 (2012)
http://www.mii.lt/olympiads_in_informatics/contents.htm

Foreword (1-2)

Giorgio AUDRITO, G. Barbara DEMO, Elio GIOVANNETTI
The Role of Contests in Changing Informatics Education: A Local View (3-20)

Vladimir BOZA, Michal FORISEK
FCL-STL, a Generics-Based Template Library for FreePascal (21-30)

Sebastien COMBEFIS, Vianney le CLEMENT de SAINT-MARCQ
Teaching Programming and Algorithm Design with Pythia, a Web-Based Learning Platform (31-43)

David GINAT
Insight Tasks for Examining Student Illuminations (44-52)

Steven HALIM, Zi Chun KOH, Victor Bo Huai LOH, Felix HALIM
Learning Algorithms with Unified and Interactive Web-Based Visualization (53-68)

Mathias HIRON, Loic FEVRIER
A Self-Paced Learning Platform to Teach Programming and Algorithms (69-85)

Stefano MAGGIOLO,, Giovanni MASCELLANI
Introducing CMS: A Contest Management System (86-99)

Martin MARES, Bernard BLACKHAM
A New Contest Sandbox (100-109)

Pavel S. PANKOV, Kirill A. BARYSHNIKOV
Tasks of a Priori Unbounded Complexity (110-114)

Noa RAGONIS
Type of Questions - The Case of Computer Science (115-132)

Francisco ALMEIDA, Vicente BLANCO PEREZ, Javier CUENCA, Ricardo FERNANDEZ-PASCUAL, Gines GARCIA-MATEOS, Domingo GIMENEZ, Jose GUILLEN, Juan Alejandro PALOMINO BENITO, Maria-Eugenia REQUENA, Jose RANILLA
REPORTSAn Experience on the Organization of the First Spanish Parallel Programming Contest (133-147)

Francis DOGBEY
Learning Computer Programming as an Extra Curriculum Activity, the Challenges (148-157)

Aleksandar ILIC, Andreja ILIC
IOI Training and Serbian Competitions in Informatics (158-169)

Jyldyz R. JANALIEVA
Conducting Off-Line Informatics Olympiads with Individual Tasks (170-177)

Emil KELEVEDJIEV, Zornitsa DZHENKOVA
Competitions' Tasks in Informatics for the ``Pre-Master'' Group of School Students (178-191)

Plamen NEDKOV
Young Talent in Informatics \normalsizePreliminary Findings of an IOI Survey Launched by AICA in Cooperation with IT STAR (192-198)

Peter TAYLOR
Comparisons of the IMO and IOI (199-204)

Jelko URBANCIC, Mitja TRAMPUS
Putka - A Web Application in Support of Computer Programming Education (205-211)

Willem van der VEGT
Theoretical Tasks on Algorithms; Two Small Examples (212-217)

Ela ZUR, Tamar BENAYA, Oren BECKER, David GINAT
Israel: The Regional Competition and Teacher Involvement (218-225)

REVIEWS, COMMENTS (226-231)

Мой профиль

FCL-STL, a Generics-Based Template Library for FreePascal
Vladimir BOZA, Michal FORISEK
Comenius University, Bratislava, Slovakia E-mail: {usama,misof}@ksp.sk

Abstract

We present the design and usage of a new set of FreePascal units we created. These units aim to be the counterpart of the Standard Template Library in C++. The library is already included in the development branch of FreePascal (v. 2.7.1), and it should be a part of the stable branch (v. 2.6.?) at some point in future. Available data structures include vectors, sets, maps (both ordered and unordered) and more.

For many tasks used in past programming competitions there were C++ solutions that were significantly easier to implement than any Pascal solution. Problem setters usually needed to ensure that a reasonable Pascal solution exists. This library, once available, will mitigate the difference between the powers of these two languages.

Keywords:
FreePascal, templates, generic programming, algorithm library, STL

At programming contests this provided a clear disadvantage to contestants who use
Pascal. For instance, this is the case at the International Olympiad in Informatics (IOI)
where for many years the allowed programming languages are only Pascal and C/C++.
The lack of a standard library for FreePascal has directly in?uenced the choice of past
competition tasks. For instance, tasks solvable using balanced binary trees were used in
the competition only if there was an alternate solution in Pascal without balanced trees,
but with the same asymptotic time complexity. (E.g., solutions that use various interval
trees fall into this category.) In addition to leveling the playing ?eld, this library should
broaden the spectrum of suitable competition tasks for the IOI.

In the IOI Syllabus (Verhoeff et al., 2006; Verhoeff et al., 2012) most algorithms and
data structures from standard libraries have the status “not for task description”, meaning
that such concepts should not be discussed in the task statements but using them may be
necessary to solve some of the competition tasks. Here we see a direction in which the
Syllabus ought to be improved in the future: At the moment, there is no clean distinc-
tion between understanding such data structures, using their library implementation and
implementing them from scratch. The general consensus is that the ?rst two are surely
necessary; further discussion about requiring their implementation would be helpful.

2. Library Contents – Algorithms

In this section we list and brie?y describe algorithms implemented as a part of the FCL-STL FreePascal library. If unclear about the semantics of a particular algorithm, please
refer to (Cormen et al., 2009) or an equivalent algorithm textbook. The same applies to
the next section.

Sort

Sort is a generic array sort function. Internally the implementation uses IntroSort
(Musser, 1997) – which is basically a QuickSort with a fallback to HeapSort in order
to achieve a guaranteed O ( n log n) worst case time complexity.

Random Shuffle

RandomShuffle randomly shuffles the elements in an array. The time complexity is
worst case O ( n) , and the random distribution is uniform assuming a uniform internal
random function.

Next Permutation

NextPermutation rearranges the elements in an array to obtain the next permutation
in lexicographic order and returns true . The only exception: if the input is an array
with elements in descending order, the array is reversed (to obtain the lexicographically
smallest permutation) and NextPermutation returns false.
The time complexity of a single call is O ( n) . More precisely, the time complexity of a
single call is linear in the number of necessary changes. Hence a full cycle iterating over
all permutations of a given n-element array runs in O ( n!) .

3. Library Contents – Data Structures

Vector

TVector is an array that can be resized at the end ef?ciently (doubling storage size
when necessary). Most important operations:
• indexing using [] in O (1) ;
• PushBack in amortized O (1) .

Stack

TStack is a traditional stack data structure. Most important operations:1
• Push in amortized O (1) ;
• Top and Pop in O (1) .

Queue

TQueue is a traditional queue data structure. Most important operations:
• Push in amortized O (1) ;
• Front and Pop in O (1) .

Deque

TDeque is a deque (usually pronounced [deck], also called a double-ended queue) – a
self-resizing array that supports indexing and fast element addition/removal at both ends.
Most important operations:
• PushFront and PushBack in amortized O (1) ;
• indexing using [] in O (1) ;
• PopFront and PopBack in O (1) .

The implementations of TStack , TQueue and TDeque all use TVector's for internal data storage,
hence the amortized complexity bounds on insertions. Although there are possible implementations of stacks
and queues with guaranteed constant time complexity, this is the industry standard in other languages. For most uses in practice the amortized time complexity does not matter, and in the remaining cases the stacks/queues can easily be implemented as linked lists.

Priority Queue

TPriorityQueue is a priority queue that allows insertion of ordered elements and
fast extraction of the maximal element. Internally the priority queue is implemented as a
binary heap. Most important operations:
• Push in amortized O (log n) ;
• Top in O (1) ;
• Pop in O (log n) .

Ordered Sets and Maps

TSet is an ordered container of unique elements. TMap is an ordered associative array.
Internally, sets are implemented using left-leaning red-black trees (Sedgewick, 2008),
and maps are implemented as sets of pairs (key,value).
Most important operations:
• Insert , Find, Delete in worst-case O (log n) ;
• Min, Max in worst-case O (log n) ;
• FindLess[Equal] , FindGreater[Equal] in worst-case O (log n) ;
• iteration over all elements in worst-case O ( n) ;
• maps: indexing using [] in worst-case O (log n) .

Unordered Sets and Maps

THashSet is an unordered container of unique elements. THashMap is an unordered
associative array. Internally, unordered sets and maps are implemented as self-resizing
hash tables, with collisions resolved by chaining.
Most important operations (assuming a good hash function is used):
• Insert , Contains , Delete in expected O (1) ;
• iteration over all elements in worst-case O ( n) ;
• maps: indexing using [] in expected O (1) .

(At the moment there are no pre-written hash functions, the programmer has to pro-vide one when using a data structure with a hash table. Default hash functions for basic types are a possible addition in the future.)

4. Comparison o f C ontents to C ++ STL

Table 1 summarizes the correspondences between FPC-STL and the Standard Template
Library for C++. We also highlighted some algorithms and data structures that are avail-able in C++, but are not a part of FCL-STL yet.

FreePascal FCL-STL    C++ STL equivalent

Sort                  sort
RandomShuffle         random_shuffle
NextPermutation       next_permutation
--                    stable_sort, nth_element
TVector               vector
TStack, TQueue        stack, queue
TDeque                deque
TPriorityQueue        priority_queue
TSet, Tmap            set, map
THashSet, THashMap    unordered_set, unordered_map
--                    list
--                    bitset
--                    (unordered) multiset

Sedgewick, R. (2008). Left-leaning red-black trees. Workshop on Analysis of Algorithms, Maresias, Brazil.
Verhoeff ... (2012). IOI Syllabus

Мой профиль

Learning Algorithms with Unified and Interactive Web-Based Visualization
Steven HALIM, Zi Chun KOH, Victor Bo Huai LOH, Felix HALIM
School of Computing, National University of Singapore

We present a unified and interactive web-based visualization of various classical and
non-classical algorithms at http://www.comp.nus.edu.sg/~stevenha/visualization
Our collection of algorithm visualizations has the following advantages over many other web-based algorithm visualizations in the Internet –
(1) it has visualizations of various non-classical algorithms that currently cannot be found elsewhere in the Internet;
(2) it is interactive; users (usually students) can enter their own input data to test the behavior of the algorithm;
(3) it has a consistent user interface across different algorithm visualizations that are currently available;
(4) it is built with HTML5 making it accessible on modern portable PCs including tablets and smart-phones. User studies in two algorithm classes in NUS show that our visualizations is of immense help to some students who prefer to learn visually.

In our opinion, a better way to teach algorithms is to give a combination of a well-
chosen and scripted example with animation (to introduce the concept for the ?rst time )
combined with two-or-three more examples on student-supplied input data. There are
two conditions for this approach to be effective – the visualization of the spontaneous
examples must be animated in a manner that is consistent and bug-free, and it must be
done quickly and not take up too much time.

We made the decision to deliver our visualization on a web-based platform through
the browser so that algorithmic knowledge is accessible to a larger pool of audience
worldwide. Almost every devices nowadays – desktops, laptops, tablets, and even smart-
phones – have bu ilt-in web browser(s), e.g., Mozilla Firefox, Google Chrome, Safari1,
etc., that support HTML5 natively. There is thus no need to install any program or worry
about cross-platform issue.

Standalone visualizations (all URLs are correct as of April 2012)

Various linear data structures 1 2
Various sorting algorithms 1 2 3
Bitmask or bit manipulation (see Section 4.1)
Basic BST (Table) 1 2 3
Balanced BST (AVL) 1 2 3
Heap (priority queue) 1 2
Graph DS (Adjmatrix or list) 1
Union find disjoint sets 1 2
Segment tree (in our future works)
Binary indexed (Fenwick) tree (see Section 4.3)
n-queens recursive backtracking 1 2
Classic dynamic programming (in our future works)
Graph traversal: BFS/DFS+ 1 2
Finding cut vertices, bridges, SCCs (see Section 4.5)
MST (Prim’s) 1 2
MST (Kruskal’s) 1 2
SSSP (Bellman Ford’s) (see Section 4.7)
SSSP (Dijkstra’s) 1 2
APSP (Floyd Warshall’s) 1
Network flow (Edmonds Karp’s) 1 2
Algorithms on DAG (in our future works, e.g., topological sort, shortest/longest path, counting paths)
Algorithms on tree (in our future works, e.g., shortest/longest path, all pairs shortest paths, Lowest Common Ancestor)
Algorithms on bipartite graph 1
String matching 1
Suffix tree 1
Suffix array 1
Algorithms on polygon (see Section 4.9)
Convex hull (Graham’s scan, Andrew’s, Jarvis March) 1 2 3

2.2. Unified Visualizations

Other than the standalone visualizations listed in Table 1, we also found the following unified visualizations that offer more than three visualizations in their website:

1. algoviz.org
is basically a portal that contains links to various algorithm visu-alization websites. In the future, our visualization project will also be listed there.
However, as of April 2012, some of our algorithm visualizations in Section 3 (e.g.,
Fenwick Tree, Tarjan’s SCC, etc.) are not yet available there.

2. www.ansatt.hig.no/frodeh/algmet/animate.html
is another portal that compiles URLs to other visualization websites (similar nature with algoviz.org).

3. nova.umuc.edu/~jarc/idsv/
has visualizations for binary trees, several graph representation and algorithms, and sorting.

4. www.csse.monash.edu.au/~dwa/Animations/index.html
has several visualizations similar nova.umuc.edu/~jarc/idsv/.

5. research.cs.vt.edu/AVresearch/
has several algorithm visualizations developed between 2003 and 2009.

6. www.cs.usfca.edu/~galles/visualization/Algorithms.html
is the closest uni?ed visualization project that is the most similar with the ideas
presented in this paper. It also built with HTML5. We highlight some of the differences between our visualization and this project in Section 3.

Мой профиль

A Self-Paced Learning Platform to Teach Programming and Algorithms
Mathias HIRON, Loic FEVRIER
France-IOI Organization www.france-ioi.org

Self-paced learning platforms have received a lot of attention recently, with the promise of fundamentally changing education. For more than 10 years, the members of the France-IOI non-profit organization have been developing such a platform for teaching programming and algorithmics to self-motivated users ranging from beginners to advanced programmers. With the introduction of algorithmics in the French mathematics curriculum of high school, it is now starting to be used by teachers in classrooms. In this paper, we present and explain the choices we made when creating the contents and tools that constitute this platform.

Keywords: self-paced learning, programming, algorithmics, exercises, e-learning platform

Providing an education perfectly tailored to the needs of each student in a classroom has
long been a dream for teachers as well as students. The practical constraints of giving
an education to the vast majority of children in a country, while trying to give an equal
chance to every child, can often make teaching and learning a very frustrating endeavor.
Teaching children by batches of 25 or sometimes much more, with the criteria for forming
the groups being mostly based on age and place of residence, makes it very hard for
teachers to provide an effective educational experience to every child in the group.
Even if we could somehow form ideal groups where every student had the same back-ground, the same level at the beginning of the year, the same set of skills and learning
style, there would still be no way of giving a lecture in front of this group so that the pace
and content of that lecture would ?t every student’s needs. Anyone can get distracted at
some point and miss a key concept that is essential to understanding the rest of the lec-ture, and students who understood it well the ?rst time will get bored and miss other parts
if the teacher repeats it one more time to make sure everyone gets it.

With a self-paced approach to teaching, each student learns at her own speed, so at
any time, every student in a group could be studying something different. The teacher is
no longer the main provider of knowledge, the time usually spent broadcasting a lecture
to the whole group is freed, and the teacher becomes available to guide students and
help them individually. For a self-paced approach to work well, the external source of
educational content must be of a very good quality, very clear and engaging, so that each
student stays focused and continues learning at a good pace while the teacher is helping
others.

The trend is now changing, and changing fast. A single educational resource, initially
created by one dedicated man, Salman Khan, who authored around 3000 short educational
videos and put them on YouTube, seems to have been the key resource that was
needed for self-paced learning to become possible and popular (Khan 2011). With millions
of students now using the Khan Academy to learn at their own pace, this non-profit
with now 30 full-time employees, has become the source of inspiration for several other
significant initiatives in this field.

One such example is Udacity, an online university
co-founded by Sebastian Thrun, a former Stanford teacher, who after an experiment of
successfully providing a Stanford course on Artificial Intelligence as an online interactive
course to tens of thousands of students around the world, realized that he could have
a much broader educational impact by creating online educational resources available to
everyone, as opposed to teaching smaller groups of Stanford students in classrooms every
year (Eddy, 2012).

... providing the reason for learning the concept before even presenting the concept itself:
instead of providing a short course followed by an application exercise, we start by describing
the exercise and follow on the same page with a short
course that introduces the new concept needed to solve that exercise. The student reads
the short course not because it is pushed to her, but because she is looking for a way to
solve the exercise. Instead of being a passive receiver of a lecture, the student becomes
active and seeks the information.

Most of our users are using our platform from home, so when they get stuck and the platform
doesn’t help them, they are likely to just give up and never come back.

Anticipating Errors

1. By providing courses that present different common errors associated with a recently
learned programming concept, and show the corresponding error messages.
Giving different examples and highlighting where the error is brings their attention
to the types of errors that are possible. By showing and explaining the error
messages associated with them, we reduce the amount of surprise and frustration
the student might get in the future, if he encounters these same error messages. We
don’t necessarily expect students to remember each message, but merely recognizing
something familiar and getting a rough idea of what types of errors can produce
certain types of messages makes things much easier.

2. We give exercises whose only goal and dif?culty is to ?nd and ?x syntax errors in
one or more example programs. By solving these exercises, students learn to look
for and ?x the most common syntax errors. They are then more likely to notice
their own errors in the future.

Providing Help, through the Community or Automatically

Instead of giving them the solution, our goal is to give them the minimum amount of
help that they need to continue by themselves. When possible, we avoid giving them even
part of the solution and try to tell them something that will help them ?nd the solution by
themselves.

.. as the number of our users increased, and our free time diminished, we
decided to set up a system so that other users could help each other. The principle of this
system is quite basic: when stuck on an exercise, a student can ask for help on a forum
where any student who has already solved that exercise can see the question and provide
an answer. We try to make sure people who help others have access to all of the necessary
information, by showing them the history of submissions of the student on that speci?c
exercise. We make it very clear that helping a student doesn’t mean giving
him the solution directly, but only hints that make sure they don’t stay stuck too long.

Keeping Students Engaged
- Presenting Each Exercise in the Context of a Small Story
- Making Each Exercise Part of a Big Adventure
- Recognizing Short Term and Long Term Accomplishments
- Challenges

In 2009, the French ministry of education decided to introduce algorithmic thinking
as a part of the mathematics curriculum in high schools.

By school year 2011–2012, it was clear that most math teachers who were put in charge of teaching this subject had not found a good way to do so, having received no specific training to prepare them for
this change. In August 2011, one of these teachers contacted us, to bring to our attention
the fact that our platform had the potential to become a great tool for teachers to use in
their classrooms. Until then, our target had mostly been self-motivated and passionate
students, and even though we already had some programming courses used by thousands
of users, these were not ready to be used by average high school students with no prior
interest in the subject.

Мой профиль

(продолжение)

The programming concepts listed in this official curriculum are no different than the
first concepts any person interested in learning programming has to learn. As our users
come from a wide range of backgrounds, we decided to make as few assumptions as
possible on their pro?ciency with mathematical concepts. As a consequence, we have
clearly separated our introductory exercises into two categories:

1. Exercises and courses dedicated but limited to introducing the programming con-
cepts. They form a clearly identified linear progression that constitutes the ?rst
chapters of the 5 levels of our core content The chapters that correspond to the
of?cial curriculum contain around 100 small exercises, and an average student is
expected to be able to solve most of these by spending about 20 hours of work.

2. Exercises and courses where these concepts are combined with mathematical
concepts. These exercises are grouped by mathematical subject, and the algorithmic
prerequisites are always given. For each subject, the underlying mathematical
concepts are introduced and progressively mastered, from an algorithmic point of view.
This category now has 40 exercises, and we are planning to greatly increase this
number with the help of teachers, and hope to cover most of the mathematics
curriculum in high school.

All this is work is done by a team of volunteers, including former IOI contestants and
teachers. We do this because we are passionate about algorithmics and teaching it, and we
believe all students have a tremendous potential that can they can reach if they have access
to the right content and tools. As we don’t want to restrict the access to any particular
group, we are looking for volunteers to help us extend the reach of this platform, by
translating existing content into as many languages as possible. The platform is ready
for internationalization, and translation efforts have already started in various languages,
such as English, Spanish, Lithuanian and German.