Форум DL

Мой профиль

Очень часто многие на разборе понимают, что для решения задачи не нужно было знать ничего сверх того, что они уже знают.

И тогда встают вопросы
- Почему же не придумалось решение?
- Что и как нужно делать во время олимпиады, чтобы ПРИДУМЫВАТЬ решения, для которых уже есть достаточно теоретических знаний?

В статье
Teaching Algorithmics for Informatics Olympiads: The French Method
http://www.mii.lt/olympiads%5Fin%5Finformatics/pdf/INFOL018.pdf

Авторы утверждают, что разработали метод решения задач.
Далее приводится конспект их оригинального текста по вопросу
(ссылка на полный текст статьи приведена выше).
Для тех, кто с анлийским "не на короткой ноге" я приведу максимально полный и точный перевод этого конспекта. А затем предлагаю ВСЕМ олимпиадникам, особенно наиболее успешным поделиться СВОИМ опытом придумывания решений - в ответах на данное сообщение.

Teaching the Problem Solving Method

While training students along the years, it was tried as much as possible to give reusable hints, i.e., hints valuable not only to the current problem but for others as well. Reusable hints were then collected and sorted in an organized document. In recent years, the authors have improved this document by carefully analyzing the way they come up with ideas for solving difficult problems. As a result, a general problem solving method was
developed. This method is not a magical recipe that can be applied to solve any algorithmic problem, but someone who is sufficiently trained to apply this method will be able to solve more difficult problems than he/she could have solved without it.

Dimensions of the Problem

The objective is to build an exhaustive list of the dimensions of the problem. The word “dimension” is to be taken in its mathematical sense; informally it corresponds to everything in the problem that can take multiple values (or could if it was not settled to a specific value). Dimensions should be ordered by type: they can be the values from the input data, from the output data, or intermediate values that are implicitly necessary
to be manipulated in order to get the output. For each dimension in that list, the range of possible values should be indicated. The
constraints for the input dimensions are usually given in the task. For other dimensions, some calculations (or approximations) might be needed.

The Power of Simplification

“Simplify the problem, and try to solve each simplified version as if it was a new, independent problem.”

1. For each dimension of the task (see Subsection 4.2) try to simplify the problem by either:
(a) removing the dimension,
(b) setting the value for this dimension to a constant, or
(c) reducing the range of possible values for that dimension.

2. Among the resulting simplifications, rule out those which clearly lead to a noninteresting problem. Then, for the sake of efficiency, sort the remaining simplified problems according to their interest – this is to be guessed by experience.

3. For each simplification considered, restate the corresponding problem as clearly as possible and try to solve it as if it were a completely independent problem. This may involve applying the problem solving method recursively, including a further
simplification attempt.

4. Try to combine the solutions of the different problems in order to get some ideas for the complete problem. (There are some specific techniques to help with this step).

Graphical Representations: Changing Points of View

Drawing different examples on a piece of paper and looking at them can be a very good way to get ideas. “Don’t stick to your first idea of a graphical representation and try different ways to draw examples”.

General Structure

1. Restate the problem (or sub-problem) in the simplest way, discarding superficial elements of the story, to get a clear idea of its essence. A good formulation usually involves two sentences: the first one describes the data and the second one the question that must be answered on this data. Someone who has not seen the full task should be able to start looking for a solution after reading this description only.

2. Write down a list of all the dimensions involved in the task and the corresponding constraints. This further helps to get a clear idea of the task and is necessary both to find a good graphical representation (Step 3) and to simplify the problem (Step 6).

3. Find the best graphical representations for the task. This can make working on examples (Step 4) much more effective at bringing ideas.

4. Generate different kinds of examples and solve them carefully and entirely by hand. These examples should be large enough so that the answer is not obvious and needs some effort to be determined. This step has many benefits. First, it helps to get all the details of the problem clearly in mind. Also since the brain is naturally lazy, ways to avoid doing too much work will often come automatically, which can lead to good ideas. These examples will be used again later to test new ideas and check the final implementation, so writing them rigorously is rarely a waste of time.

