Конечно, не станет. Поэтому мое предложение и было на основе патченого хрома, где кодек будет заменен на заглушку, которая это съест, выдаст в сеть и вернет что-то правдоподобное.
Потому что ваша комбинация filter и indexOf - это квадратичный алгоритм на ровном месте. Там где достаточно линейного. Если у вас массив хотя бы на 1000 элементов у вас уже заметное время будет работать код, который может отработать мгновенно.
Конечно, если ваш язык уже имеет какой-то встроенный unique(), то используейте его. Но если нет и у вас там больше 10 элементов, то лучше писать руками нормальные алгоритмы. Если хотите более фнукциональный и кроткий код, то вам нужен filter с аккумулятором, куда вы будете передавать предыдущий элемент и проходить фильтр только если текущий от предыдущего отличается. Или сначала запихайте массив в map и используйте его вместо IndexOf. Правда тут все-равно может остаться проблема с лишней аллокацией памяти.
Я не это имел ввиду. Там почти везде каждый фрейм ссылается на предыдущий и все. Очень простая структура. Но это не важно.
RTCEncodedVideoFrame
Вы этот Encoded transform незаметно не сможете навесить наверно, думаю приложение как-то сможет изменение повдедения. Хотя эта идея очень близка к моей и даже проще в реализации. Этот трансформ - это lossless изменение битстрима. Им, например, можно сделать E2E шифрование. А можно тупо заменять закодированные данные на то, что вы хотите передать. Это и есть мое предложение.
Ни один из этих кодеков не подразумевает стриминг lossless видео (ну то есть там конечно есть CRF 0
Еще раз, никакого видео кодирования в этой схеме вообще не происходит. Наш волшебный кодек вместо h264 битстрима выдает содержимое тоннеля. Вообще игнорируя видео с камеры, настройки и все что угодно кроме только битрейта. А декодер это содержимое выливает в сеть на своей стороне и выдумывает видео картинку для обдуривания приложения. Если выдерживать правдоподобные размеры закодированных фреймов на отправителе, то это будет не видно никак приложению. Или можно не удалять настоящий кодек, а просто перезаписывать им произведенные данные с тем же размером. Задержку только реалистичную надо еще на декодере проэмулировать.
Или вы про передачу данных не через видео, а через сопутствующий DataStream? Их уже давно начали резать ЕМНИП.
Нет, я про передачу данных ВМЕСТО видео. Вместо закодированного видео. Еще раз, данные не сжимаются кодеком. Данные тупо перезаписывают его работу. Раскодировать это в видео, конечно, не получится никак. На принимающей стороне надо будет видео просто "выдумать". На уровне хрома это просто - декодер выдает видео фрейм из локального файла.
Фреймрейт будет стандартный, 30 фреймов в секунду. Но это не важно. CRC там уже есть на уровне пакетов в DTLS.
В RTC видео нет никаких P/B фреймов и I-frame пытаются посылать как можно реже.
Смотрите на это так: вот у вас есть энкодер, он выдает какой-то битстрим. Какие-то бинарные данные. 1.7mb/s. И эти данные как-то сами без ошибок и перестановок попадают на декодер на другом конце. В удачном случае целиком. В неудачном случае с редкими пропусками куска. Вам не важно что там с фреймрейтом, как устроены фреймы, что за кодек. Вот есть у вас тоннель.
Вы эти данные на отправителе переписываете на свои собственные (с какой-то служебной информацией, чтобы можно было их на нормальные IP пакеты порезать на другом конце), и получаете на другом конце.
Вы не предаете ваши данные в виде пикселей, которые энкодер потом как-то квантует. Там все будет действительно очень грустно, потому что сжатие с дикими потерями.
Для этого придется собирать свой собственный хром, с пропатченными энкодерами/декодерами. Если надо, я даже подскажу где и как это сделать. Энкодер вместо условного h264 битстрима вставляет (зашифрованные, конечно) ваши данные и тупо игнорирует входной видео-поток. Декодер полученный битстрим выдает из тоннеля, и выдает очередной кадр из фиктивного видео файла назад в web приложение.
Не знаю, может и не нужен целый хром. Может можно просто прикидываться веб-приложением и посылать всякие http запросы и DTLS/RTP трафик. Но это проще детектить будет. А если пропатченный хром еще и реалистичные задержки ставит и прикидывается, что он что-то там кодирует/раскодировывает, то это очень сложно обнаружить. Это надо попытаться видео на сервере перекодировать. Это дорого и без особой надобности этого не делают обычно. А если еще и E2E шифрование на клиенте работает, то это вообще невозможно.
Вообще, может. И гугл может. Там соединение происходит с сервером. Сервер потом ваше видео раздает всем остальным клиентам. Потому что каждому из нескольких собеседников отдельно ваше видео передавать - никакой пропускной способности у вас не хватит. Гугл вообще умеет ваше видео перекодировывать на лету, если получатель не умеет раскодировать то, что вы можете посылать. Или накладывать фильтры вроде замены фона, если ваш комп не тянет.
У гугл meet есть отдельный режим работы со сквозным шифрованием, если кому-то особо важно, и некоторые корпоративные клиенты им пользуются. Но там всякие дополнительные плюшки обработки на серверах не работают. Есть ли такое у Яндекса и можно ли частникам такое себе замутить я не знаю.
Но с другой стороны, никто ваше видео смотреть не будет. Хранить его экономически нецелесообразно. А для товарища майора хватит и записи звука.
Но точно также почти все мессенджеры могут ваши сообщения читать. Есть режимы вроде секретных чатов в телеграмме, но ими без особой надобности не пользуются, потому что неудобно.
Так что если вам важна строгая гарантия приватности - не пользуйтесь корпоротивным мейнстримом. Поднимайте свой собственный сервер jitsi meet или еще чего-то такого.
Проблема в том, что ее надо будет решать и со стороны выхода канала - на том сервере, который в свободном интернете. Для этого надо туда доступ как-то получить, а для этого нужен рабочий тоннель.
Это сырой битрейт передачи данных. Небольшие потери будут автоматически восстановлена средствами webrtc (NACK/RTX) и вы их даже не заметите. Но при достаточно больших потерях случится страшное: будет запрос на новый ключевой кадр или получатель просто дропнет какой-то фрейм. Вместе с большим и нестабильным RTT это может сделать TCP трафик медленным. Но это должно быть весьма редкое событие.
Нет, если передавать данные прямо в битстриме, то скорость будет не настолько уж и плохая, 1.7 мегабит и до 3.5мбит если вам 1080p разрешат. Вот только без сквозного шифрования будет видно на сервере, что видео не раскодируется.
В Google Meet есть вариант с E2E шифрованием трафика. Поддерживает ли такое Телемост?
Вообще, данные можно гонять в видео потоке напрямую. Надо лишь собрать собственный хром для двух клиентов, там енкодер/декордер тупо игнорируют данные с камеры и выдают данные для тунеля/из тунеля. Или какой-то паддинг, если нечего передавать. Надо только размер каждого закодированного фрейма выдавать случайного размера, но примерно в зависимости от установленного битрейта.
Это яндекс вообще никак отследить не сможет. Обычный хром клиент, передает какое-то видео, и посмотреть его из-за Client-Side-Encryption никак. Возможно надо будет переодически начинать новую конференцию и переподключатся с разными пользователями, а то видеозвонок висящий 24/7 все сломает.
Можно и без своей криптографии, но тогда яндекс может заметить ботву в видеопотоке.
Можно ли его обобщить на N групп (по которым распределяются числа k, 2k, ..., N*k)?
Если N+1 простое - мой метод работает как есть.
Для непростых N+1 - уже нет. Но не факт что такие разбиения вообще всегда существуют. Хотя я контрпримеров пока не нашел.
определяем в числе степени множителей 2, 3 и 5,
Вообще, логично. Все множители 1..N только меняют степени у этих чисел, поэтому числа с разными другими простыми множителями никогда и никак не получатся вместе, а значит у нас бесконечно идентичных компонент связности в графе конфликтов. Если мы как-то расположим только числа с этими простыми делителями. мы можем скопировать это решение на все оставшиеся компоненты. Кстати, это еще показывает, что решений бесконечно много, если они есть, даже без учета перестановок N групп. Можно брать разную перестановку в каждой отдельной компоненте связности.
Для числа k, выделим все степени 7: k = 7^m*b, b % 7 != 1. Положим число в группу b % 7 (от 1 до 6).
При умножении на 1-6 максимальная степень 7 в числе останется m. Поэтому x*k (1 <= x <= 6) пойдет в группу (x*b)%7. при чем b%7 != 0, x%7 != 0. Все 6 чисел будут разными, потому что таблица умножения ненулевых чисел по модулю 7 имеет перестановки в каждой строке или столбце. Это потому что умножение по модулю 7 обратимо, ведь 7 - простое число.
Это можно заметить, если руками распихать первые 6 чисел и ими порожденные числа. Там почти однозначно числа распределяются по модулю 7. И тогда остается вопрос, что делать с числами, делящимеся на 7.
Что-то как-то перемудрено совсем. Ясно, что иначе бы статьи не получилось бы, но так упорно не замечать слона в комнате - очень странно.
Обычный бинарный поиск тут работает. Не надо ничего считать и выдумывать. У вас на каждом этапе есть отрезок допустимых чисел длины n. Изначально это числа от 1 до N. В общем случае у вас отрезок от l до r включительно, и называть надо floor((r+l)/2). Если угадали - молодцы, иначе делаете l = m+1, если ">" или r=m-1, если "<".
Весь максимин Кнута сводится именно к этому, например. Это относительно легко доказывается. Если применить к нему элементарную математику и логику, то можно аналитически вывести значение искомой функции и что надо называть.
Первый шаг: очевидно, что у вас всегда множество возможных ответов будет непрерывным отрезком чисел.
Второе: очевидно, что от отрезка нам важна только его длина. Вот уже минимизируемая функция будет от одного аргумента F(n) - сколько нужно шагов, чтобы отгадать число среди n.
Третье: вот она
argmin в этой формуле скажет, какое число надо называть.
Четвертое: теперь осталось только доказать, что функция монотонно не убывает. Это доказывается логически: не может f(n-1) быть больше f(n-1). Ведь всегда можно запустить алгоритм для поиска в 1..n в случае с 1..n-1 числами и просто не спрашивать само число n - ответ на эту догадку ("<") вы уже знаете.
Ну вот, раз функция монотонно не убывает, значит max внутри можно раскрыть. В первой половине индексов больше будет f(n-i), потом для нечетных n будет равенство i-1=n-i, потом будет больше n-i. Первая и третья части совпадают, поэтому третью часть можно опустить. Остается только те части где n-i >= i-1, т.е. i <= (n+1)/2:
Но, опять же, по монотонности можно раскрыть и минимум. Остается только последний индекс ведь там аргумент функции наименьший: f(n) = f(n-ceil(n/2)) + 1 = f(floor(n/2)) + 1.
Теперь по индукции можно доказать что
И называть каждый раз надо число, самое близкое к середине.
Мне приходилось, аж много раз. При реализации пакетизации h264 битстрима: по спецификации там есть режим, что энкодер выдает несколько кусков, и их нельзя резать дальше при распихивании этого по пакетам. Странная идея, но так придумали кучу лет назад, а нам это реализовывать. Можно несколько кусков целиком засунуть в очередной пакет. Переставлять куски, очевидно, тоже нельзя. Надо чтобы эти группы не превышали лимит размера пакета, было как можно меньше пактов, а максимальный пакет был как можно меньше. Без последнего ограничения задача решается тупой жадностью: заполняем пакет, пока туда влезает. Потом начинаем следующий, и так пока куски не кончатся. Но так получаются очень разные пакеты и это плохо для выдерживания пропускной способности сети. Хотелось бы решить задачу с ним. С этим дополнительным условием задача решается через ДП.
Потом, писал для себя утилиту. Было это в старые времена, когда интернет был не безлимитный и за сериальчиками все ходили в гости с жесткими дисками, да качали из локальных сеток. Но место на жестких дисках ограниченно, поэтому сериалы резали на CD а потом и DVD. Десятки, сотни дисков. И опять задача - хотелось бы как-то более эффективно диски использовать. При этом есть всякие естественные ограничения: вроде файлы серий надо записывать подряд, сериал может быть по нескольким дискам, но подряд, чтобы эти диски в стопке рядом лежали. Чтобы когда решишь посмотреть, взять несколько дисков и подряд их вставлять в привод. В итоге навороченная задача о рюкзаке получилась. Моя утилита диски довольно хорошо упаковывала, гораздо лучше чем я руками это делал.
Потом, это применяется в индустриальной оптимизации. Мою программу-курсовую никуда не пристроили, конечно, но знаю, что в моем университете разработали программы и они крутится на производстве фанеры, досок и чего-то еще. По заказам размеров выдает как и что раскраивать, чтобы было как можно меньше отходов. И там помимо методов решения задач линейного программирования в частности вылезает именно динамическое программирование как подзадача.
Ну и почти любой поиск пути в графе, который весьма часто встречается и реализуется алгоритмом Дейкстры - по сути является ДП.
Нет, это артефакты интерполяции. ЛЛМ учат продолжать фразу, как было в обучающей выборке, а потом просят продолжить какую-то другую фразу. Это интерполяция в чистом виде. Ну вот очень большая и хитрая формула, которую вычисляет ЛЛМ, не достаточно хорошо предсказывает реальность. Когда она попадает в точку, это называют удивительными аналитическими способностями ЛЛМ, а когда нет - это называют галлюцинацией, как будто это какой-то баг, какай-то особый режим поведения, который вроде как и исправить можно. Хвала маркетологам: хорошо придумали.
Но это никакой не особый режим и не баг, это тупо интерполированная функция не совпадает с реальной. Функция реальности слишком сложна, чтобы ее можно было даже миллиардами ReLU представить. Удивительно скорее, что оно вообще работает, а не что оно "галлюционирует"
Но его можно применять только при двух условиях: ... Перекрывающиеся подзадачи.
Вовсе нет. Эта мысль много где бездумно повторяется, но это вообще не обязательно. ДП все еще будет отлично работать. Например, найти глубину дерева, или подсчитать "хеш" дерева для проверки изоморфизма.
Да, в этом случае граф вызовов будет деревом и мемоизация по сути не нужна, но мемоизация - это лишь деталь реализации, оптимизация. Суть из рекуррентного соотношения остается.
Другие мои 5 копеек:
Динамическое программирование очень полезно формализовывать. Так понятнее, что решение работает, его так легче придумывать.
Вам надо определить:
1) Множество состояний и рекуррентное соотношение. Или же множество задач и как задача решается через подзадачи.
2) База - какие-то состояния имеют фиксированный ответ
3) Ответ. Где ответ на изначальную задачу. Не всегда задача как она есть является одной из подзадач. Иногда в решении вы вводите какие-то новые параметры, которых в условии изначальной задачи нет.
"осенний пакет"? Если есть шифрование никакой анализ не покажет, что там зашифровано - настоящий h264 битстрим, или пакеты из впн.
Конечно, не станет. Поэтому мое предложение и было на основе патченого хрома, где кодек будет заменен на заглушку, которая это съест, выдаст в сеть и вернет что-то правдоподобное.
Потому что ваша комбинация filter и indexOf - это квадратичный алгоритм на ровном месте. Там где достаточно линейного. Если у вас массив хотя бы на 1000 элементов у вас уже заметное время будет работать код, который может отработать мгновенно.
Конечно, если ваш язык уже имеет какой-то встроенный unique(), то используейте его. Но если нет и у вас там больше 10 элементов, то лучше писать руками нормальные алгоритмы. Если хотите более фнукциональный и кроткий код, то вам нужен filter с аккумулятором, куда вы будете передавать предыдущий элемент и проходить фильтр только если текущий от предыдущего отличается. Или сначала запихайте массив в map и используйте его вместо IndexOf. Правда тут все-равно может остаться проблема с лишней аллокацией памяти.
Что у вас с формулами в статье? Мало $ вокруг них поставить, надо еще кнопочку
нажать.
Если есть E2E шифрование - то нет.
Я не это имел ввиду. Там почти везде каждый фрейм ссылается на предыдущий и все. Очень простая структура. Но это не важно.
Вы этот Encoded transform незаметно не сможете навесить наверно, думаю приложение как-то сможет изменение повдедения. Хотя эта идея очень близка к моей и даже проще в реализации. Этот трансформ - это lossless изменение битстрима. Им, например, можно сделать E2E шифрование. А можно тупо заменять закодированные данные на то, что вы хотите передать. Это и есть мое предложение.
Еще раз, никакого видео кодирования в этой схеме вообще не происходит. Наш волшебный кодек вместо h264 битстрима выдает содержимое тоннеля. Вообще игнорируя видео с камеры, настройки и все что угодно кроме только битрейта. А декодер это содержимое выливает в сеть на своей стороне и выдумывает видео картинку для обдуривания приложения. Если выдерживать правдоподобные размеры закодированных фреймов на отправителе, то это будет не видно никак приложению. Или можно не удалять настоящий кодек, а просто перезаписывать им произведенные данные с тем же размером. Задержку только реалистичную надо еще на декодере проэмулировать.
Нет, я про передачу данных ВМЕСТО видео. Вместо закодированного видео. Еще раз, данные не сжимаются кодеком. Данные тупо перезаписывают его работу. Раскодировать это в видео, конечно, не получится никак. На принимающей стороне надо будет видео просто "выдумать". На уровне хрома это просто - декодер выдает видео фрейм из локального файла.
Фреймрейт будет стандартный, 30 фреймов в секунду. Но это не важно. CRC там уже есть на уровне пакетов в DTLS.
В RTC видео нет никаких P/B фреймов и I-frame пытаются посылать как можно реже.
Смотрите на это так: вот у вас есть энкодер, он выдает какой-то битстрим. Какие-то бинарные данные. 1.7mb/s. И эти данные как-то сами без ошибок и перестановок попадают на декодер на другом конце. В удачном случае целиком. В неудачном случае с редкими пропусками куска. Вам не важно что там с фреймрейтом, как устроены фреймы, что за кодек. Вот есть у вас тоннель.
Вы эти данные на отправителе переписываете на свои собственные (с какой-то служебной информацией, чтобы можно было их на нормальные IP пакеты порезать на другом конце), и получаете на другом конце.
Вы не предаете ваши данные в виде пикселей, которые энкодер потом как-то квантует. Там все будет действительно очень грустно, потому что сжатие с дикими потерями.
Для этого придется собирать свой собственный хром, с пропатченными энкодерами/декодерами. Если надо, я даже подскажу где и как это сделать. Энкодер вместо условного h264 битстрима вставляет (зашифрованные, конечно) ваши данные и тупо игнорирует входной видео-поток. Декодер полученный битстрим выдает из тоннеля, и выдает очередной кадр из фиктивного видео файла назад в web приложение.
Не знаю, может и не нужен целый хром. Может можно просто прикидываться веб-приложением и посылать всякие http запросы и DTLS/RTP трафик. Но это проще детектить будет. А если пропатченный хром еще и реалистичные задержки ставит и прикидывается, что он что-то там кодирует/раскодировывает, то это очень сложно обнаружить. Это надо попытаться видео на сервере перекодировать. Это дорого и без особой надобности этого не делают обычно. А если еще и E2E шифрование на клиенте работает, то это вообще невозможно.
Вообще, может. И гугл может. Там соединение происходит с сервером. Сервер потом ваше видео раздает всем остальным клиентам. Потому что каждому из нескольких собеседников отдельно ваше видео передавать - никакой пропускной способности у вас не хватит. Гугл вообще умеет ваше видео перекодировывать на лету, если получатель не умеет раскодировать то, что вы можете посылать. Или накладывать фильтры вроде замены фона, если ваш комп не тянет.
У гугл meet есть отдельный режим работы со сквозным шифрованием, если кому-то особо важно, и некоторые корпоративные клиенты им пользуются. Но там всякие дополнительные плюшки обработки на серверах не работают. Есть ли такое у Яндекса и можно ли частникам такое себе замутить я не знаю.
Но с другой стороны, никто ваше видео смотреть не будет. Хранить его экономически нецелесообразно. А для товарища майора хватит и записи звука.
Но точно также почти все мессенджеры могут ваши сообщения читать. Есть режимы вроде секретных чатов в телеграмме, но ими без особой надобности не пользуются, потому что неудобно.
Так что если вам важна строгая гарантия приватности - не пользуйтесь корпоротивным мейнстримом. Поднимайте свой собственный сервер jitsi meet или еще чего-то такого.
Проблема в том, что ее надо будет решать и со стороны выхода канала - на том сервере, который в свободном интернете. Для этого надо туда доступ как-то получить, а для этого нужен рабочий тоннель.
Это сырой битрейт передачи данных. Небольшие потери будут автоматически восстановлена средствами webrtc (NACK/RTX) и вы их даже не заметите. Но при достаточно больших потерях случится страшное: будет запрос на новый ключевой кадр или получатель просто дропнет какой-то фрейм. Вместе с большим и нестабильным RTT это может сделать TCP трафик медленным. Но это должно быть весьма редкое событие.
Нет, если передавать данные прямо в битстриме, то скорость будет не настолько уж и плохая, 1.7 мегабит и до 3.5мбит если вам 1080p разрешат. Вот только без сквозного шифрования будет видно на сервере, что видео не раскодируется.
В Google Meet есть вариант с E2E шифрованием трафика. Поддерживает ли такое Телемост?
Вообще, данные можно гонять в видео потоке напрямую. Надо лишь собрать собственный хром для двух клиентов, там енкодер/декордер тупо игнорируют данные с камеры и выдают данные для тунеля/из тунеля. Или какой-то паддинг, если нечего передавать. Надо только размер каждого закодированного фрейма выдавать случайного размера, но примерно в зависимости от установленного битрейта.
Это яндекс вообще никак отследить не сможет. Обычный хром клиент, передает какое-то видео, и посмотреть его из-за Client-Side-Encryption никак. Возможно надо будет переодически начинать новую конференцию и переподключатся с разными пользователями, а то видеозвонок висящий 24/7 все сломает.
Можно и без своей криптографии, но тогда яндекс может заметить ботву в видеопотоке.
Вот не моментально, почему-то. Мне всегда в итоге возвращали, но иногда аж на следующий день.
Если N+1 простое - мой метод работает как есть.
Для непростых N+1 - уже нет. Но не факт что такие разбиения вообще всегда существуют. Хотя я контрпримеров пока не нашел.
Вообще, логично. Все множители 1..N только меняют степени у этих чисел, поэтому числа с разными другими простыми множителями никогда и никак не получатся вместе, а значит у нас бесконечно идентичных компонент связности в графе конфликтов. Если мы как-то расположим только числа с этими простыми делителями. мы можем скопировать это решение на все оставшиеся компоненты. Кстати, это еще показывает, что решений бесконечно много, если они есть, даже без учета перестановок N групп. Можно брать разную перестановку в каждой отдельной компоненте связности.
Нет, понятно же. Поделить на 7, пока делится. Я тут имел ввиду, что я не знаю, как я до этого додумался.
Для числа k, выделим все степени 7: k = 7^m*b, b % 7 != 1. Положим число в группу b % 7 (от 1 до 6).
При умножении на 1-6 максимальная степень 7 в числе останется m. Поэтому x*k (1 <= x <= 6) пойдет в группу (x*b)%7. при чем b%7 != 0, x%7 != 0. Все 6 чисел будут разными, потому что таблица умножения ненулевых чисел по модулю 7 имеет перестановки в каждой строке или столбце. Это потому что умножение по модулю 7 обратимо, ведь 7 - простое число.
Это можно заметить, если руками распихать первые 6 чисел и ими порожденные числа. Там почти однозначно числа распределяются по модулю 7. И тогда остается вопрос, что делать с числами, делящимеся на 7.
Что-то как-то перемудрено совсем. Ясно, что иначе бы статьи не получилось бы, но так упорно не замечать слона в комнате - очень странно.
Обычный бинарный поиск тут работает. Не надо ничего считать и выдумывать. У вас на каждом этапе есть отрезок допустимых чисел длины n. Изначально это числа от 1 до N. В общем случае у вас отрезок от l до r включительно, и называть надо floor((r+l)/2). Если угадали - молодцы, иначе делаете l = m+1, если ">" или r=m-1, если "<".
Весь максимин Кнута сводится именно к этому, например. Это относительно легко доказывается. Если применить к нему элементарную математику и логику, то можно аналитически вывести значение искомой функции и что надо называть.
Первый шаг: очевидно, что у вас всегда множество возможных ответов будет непрерывным отрезком чисел.
Второе: очевидно, что от отрезка нам важна только его длина. Вот уже минимизируемая функция будет от одного аргумента F(n) - сколько нужно шагов, чтобы отгадать число среди n.
Третье: вот она
argmin в этой формуле скажет, какое число надо называть.
Четвертое: теперь осталось только доказать, что функция монотонно не убывает. Это доказывается логически: не может f(n-1) быть больше f(n-1). Ведь всегда можно запустить алгоритм для поиска в 1..n в случае с 1..n-1 числами и просто не спрашивать само число n - ответ на эту догадку ("<") вы уже знаете.
Ну вот, раз функция монотонно не убывает, значит max внутри можно раскрыть. В первой половине индексов больше будет f(n-i), потом для нечетных n будет равенство i-1=n-i, потом будет больше n-i. Первая и третья части совпадают, поэтому третью часть можно опустить. Остается только те части где n-i >= i-1, т.е. i <= (n+1)/2:
Но, опять же, по монотонности можно раскрыть и минимум. Остается только последний индекс ведь там аргумент функции наименьший: f(n) = f(n-ceil(n/2)) + 1 = f(floor(n/2)) + 1.
Теперь по индукции можно доказать что
И называть каждый раз надо число, самое близкое к середине.
Вот, никаких O(N^2) вычислений не надо.
Edit:
Блин. На календарь посмотреть забыл.
Мне приходилось, аж много раз. При реализации пакетизации h264 битстрима: по спецификации там есть режим, что энкодер выдает несколько кусков, и их нельзя резать дальше при распихивании этого по пакетам. Странная идея, но так придумали кучу лет назад, а нам это реализовывать. Можно несколько кусков целиком засунуть в очередной пакет. Переставлять куски, очевидно, тоже нельзя. Надо чтобы эти группы не превышали лимит размера пакета, было как можно меньше пактов, а максимальный пакет был как можно меньше. Без последнего ограничения задача решается тупой жадностью: заполняем пакет, пока туда влезает. Потом начинаем следующий, и так пока куски не кончатся. Но так получаются очень разные пакеты и это плохо для выдерживания пропускной способности сети. Хотелось бы решить задачу с ним. С этим дополнительным условием задача решается через ДП.
Потом, писал для себя утилиту. Было это в старые времена, когда интернет был не безлимитный и за сериальчиками все ходили в гости с жесткими дисками, да качали из локальных сеток. Но место на жестких дисках ограниченно, поэтому сериалы резали на CD а потом и DVD. Десятки, сотни дисков. И опять задача - хотелось бы как-то более эффективно диски использовать. При этом есть всякие естественные ограничения: вроде файлы серий надо записывать подряд, сериал может быть по нескольким дискам, но подряд, чтобы эти диски в стопке рядом лежали. Чтобы когда решишь посмотреть, взять несколько дисков и подряд их вставлять в привод. В итоге навороченная задача о рюкзаке получилась. Моя утилита диски довольно хорошо упаковывала, гораздо лучше чем я руками это делал.
Потом, это применяется в индустриальной оптимизации. Мою программу-курсовую никуда не пристроили, конечно, но знаю, что в моем университете разработали программы и они крутится на производстве фанеры, досок и чего-то еще. По заказам размеров выдает как и что раскраивать, чтобы было как можно меньше отходов. И там помимо методов решения задач линейного программирования в частности вылезает именно динамическое программирование как подзадача.
Ну и почти любой поиск пути в графе, который весьма часто встречается и реализуется алгоритмом Дейкстры - по сути является ДП.
Нет, это артефакты интерполяции. ЛЛМ учат продолжать фразу, как было в обучающей выборке, а потом просят продолжить какую-то другую фразу. Это интерполяция в чистом виде. Ну вот очень большая и хитрая формула, которую вычисляет ЛЛМ, не достаточно хорошо предсказывает реальность. Когда она попадает в точку, это называют удивительными аналитическими способностями ЛЛМ, а когда нет - это называют галлюцинацией, как будто это какой-то баг, какай-то особый режим поведения, который вроде как и исправить можно. Хвала маркетологам: хорошо придумали.
Но это никакой не особый режим и не баг, это тупо интерполированная функция не совпадает с реальной. Функция реальности слишком сложна, чтобы ее можно было даже миллиардами ReLU представить. Удивительно скорее, что оно вообще работает, а не что оно "галлюционирует"
Вовсе нет. Эта мысль много где бездумно повторяется, но это вообще не обязательно. ДП все еще будет отлично работать. Например, найти глубину дерева, или подсчитать "хеш" дерева для проверки изоморфизма.
Да, в этом случае граф вызовов будет деревом и мемоизация по сути не нужна, но мемоизация - это лишь деталь реализации, оптимизация. Суть из рекуррентного соотношения остается.
Другие мои 5 копеек:
Динамическое программирование очень полезно формализовывать. Так понятнее, что решение работает, его так легче придумывать.
Вам надо определить:
1) Множество состояний и рекуррентное соотношение. Или же множество задач и как задача решается через подзадачи.
2) База - какие-то состояния имеют фиксированный ответ
3) Ответ. Где ответ на изначальную задачу. Не всегда задача как она есть является одной из подзадач. Иногда в решении вы вводите какие-то новые параметры, которых в условии изначальной задачи нет.