Labunsky

Не сложный алгоритм. Берешь таблицу, и начинаешь слева-направо:
1. Берешь слово;
2. Выбираешь первую попавшуюся свободную клетку (при обходе слева-направо, сверху-вниз, специально для longclaps. Сначала это угол, потом как пойдет);
3. Выбираешь случайное направление движения из доступных (должна быть хоть одна свободная клетка по этому направлению);
4. Начинаешь записывать слово по буквам, используя обход в глубину (ячейки клетки - вершины графа, ребра образуются между двумя свободными клетками, соединенными под прямым углом), с приоретитом на сохранение направления (никаких поворотов, кроме как при упоре в стенку);
5. Если есть еще слова - бери их и иди в п.1.

Это не омега, это "О-большое". Грубо говоря - ограничение сверху. Алгоритм, имеющий сложность O(f(n)), при росте n будет расти (в плане времени работы) не быстрее, чем C*f(n) (C - константа)

UPD. Глаза мыльные, моя беда, ответ - да, "омега"-нотация обозначает лучший случай, О-большое - асимптотически худший

Есть отдельные R&D конторы. Там сидят умные ребята и много думают на заказ

Не тестировал, но как-то так:
1. Считаем сумму всех значений матрицы N, а так же сумму для каждой строки и столбца M[] и соотношение 1 к 0 Z;
2. Вычитаем из N минимальное значение среди M: N -= min(M).;
3. "Убираем" строку или столбец соответсвующую min(M) из матрицы: вычитаем из каждого столбца или строки (соответственно) значения на пересечении и параллельно обновляем Z;
4. Сравниваем Z с предыдущим значением. Если оно стало больше - вернуться к шагу 2. Если меньше - комбинация найдена (неудаленые строки и столбцы).

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

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

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

Очевидно, с помощью обходов графа.
Какой из алгоритмов лучше использовать и какие модификации можно внести - зависит уже от конкретных особенностей графа, то есть у произвольного заранее неизвестно, какая вариация окажется самой оптимальной.
Если возможно, то нужно собрать статистику и посмотреть на возможные особенности обрабатываемых графов. Так, например, для "звезд" будет оптимальным обход центра с BFS, после чего обработка лучей с помощью DFS.

1. Представим все вершины числами от 0 до n;
2. Заводим массив visited, забитый нулями, и переменную count = 0;
3. Находим кратчайший путь между v и u (например, Дейкстрой). Если такой путь существует, то count++ и для каждой его вершины g, отличной от u и v, visited[g]++. Если пути не существует, перейти к шагу 6;
4. Удаляем последнее ребро в найденом пути;
5. Возвращаемся к 3.
6. Ищем такую g, что visited[g] == count. Если такая есть, она и является искомой;

Возможно, данный алгоритм не самый оптимальный, зато простой.

1. Если изначально последовательность правильная - любая инверсия приводит к ее порче;
   
2. Если инверсии было две - последовательность может быть правильной, только когда
   

• Инвертировались скобки разного типа ('(' и ')')
  
• Между ними должно быть четное количество других скобок
  

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

1. Предположим, что скобочная последовательность хранится в виде массива, элементами которого являются скобки, для каждой из которых хранится индекс ее пары (соответствующей закрывающей/открывающей скобки)
   
2. При каждой инверсии будем затирать для соответствующих скобок (открывающая/закрывающая) индексы и помечать их
   
3. Так как инверсии было две, то получим 4 помеченных индекса. В силу того, что инвертировались разные типы скобок, среди них будут либо образовываться две новые пары, не противоречащие правильности последовательности (проверяется это травиально), либо нет
   

Быстрее ничего придумать не получается. Единственное тонкое место - проверка в последнем пункте, так как в различных случаях может занимать как константное время, так и O(k), где k строго меньше n и в среднем случае является логарифмом.