Please subscribe to the official Codeforces channel in Telegram via the link ×

Разбор задач Educational Codeforces Round 9

Revision en1, by Edvard, 2016-03-02 03:33:00

632F - Magic Matrix

The problem was suggested by Lewin Gan Lewin. The solution and proof also belongs to him.

Consider the undirected complete graph with n nodes, with an edge between nodes i, j with cost aij. Let Bij denote the minimum possible value of the max edge of a path from i to j. We know that aij ≥ Bij by definition.

If the matrix is magic, we can choose arbitrary k1, k2, ..., km such that aij ≤ max(ai, k1, ak1, k2, ..., akm, j) by repeating invocations of the inequality given. Also, you can show that if this inequality is satisfied, then the matrix is magic (by choosing an m = 1 and k1 arbitrary).

So, this shows that the matrix is magic if and only if aij ≤ Bij. Thus, combining with aij ≥ Bij, we have aij = Bij.

We need a fast way to compute Bij for all pairs i, j. This can be computed as the MST, as the path in the MST minimizes the max edge between all pairs of nodes. So, the algorithm works as follows. First, find the MST on the complete graph. Then, the matrix is magic if and only if the max edge on the path between i, j in the MST is exactly equal to ai, j. Also you shouldn't forget to check symmetry of the matrix and diagonal for zeros.

P.S.: Unfortunately we couldn't increase the value n in this problem: the tests already had the size about 67MB and they couldn't be given with generator. So most of the users who solved this problem uses bitset-s. The complexity of their solution is , where b = 32 or b = 64.

C++ solution, binary lifts by me.

Java solution by Lewin.

Complexity: O(n2logn) or O(n2).

Tags educational round 9, editorial


  Rev. Lang. By When Δ Comment
en7 English Edvard 2016-03-03 02:14:37 138
ru12 Russian Edvard 2016-03-03 02:04:28 140
ru11 Russian Edvard 2016-03-02 17:52:11 122
en6 English Edvard 2016-03-02 17:51:16 2062
en5 English Edvard 2016-03-02 17:29:46 963
en4 English Edvard 2016-03-02 17:17:52 1105
ru10 Russian Edvard 2016-03-02 17:05:02 180
en3 English Edvard 2016-03-02 17:03:47 748
en2 English Edvard 2016-03-02 16:58:00 686
ru9 Russian Edvard 2016-03-02 03:33:59 39
en1 English Edvard 2016-03-02 03:33:00 1838 Initial revision for English translation
ru8 Russian Edvard 2016-03-02 03:24:21 2035 Мелкая правка: '_2},\ldots\n,a_{k_m,j}' -
ru7 Russian Edvard 2016-03-02 02:55:42 4
ru6 Russian Edvard 2016-03-02 02:46:07 2299
ru5 Russian Edvard 2016-03-02 02:11:36 2
ru4 Russian Edvard 2016-03-02 02:08:48 870 Мелкая правка: 'руков [used:pitfall].' -
ru3 Russian Edvard 2016-03-02 01:36:50 1379 Мелкая правка: 'ость: $O(n logn l)$, где $l$ --- наиб' -
ru2 Russian Edvard 2016-03-02 01:14:49 776
ru1 Russian Edvard 2016-03-02 01:03:34 748 Первая редакция (опубликовано)