Wataru

Ну ведь тут массив же отсортирован. Хоть и с приколом: он сдвинут. Можно тем же бинарным поиском найти, где там "разрыв" происходит, а после у вас 2 отсортированных куска. Или сразу модифицировать бинпоиск.
Представьте, что у вас массив, где сначала идут 1, а потом 0. Можете найти в нем, где 1 переходит в 0?

Или смотрите так: ищите вы x. Взяли значение a[m]. Можете, посмотрев на a[l], a[m], a[r] и x понять, в какой половине лежит x?

Edit: ах, тут числа могут быть одинаковыми. Тогда бинпоиск тут не работает. Ибо может быть тест {1,1,1,2,1,1} - и тут можно 2 в любую позицию поставить. И, если вам надо эту 2 найти, то вам придется просмотреть все числа, иначе вы ее не найдете. Бинпоиск возможен, если первое и последнее числа разные.

Если у вас диапазоны такие маленькие, то можно прямо в классе буфера завести еще и массив mutex-ов. И каждый поток будет их лочить слева на-право по всему диапазону (важно, что каждый поток делает это в одном и том же порядке, а то дедлоки получите).

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

Если же у вас ожидаются интервалы побольше 100, то тут возможно лучше будет вот такое решение:
У вас будет одна глобальная структура-индекс, где вы будете хранить статус буфера (о ней позже). Потоки будут к ней обращатся и просить у нее выделить потоку кусок.
Внутри этой структуры, похоже, придется сделать один глобальный мьютекс.
В качестве самой структуры хорошо подойдет дерево отрезков с отложенным добавлением. Пусть оно будет считать сумму на отрезке. При запросе на выделение вы смотрите, равна ли сумма на запрошенном отрезке 0. Если да, то прибавляете на отрезке 1. Если нет, то возвращаете неудачу и поток должен будет опять обратиться к структуре. При освобождении интервала прибавляйте -1.

Тут операция выделения сама по себе будет сильно быстрее. Но это фактически спинлок - каждый поток будет в цикле пытаться выделить себе интервал, пока не сможет. Если ожидается, что потокам придется долго ждать, то надо какие-то стратегии back-off добавлять (спать между вызовами). И вообще спинлоки - это плохо.

Как сделать это без спинлоков с деревом отрезков - я не придумал.

Вы правильно поняли, что у вас вершинами в гарфе являются клетка+направление, по которому пришли.
Но раз у вас вот это вершины, то вам и пометки о песещении вершины надо делать в трехмерном массиве. А начальных и финальных вершин у вас по 4 штуки: клетка x 4 направления (на самом деле, начинать достаточно только с 2 направлений, но неважно).

Ага, ДП тут отлично входит. F(n) - ответ на задачу для префикса длины n. Там перебираете длину последней группы x и берете в качесвте ответа max(a[n-x]..a[n-1]) - min(a[n-x]..a[n-1]) + F(n-x). По всем l<=x<=r выбераете максимум. Если n < l, то ответ - минус бесконечность.

Это будет решение за O(n^2). Что-нибудь за O(n log n) я так сходу придумать не могу.

Минимизируйте стоимость строительства самой дорогой построенной предложенной линии.

не сумма всех взятых ребер, а стоимость максимального из них.

1 2 (2) и 2 3 (1) - максимальная стоимость 2 (max(1,2)).

1 3 (3) - максимальная стоимость 3 max(3). 3 больше 2, значит ответ выше лучше.

Так задача легче, чем с суммой.

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

Я правильно понял, что идет обмен между двумя игроками, если их окружности пересекаются?

Самый наивный алгоритм - перебрать все пары на сервере, если два игрока достаточно близкие, то выдать каждому список из соседей, а игрок уже сам с ними общается. Ну, или каждый игрок заправшивает у сервера кто его соседи, сервер ищет, перебирая всех соседей, и выдает список. Можно считать квадрат расстояния по теореме пифагора, и сравнивать с квадратом нужного расстояния (диаметр окружности).

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

Конечно, на эту задачу можно натянуть префиксные деревья (это же вы бор/trie имеете ввиду, да?). Но тут какая-то растянутая сова получается.

Например, можно, действительно, все слова сложить в trie, а потом его обойти. Вам нужно будет в рекурсивном обходе поддерживать количество последних ребер, которые шли по алфавиту. Еще в каждой вершине сразу хранить, сколько раз через нее проходят добавленные строки. Тогда в каждой вершине прибавляйте к ответу произведение двух счетчиков. При рекурсивном вызове или увеличивайте счетчик последних упорядоченных ребер, если следующий символ больше символа к отцу, или передавайте 1.

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

