Неделя 2

Семинар. Два указателя, окно, префиксные суммы

скачать .ipynb lab02_tests.py

Семинар 2. Два указателя, окно, префиксные суммы

На этой паре вы решите задачи на массивы: частотный подсчёт, два указателя, скользящее окно, префиксные суммы и разностный массив. Сдаёте этот файл в LMS.

На семинаре 1 дополнительная память $O(1)$ значила «несколько переменных». Здесь массив нужен: индекс бывает позицией во входе, а бывает значением. Квадратный перебор по длине отрезка или по всем парам на больших тестах не успеет: тестер даёт TLE (лимит 2 секунды на тест), не только «не тот ответ».

Задачи 1–8 — основа занятия. Девятая и десятая — если после восьмой осталось время.

Можно спрашивать соседа и семинариста. Готовое решение копировать не стоит: тесты это не заменят, а на зачёте рядом никого не будет.

Как устроен ноутбук

Как на семинаре 1: ячейки Markdown и Code; командный режим — Esc, правка — Enter; Shift+Enter выполняет ячейку.

Скачайте с сайта курса этот файл .ipynb и файл lab02_tests.py в одну папку. Без файла тестов проверка не запустится. Откройте ноутбук из этой папки.

Ввод, вывод и тесты

Решение — функция без аргументов: внутри input и print, как в контесте. Тест подставляет входы сам. Не заполняйте поле ввода Jupyter.

В каждой задаче стоит заглушка: она что-то читает и печатает неверный ответ. Сначала запустите ячейку: увидите «не OK» или TLE, вход, «ожидалось» и «получено». Потом замените тело функции.

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

In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]

from lab02_tests import (
    test_task1,
    test_task2,
    test_task3,
    test_task4,
    test_task5,
    test_task6,
    test_task7,
    test_task8,
    test_task9,
    test_task10,
)

print('Тесты подключены')

Частотный массив: индекс — значение

На семинаре 1 индекс обычно значил позицию во входе. Здесь диапазон значений маленький и известен заранее: от $0$ до $1000$. Тогда ячейка массива может значить не «кто стоит на месте $i$», а «что известно про число $v$».

После одного прохода по входу у вас есть сводка по всем значениям. Нуля в сводке и «значение ни разу не встретилось» — разные вещи.

Найдите самое редкое встретившееся значение; при равной частоте — меньшее число.

Задача 1. Самое редкое значение

Дан массив целых чисел из диапазона от $0$ до $1000$ включительно. Среди значений, которые встречаются в массиве хотя бы один раз, найдите то, которое встречается наименьшее число раз. Если таких значений несколько, выведите меньшее из них.