5. Look for an algorithm that gives a correct answer to the problem, without worrying about efficiency, and describe it clearly. The purpose is to separate the concern of correctness from the concern of efficiency and this often helps to clarify the
recursion involved in the task. In some cases, writing it as pseudo-code may be a good idea. Depending on the form of this “naive” solution, different specific methods can then be applied to transform it into an efficient solution. Note that it is
sometimes useful to implement such a brute-force solution, to generate data from some examples that one can then analyze to look for specific properties.

6. Simplify the problem and try to solve each simplified version as if it were a new, independent problem. Then try to combine the
different ideas into a solution for the original problem.

7. Try to see the task from different point of views by listing standard algorithms and wondering how they could be applied. One may ask questions like “can the problem be seen as a graph problem?”, “could it be solved with a shortest path algorithm?”, or “how could a sweep-line technique be applied?” and so on. Even
in the case where the solution is not a standard algorithm, changing point of view on the task in this way may help to bring new, original ideas.

For each promising idea obtained during this first part the students are asked to go through the following steps. Note that Step 5 should be applied on any “reasonable” idea that is found to be incorrect.

1. Describe the solution in a couple of sentences. The objective is to make it clear enough that anyone who knows the task and is experienced with algorithmics can understand the idea. Depending on the type of the algorithm, the method provides standard ways to describe the solution.

2. Find a good graphical representation of the algorithm. In a similar fashion, there is often one or more good ways to represent
the dynamics of an algorithm graphically. This can help to understand why it works and brings attention to special cases or possible optimizations. Again, the method provides standard representations for certain classes of algorithms.

3. Using this graphical representation, try to execute the algorithm by hand on a couple of examples. This gives a better feeling of how it works and may bring up elements to think about during the implementation.

4. Look for counter-examples to this algorithm, as if it were a competitor’s solution that you want to prove wrong (i.e., forget that you really hope it works). If a counter-example can be found, then it often offers an excellent example to use when looking for better ideas. It is also useful to explicitly state why the idea does not work.

Мой профиль

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

5. After spending some time looking for counter-examples without finding any, it usually becomes clear why there is no chance of finding a counter-example. In other words, it becomes clear why the algorithm is correct. While it is too hard and too long to carry out a formal demonstration of correctness, stating the main invariants that make the algorithm work reduces the risk of implementing an incorrect algorithm.

6. Determine the time and memory complexities as well as the corresponding running time and actual memory needed. At this point you may decide if it is worth going ahead with this algorithm or better to keep looking for more efficient and/or simpler solutions.

7. Write the pseudo-code of the algorithm, try to simplify it and test it before going ahead with the actual implementation.

Мой профиль

Итак обещанный перевод

Обучение методу решения задач

Тренируя школьников много лет, мы пытались давать как можно более "повторно-используемые" советы, то есть советы, полезные не только для решения текущей задачи, но также и для решения других задач. Эти "повторно-используемые" советы собирались, и включались в хорошо организованный документ. В последние годы авторы улучшили этот документ, внимательно анализируя путь, которым они пришли к идеям для решения трудных задач. Как результат был разработан общий метод решения задач. Этот метод не является магическим рецептом, который может быть применен для решения любой алгоритмической задачи. Однако те, кто научился успешно применять этот метод, способны решить более трудные задачи, чем они могли решать без этого метода.

Предварительные понятия

Размерности задачи

Цель - построить исчерпывающий список размерностей задачи. Слово "размерность" рассматривается здесь в математическом смысле. Неформально, оно соответствует всему в задаче, что может принимать различные значения. Размерности необходимо упорядочить по типам:
входные переменные, выходные переменные, промежуточные переменные, которые требуются, чтобы получить выходные. Для каждой такой величины нужно указать полный диапазон значений, которые она может принимать. Ограничения для входных значений обычно даются в условиях задачи. Для других величин могут потребоваться некоторые вычисления или аппроксимации.

Сила упрощения

"Упрощай задачу и старайся решить каждую упрощенную версию как новую, независимую задачу"

1. Для каждой размерности задачи старайся упростить ее одним из способов:

(a) удалив размерность
(b) установив значение величины в постоянное
(c) уменьшив диапазон возможных значений для этой величины

