Russian Code Cup 2012: Разбор задач второго квалификационного раунда

[tagir_valeev]

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

[raliev]

Спасибо, поправил

[socro]

Есть ощущение, что формула для вычисления объема тетраэдра не работает для отрезков, из которых невозможно составить этот самый тетраэдр. То есть, применив её к такому набору отрезков, получим множество false positives.

[dzhioev]

Нет, как раз получим отрицательные значения в случае несуществующего тетраэдра. A negative value of the determinant means that a tetrahedron cannot be constructed with the given distances.

[Mrrl]

Формально это фраза дает следствие не в ту сторону: если объем мнимый, то тетраэдра не существует. Обязательно ли он существует при действительном объеме, не сказано. Хотя контрпримера сходу найти не удалось.

[dzhioev]

Вы правы, действительный объем не является достаточным условием, надо еще требовать выполнения неравенств треугольника для граней. Пример, когда объем действительный, но тетраэдра не существует:
d₁₂ = 32
d₁₃ = 297
d₁₄ = 332
d₂₃ = 450
d₂₄ = 48
d₃₄ = 900
V² = 32933194970324
Теперь понятно, почему мое решение не проходило. А я на переполнение грешил.

[dzhioev]

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

[Mrrl]

Да, надо проверять еще неравенства треугольника для все граней. Если выполняются, то проверки объема хватит.

[dzhioev]

Спасибо за разбор. В задаче «Тетраэдр», если считать по, приведенной в первом способе, формуле, то вроде наступает переполнение даже на long long, т.к. величины порядка (10^3)^6 = 10^18 получаются.

[Mrrl]

Максимальное значение формулы в скобках — 2*10^18 < 2^61. Так что в long long умещается.

[tvolf]

Спасибо за статьи. Обнаружил у вас опечатку.
Вместо
==
p[i] = p[i-1] + 1, если i>0 и s[0] = s[l — i — 1]
==
в описании решения задачи «Ключ» должно быть
==
p[i] = p[i-1] + 1, если i>0 и s[i] = s[l — i — 1]
==

[raliev]

спасибо, поправил, действительно опечатка )

[tvolf]

Еще есть один вопрос по решению задачи D «Задачи». Там у вас в коде фигурирует двумерный массив P, одно измерение которого представляет собой уровни задач, а другое — маски тем, как я понял. В первой части программы, которая отвечает за получение/неполучение решения, есть обращение к этому массиву: P[i].length, P[i][mask]. Присутствует, например, сравнение на неравенство элемента массива значению "-1". Но нигде в коде нет установки элементов этого массива в значение, отличное от "-1" ("-1" устанавливается на этапе инициализации). Если можно, проясните, пожалуйста, назначение этого массива?

[raliev]

Тут не полностью исходник, конечно. Весь массив инициализируется -1 по умолчанию.

for (int[] t : P) {
			Arrays.fill(t, -1);
		}
		
		P[0][0] = -2;

И вот с (0,0) и начинается путь.

[tvolf]

Вы не могли бы выложить куда-нибудь полный исходник, если можно? Просто здесь присваивание идет только в первый элемент массива P, а сравнение выполняется для совершенно произвольных элементов:
===
P[i][mask]
===
где i — номер текущего уровня, а mask — текушая маска уровней сложности задач.
То есть, не видно, где эти значения устанавливаются.

[raliev]

Так все исход выложены — russiancodecup.ru/round/7/
Прямая ссылка на зип — russiancodecup.ru/tests/russiancodecup-2012-qual2.zip

[raliev]

Поправлю и в статье, чтобы было яснее