160922 recipes

• swap

Представьте, что числа были бы 10^6. Тогда бы задача решалась просто массивом, верно?

Но числа 10^9, нельзя массив с такими большими индексами. И вот тут на помощь приходит хеш-таблица.

В конспекте есть по сути готовый код.

Без readInt/writeInt вряд ли зайдет.

Помните, что табличка должна быть больше, чем число элементов в ней, но помните и то, что чем больше съедено памяти, тем медленнее программа.

• mice

Похожа на meeting с прошлой недели, решение которой выложено.

Вообще выложены все решения всех старых задач. Туда можно и полезно смотреть.

• evalpm, evalhard

Есть набросок кода в конспетке. Можно заглянуть еще в прошлогодний конспект (стр. 26), он тоже есть на страничке вики (уже).

Не ленитесь тестировать.

• isgood

Решается за O(n).

Может помочь разбор доп4a практики. Но определить, есть ли у подстроки хороший циклический сдвиг, может быть даже проще, чем хороша ли сама подстрока.

• painter

Обратите внимание на размер входных данных!!

• fastadd

Разобрана на практике последней (4a). Очень короткий и простой код, он почти весь в разборе практики приведен.

Кстати, можно не бояться создавать массив размера 2^{24}.

А еще вы теперь умеете брать по модулю :)