Wataru

Ну вы подставьте в формулу число. Допустим, N=3: 1+2+3 = 6. N(N-1)/2= 3*2/2 = 3. Не сходится!
Правильная формула, все-таки N(N+1)/2.

А разница в том, что в учебнике получается сумма от 1 до N-1. Т.е. в формулу прогрессии от 1 до N надо подставить N-1. Вот и получается (N-1)(N-1+1)/2 = (N-1)N/2

Что значит, несравнимых элементов? Типа, вы знаете, что элементы каждого списка строго упорядочены, но про разные элементы из разных списков ничего сказать не можете, только если косвенно?

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

Надо, чтобы "четность" перестановки совпадала с четностью финального поля (1).
Занумеруйте все 16 позиций слева направо сверху вниз.
чтобы подсчитать четность, рассматривайте каждую пару заполненных позиций (15\*14/2=105 пар) - если числа идут не в том порядке (большее число на позиции с меньшим номером) - то прибавьте 1 к ответу. В конце возьмите ответ по модулю 2. Это и будет четность перестановки.

Чтобы получить поле, которое можно собрать, сгенерируйте любую перестановку (случайно перемешайте 15 чисел), а потом посчитайте ee четность. Если четность плохая, то поменйте местами любые 2 соседних элемента (выберите случайно, или меняйте первые 2 всегда - на вероятности всех возможных полей это не влияет).

Edit: Но вы это почти все итак знатете, ибо функция is_solvable в вашем коде как раз инверсии уже считает.
Значит, Но вы знаете, что плохое поле от хорошего отличается лишь четностью, значит, если поле плохое - меняйте местами 2 соседних по порядку элемента. Например верхний левый со вторым в верхней строке.

Алгоритм называется "обход в глубину на графе". Работает за линию, все очень быстро. Правда, его придется применить несколько раз.

Все неравенства "==" замените на пару "<=" и ">=".
Добавьте неравенства 1 < 2, 3 < 4 и т.д. для каждой пары соседних на числовой прямой чисел во входных данных

Постройте граф: Каждой переменной и уникальному числу во входных данных сопоставьте одну вершину. Проведите для каждого неравнества ребро от меньшей вершины к большей, раскрашенное в 2 цвета: черный, если неравнество нестрогое (<=), белый - иначе.

Теперь, если в этом графе нет циклов, содержащих белые ребра (строгие неравенства) - то противоречий нет: Все циклы целиком из черных ребер означают, что все вершины имеют одинаковое значение. Можно эти вершины все объединить в одну новую. Раз белые ребра (<) циклов не образуют, то получившийся граф будет ациклическим и можно назначить всем вершинам какие-то числовые значения, удовлетворяющие условиям. Проблема может еще быть, что нет целых решений вроде 1== a < b < c == 2, но это можно потом проверить в топологической сортировке жадно назначая всем вершинам числа. Или противоречия вида 2==3. Тоже решается после получения компонент связности.

Итак, алгоритм: найдите в этом графе компоненты сильной связности. Потом проверьте все ребра. Если белое ребро (строгое неравнество) имеет оба конца в одной и той же компоненте - вы нашли противоречие.

Теперь надо постараться назначить кадой компоненте числовое значение так, чтобы не было противоречий. Это можно делать жадно, назначая каждой компоненте минимально возможное значение.

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

В конце вы получите для каждой компоненты ее численное значение без каких-либо противоречий.

Берете 2 любве точки, пересекаете окружности. 2 получившиеся точки проверяете с остальными n-2 окружностями.

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

Но если вам по заданию надо бинпоиск использовать, то у вас там следующие ошибки в реализации:
- постоянное преобразование к toLowerCase - это ОЧЕНЬ неэффективно. Один раз все приведите к lowerCase и работайте только с этим. Можно эти ключи схоранить в новых полях.
- когда вы нашли совпадение, можно делать из цикла break.

Вы не сможете бинпоиском найти все объекты. Он может найти только один. Самый левый, самый правый, или как повезет - зависит от реализации.
Вам надо запустить два бинпоиска последовательно. Один будет искать минимальный элемент, больше равный искомому (lower_bound), а второй бинпоиск будет искать максимальный элемент строго больший искомому (upper_bound). Пусть ваши бинпоиски возвращают индекс в массиве list. Эти две функции будут отличаться только в одном месте - там будет < и <= соответсственно.
Ответ к задаче будет в массиве list по индексам от lower_bound (включительно) до upper_bound (не включительно). Может быть и так, что lower_bound == upper_bound, если искомого элемента в массиве нет и ответ будет пустым.

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

Я бы действительно не вводил сущность ребро. И просто в вершинах хранил список соседних вершин (оно еще называется список смежности). Так экономнее, быстрее и проще.

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

Линейная сложность и там и там.

Если вместо синусов и косинусов использовать вектора, то формулы будут сильно проще. Все изменения происходят вдоль нормали соприкосновения. А там одномерная формула вообще: проецируете скорости на нормаль, потом считаете коэффициенты изменений одной и другой скорости, чтобы сохранился импульс и энергия. Потом прибавляете вектора изменений к векторам скоростей. Вместо синусов/косинусов считаете векторное/скалярное произведение векторов.

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

В тексте задания уже есть ответ на ваш вопрос:

To better utilize memory, the list should include an array T=8 of structures representing a block

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

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

Фактически у вас тут запросы, "найти строки где много нулей на этих произвольных позициях". Никакого предподсчета я тут не вижу. Можно здорово ускорить, если хранить от строк только битовые последовательности (где '0' заменяется на единичный бит). Далее каждую строку надо про AND-ить побитово с новой и подсчитать количество единичных бит. Это теооетически раз в 64-100 ускорит вычисления, если 64-битный целый тип использовать. Или еще несколько раз сверху, если использовать векторизацию. Но как это в php сделать, я не знаю.

Даже без 5% ошибок оно не оптимизируется предподсчетами. Тупо найти строки, в которых '0' вот на этих позициях - особо не наоптимизируешь.

Сумму на отрезке надо делать хитро: в каждой вершине поддерживайте счетчик, сумму значений всех вершин в поддереве, а так же минимальное и максимальное значение в поддереве.

Рекурсивно спускайтесь, если текущее поддерево целиком лежит в запросе - возвращайте известную сумму.
Иначе запускайтесь слева или справа только если отрезок там пересекается. Или можно просто возвращать 0 вместо этих проверок, если все вершины в поддереве не попадают в отрезок (меньше левой границы запроса или больше правой). Такой подход найдет сумму за O(log n) а не за O(n).

С такими ограничениями надо менять алгоритм. У вас наивная реализация за O(nq). А надо реализовывать rope за O(q log n).

Какими-то стандартными контейнерами это не сделать вообще никак.

Советую реализовывать декартово дерево по неявному ключу. Это самая простая реализация будет. Ну, а дальше вам надо будет это дерево разрезать на три части двумя Split, две крайние объеденить, разрезать это в новом месте и слить уже 3 части с вырезанным куском в середине.

Это вроде как решето Эратосфена (только с багами).

Этот цикл по идее помечает составными все числа, делящиеся на i (которое к этому моменту вроде как простое). Таким образом все составные числа должны быть помечены в массиве a.
Тут есть оптимизация: помечаются только те числа, для которых i - делитель не больше корня. Иначе бы цикл был не от i*i а от i. Эту оптимизацию можно делать, потому что у каждого числа обязательно есть простой делитель не больше корня, а значит и такой цикл пометит все составные числа.

Сложность тут O(n log(log n)) - Доказательство смотрите в википедии.