Алгоритмы и структуры данных на ПМИ 2017/2018 (основной поток)/Кр критерии

Вариант 1

Задача 1

• Решение за квадратичное время при наличии доказательства и оценки времени — 2 балла
• Решение за квадратичное время без доказательства или оценки времени — 1 балл
• Решение с поиском точек сочленения без учета городов A и B — штраф 2 балла
• Решение с поиском точек сочленения с неполным доказательством корректности и оценкой времени — штраф 1–2 балла
• "Решается через точки сочленения из дз" — 1 балл
• "Решается через мосты из дз" — 0 баллов

Задача 5

• Решение за время O(nf) — 6 баллов
• Решение за время O(n log f) — 8 баллов
• Решение за время O(n) — 10 баллов.
• Неправильное решение с разумными мыслями — 2 балла

Вариант 2

Задача 2

• Задача верно решена и обоснована — 5 баллов
• Задача решена верно, в обосновании присутствуют недочёты — 4 балла
• Задача решена верно, в обосновании есть серьёзные ошибки, либо оно отсутствует вовсе — 3 балла
• Задача решена частично, получен неправильный ответ — 2 балла
• Решение не доведено до конца — 1 балл
• Решение отсутствует — 0 баллов

Задача 5

• Корректное и оптимальное решение — 8 баллов
• Корректное, но не оптимальное решение — 5 балла
• Корректно описано формирование графа — 3 балла