Разбор задачи «Витрина прототипов»

Идея задачи

У нас есть массив a[1..n], где a[i] — качество прототипа в позиции i.

Нужно выбрать как можно более длинную последовательность индексов p1 < p2 < ... < pk, такую что:

• каждый следующий индекс кратен предыдущему: p(i+1) % p(i) == 0;
• значения строго возрастают: a[p(i+1)] > a[p(i)].

Требуется найти максимальное возможное значение k.

Наблюдение

Если последовательность заканчивается в позиции i, то предыдущая позиция j должна удовлетворять двум условиям:

• j < i;
• i % j == 0;
• a[j] < a[i].

Это сразу подсказывает динамику.

Динамическое программирование

Обозначим через dp[i] длину максимальной корректной последовательности, которая заканчивается в позиции i.

Тогда:

• минимум dp[i] = 1, потому что можно взять только сам индекс i;
• если существует подходящий делитель j, то можно перейти из j в i.

Формула перехода:

dp[i] = 1 + max(dp[j])

по всем j, для которых:

j < i
i % j == 0
a[j] < a[i]

Ответом будет:

max(dp[i])

по всем i.

Почему простой перебор не подходит

Можно было бы для каждого i перебрать все j < i и проверить:

• делит ли j число i;
• выполняется ли a[j] < a[i].

Но такой подход работает за O(n^2), что слишком медленно при n до 100000.

Нужен более эффективный способ перебора только подходящих индексов.

Как ускорить переходы

Если j должен делить i, то вместо перебора всех предыдущих позиций можно делать наоборот:

• фиксируем j;
• перебираем все его кратные: 2j, 3j, 4j, ....

То есть из каждой позиции j мы пытаемся перейти во все позиции k, где k кратно j.

Если при этом a[k] > a[j], то можно улучшить dp[k]:

dp[k] = max(dp[k], dp[j] + 1)

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

Пошаговая схема решения

1. Считываем массив.
2. Создаем массив dp, изначально заполненный единицами.
3. Для каждого индекса i перебираем все его кратные j = 2*i, 3*i, ....
4. Если a[j] > a[i], то обновляем dp[j].
5. В конце берем максимум по массиву dp.

Пример работы

Пусть:

n = 6
a = [1, 4, 2, 3, 6, 5]

Будем считать индексацию с 1.

Изначально:

dp = [1, 1, 1, 1, 1, 1]

Переходы из 1

Кратные 1: 2, 3, 4, 5, 6

• a[2] = 4 > 1 → dp[2] = 2
• a[3] = 2 > 1 → dp[3] = 2
• a[4] = 3 > 1 → dp[4] = 2
• a[5] = 6 > 1 → dp[5] = 2
• a[6] = 5 > 1 → dp[6] = 2

Теперь:

dp = [1, 2, 2, 2, 2, 2]

Переходы из 2

Кратные 2: 4, 6

• a[4] = 3, но 3 > 4 неверно
• a[6] = 5 > 4 → dp[6] = max(2, 2 + 1) = 3

Теперь:

dp = [1, 2, 2, 2, 2, 3]

Переходы из 3

Кратные 3: 6

• a[6] = 5 > 2 → dp[6] = max(3, 2 + 1) = 3

Ответ: 3.

Одна из подходящих цепочек: 1 -> 2 -> 6.

Доказательство корректности

Докажем, что описанный алгоритм действительно находит максимальную длину корректной последовательности.

Что хранит dp[i]

Будем понимать под dp[i] максимальную длину корректной последовательности, которая заканчивается в позиции i.

Это определение естественно, потому что ответ по задаче тогда равен максимуму среди всех dp[i].

Почему переход верный

Рассмотрим любую корректную последовательность, заканчивающуюся в i. Если ее длина больше 1, то в ней есть предыдущий индекс j. По условию задачи обязательно выполняется:

• j < i;
• i кратно j;
• a[i] > a[j].

Значит, перед тем как попасть в i, мы обязаны находиться в одной из допустимых позиций j, а длина такой последовательности будет равна dp[j] + 1.

Следовательно, лучшая последовательность для i действительно вычисляется как максимум по всем таким j.

Почему достаточно перебирать кратные

В алгоритме мы не ищем для каждого i все делители j, а делаем наоборот: для каждого j идем по всем кратным j. Это не меняет множество рассматриваемых переходов.

Каждый допустимый переход вида j -> i, где i % j == 0, будет рассмотрен ровно тогда, когда внешний цикл стоит в j, а внутренний доберется до i.

Почему порядок обхода правильный

Все переходы идут только из меньших индексов в большие, потому что кратное j имеет вид 2j, 3j, ..., то есть всегда больше j.

Следовательно, когда мы обновляем dp[k] из dp[i], значение dp[i] уже окончательно посчитано и корректно.

Вывод

Значит, после завершения всех переходов каждое dp[i] равно длине наилучшей корректной последовательности, заканчивающейся в i, а максимум по всем i и есть ответ.

Оценка сложности

Для каждого i мы перебираем числа:

2*i, 3*i, 4*i, ...

Количество таких переходов для фиксированного i равно примерно n / i.

Итоговая сложность:

n/1 + n/2 + n/3 + ... + n/n = O(n log n)

Память:

O(n)

Это укладывается в ограничения.

Эталонная реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        vector<int> dp(n + 1, 1);
        int ans = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = i + i; j <= n; j += i) {
                if (a[j] > a[i]) {
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            ans = max(ans, dp[i]);
        }

        cout << ans << '\n';
    }

    return 0;
}

Эталонная реализация на Python

import sys

input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    dp = [1] * (n + 1)

    for i in range(1, n + 1):
        for j in range(i * 2, n + 1, i):
            if a[j] > a[i]:
                dp[j] = max(dp[j], dp[i] + 1)

    print(max(dp))

Типичные ошибки

1. Неправильная индексация

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

2. Неверный знак сравнения

Нужно именно строгое возрастание:

a[j] > a[i]

при переходе из i в j.

Если написать >=, ответ станет неверным.

3. Перебор всех пар индексов

Решение O(n^2) не пройдет по времени. Нужно использовать перебор только по кратным.

4. Забыть, что тестов несколько

Важно заново создавать массив dp для каждого набора данных.

Что полезно вынести из задачи

Эта задача хорошо тренирует два важных приема:

• динамику по индексам;
• перебор делителей и кратных вместо полного квадратичного перебора.

Во многих задачах на массивы и теорию чисел полезно думать не только в формате «для текущего элемента ищем предков», но и наоборот — «из текущего элемента куда можно перейти». Здесь именно такой взгляд приводит к эффективному решению.

Итог

Ключевая идея состоит в том, что:

• dp[i] — лучшая длина цепочки, оканчивающейся в i;
• переходы возможны только в кратные позиции;
• поэтому удобно перебирать не делители текущего индекса, а кратные каждого индекса.

Это дает решение за O(n log n) и полностью укладывается в ограничения.