Тюрьма для Зедда

Заметим, что противоположные грани параллелепипеда должны быть равны, поэтому можно поворотом перевести каждый прямоугольник к виду ai ≤ bi, и искать уже три прямоугольника. Далее следует понять, что если длины сторон, исходящих из одной вершины, равны A, B и C, то параллелепипед должен быть составлен из трех прямоугольников со сторонами A × B, A × C, B × C, не забыв, учесть два аспекта: для каждой грани должно быть хотя бы по два соответствующих прямоугольника, кроме того, если два или три размера равны друг другу, некоторые грани совпадают и количество необходимых прямоугнольников возрастает до 4 и 6, соответственно.

Решение первой подзадачи (27 баллов): можно перебрать три прямоугольника, которые войдут в ответ, и явно проверить условие, описанное ранее. Данное решение работает за O(n3).

Решение второй подзадачи (63 балла): можно перебрать один прямоугольник. Пусть он имеет размер A × B — у нас уже известно две размерности параллелепипеда, осталось лишь перебрать третью размерность параллелепипеда C и проверить, есть ли прямоугольники размера A × C и B × C. На этом моменте можно допустить ошибку, когда A = B, A = C или B = C, попытавшись использовать один прямоугольник дважды, хотя его можно взять не больше одного раза. Для простоты можно считать что A, B и C различны, а случаи, когда какая-то пара совпадает, разобрать отдельно, это несложно сделать за O(n). Данное решение работает за O(n2).

Полное решение (100 баллов): будет удобно перейти к графовой интерпретации задачи. Наличие прямоугольников со сторонами A × B, A × C, B × C эквивалентно нахождению цикла длины 3 в графе, построенном на числах, отвечающих за размерности параллелепипеда — прямоугольник A × B отвечает в таком графе за ребро AB.

Решение за O(n2 / 64): перебираем одно из ребер uv треугольника, и смотрим на пересечение множества соседей вершин u и v. Это можно сделать пересечением bitset-ов за n2 / 64, и перебрать третью вершину треугольника как все единички в пересечении bitset-ов.

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

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