Практика: Временная сложность

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

• Потерянная карточка: N до 10⁵, поэтому искать каждое число среди карточек — это около 10¹⁰ шагов. Пометьте карточки в векторе seen или вычтите их сумму из N · (N + 1) / 2 — в long long.
• Выравнивание массива: не прибавляйте по 1 — ответ может быть около 10¹⁴. Каждый элемент должен дорасти до максимума, поэтому сложите mx - a[i] в long long.
• Циклический сдвиг массива 2: сдвиг на одно место, повторённый k раз, — это n · k шагов. Ставьте каждый элемент сразу на его место, b[(i + k) % n] = a[i], или выведите сначала последние k элементов, а потом остальные.