Codeforces Round #448(Div.2) Editorial

Правка en2, от NBAH, 2017-11-26 23:28:36

895A - Pizza Separation

We can notice that if one of the sectors is continuous then all the remaining pieces also form a continuous sector.If angle of first sector is equal to x then difference between angles of first and second sectors is |x - (360 - x)| = |2 * x - 360| = 2 * |x - 180|. So for each possible contnuous sector we can count it's angle and update answer.

Time complexity O(n2) or O(n).

895B - XK Segments

First, we need to understand how to find the number of integers in [l, r] segment which are divisible by x. It is r / x–(l - 1) / x. After that we should sort array in ascending order. For each left boundary of the segment l = a[i] we need to find minimal and maximal index of good right boundaries. All right boundaries r = a[j] should satisfy the following condition a[j] / x–(a[i] - 1) / x = k. We already know (a[i] - 1) / x, a[j] / x is increasing while a[j] increases. So we can do binary search on sorted array to find minimal/maximal index of good right boundaries and that mean we can find the number of good right boundaries.

Time complexity O(n * log(n)).

895C - Square Subsets

We can notice that x is a perfect square of some integer if and only if each prime number enters decomposition of x into prime factors even times. There are only 19 prime numbers less than 70. Now we should find the bitmask for each integer in [1, 70] by the following way: There is 1 in bit representation of mask in k-th place if k-th prime number enters decomposition of that numbrer odd times. Else there is 0. For each integer between 1 and 70 we need to find the number of ways we can take odd and even amount of it from a. Let f1[i], f0[i] be that number of ways relatively. Let dp[i][j] be the number of ways to choose some elements which are <= i from a, and their product has only those prime numbers in odd degree on whose index number j has 1 in binary representation. Initially dp[0][0] = 1.

dp[i + 1][jxormask[i + 1]] +  = dp[i][j] * f1[i + 1]

dp[i + 1][j] +  = dp[i][j] * f0[i + 1]

The answer is dp[70][0].

Time complexity is O(max*2^cnt(max)), where max is maximal integer a[i], and cnt(max) is the number of prime numbers less than max.

895D - String Mark

895E - Eyes Closed

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru5 Русский NBAH 2017-11-27 21:27:21 218
en7 Английский NBAH 2017-11-27 21:27:21 218
en6 Английский NBAH 2017-11-27 19:51:42 533
ru4 Русский NBAH 2017-11-27 19:47:24 494
ru3 Русский NBAH 2017-11-26 23:49:49 7 Мелкая правка: 'dp[i+1][j xor mask[i+1]' -> 'dp[i+1][j \oplus mask[i+1]' (опубликовано)
en5 Английский NBAH 2017-11-26 23:47:46 10
en4 Английский NBAH 2017-11-26 23:39:54 5
en3 Английский NBAH 2017-11-26 23:39:06 2154
en2 Английский NBAH 2017-11-26 23:28:36 1901
en1 Английский NBAH 2017-11-26 23:27:38 4288 Initial revision for English translation (saved to drafts)
ru2 Русский NBAH 2017-11-26 23:10:57 6
ru1 Русский NBAH 2017-11-26 22:50:09 4468 Первая редакция (опубликовано)