Вход. Первая строка: целое $n$ ($1 \le n \le 2\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($0 \le a_i \le 1000$).

Выход. Одно целое — ответ.

-> 6
-> 3 1 3 2 1 3
--
<- 2

-> 5
-> 7 7 7 7 7
--
<- 7

-> 4
-> 0 1000 0 5
--
<- 5
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task1


def task1():
    n = int(input())
    a = list(map(int, input().split()))
    print(0)


test_task1(task1)

Два указателя вперёд: слияние

Даны два уже упорядоченных массива. Нужен один общий, тоже по неубыванию.

Сортировать склейку целиком можно, но приём этой недели другой: оба массива уже стоят в нужном порядке, и достаточно смотреть на их «головы». Подумайте, кого взять в ответ сейчас и что делать, когда один из массивов кончился.

Пустой массив бывает: $n = 0$ или $m = 0$. Тогда input() вернёт пустую строку.

Слейте два упорядоченных массива в один.

Задача 2. Слияние двух массивов

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

Вход. Первая строка: $n$ и $m$ ($0 \le n, m \le 2\cdot 10^5$, $n+m \ge 1$). Вторая строка: $n$ чисел (если $n = 0$, строка пустая). Третья: $m$ чисел (если $m = 0$, строка пустая). $|a_i|, |b_i| \le 10^9$.

Выход. Одна строка из $n+m$ чисел через пробел.

-> 3 3
-> 1 3 5
-> 2 4 6
--
<- 1 2 3 4 5 6

-> 2 3
-> 1 1
-> 1 1 2
--
<- 1 1 1 1 2

-> 0 2
->
-> 4 7
--
<- 4 7
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task2


def task2():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    print(0)


test_task2(task2)

Два указателя с концов

Массив уже упорядочен по неубыванию. Нужны два разных индекса, сумма значений равна $S$.

Перебор всех пар на больших $n$ не успеет (TLE). Раз массив упорядочен, концы отрезка несут информацию: слишком большая или слишком маленькая сумма подсказывает, какой конец сузить. Индексы в ответе — с единицы, $i < j$. Если пар несколько, тесты принимают любую верную.

Найдите любую пару индексов с суммой $S$.

Задача 3. Пара с суммой S

Дан массив из $n$ целых чисел, упорядоченный по неубыванию, и число $S$. Найдите два элемента с разными индексами, сумма которых равна $S$.

Гарантируется, что хотя бы одна такая пара существует. Если подходящих пар несколько, выведите любую.

Вход. Первая строка: $n$ и $S$ ($2 \le n \le 2\cdot 10^5$, $|S| \le 2\cdot 10^9$). Вторая строка: $n$ чисел, $a_1 \le \ldots \le a_n$, $|a_i| \le 10^9$.

Выход. Два целых $i$ и $j$ ($1 \le i < j \le n$).

-> 4 9
-> 2 7 11 15
--
<- 1 2

-> 4 18
-> 2 7 11 15
--
<- 2 3

-> 5 8
-> 1 2 3 4 4
--
<- 4 5
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task3


def task3():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    print(1, 2)


test_task3(task3)

Префиксные суммы

Нужны суммы на многих отрезках $[l, r]$ (нумерация с единицы, оба конца включительно). Заново складывать элементы отрезка на каждый запрос на больших $n$ и $q$ не успеет.

Имеет смысл один раз подготовить массив и дальше отвечать на запрос, не глядя внутрь отрезка. Аккуратно решите, что брать на границах: «до $r$ включительно» легко спутать с полуинтервалом.

Ответьте на серию запросов, не складывая отрезок заново каждый раз.

Задача 4. Сумма на отрезках

Дан массив из $n$ целых чисел. Поступают $q$ запросов: для каждого выведите сумму элементов на отрезке с индексами от $l$ до $r$ включительно (нумерация с единицы).

Вход. Первая строка: $n$ и $q$ ($1 \le n, q \le 2\cdot 10^5$). Вторая: $n$ чисел, $|a_i| \le 10^9$. Далее $q$ строк: $l$ $r$ ($1 \le l \le r \le n$).

Выход. $q$ строк: в $i$-й — сумма для $i$-го запроса.

-> 5 3
-> 1 2 3 4 5
-> 1 1
-> 2 4
-> 1 5
--
<- 1
<- 9
<- 15

-> 3 2
-> -5 10 -3
-> 1 3
-> 2 2
--
<- 2
<- 10
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task4


def task4():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    for _ in range(q):
        l, r = map(int, input().split())
        print(0)


test_task4(task4)

Скользящее окно фиксированной длины

Нужна сумма каждого отрезка длины $k$: с позиции $1$, затем $2$, и так до конца.

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

Выведите суммы всех отрезков длины $k$.

Задача 5. Окно длины $k$

Дан массив из $n$ целых чисел и число $k$. Для каждого отрезка длины $k$ выведите сумму его элементов. Отрезки идут подряд: с индексов $1\ldots k$, $2\ldots k+1$, …, $n-k+1\ldots n$ (нумерация с единицы).

Вход. Первая строка: $n$ и $k$ ($1 \le k \le n \le 2\cdot 10^5$). Вторая: $n$ чисел, $|a_i| \le 10^9$.

Выход. Одна строка из $n-k+1$ чисел — суммы в порядке возрастания левой границы.

-> 5 3
-> 1 2 3 4 5
--
<- 6 9 12

-> 4 4
-> 2 -1 2 -1
--
<- 2

-> 6 1
-> 7 0 7 0 7 0
--
<- 7 0 7 0 7 0
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task5


def task5():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    print(0)


test_task5(task5)

Перестановка на месте

Нужно изменить порядок только части элементов: положительные должны идти в обратном порядке появления, остальные остаться где были.

Собрать нужные числа во второй список — верный вывод, но условие просит дополнительную память $O(1)$ кроме данного массива. Тесты это не проверяют: это требование к тому, как вы думаете. Подумайте, какими двумя позициями можно идти по массиву, не копируя положительные отдельно.

Переставьте положительные, не копируя их во второй список.

Задача 6. Реверс положительных

Дан массив из $n$ целых чисел. Числа $\le 0$ остаются на местах. Положительные нужно переставить в обратном порядке их появления.

Разрешается изменять данный массив. Дополнительная память кроме него — $O(1)$: нельзя собирать положительные в отдельный список.

Вход. Первая строка: $n$ ($1 \le n \le 2\cdot 10^5$). Вторая: $n$ чисел, $|a_i| \le 10^9$.

Выход. Одна строка из $n$ чисел.

-> 5
-> 1 -2 3 0 4
--
<- 4 -2 3 0 1

-> 3
-> 1 2 3
--
<- 3 2 1

-> 3
-> -1 0 -2
--
<- -1 0 -2

-> 3
-> 1 -1 2
--
<- 2 -1 1
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task6


def task6():
    n = int(input())
    a = list(map(int, input().split()))
    print(*a)


test_task6(task6)

Разностный массив

Дан массив из нулей и много операций «прибавить $x$ на отрезке». Идти циклом по отрезку на каждую операцию на больших $n$ и $q$ не успеет.

Это обратная сторона префиксных сумм: обновление отрезка можно оставить следами на границах, а сам массив восстановить одним проходом в конце. Снова следите за тем, включён ли правый конец.

Выполните все прибавления и выведите итоговый массив.

Задача 7. Прибавления на отрезках

Дан массив из $n$ нулей. Выполняется $q$ операций: к каждому элементу на отрезке с индексами от $l$ до $r$ включительно прибавить $x$. Выведите массив после всех операций. Нумерация с единицы.

Вход. Первая строка: $n$ и $q$ ($1 \le n, q \le 2\cdot 10^5$). Далее $q$ строк: $l$ $r$ $x$ ($1 \le l \le r \le n$, $|x| \le 10^9$).

Выход. Одна строка из $n$ чисел.

-> 5 2
-> 1 3 2
-> 2 5 1
--
<- 2 3 3 1 1

-> 4 3
-> 1 4 5
-> 2 2 -3
-> 3 4 1
--
<- 5 2 6 6

-> 3 1
-> 2 3 0
--
<- 0 0 0
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task7


def task7():
    n, q = map(int, input().split())
    for _ in range(q):
        l, r, x = map(int, input().split())
    print(*([0] * n))


test_task7(task7)

Медиана и тот же диапазон

Диапазон снова $0\ldots 1000$. Медиана здесь — элемент на заданной позиции, если выписать все $n$ чисел по неубыванию (позиции с единицы). Для нечётного и чётного $n$ позиция считается по формуле в условии.

Сортировка сравнением даст верный ответ. Приём пары — опереться на сводку по значениям, как в первой задаче, и понять, когда накопленное количество уже накрыло нужную позицию. Так вы готовитесь к сортировке подсчётом, не вызывая sort.

Найдите медиану в смысле позиции из условия.

Задача 8. Медиана набора

Дано $n$ целых чисел из диапазона от $0$ до $1000$ включительно. Медиана — элемент на позиции $\lfloor (n+1)/2 \rfloor$ после выписывания всех чисел по неубыванию (позиции с единицы).

Вход. Первая строка: $n$ ($1 \le n \le 2\cdot 10^5$). Вторая: $n$ чисел $0 \le a_i \le 1000$.

Выход. Одно число — медиана.

-> 5
-> 10 1 10 5 10
--
<- 10

-> 4
-> 1 3 2 4
--
<- 2

-> 1
-> 0
--
<- 0
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task8


def task8():
    n = int(input())
    a = list(map(int, input().split()))
    print(0)


test_task8(task8)

Если осталось время

Две задачи ниже — для тех, кто закрыл тестами первые восемь. Новых обязательных конструкций нет: снова указатели, частоты по остатку и аккуратная перестановка.

Пара с расстоянием и модулем

Нужна максимальная сумма двух элементов с разными индексами: сумма делится на $M$, номера отличаются не меньше чем на $K$. Пары нет — ответ $0$.

Перебор всех пар не успеет. Подумайте, что достаточно помнить про уже просмотренные элементы, которые отстоят от текущего достаточно далеко, и как здесь помогает остаток по модулю $M$.

Найдите максимальную подходящую сумму или $0$.

Задача 9. Максимальная сумма пары

Дана последовательность из $n$ чисел, а также $K$ и $M$. Среди пар с разными индексами найдите максимальную сумму, которая делится на $M$, если номера отличаются не меньше чем на $K$. Если подходящей пары нет, выведите $0$.

Нумерация с единицы: у соседних номера отличаются на $1$.

Вход. Первая строка: $n$, $K$, $M$ ($2 \le n \le 2\cdot 10^5$, $1 \le K < n$, $1 \le M \le 1000$). Вторая: $n$ чисел $0 \le a_i \le 2\cdot 10^6$.

Выход. Одно число — максимальная подходящая сумма либо $0$.

-> 10 4 101
-> 240 26 35 8 152 222 183 41 268 6
--
<- 303

-> 5 2 10
-> 3 3 3 3 7
--
<- 10

-> 4 3 2
-> 1 1 1 1
--
<- 2
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task9


def task9():
    n, k, m = map(int, input().split())
    a = list(map(int, input().split()))
    print(0)


test_task9(task9)

Следующая перестановка

Нужна следующая последовательность из тех же чисел в лексикографическом порядке. Одинаковые значения неразличимы. Если текущая уже последняя, берут первую — неубывающую.

Полный перечень перестановок строить не нужно: достаточно понять, чем соседние в порядке последовательности отличаются локально.

Сдвиньте последовательность на следующую в лексикографическом порядке.

Задача 10. Следующая перестановка

Дана последовательность из $n$ целых чисел. Замените её на следующую перестановку этих чисел (с учётом повторов). Если данная уже последняя, замените на первую (неубывающую).

Лексикографический порядок: $p$ меньше $q$, если на первой позиции, где они различаются, в $p$ стоит меньшее число.

Вход. Первая строка: $n$ ($1 \le n \le 10^5$). Вторая: $n$ чисел, $|a_i| \le 10^9$.

Выход. Одна строка из $n$ чисел.

-> 3
-> 1 2 3
--
<- 1 3 2

-> 3
-> 3 2 1
--
<- 1 2 3

-> 3
-> 1 1 5
--
<- 1 5 1

-> 4
-> 1 3 2 3
--
<- 1 3 3 2
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab02_tests import test_task10


def task10():
    n = int(input())
    a = list(map(int, input().split()))
    print(*a)


test_task10(task10)

Сдача

Перед отправкой проверьте:

  • сохранили ноутбук: File → Save;
  • рядом с ноутбуком лежит lab02_tests.py;
  • в ячейке решения есть from lab02_tests import test_taskN (после перезапуска ядра выполните эту ячейку снова);
  • отправили этот файл .ipynb в задание семинара 2 на courses.ai.msu.ru.

Если LMS не открывается, пришлите файл семинаристу в личные сообщения до конца дня.

Недорешенные задачи не мешают отправке: сдайте то, что успели. Красный тест у заглушки — нормально. TLE значит «слишком медленно», обычно квадрат там, где нужен линейный проход.