Wataru

Если боты должны обходить полигоны на каком-то расстоянии (не могут их касаться, как у вас на картинке), то раздуйте все полигоны на этот радиус (для каждой вершины найдите 2 внешние нормали к соседним сторонам, сдвиньте стороны на r вдоль этих нормалей и пересеките). Можно вывести формулу на бумажке через косинусы/синусы между нормалями (т.е. векторное/скалярное произведения нормалей). Надо будет к точке прибавить обе нормали, умноженные на 1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.

Теперь можно считать ботов точками и они могут касаться полигонов.

Постройте граф. Вершины в графе - вершины полигонов, боты и игрок. Для каждой вершины и другого полигона найдите 2 касательные с точки на полигон - можно перебрать все отрезки из вершины на другой полигон и отбросить те, относительно которых 2 стороны второго многоугольника лежат по разные стороны. Также все эти касательные проверьте на пересечение со всеми остальными полигонами и удалите те, которые пересекаются (проверьте каждую сторону полигона, и пересеките сторону с известным отрезком-касательной).

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

Теперь, для каждого бота и игрока сделайте то же самое - постройте касательные на все многоугольники, удалите те, которые пересекаются с другими полигонами. Также добавтье прямые пути игрок-бот, если нет пересечений с полигонами. В этом графе нужно найти кратчайшие пути (лучше Дейкстрой от игрока до всех ботов).

Обход других ботов делается так - у ботов есть подсчитанные пути. Боты пытаются сделать маленькие шаги вдоль пути. Если они пересекаются с другим ботом, то можно пропустить ход, или попытаться толкнуть другого бота. Расствьте ботам случайные приоритеты и, если бот с большим приоритетом хочет пересечься с ботом с меньшим приоритетом, то второй делает шаг назад.

Они будут толпиться в узких проходах, но в итоге выстроятся шеренгой и пойдут друг за другом. Но это если игрок один. Тогда боты идут в одну сторону. Если они могут ходить против друг друга, то будет хуже. Они могут запереть друг друга в узком проходе и долго выталкивать друг друга.

Теперь - пересчет при движении игрока. Переодически надо пересчитывать пути для ботов. Для этого надо перестроить касательные от игрока и ботов на полигоны и снова прогнать Дейкстру.

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

Касательные между препятствиями вы строите только один раз, тут скорость не так важна. Хуже с точками ботами и игроком. Тут касательные надо искать часто. Если полигоны очень большие, то можно искать точки пересечения и касательные за логарифм, но это очень заумные алгоритмы, через троичный поиск. Могу потом написать, если надо.

Самое медленное, это для каждой касательной проверять на пересечения со всеми полигонами (это n^2 проверок, если у вас n полигонов). Тут можно тоже очень хитро ускорить до n log n проверок, если все касательные отсортировать по углу и потом сделать что-то вроде алгоритма заметающей прямой, но вращать ваш взгляд вокруг точки. Это совсем сложно даже описать, не говоря уж о реализации. Надо складывать полигоны в что-то вроде сбалансированного дерева поиска, которое будет поддерживать их в отсортированном порядке относительно расстояния до точки. Каждая касательная или добавляет полигон, или удаляет его. Вы добавляете касательную только если при добавлении или удалении полигона он был самым ближайшим. Тут нужно будет уметь определять расстояние от точки до полигона вдоль прямой. Опять же, можно сделать тернарным поиском по точкам полигона.

Еще есть вариант через BSP (как в Думe. Дейстивительно эта задача, фактически, узнать, какие полигоны видны из любой точки. Очень близкро к компьютерной графике). Надо разбить всю плоскость на области и для каждой области хранить, на какие полигоны есть касательные из нее. Для этого надо все стороны полигонов продлить до прямых. Все со всем персечь, выделить области. Потом для любой точки в каждой области построить касательные и сохранить. Потом все эти области объеденить в BSP. Это очень хорошее ускорение, но оно работет только если у вас карта статичная. Можно предподсчитать и записывать в файл уже BSP.

Поиск пути в графе тоже можно подускорить. Без добавления ботов и игрока в граф найдите все кратчайшие пути методом Флойда. Теперь, когда вы построили все касательные, для каждого бота переберите касательную его и касательную из игрока. Вы можете моментально подсчитать кратчайший путь через эти касательные, ведь часть пути внутри графа на полигонах уже предподсчитана из алгоритма Флойда. Это будет заметно быстрее, чем гнать дейкстру каждый раз, ибо касательныйх сильно меньше, чем вершин всего в графе.

Алгоритм обхода в ширину или в глубину. Еще его называют алгоритм заливки. Гуглите. Если за одну заливку вы закрасили все черные пиксели, то фигура одна. Иначе, если компонент взязности несколько - разрыв есть.

Мне лень разбираться в вашем коде. Вот правильное решение:

