Занятие 13. Рубежный контроль № 1

Занятие 13 — первый рубежный контроль: письменная работа по материалу занятий 1–12. Эта страница — всё, что нужно для подготовки: формат, карта тем со ссылками на конспекты, критерии и тренировочный вариант, устроенный ровно как боевой.

Формат

• 90 минут, письменно, без электроники и конспектов.
• 6 заданий, 26 баллов; вес указан у каждого задания, частичные баллы есть везде — пишите рассуждение, даже если ответ не добит.
• Код — на C++, не псевдокод. Мелкие синтаксические неточности не штрафуются; логика — да.
• В задачах на двоичный поиск и два указателя выписанный инвариант обязателен: решение без инварианта оценивается не выше половины баллов задания.
• Два параллельных варианта, равной сложности.

Карта заданий

Как выглядит решение на полный балл

В задачах 5–6 проверяется схема рассуждения, а не только код: предикат → довод монотонности одной фразой → инвариант → сдвиги под инвариант → ответ и сложность. Инвариант — это и есть решение; код — его расшифровка.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// Предикат: can(d) = [сумма floor(a_i / d) >= k]
// Монотонность: d растёт => каждое слагаемое не растёт
//   => can: true...true false...false
// Инвариант: can(l) = true, can(r) = false
long long l = 1, r = maxA + 1;
while (r - l > 1) {
    long long m = l + (r - l) / 2;
    if (can(m)) l = m;
    else        r = m;
}
return l;   // последний true
// Сложность: O(n log(max a))

Тот же код без трёх строк комментария — минус половина баллов задания.

Топ граблей прошлых лет

1. «Два вложенных цикла ⇒ n log n». Глубины циклов не перемножаются — считается сумма работы. Внешний цикл с удвоением даёт геометрическую прогрессию $1 + 2 + 4 + \dots < 2n$ — это $\Theta(n)$.
2. (l + r) / 2. Переполнение — девятилетний баг java.util.Arrays. Только l + (r - l) / 2; в предикатах проверяйте и m * m — спасает сравнение делением m <= n / m.
3. for (auto x : v) x *= 2; — удваиваются копии, вектор не тронут. Нужен auto&.
4. «Амортизация = всегда O(1)». Нет: отдельная операция бывает $\Theta(n)$; гарантия — на сумму по худшей серии операций, без всяких вероятностей.

Тренировочный вариант

Устроен ровно как боевой: те же темы, тот же вес, другие числа. Сначала решите на время — 90 минут без конспекта, — потом открывайте ответы.

Задание 1. Сложность (4 балла)

a) Оцените время работы как $\Theta$ от $n$, обоснуйте:

1
2
3
4

long long s = 0;
for (int i = 0; i < n; i += 2)
    for (int j = n; j > 1; j /= 2)
        s += j;

b) Упорядочите по скорости роста, отметьте равные: $2^{2\log_2 n}$, $n \log_2 n$, $\sqrt{n} \cdot \sqrt{n}$, $3^n$.

Задание 2. Рекурренты (4 балла)

a) Решите основной теоремой (укажите $a$, $b$, $c$ и случай): $T(n) = 2\,T(n/4) + \Theta(\sqrt{n})$.

b) Из двух соотношений одно решается основной теоремой, другое — нет. Решите оба и объясните, какое и почему выпадает из теоремы: $T(n) = T(n/2) + \Theta(1)$ и $T(n) = T(n-2) + \Theta(1)$.

Задание 3. Чтение C++ (5 баллов)

a) Что напечатает программа и почему?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

struct C {
    int v;
    int  get() const { return v; }
    void set(int v)  { v = v; }
};
int main() {
    C c{10};
    c.set(42);
    std::cout << c.get();
}

b) Автор положил в заголовок utils.h строку static int counter = 0; и включил его в три .cpp-файла, ожидая общий счётчик. Что получилось на самом деле?

c) Для каждой строки: компилируется ли, и если да — какой тип:

1
2
3
4

enum class Level : std::uint8_t { Low, High };
auto a = Level::Low;          // (1)
int  b = Level::High;         // (2)
auto c = 7 / 2.0;             // (3)

Задание 4. Амортизация (5 баллов)

Двоичный счётчик на $k$ битах поддерживает одну операцию — инкремент: он перещёлкивает младшие единицы в нули и первую попавшуюся ноль в единицу.

a) Докажите банковским методом, что инкремент имеет амортизированную стоимость $O(1)$: укажите тариф и объясните, почему баланс не уходит в минус.

b) Отдельный инкремент может перещёлкнуть все $k$ бит. Сформулируйте точно, что гарантирует амортизированная оценка — и чего она не гарантирует.

Задание 5. Двоичный поиск по ответу (5 баллов)

Найдите наибольшее целое $k$ такое, что $k^3 \le n$, для $n$ до $10^{18}$.

a) Предикат, довод монотонности, инвариант.

b) Функция long long icbrt(long long n); сложность. Осторожно: $m^3$ для середины $m$ может не влезать в long long — как проверять без переполнения?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

long long icbrt(long long n) {
    long long l = 0, r = 1'000'001;
    // инвариант: l^3 <= n < r^3
    while (r - l > 1) {
        long long m = l + (r - l) / 2;
        // m^3 <= n  без переполнения: делим, а не умножаем
        if (m <= n / m / m) l = m;
        else                r = m;
    }
    return l;
}

Задание 6. Два указателя (3 балла)

Массив из $n$ положительных чисел. Найдите максимальную длину подотрезка с суммой $\le M$ за $O(n)$. Инвариант окна обязателен.

1
2
3
4
5
6

long long sum = 0; int best = 0, l = 0;
for (int r = 0; r < n; r++) {
    sum += a[r];
    while (sum > M) sum -= a[l++];
    best = std::max(best, r - l + 1);
}

Стратегия на 90 минут

Застряли на десять минут — переключитесь: балл в соседней задаче дешевле. Проверка краёв — как на семинаре 12: массив из двух элементов, массив из одинаковых, пустая структура.

После контрольной

Разбор обоих вариантов — в начале занятия 14; апелляции — неделя после объявления результатов, приходить с работой и конкретным пунктом критериев. Дальше по курсу — умные указатели: занятие 11 обещало «delete на всех путях сделают за нас», посмотрим, как именно.