Весна часть 1

1.

Весна: встреча 1
Лодыгин Игорь Олегович,
ассистент кафедры автоматики, робототехники и
управления техническими системами

2.

Что будет сегодня и что будет ещё неделю
Сейчас:
- Рассказ о том, как работает Codeforces и как сделать так, чтобы
пустило.
- Лёгкие, едва весомые подсказки по задачам.
27-го числа:
- Открытие 2-й половины отбора.
29-го числа:
- Очередная серия лёгких подсказок.
- Разбор первой половины отбора.
Когда-то после:
- Разбор второй половины отбора.

3.

Как добраться до задач: часть 0
Осуществите регистрацию
на платформе
codeforces.com в целом.

4.

Как добраться до задач: часть 1

5.

Как добраться до задач: часть 2

6.

Как сдать задачу?

7.

Что такое тестирующая система и почему
ваше решение не зачлось?
1. Компиляция
Сначала система компилирует твой код (если язык требует компиляции, как
C++ или Java).
Если есть ошибки компиляции — тебе сразу покажут, и тестировать не будут.
1. Тестирование
Система запускает твой код на наборе тестов. Есть два типа тестов:
1. Примеры из условия (они прогоняются первыми, но результат не
обязательно показывается отдельно).
2. Скрытые тесты — это главный набор, на котором реально проверяется
твое решение. Эти тесты ты не видишь, они заранее подготовлены
авторами задачи.

8.

Твое решение проверяется на:
1. Правильность (сравнивается вывод твоей программы с правильным
ответом).
1. Скорость (время работы не должно превышать лимит — обычно 1-2
секунды).
1. Память (нельзя выходить за пределы по памяти — например, 256MB).
1. Выход за границы массива, деление на 0, краши и т.д. — всё это тоже
ловится.

9.

С какими вердиктами падают задачи
1. Полное решение
2. Ошибка компиляции
3. Неправильный ответ на тесте Х
4. Превышено ограничение времени на тесте Х
5. Превышено ограничение памяти на тесте Х
6. Ошибка исполнения на тесте Х

10.

Неправильный ответ – почему, и как
бороться?
Сгенерированный вашей программой ответ не совпал с верным ответом.
-1. (отдельным лицам) Осознайте свою версию python.
0.
Прочитайте условие заново в н и м а т е л ь н о!
1. Проверьте ваше решение на крайних и близких к крайним случаях.
2. Если задача состоит из мультитеста, проверьте, разделяются ли
решения по каждому тесту переводом строки.
3. Если задача подразумевает нецелый ответ, попробуйте повысить
количество выводимых цифр.
4. Если задача подразумевает целый ответ, избегайте нецелых значений.
5. Если вы пишете на С++, то прекратите уже использовать int и
переходите на long long.
6. Если ничего не помогло, подумайте, действительно ли ваше решение
правильно?

11.

Ошибка исполнения: как с этим бороться
Ошибка исполнения (на Codeforces — это Runtime Error, сокращённо RE)
означает, что ваша программа "упала" во время работы на каком-то тесте.
То есть она скомпилировалась, запустилась, но в процессе произошло
что-то плохое — и программа аварийно завершилась.
0.
Перестаньте использовать ChatGPT вместо головы :)
1. Проверьте, не выводите ли вы нечто лишнее и не вводите ли нечто
лишнее. Также проверьте, вводите ли вы все, что надо, и выводите ли
все, что надо.
2. Проверьте на выход за границы массивов, списков, строк и т.д.
3. Проверьте код на деление на 0
4. В Python ошибка исполнения выводится при использовании
рекурсивных функций с глубиной погружения >1000.

12.

Превышено ограничение по времени
На каком-то большом тесте ваша программа работает неприлично долго!
Проведите оценку асимптотической сложности вашего решения и
сопоставьте ее с ограничениями задачи.
Размер n (или x или q, или …)
Максимальная допустимая
асимптотика
Пример допустимой сложности
> 10 000 000
O(1) или O(log n)
Математическая формула,
ветвление,
бинарный/тернарный поиск
<= 10 000 000
O(n)
Перебор в цикле
<= 1 000 000
O(n log n)
Встроенная сортировка,
бинарный поиск в цикле
<= 40 000
O(n^2)
Цикл, вложенный в цикл
<= 1 000
O(n^3)
Тройной вложенный цикл (к
примеру, алгоритм Флойда)
< 30
O(2^n)
Перебор подмножеств

13.

Асимптотическая сложность – как
оценить?
Что работает за О(1)?
1. Считывание одного значения
2. Считывание двух значений
3. Считывание определенно небольшого количества значений
4. Арифметические операции
5. Ветвление (if-elif-else)
6. Вывод определенно небольшого количества значений
7. Добавление элемента в конец списка (Python)/вектора(С++)
8. Удаление элемента из конца списка (Python)/вектора(С++)
9. Добавление элементов в множество/словарь (Python)/в
неупорядоченное множество/словарь (С++)

14.

Асимптотическая сложность – как
оценить?
Что работает за O(log n)?
1. Добавление элементов в множество/словарь (С++)
2. Цикл по длине числа в пределах n
3. Бинарный/тернарный поиск в пределах n
Что такое log n?
Логарифм — это математическая операция, которая помогает понять,
сколько раз нужно разделить число на какое-то другое, чтобы получить 1.
Когда говорят O(log n), это значит, что программа делит число n на 2 (или
другое число) несколько раз, пока не получит 1. Количество шагов — это и
есть log n.
log n – небольшая величина (зачастую существенно меньше корня из n),
но его все равно важно учитывать

15.

Асимптотическая сложность – как оценить?
Что работает за О(n)?
1. Большая часть операций на списке или строке размера n (find, count,
erase, срезы и т.д.)
2. Цикл от 1 до n. Или от 1 до 2n. Или от одного до 5n. И так далее.
3. Ввод/вывод n чисел или списка размером n
Что работает за O(n log n)?
1. Встроенные алгоритмы сортировки
O(n + 2n + n + 1 + log n) – это все еще O(n)
O(n^2 + 10n + 1 + n log n) – это все еще O(n^2)

16.

Как решалось А + В
Python
C++

17.

Остальное: без чёткого решения ;-)
B: вспомнить самую малость из математики (простой путь), или же
написать полный перебор (сложный, но интересный путь). В python полный
перебор через itertools - более приятен, чем в среднем по выборке языков.
С: проверить достаточно очевидный факт любым из желаемых способов: в
текущих ограничениях даже и оптимизировать что-то толком не нужно.
D: подобрать формулу (неинтересно, но возможно) или изучить линейный
случай динамического прогарммирования и перенести на задачу
(интересно, полезно)
E: можно подобрать простой и очевидный способ. Можно постепенно
добавлять по одному элементу в строку, проверяя очевидное.

18.

Остальное, часть 2.
F: О нет! Полный перебор вариантов больше не работает! Задайтесь
вопросом: что можно делать с масивом/списком/вектором, кроме как
хранить в нём ряд из чисел?
G: По ограничениям вполне себе пройдёт решение, работающее за
О(n^2), что позволяет писать очень многое. Значения у нас три - можно ли
перебирая лишь одно из них (O(n)) отвечать за два остальных за
оставшийся (O(n)) ?
H: Классическая ситуация, в которой можно вспомнить жадный подход
(для всех) или даже углубиться в тему нетрадиционных систем счисления
(можно, но зачем?)
I: “Квадратное” (а на самом деле и вовсе кубическое) решение с
перебором всех возможных вариантов точно не прокатит. Но кто мешает
его оптимизировать, задавшись вопросом “А в каком случае всё точно
YES?”