2. Среди получающихся вариантов отбрасывайте вырожденные случаи, а остальные упорядочивайте по важности - полагаясь на свой опыт.

3. Для каждого совершенного упрощения, переформулируйте задачу так просто, как это возможно, и попытайтесь решить ее, возможно применив рекурсивно данный метод решения задач, продолжая попытки упрощения.

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

Графическое представление: изменение точек зрения

Рисование различных примеров на листке бумаги и разглядывание их может оказаться хорошим способом для появления идей. "Не зацикливайтесь" на первой идее графического представления и старайтесь рисовать примеры различными способами.

Общая схема

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

2. Выпишите все размерности задачи и соответствующие ограничения. Это поможет в дальнейшем получить ясную идею задачи, и необходимо и для отсыкания хорошего графического представления, и для упрощения задачи.

3. Найдите наилучшее графическое представление для задачи. Это можно сделать, работая над примерами. И это может быть эффективно для выработки идей.

4. Придумывайте различные виды примеров и решайте их внимательно вручную. Эти примеры должны быть достаточно большими, чтобы ответ не был очевиден, и требовались некоторые трудозатраты для его получения. Этот шаг приносит много выгод. Первое - это поможеть осознать все детали задачи. Также, посокольку мозгу естественно лениться, пути избежать выполнения большей работы возникают автоматически, а это может привести к хорошим идеям.

Наконец, эти примеры могут быть использованы позже для тестирования
новых идей и проверки окончательной реализации, поэтому такая
работа редко бывает пустой тратой времени.

5. Взгляните на алгоритм, который дает правильный ответ для задачи,
не заботясь об эффективности, и опишите его ясно. Цель - отделить
корректность от эффективности. И это часто помогает уточнить
рекурсию, присущую задаче. В некоторых случаях, записывание
алгоритма на псевдо-коде, может быть хорошей идеей. В зависимости
от формы этого "наивного" решения, различные специфические методы
могут быть применены для преобразования его в эффективное решение.
Заметим, что иногда полезно бывает реализовать такое "brute-force"
решение (полный перебор), чтобы сгенерировать данные из некоторых
примеров и анализировать их в поисках специфических свойств.

6. Упрощайте задачу и старайтесь решить упрощенную версию как новую,
независимую задачу. Затем старайтесь объединить различные идеи
в решение исходной проблемы.

7. Старайтесь посмотреть на задачу с различных точек зрения,
перечисляя стандартные алгоритмы и анализируя могут ли они
быть применены и как. Можно задаваться вопросами типа:
Можно ли рассматривать эту задачу как задачу на графах?
Можно решать ее как задачу о кратчайших путях? Можно ли применить
метод сканирующей прямой? и т.д. Даже в случае, когда решение
не является стандартным алгоритмом, изменение точки зрения на
задачу может принести новые, оригинальные идеи. Для каждой
интересной идеи, полученной в результате анализа, необходимо
выполнить ручной просчет для проверки на корректность, а затем
выполнить следующие шаги.

1. Опишите решение парой предложений. Цель - сделать решение
достаточно ясным для любого, кто знает задачу и достаточно
знаком с алгоритмами, чтобы понять идею. В зависимости от типа
алгоритма метод предлагает стандартный сопсоб описывать решение.

2. Найдите хорошее графическое представление алгоритма. Аналогично
данным задачи, часто существует один или несколько хороших способов
представить динамику алгоритма графически. Это поможет понять,
почему алгоритм работает и обратить внимание на специальные случаи
и возможные оптимизации. Опять-таки метод дает стандартные
представления для определенных классов алгоритмов.

3. Используя графическое представление, постарайтесь исполнить
алгоритм на нескольких примерах. Эта даст лучшее понимание того,
как работает алгоритм и может указать на элементы, над которыми
нужно подумать во время реализации.

4. Поищите контр-примеры для этого алгоритма, как будто это решение
противника, про которое нужно доказать его ошибочность (то есть
забудьте , что Вы надеетесь, что алгоритм работает). Если удалось
найти контр-пример - улучшайте идею алгоритма. Важно в этом случае
также точно определить, почему идея не работает.