Для всех интервалов добавить в массив точек пары {время начала, +1} и {время конца+1, -1}. Это массив точек - границ вакансий на оси времени (прибавляем 1 к времени конца, потому что последняя секунда включена в интервал). Потом сортируем этот массив. Теперь одиним проходом можно выделить из массива все отрезки времени и сколько на них было открыто вакансий.

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

Для простоты советую сначла одним циклом выделить все отрезки и сложить их в отдельный массив (опять пара - длина отрезка, количество вакансий). Потом пройтись по массиву (или во время складывания) найти максимальное количество вакансий. Потом пройтись еще раз и просуммировать времена для всех отрезков с данным количеством вакансий.

Еще можете посмотреть предыдущий ответ вашему товарищу по курсу: В чем ошибка в алгоритме поиска количества интервалов?

Как преобразовать слова?

Ответ "можно" если
1) Каждому символу первой строки соответствует один и тот же символ второй строки
2) Если есть замены в виде цикла (вроде а->б, б->в, в->а), то нужна хотя бы одна свободная буква (та, которая не стоит справа в замене).

Решается так:
1) Проверить, что строки равны. Это особый случай
2) Проверить, что длина одинаковая?
3) Завести мап символ->символ, пройтись по строкам параллельно и записывать мап[строка1[i]] = строка2[i], если там пусто. Иначе - проверить, что там уже записано то же самое.
4) Проверить, что различных символов во второй строке меньше 33. Можно с помощью сета, который наполняется в том же цикле, что и в шаге 3.

Подсказка: все большие буквы подпадают под "[A-Z]" (надеюсь, вопрос не про русский язык?). Теперь вам надо проверить, есть ли в строке хоть одна буква подпадающая под эту регулярку.

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

Так для 3 символов "abc" будет вызвана функция для "ab", которая вернет [ab, a.b], дописав "c" и ".c" к каждому элементу мы получим [abc, ab.c, a.bc, a.b.c].

Обычное k-d дерево, как по ссылке у freeExec тут будет работать неплохо и будет потреблять сравнительно мало памяти. Но оно не дает гарантию времени выполнения. Может так получится, что вы обойдете почти все вершины в дереве (то же O(n), n - количество точек), даже если в прямоугольник не попала ни одна точка. Правда для этого нужно иметь весьма специфическую конфигурацию точек и очень прямоугольник с большим периметром. Я думаю, этот вариант вам лучше всего подходит, если точки более менее случайно разбросаны и экран занимает лишь маленькую, более менее квадратную область.

R-дерево (по той же ссылке) дает гарантию по времени выполнения и знимает сравнительно мало памяти, но его долго пересчитывать, если точки двигаются или добавляются/удаляются.

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

Дерево отрезков, оно же segment tree - это структура данных, которая делит все пространство координат на половинки, пока не получит в листах по одной координате.

Дерево поиска - это сбалансированное двоичное дерево поиска. Типа avl, красно-черных или декартовых деревьев. Возможно стандартный Set из JS или его аналог тут подойдет.

Суть решения такая - вы разбиватете все пространство по одной координате (скажем, y) деревом отрезков. Каждая вершина этого дерева отвечает за некоторую горизонтальную полосу c фиксированными y координатами и ханит в себе Set всех точек, которые в эту полосу попадают. В Set храните какие-то ссылки на точки (допустим, их id в массиве всех точек), упорядоченные по x координате, а потом по y координате, а потом по id.

Это фактически 2D дерево отрезков, но наивная реализация требовала бы MaxW*MaxH памяти, что слишком много. Замена внутренних деревьев отрезков на Set позволяет сильно сэкономить в памяти.

При добавлении/удалении точки надо в дереве отрезков найти все вершины, которые покрывают ее y координату (их будет Log MaxH) и в их сетах удалить/добавить вершину с заданными (x,y) координатами.

Важно, что set упорядочен по x координате, не той же по которой упорядочено дерево отрезков.

Для получения всех точек в прямоугольнике стандартным обходом дерева отрезков найдите log(MaxH) вершин покрывающих прямоугольник по y координате. Теперь для каждого из найденных Set() найдите upper_bound левой границы. Теперь обойдите точки в Set, начиная с этой, пока не выйдете за правую границу прямоугольника и рисуйте их.

Эта структрура данных найдет все точки в прямоугольнике за O(k + log(MaxW) * log N), где k - количество точек в прямоугольнике, MaxW - высота пространства, N - общее количество точек. При этом каждая точка будет хранится ровно log(MaxW) раз, т.е. по памяти эта структура данных не такая и прожорливая - O(n log(MaxW)).

Единственная проблема: похоже стандартный Set в JS не умеет делать upper_bound. Если точки не меняются часто, то можно вместо Set хранить массив точек отсортированный по x и бинарным поиском искать левую границу при обходе прямоугольника. Иначе же используйте вместо Set более продвинутую реализацию дерева поиска, которая поддерживает upper_bound. Возможно даже есть что-то стандартное в JS или есть готовые библиотеки - я не специалист.

