Codeforces Round #323 Editorial

Правка en9, от danilka.pro, 2015-10-03 18:55:30

To solve the problem one could just store two arrays hused[j] and vused[j] sized n and filled with false initially. Then process intersections one by one from 1 to n, and if for i-th intersections both hused[hi] and vused[vi] are false, add i to answer and set both hused[hi] and vused[vi] with true meaning that hi-th horizontal and vi-th vertical roads are now asphalted, and skip asphalting the intersection roads otherwise.

Such solution has O(n2) complexity.

Let the answer be a1 ≤ a2 ≤ ... ≤ an. We will use the fact that gcd(ai, aj) ≤ amin(i, j).

It is true that gcd(an, an) = an ≥ ai ≥ gcd(ai, aj) for every 1 ≤ i, j ≤ n. That means that an is equal to maximum element in the table. Let set an to maximal element in the table and delete it from table elements set. We've deleted gcd(an, an), so the set now contains all gcd(ai, aj), for every 1 ≤ i, j ≤ n and 1 ≤ min(i, j) ≤ n - 1.

By the last two inequalities gcd(ai, aj) ≤ amin(i, j) ≤ an - 1 = gcd(an - 1, an - 1). As soon as set contains gcd(an - 1, an - 1), the maximum element in current element set is equal to an - 1. As far as we already know an, let's delete the gcd(an - 1, an - 1), gcd(an - 1, an), gcd(an, an - 1) from the element set. Now set contains all the gcd(ai, aj), for every 1 ≤ i, j ≤ n and 1 ≤ min(i, j) ≤ n - 2.

We're repeating that operation for every k from n - 2 to 1, setting ak to maximum element in the set and deleting the gcd(ak, ak), gcd(ai, ak), gcd(ak, ai) for every k < i ≤ n from the set.

One could prove correctness of this algorithm by mathematical induction. For performing deleting and getting maximum element operations one could use multiset or map structure, so solution has complexity .

Теги editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru6 Русский danilka.pro 2015-10-05 16:27:13 13
en38 Английский danilka.pro 2015-10-05 16:27:03 13
ru5 Русский danilka.pro 2015-10-05 16:25:24 4 Мелкая правка: 'C[i][j]=\min\limits_{k' -> 'C[i][j]=\max\limits_{k'
en37 Английский danilka.pro 2015-10-05 16:25:08 4 Tiny change: 'C[i][j]=\min\limits_{k' -> 'C[i][j]=\max\limits_{k'
ru4 Русский danilka.pro 2015-10-04 18:11:51 2795
ru3 Русский danilka.pro 2015-10-04 17:50:17 2316
ru2 Русский danilka.pro 2015-10-04 17:32:41 1720
en36 Английский danilka.pro 2015-10-04 17:22:08 0 (published)
ru1 Русский danilka.pro 2015-10-04 17:21:49 11138 Первая редакция перевода на Русский (сохранено в черновиках)
en35 Английский danilka.pro 2015-10-04 16:38:30 4 Tiny change: '\n$mn_r=\min\limits_{i' -> '\n$mn_r=\max\limits_{i'
en34 Английский danilka.pro 2015-10-04 00:34:59 54
en33 Английский danilka.pro 2015-10-03 23:46:45 12
en32 Английский danilka.pro 2015-10-03 23:38:05 38
en31 Английский danilka.pro 2015-10-03 23:36:33 389
en30 Английский danilka.pro 2015-10-03 23:26:56 1 Tiny change: ' \cdot sr[mask]$, wh' -> ' \cdot sr[smask]$, wh'
en29 Английский danilka.pro 2015-10-03 23:15:16 9 Tiny change: 'nts $i+k-1\equiv j \mod{n}). Any it's' -
en28 Английский danilka.pro 2015-10-03 22:12:48 0 (published)
en27 Английский danilka.pro 2015-10-03 22:12:15 107
en26 Английский danilka.pro 2015-10-03 22:10:24 5 Tiny change: 'bitmask.\n()&()\nNow, we ' -> 'bitmask.\n\nNow, we '
en25 Английский danilka.pro 2015-10-03 22:09:58 1 Tiny change: ' in $mask ^ submask$' -> ' in $mask \^ submask$'
en24 Английский danilka.pro 2015-10-03 22:09:28 3238
en23 Английский danilka.pro 2015-10-03 21:42:17 2 Tiny change: '~~\n\n\n\n' -> '~~\n\n\n\n\n'
en22 Английский danilka.pro 2015-10-03 21:39:38 595
en21 Английский danilka.pro 2015-10-03 21:32:22 48
en20 Английский danilka.pro 2015-10-03 21:31:26 2313
en19 Английский danilka.pro 2015-10-03 20:42:49 196
en18 Английский danilka.pro 2015-10-03 20:33:33 413
en17 Английский danilka.pro 2015-10-03 20:24:17 26 Tiny change: 'alpha = \left$\n\n' -> 'alpha = \lfloor \frac{n}{p} \rfloor$\n\n'
en16 Английский danilka.pro 2015-10-03 20:22:20 26
en15 Английский danilka.pro 2015-10-03 20:22:08 990
en14 Английский danilka.pro 2015-10-03 19:43:54 93
en13 Английский danilka.pro 2015-10-03 19:39:55 44
en12 Английский danilka.pro 2015-10-03 19:38:49 1441
en11 Английский danilka.pro 2015-10-03 19:16:11 1016
en10 Английский danilka.pro 2015-10-03 18:56:25 419
en9 Английский danilka.pro 2015-10-03 18:55:30 1 Tiny change: ' inductions. For perf' -> ' induction. For perf'
en8 Английский danilka.pro 2015-10-03 18:55:08 8 Tiny change: 'g maximum operation' -> 'g maximum element operation'
en7 Английский danilka.pro 2015-10-03 18:54:42 13 Tiny change: '< i \le n$.\n\nOne c' -> '< i \le n$ from the se.\n\nOne c'
en6 Английский danilka.pro 2015-10-03 18:54:27 24 Tiny change: 'a_k, a_i)$.\n\nOne ' -> 'a_k, a_i)$ for every $k < i \le n$.\n\nOne '
en5 Английский danilka.pro 2015-10-03 18:53:52 47
en4 Английский danilka.pro 2015-10-03 18:52:50 22
en3 Английский danilka.pro 2015-10-03 18:52:04 1329
en2 Английский danilka.pro 2015-10-03 18:51:34 38 Tiny change: 'herwise.\n\n' -> 'herwise.\nSuch solution has $O(n^2)$ complexity.\n'
en1 Английский danilka.pro 2015-10-03 18:49:46 494 Initial revision (saved to drafts)