Codeforces Round 270 |
---|
Закончено |
Помимо прочего, можно придумывать новые задачи, решая обратные задачи к старым задачам. Обратная задача — это когда в качестве входных данных даются выходные данные исходной задачи и нужно сгенерировать в качестве выходных данных такие входное данные, что решение исходной задачи на них выдавало бы заданные входные данные. Самая сложная задача Topcoder Open 2014 раунда 2C, InverseRMQ, является хорошим примером такого подхода.
Попробуем придумать новую задачу таким способом. В качестве основы используем следующую задачу: задано дерево; подсчитайте расстояние между всеми парами его вершин. Да, это просто. Но обратная версия этой задачи куда сложнее: задана матрица расстояний размера n × n. Определите, может ли данная матрица быть матрицей всех попарных расстояний между вершинами взвешенного дерева (все веса должны быть целыми положительными числами).
В первой строке записано целое число n (1 ≤ n ≤ 2000) — размер матрицы (и количество вершин соответствующего дерева).
В следующих n строках содержится по n целых чисел di, j (0 ≤ di, j ≤ 109) — расстояние между вершиной i и вершиной j дерева.
Если такое дерево существует, выведите «YES», в противном случае выведите «NO».
3
0 2 7
2 0 9
7 9 0
YES
3
1 2 7
2 0 9
7 9 0
NO
3
0 2 2
7 0 9
7 9 0
NO
3
0 1 1
1 0 1
1 1 0
NO
2
0 0
0 0
NO
В первом примере необходимое дерево существует. Оно состоит из ребра между вершинами 1 и 2 с весом 2 и ребра между вершинами 1 и 3 с весом 7.
Во втором примере дерево не существует, потому что d1, 1 должно равняться 0, а оно равняется 1.
В третьем примере дерево не существует, потому что d1, 2 должно равняться d2, 1.
Название |
---|