Вам обязательно отвечать на вопрос об электричесвте в конкретном доме по мере добавления ребер/вершин в граф?
Если вам только тесты надо делать, то можно сначала создать весь мир, а потом поспрашивать его о статусах домов. При чем сами вычисления (обход графа) можно сделать только один раз, получить данные по всем домам и потом их проверить.

В этом случае надо, как вы и предположили, хранить массив "посещенности" домов. Можно совместить его с массивом-ответом или статусами домов. Ваш метод уже не принимает конкретный дом как параметр, а просто считатет для всех домов. Он изначально заполняет массив для всех домов и электростанций нулями, что значит, что электричества в доме нет. Потом выполняется DFS (обзод в глубину) или BFS (обход в ширину) от электростанций, которые активны. При этом все посещенные вершины помечаются 1 в массиве. В уже помеченные вершины вы не ходите, поэтому алгоритм незациклиться.

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

Можно сделать гораздо быстрее. Если связи между домами только добавляются (но ни в коем случае не удаляются), то можно использовать систему непересекающихся множеств (DSU). Изначально каждый дом и электростанция - сами себе множество. В каждом множестве поддерживайте счетчик активных электростанций (изначально у домов - 0, у электростанций - 1). Это просто в реализации: у вас есть какой-то массив ссылок root, элеметы которого указывают сами на себя только в корне множества. Заведите второй массив, который будет по тем же индексам хранить счетчики для элементов. Точно также в вики по ссылке выше поддерживатеся rank.

При добавлении провода вы должны слить 2 множества. При этом пересчитайте счетчик (прибавьте счетчик нижнего множества к счетчику верхнего множества).

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

Это решение будет фактически работать за O(1) при каждом запросе и добавлении ребра (если использовать эвристику сжатия путей).
Наивное же решение с полным обходом графа каждый раз было бы O(1) при добавлении ребра и O(n) при запросе.

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

Можно хранить список взятых чисел в глобальном массвие/списке. Но надо аккуратно его откатывать. Перед рекурсивным вызовом, если добавили новое число, то после вызова его из массива/списка удалите. Так будет потребление памяти O(n) вместо O(n^2).

Что-то типа такого:

void Generate(int n, int next, int sum, vector<int> taken) {
  if (next > n || sum > n) return;
  if (sum == n) {
   Output(taken);
  }
  Generate(n, next+1, sum, taken);
  taken.push_back(next);
  Generate(n, next+1, sum+next, taken);
}

...

Generate(n, 1, 0, {});

Но это решение будет не самым быстрым - ибо оно будет заходить в длинные "тупики".

Вариант 2 - оптимизированный перебор, который не перебирает ничего лишнего. Сначала, как в задаче о рюкзаке, при решении динамическим программированием, найдем все варианты набрать каждую сумму.

Заведите двумерный массив n x (n+1). d[i][j] будет хранить, можно ли собрать сумму j используя числа от 1 до i.

База - d[0][0] = true (нет чисел - ноль набрать можно), d[i][0] = false (нет чисел. Не ноль набрать нельзя).

пересчет: d[i][j] = d[i-1][j-i] or d[i-1][j] (или берем текущее число или нет)
Естественно, первый вариант рассматривается только если i<=j. Можно подсчитать этот массив или рекурсивной функцией с запоминанием или просто тупо двумя вложенными циклами.

Потом модифицируем нашу рекурсивную функцию из первого варианта. Теперь она будет как бы идти с конца и параметры будут - сколько первых чисел мы можем использовать, какую сумму должны набрать и какие бОльшие числа уже взяли. В функции опять 2 варианта - или берем текущее число или нет. Но при этом смотрим в массиве d[][], а можем ли мы вообще набрать нужную сумму данными нам числами. Если нет - сразу возвращаемся. Когда пришли к оставшейся сумме в 0, выводим набранные числа.

Оба решения имеют временную сложность O(2^n), но второе будет в несколько раз быстрее, потому что не перебирает никаких тупиков. Возможно, если еще подумать можно избваиться от динамического программирования и вообще вывести формулу, когда из чисел от 1 до i можно собрать заданное число k (может там формула типа i*(i+1)/2 <= k).

Если у вас задача стоит не вывести все наборы (их много! Порядка 2^n), а подсчитать их количество, то тут не надо рекурсивного перебора, а можно подифицировать динамическое программирование, которое будет вместо true/false считать сколько способов собрать из i чисел сумму j. будет формула вида d[i][j] = d[i-1][j] + d[i-1][j-i]. Тогда все решение будет за O(n^2) по времени и можно сделать его O(n) по памяти, если немного подумать (и хранить только две или одну строку матрицы d).