В данной задаче не было ничего сложного. Нужно было уметь пользоваться div и mod. Понятно, что если n>0, то нет смысла удалят цифру. А иначе, нужно удалять.
Для лучшего понимая посмотрите решение
Предпосчитаем такой масив Ai, что Ai = 1, если si = si + 1, иначе Ai = 0. Теперь не сложно заметить, что ответом на запрос будет SumA, l, r - 1. Данную функцию можно организовать множеством вариантов. Одним из, является дерево отрезков. Но так как запросы можно выполнять в оффлайн, то можно использовать массив частичных сумм. Пусть Sumi – это сумма всех Aj, (j ≤ i). Тогда, что бы найти сумму на отрезке (l, r - 1) – нужно Sumr - 1 - Suml - 1.
Для лучшего понимая посмотрите решение.
Для начала отсортируем массив. Пусть Сi –-- это количество раз вхождения числа Аі в оптимальную расстановку. Понятно, что ответом будет сумма всех чисел Ai*Ci (1 ≤ i ≤ 4n). Теперь нужно заметить, что максимальный элемент будет входить n + 1 раз. (Если размер массива равен 4n). Следующие 3 числа, будут входить в ответ n раз, еще следующие 12 уже n - 1. И так далее. Представим, что массив отсортирован по не возрастанию. Не сложно заметить, что ответом будет Sum(1, 1) + Sum(1, 4) + Sum(1, 16)… + Sum(1, 4n). Сумму на отрезках можно реализовывать в лоб, так как это позволяли ограничения.
Для лучшего понимая посмотрите решение.
Для того что бы решить эту задачу нужно было разбить её на две более легкие. Пусть Fulli, j – минимальная стоимость покрыть заданными отрезками, отрезок (i, j). Для того что бы подсчитать эту величину, для всех (i, j) нужно перебрать левую границу отрезка і, и двигать правую. Решение данной подзадачи имеет сложность О(nm). Теперь нам нужно решить вторую подзадачу. Вторая подзадача звучит так: покрыть не менее К точек, отрезками которые не пересекаются (Их стоимости мы знаем, так как мы решили первую подзадачу). Для её решения нужно использовать тот же метод динамического программирования, который намного проще чем решение первой подзадачи. Пусть dpi, j — минимальная стоимость покрыть j точек, если мы просмотрели только префикс длинной i. Из состояния (i, j) мы можем перейти в такие состояния:
1) dpi + 1, j = min(dpi + 1, j, dpi, j); Скажем, что мы не будем покрывать точку с номером i + 1
2) dpk, j + len = min(dpk, j + len, dpi, j + Cost); Cost — стоимость покрытия отрезка длинной len, который заканчивается в точке k. Значение Cost мы предпосчитали в первой подзадаче.
Для лучшего понимая посмотрите решение
Для решения данной задачи нужно уметь использовать кучу и дерево интервалов. Заметим, что если мы берем цифру і с первого числа, и цифру j со второго, то в третьей будет цифра ((i + j)mod m). На каждом шагу из всех таких пар выбирается максимум. Ответ мы выводим на экран, а те две цифры, что мы использовали, нужно удалить. Для решения уже новой задачи, можно завести кучу, в которой изначально будет N значений. Для каждой цифры из первого множества, та цифра из второго которая будет самым оптимальным для ответа. То есть (i1 + i2)mod m = MAX. Но когда мы используем какую-то пару, возможно распадется другая пара. Для того что бы быстро строить новые пары, нужно использовать дерево интервалов для поиска К-го элемента.
Для лучшего понимая посмотрите решение
Также, существует более простое и понятное решение, которое описал MrDindows. Решение MrDindows
Извините за ожидание.
Для того что бы быстро строить новые пары, нужно использовать дерево интервалов для поиска К-го элемента.
Обьясните, пожалуйста, поподробнее эту часть.
Задачу D можно решать без дерева интервалов.
dp[i][j]минимальное количество денег, которое необходимо потратить, чтобы среди первыхiям покрытьjям. Пересчет ведется следующим образом:dp[i][j] = min(dp[i][j],dp[i - 1][j]), далее среди всех отрезков заканчивающихся вi, т.е. для всехk <= iихO(n)нужно взять минимумdp[r - 1][j - (i - r + 1)], k <= r && r <= i, гдеi - r + 1это количество ям которые не перекрываются, если взять текущий отрезок. Но это уже O(n^4). Чтобы довести доO(n^3)нужно перебирать отрезки по возрастанию длины, и "тащить" минимум, добавляя каждый разdp[k - 1][j - (i - k + 1)].Задача Е очень просто решается двумя мультисетами. В целом: Заведем два мультисета. Будем брать максимум в первом и максимум во втором. Потом lower_bound'ом поищем пару для каждого из них. Если обе пары в сумме меньше m, то проверим, какая пара из них больше, ее в ответ и закинем. Если же обе пары в сумме больше, чем m, то закинем в ответ эту пару максимумов, потому что большую пару из них составить никак нельзя. Аккуратно разберем остальные случаи, когда не нашли пару или когда одна из пар в сумме больше m, а вторая меньше.
thanks and great contest
Судя по этому решению: 3803538 , задача Е решается без всяких куч, деревьев, мультисетов и бинпоисков. Ну и на данный момент это самое быстрое из AC решений. Может кто объяснить, что в нём за магия?)
Раз никто не хочет объяснять, придётся самому=)
И так. Имеем чистый жадник за O(n + m). Суть такова:
1) Берём числа из наших последовательностей в отсортированном виде, по частотам. При этом из первой последовательности (далее — первого типа) — в прямом порядке, из второй — в обратном.
2) Эти числа помещаем в стек, при этом, если, занося в стек число второго типа, наверху находим число первого типа, то эту пару извлекаем и добавляем в ответ.
3) В конце, очевидно, в стеке у нас может оказаться некоторое число чисел второго типа снизу и первого — сверху. Тогда их группируем в ответ попарно с начала и конца.
Почему это работает: Извлекая пару во втором пункте, мы имеем гарантированно наилучшую пару для обоих чисел, так как шагаем мы так, что сумма текущих рассматриваемых чисел не больше m-1, то-есть на этом этапе берём пары без переполнения в сумме; соответственно, все числа второго типа, занесённые уже в стек, с текущим числом первого типа будут давать переполнение, а значит и меньший в сумме результат, чем числа второго типа, ещё не занесённые в стек. Для второго типа чисел критерии оптимальности аналогично противоположны.
В третьем пункте мы формируем все пары с переполнением, а тут очевидная жадность: для большего числа первого типа необходимо взять большее число второго типа. В стеке они размещены соответственно так, как мы их берём=)
Will the English editorial public？
google translate may help you ;)
sorry for delay, but in nearest future I will make it.
thx
Может кто-то показать решение первой подзадачи D?
I still don't get problem D's explanation.
This editorial looks like it is written for those whom have already solved the problems, not for those who struggled with some.
Me too. Please explain it clearly. DP[i,j] is explained really confusing.
Thanks. GL & HF!
I will try to explain.
First, lets define cost[i,j] as the minimum cost to fix interval [i,j]. This can be achieved by doing the following for each of the M companies that fixes the holes of the interval [a,b] with cost C: cost[a,l] = min(cost[a,l], C), a <= l <= b.
Once cost[i,j] is defined lets define dp[i,j]. dp[i,j] stores the minimum cost to fix J holes using the interval [1,i]. With this definition our answer lies in dp[N,k] (N as defined by the problem statement, length of the road/amount of holes).
Now lets look at the transitions of this state. To compute dp[i,j] I have to take into account:
a) not fixing any hole, or in other words, dp[i,j] = min(dp[i,j], dp[k,j], 1 <= k < i (with this I'm querying every interval [1,k] that is smaller than [1,i] that has already fixed J holes);
b) to fix k holes. The holes that we'are going to fix are the ones at the end ([i-k,i], 1 <= k <= i). So we will query the states dp[i,j] = min(dp[i,j], dp[i-k][j-k]+cost[i-k][i]) [1].
This works because a) the problem statements says to "fix at LEAST k holes" b) it will not add the cost of a company more than one time (if you can't see this stare a bit longer at the code).
[1] the indexes are not quite correct, take a look at my code: http://codeforces.me/contest/313/submission/3812990
nice.
but no need to calculate
dp[i,j] = min(dp[i,j], dp[k,j], 1 <= k < ibecause these values do not change when you go to new "i". enough of this:dp[i][j] = min(dp[i][j], dp[i-1][j]);sorry for my english.
in problem C, i can't seem to understand why the sorting worked here. i was thinking of this to recursively divide the matrix at each step and then find the maximum of such submatrices and the maximum of whole matrix and then add them and then so on.
i don't understand how magically you sorted them and did those things mentioned above and it did what exactly is mentioned in the problem i.e dividing the matrix into submatrices.
can you make this problem C little clear to me especially WHY THIS SORTING ?
Your largest matrix will have 4^N integers. At first, you will pick the largest number from it, right? Next, you break this largest matrix, into four smaller matrices. You will be picking four integers out of them, such that your overall beauty is maximised. That is only possible if these four matrices have the four largest numbers out of the 4^N integers in them. On next step, you get 16 smaller matrices, and you want them to have the largest 16 integers in them in order to maximise overall beauty. And so on...
I hope you get the idea behind sorting now.
wonder to know the harder "author solution" since the correctness of "MrDindows" is not that obvious.
can you explain more clearly?
thanks in advanced.
This is my idea but my code wasn't right for samples: First I define dp[i][j][k] = minimum cost to fix at least k holes in j first holes using first i companies. while companies are sorted by their right points. And the update: dp[i][j][k] = min (dp[i — 1][j][k], dp[i — 1][j — (j — company[i].left + 1)][k — (j — company[i].left)] + company[i].cost) I saw that the difference between second and third dimensions of dp is always the same, so I omitted third dimension. And so this dp is my solution: dp[i][j] = minimum cost to fix at least j — n + k holes in first j holes using first i companies while companies are sorted. Is this solution right ? :-?
Your intervals are not intersect. Is it right? If its true, then its wrong, because your intervals may intersect. For example: 10 2 5 1 4 1 2 5 1
You need to take 2 intervals, that covers 5 points. Is it clear now?
I don't get why my solution doesn't satisfy this condition. :-?
You solution dont use intervals if they are intersect.
Div2 C Illya and Matrix can be solved using BFS by constructing a tree of maximum element in a submatrix (a tree very similar to Quad Tree/2D Segment Tree) also. You can refer following solution.
Implementation using Queue
@divyank1 The main solution provided in the editorial is also very similar too. Thanks
313C gives a TLE on test 48 when submitted on GNU C++14, but the same code gets ACed when submitted on GNU C++.
Why is that the case?
Problem E hint :
We have
0 <= a,b,c < mif (a + b >= m and c + b < m) (resp. c + a)then (always) (c + b) % m >= (a + b) % mbut why (c + b) % m >= (a + b) % m ?
в B я считал динамику.
dp[i] — ответ на префиксе длины i. и пересчитывал ее следующим образом: dp[i] = dp[i-1] + (int)(s[i] == s[i-1])
при ответе на запросы рассматривал 3 случая:
1) Если отрезок длины 1,т.е. r — l == 0 тогда ответ 0. 2) Если отрезок является префиксом, ответ просто dp[r]. 3) В ином случае ответ это dp[r] — dp[l-1] — (int)(s[l]==s[l-1]). Мы вычитаем 1 в случае s[l] == s[l-1] ведь в этом случае, отрезок начинается на стыке создания пары и мы его посчитаем лишний раз) Вот код: ТыК