Нет. Ну, только если вы не будете заводить таблицу на 4 миллиарда с копейками элементов (2^32) и использовать тривиальную хеш-функцию.

Потому что важно не столько количество элементов в таблице, а их значения. Их может быть 4 миллиарда различных. И даже только с 2 элементами я вам для любого меньшего размера таблицы найду 2 таких элемента, что у них хеш функция совпадет.

Вообще, теоретически, для фиксированного набора элементов можно подобрать хеш-функцию без коллизий. Она тогда называется идеальная хеш-функция. И тогда размер таблицы может быть очень маленьким - аж до количества этих элементов. Но вам надо подбирать новую хеш-функцию для каждого набора хранимых чисел.

Тут квадратное уравнение зарыто.

Обозначьте |MSL_VEL - TGT_VEL| за t.

Получите уравнение TGT_DIR = (MSL_VEL-TGT_VEL)/t

Преобразуйте: TGT_DIR*t = (MSL_VEL-TGT_VEL)

Но тут неизвестные вектор MSL_VEL и t. Но они связаны, ведь t - это длина вектора. Обозначим неизвестный вектор MSL_VEL как (x, y, z) Значит:

t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2

Ну и еще вы знаете, что скорость ракеты фиксированная же:
x^2+y^2+z^2 = MSL_SPEED^2

У вас тут 4 неизвестных и аж 5 уравнений (ведь первое - это векторное уравнение):

TGT_DIR_x*t = x - TGT_VEL_x
TGT_DIR_y*t = y - TGT_VEL_y
TGT_DIR_z*t = z - TGT_VEL_z
t^2=(x - TGT_VEL_x)^2 + (y - TGT_VEL_y)^2 + (z - TGT_VEL_z)^2
x^2+y^2+z^2 = MSL_SPEED^2

Раскройте скобки в 4-ом, подставьте туда пятое и из первых трех выразите x, y, z:

t^2 = MSL_SPEED^2+TGT_SPEED^2-2*TGT_VEL_x*(TGT_DIR_x -t*TGT_VEL_x)-... = MSL_SPEED^2+(1-2t)TGT_SPEED^2-2(TGT_DIR*TGT_VEL)

Там в конце векторное произведение векторов. Дальше сами раскройте и получите квадратное уравнение на t. Решите его по школьной формуле. Если дискриминант отрицательный, то решения тупо нет. Слишком быстро цель улепетывает. Потом не забудьте проверить, чтобы t получилось положительное. Потом подставьте t в первые 3 уравнения и найдите искомые x, y, z.

Еще можно так себе это все представить. Свяжем систему координат с целью. Тогда множество точек, куда может смотреть скорость ракеты - это сфера с центром в TGT_VEL и радиусом MSL_SPEED. Вам надо выбрать на этой сфере точку так, чтобы она была коллинеарна с вектором TGT_DIR. Т.е. у вас есть луч из центра координат вдоль векторо TGT_DIR. Вам надо найти где он пересечет сферу. Введите параметр t вдоль луча и дальше получите то же самое квадратное уравнение.

Дерево интервалов. Оно же interval tree.

Оно как раз позволяет быстро искать все отрезки, пересекающие данную точку, но изменять его очень тяжело. Хорошо, что вам это и не надо.

то в первом пункте мне не понятно как связаны индексы i и 2*i

Если нумерация массива идет с 1, то два ребенка элемента i будут 2*i и 2*i+1. У вас же нумерация с 0, т.ч. у вас дети - 2*i+1 и 2*i+2.

Первое условие достигается правильной расстановкой строгого и нестрогого неравнества в условиях в алгоритме.

Похоже, проблема в том, что у вас нумерация с 0 и, если новый элемент оказывается итак максимальным, вы вернете индекс 0, вместо нужного 1. Если вы элемент вниз просеиваете, то у вас там +1 стоит в res.first, но изначально у вас-то там 0.

Далее, вы вектор неправильно используете. Вы делаете reserve и потом работаете с пустым вектором, как-будто он фиксированного размера. Вам надо делать resize вместо reserve. Или еще лучше, вместо вашей переменной size вы используйте arr.size(). При изменении размера массива делайте pop_back() и push_back().