Общие сведения о конвейере

1. Это один из главных компонентов успеха на соревновании
2. Позволяет организовать параллельное решение задач

Конвейер организуется ситуативно и зависит от многих факторов:

1. Количества задач на соревновании
2. Максимальных возможностей команды
3. Разности уровней подготовки участников команды
4. Специализации каждого участника
5. Сложившейся ситуации

Что даёт правильная организация конвейера:

1. Минимальный простой компьютера
2. Эффективное распределение времени
3. Параллельное решение задач

---

Как организовать конвейер

В зависимости от количества задач на соревновании

Чтобы понять идею организации конвейера, необходимо ответить на вопрос: Как максимально эффективно распределить время для решения N задач возрастающей сложности, имея трёх человек в команде?

Также предполагается, что каждый участник должен самостоятельно решать от $\left \lfloor{\frac{N}{3}} \right \rfloor - 1$ до $\left \lfloor{\frac{N}{3}} \right \rfloor$ задач. Например, если на соревновании даны $N = 11$ задач, то каждый участник должен решить самостоятельно по $\left \lfloor{\frac{N}{3}} \right \rfloor = \left \lfloor{\frac{11}{3}} \right \rfloor = 3$ задачи, чтобы организовать параллельную работу конвейера. Оставшиеся две задачи будут решаться сообща, т.е. 2-3 человека будут думать над решением одной задачи.

Сначала рассмотрим ответ на этот вопрос для $N = 1$.

Очевидно, что самый эффективный способ – решение тремя людьми одной задачи.

В данной ситуации:

1. Вся команда ищет решение одной задачи
2. После найденного решения один участник программирует его
3. Вся команда тестирует написанную программу

Для $N = 2$:

Т.к. задачи возрастают по сложности, то простую задачу следует решать одному человеку, а сложную двум (схема $1 + 2$).

В данной ситуации:

1. Участник 1 решает Задачу 1
2. В то же время Участник 2 и Участник 3 вместе решают Задачу 2
3. Первый, кто получил решение своей задачи, программирует его, тестирует и отправляет на проверку
   • Если решение неверное, то ищет ошибки в нём
4. Первый, кто получил AC на своей задаче, начинает помогать в решении второй задачи

Для $N = 3$:

В данном случае может быть два варианта организации конвейера:

1. Параллельно 3 задачи за 1 этап, если каждый участник способен решить 1 задачу самостоятельно

В данной ситуации:

1. Каждый участник решает свою задачу
2. Первый, кто получил решение своей задачи, программирует его, тестирует и отправляет на проверку
   • Если решение неверное, то ищет ошибки в нём
   • Компьютер освобождается
3. Первый, кто получил AC на своей задаче, начинает помогать в решении более сложной задачи
   • Или по ситуации, в зависимости от того, в какой из оставшихся задач больше трудностей
4. Второй получивший решение своей задачи программирует его, тестирует и отправляет на проверку
   • Если решение неверное, то ищет ошибки в нём
   • Компьютер освобождается
5. Если обе задачи сданы, то освободившиеся участники помогают с решением последней задачи

2. Первые две аналогично $N = 2$, а третью вместе после решения первых двух за 2 этапа

В данной ситуации:

1. К решению Задачи 3 приступают освободившиеся участники только после получения AC для одной из первых двух задач
2. Далее должна быть сдана вторая по сложности задачи
   • А параллельно ей уже решается Задача 3
3. После получения AC на первых двух задачах вся команда решает Задачу 3

Для $N = 4$:

В данной ситуации:

1. Решение первых трёх задач происходит аналогично конвейеру для $N = 3$ за один этап
2. Первый участник, получивший AC на своей задаче, приступает к решению Задачи 4
3. Следующий участник, получивший AC на своей задаче, начинает помогать в решении оставшейся на первом этапе задачи
   • Если это не нужно, то переходит на Задачу 4
4. Последний участник получает AC на своей задаче и приступает к решению Задачи 4
5. Вся команда решает одну задачу, как для $N = 1$

Для $N = 5$:

В данной ситуации:

1. Решение первых трёх задач происходит аналогично конвейеру для $N = 3$ за один этап
2. Первый участник, получивший AC на своей задаче, приступает к решению Задачи 4
3. Следующий участник, получивший AC на своей задаче, приступает к решению Задачи 5
4. Последний участник получает AC на своей задаче и начинает помогать в решении Задачи 5
5. Команда решает 2 задачи, как для $N = 2$

Для $N = 6$:

В 3 этапа:

В данной ситуации:

1. Организация конвейера 1-го и 2-го этапов аналогична случаю для $N = 5$
2. Переход с 2-го на 3-ий этап осуществляется как для $N = 3$ в 2 этапа

В 2 этапа:

В данной ситуации:

1. Участник при решении своей задачи на 1-ом этапе переход к решению задачи на 2-ом этапе
2. Когда участник уже самостоятельно решил 2 задачи, он начинает помогать другим участникам команды
   • Если к этому моменту у какого-либо участника не завершён 1-ый этап, то необходимо помочь ему
   • Иначе по ситуации

Далее аналогично.

Общий вид организации конвейера для N задач

Для $N \mod 3 = 0$ или $N \mod 3 = 1$:

или

Для $N \mod 3 = 2$:

В зависимости от максимальных возможностей команды

Если на соревновании дано $N$ задач, а команда на соревнованиях аналогичной сложности в среднем решает $M$ задач, то необходимо организовать конвейер для решения $M$ задач. Далее действовать по ситуации, например решать задачи втроём:

В зависимости от разности уровней подготовки участников команды

Если в команде существует явная градация по уровню подготовки между участниками, то следует менять распределение задач в пределах одного этапа.

Если $Участник_1 > Участник_2 > Участник_3$, где $Участник_A > Участник_B$ значит, что $Участник_A$ более подготовлен, чем $Участник_B$, то общий вид конвейера для $N$ задач будет выглядить иначе:

Для $N \mod 3 = 0$ или $N \mod 3 = 1$:

или

Для $N \mod 3 = 2$:

---

Организация конвейера в зависимости от специализации каждого участника

Специализация по роли в команде

Если в команде есть сильный [[3. Команда на соревновании|программист]], то реализацией решений задач занимается он. Соответственно, необходимо организовать для него поток решений, которые ему нужно будет запрограммировать. Главная задача других участников команды – находить решение новой задачи, пока программист реализует решения предыдущих задач.

Специализация по классу задач

Если участник команды имеет больше опыта в решении задач на данную тему, то стоит передать решение такой задачи ему.

В зависимости от сложившейся ситуации

Могут произойти ситуации, нарушающие работу конвейера. Например, неспособность участника продолжить участие в соревновании или долгое решение одной задачи.

Нарушение работы конвейера – это гарантированный провал на соревновании.

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

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

---