Телеграмм чат группы proalgorithms страница 3731

2020 December 14

ГА

Гегам Антонян... in pro.algorithms

Добрый день. До «Если в (3) |x|>1” все понятно, но после не понятно как, скажем если x =2. Может кто нибудь помочь ?

источник

13:57пожаловаться #1

С

Степан in pro.algorithms

Добрый день, подскажите алгоритм решения:

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

Как оптимизировать, чтобы каждый раз не пробегаться по исходному массиву?

источник

14:21пожаловаться #2

БВ

Буйный Виталя... in pro.algorithms

Степан

Добрый день, подскажите алгоритм решения:

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

Как оптимизировать, чтобы каждый раз не пробегаться по исходному массиву?

Кеш

источник

14:23пожаловаться #3

P

‌‌Gleb Pilipets... in pro.algorithms

Степан

Добрый день, подскажите алгоритм решения:

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

Как оптимизировать, чтобы каждый раз не пробегаться по исходному массиву?

Массив-аргумент встречается k раз в исходном, если каждый его эллемент встречается k раз в исходном?

источник

14:25пожаловаться #4

С

Степан in pro.algorithms

Нет, порядок должен сохраняться, например, в [1.0, 2.0, 1.0, 0.0, 2.0] подмассив [1.0, 2.0] встречается только один раз

источник

14:26пожаловаться #5

С

Степан in pro.algorithms

Буйный Виталя

Кеш

Не совсем понимаю, как тут его применить 🤭

источник

14:28пожаловаться #6

P

‌‌Gleb Pilipets... in pro.algorithms

++

источник

14:28пожаловаться #7

БВ

Буйный Виталя... in pro.algorithms

Степан

Не совсем понимаю, как тут его применить 🤭

Если нету в кеше => ищем в массиве. Если нашли в массиве => положили в кеш. Возможно условие не до конца понял .

источник

14:31пожаловаться #8

AD

Alexey Dergunov in pro.algorithms

подпоследовательность наверно имеется в виду

источник

14:31пожаловаться #9

С

Степан in pro.algorithms

Ну да

источник

14:31пожаловаться #10

С

Степан in pro.algorithms

Буйный Виталя

Если нету в кеше => ищем в массиве. Если нашли в массиве => положили в кеш. Возможно условие не до конца понял .

Запросы вряд ли повторяются)
Подпоследовательность, которую нужно найти, всегда разная

источник

14:31пожаловаться #11

AD

Alexey Dergunov in pro.algorithms

ну можно на запрос отвечать за О(длины запроса * логарифм)

источник

14:32пожаловаться #12

AD

Alexey Dergunov in pro.algorithms

если создать positions[a[i]].push_back(i) а потом бинпоиском искать следующий индекс

источник

14:33пожаловаться #13

С

Степан in pro.algorithms

Именно бинпоиском?

У меня сейчас похожая штука: я храню обратные индексы для всех дробных чисел в изначальном массиве. Когда приходит запрос, беру первое число в запросе и для каждого его индекса проверяю, продолжается ли она в этом месте нужной последовательностью

источник

14:35пожаловаться #14

С

Степан in pro.algorithms

Получается О(количество вхождений первого числа в запросе), но это недостаточно быстро

источник

14:36пожаловаться #15

С

Степан in pro.algorithms

Не совсем понимаю, как исправить положение бинпоиском

источник

14:36пожаловаться #16