A. (ссылка) Решение этой задачи описано в четвертом абзаце условия. Его надо было внимательно прочитать и реализовать. Единственная сложность которая могла возникнуть - как опередить какое достоинство старше. Для этого можно было двумя проходами по массиву [ '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A' ] определить номера достоинств карт в массиве, а полученные числа сравнить.
B. (ссылка) Можно было использовать дополнительный массив, в котором true означает, что ноутбук устаревший, а false - что нет. Значение в каждой ячейке этого массива определяется проходом по всем ноутбукам и сравнения его параметров с параметрами текущего ноутбука. За еще один проход среди всех не устаревших ноутбуков нужно было выбрать самый дешевый.
C. (ссылка) Создадим массив dp размера n на m. dp[i][j] будет означать максимальное количество денег, которое мы получим если используем i единиц теста и испечем булочки с начинками типов 1..j.
Изначально dp[i][0] = 0 для всех i.
Пересчитать данную динамику несложно:
dp[i][j] = max{ dp[i-c[j]*k][j-1] + d[j]*k } по всем k от 0 до a[j]/b[j], для которых i-c[j]*k>=0
Ответом будет max{ dp[k][m] + ((n-k)/c0)*d0 } по всем k от 0 до n.
Конечно же, в разборе данной задачи деление везде целочисленное.
Полученное решение работает за O(nma), где a - максимум по a_i.
D. (ссылка) Решение представляет собой симуляцию всех инструкций от всех достопримечательностей. Однако наивное решение не проходит по времени. Решение нужно ускорить, а именно: выполнение каждой инструкции должно быть выполнена за O(1).
Это можно сделать одним из следующих способов.
1. Для каждой позиции предпосчитать положение ближайшей клетки моря по всем четырем направлениям. Теперь перед каждым выполнением инструкции нужно смотреть попадем ли мы в клетку моря при выполнении.
2. Для каждой клетки моря поставить в соответствие 1, а для всех остальных 0. После этого для каждой клетки (i,j) посчитать сумму чисел на прямоугольнике с углами в (1,1) и (i,j). Это можно сделать с помощью операций вида
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + smth
где smth - это 0 или 1 в зависимости от текущей клетки. Похожим образом можно проверять есть ли клетки моря на любом прямоугольнике, например, на узком прямоугольнике ширины 1, по которому мы будем идти в процессе выполнения инструкции.
Итоговое решение за время O(nm + kz), где z - количество достопримечательностей (это число не превосходит 26).
E. (ссылка) Авторское решение - 3 вложенных друг в друга тернарных поиска по каждой из координат.
Это работает, поскольку предложенная функция выпуклая - максимум выпуклых функций тоже выпуклая функция. Однако автор не совсем хорошо представляет себе выпуклую функцию в трехмерном пространстве, поэтому можно почитать следующее его доказательство корректности алгоритма:
Рассмотрим какую либо прямую. Функция расстояния от точек на этой прямой до какой либо точки будет выпуклой вниз (ну, это несложно представить себе). Если теперь рассмотреть все точки, то у нас будет максимум от выпуклых вниз функций, что тоже есть выпуклая вниз функция. Назовем эту функцию f1. Еще надо отметить, что выпуклость тут строгая (т.е. константных кусков нет) (*).
Теперь рассмотрим плоскость и выберем в ней прямую. Повесим на каждую точку этой прямой минимум из f1 от прямой, которая через эту точку проходит и перпендикулярна выбранной прямой. Назовем полученную функцию на выбранной прямой f2.
Итак, f2 тоже выпукла вниз. Докажем это от противного - если это не так, то найдутся хотя бы два локальных минимума. Возьмем два соседних из них. Найдем точки где они находятся на плоскости и проведем через них прямую. И функция f1 на ней получится не выпуклая! (почему - несложно понять, если представить картинку и при этом учесть (*)). Противоречие.
Теперь возьмем пространство. Проведем там прямую и заведем на ней функцию f3. Ее значениями будут минимумы f2 в плоскостях, перпендикулярных выбранной прямой. f3 тоже выпукла вниз - доказательство аналогично тому, что в предыдущем абзаце. []
Итак, теперь несложно понять, что минимум найти несложно троичными поисками по fi. Если к этим функциям прикрепить еще возврат значения, где этот минимум достигается, то несложно получить и ответ.
Также есть решения, которые используют идею градиентного спуска. Автору не удалось написать такое решения (не проходит по точности), но некоторые участники сдали такие решения.
Еще есть точное решение за время O(n^4) (более точно - O(C_n^4)), использующее теорему Хелли и следующую из него теорему Юнга:
http://ru.wikipedia.org/wiki/Теорема_Хелли
http://en.wikipedia.org/wiki/Helly's_theorem
В этом решении нужно перебрать все двойки, тройки и четверки точек и найти центр наименьшего шара, включающих их. После чего выбрать центр наибольшего из полученных шаров.
Еще можно было нагуглить что то вроде
http://www.inf.ethz.ch/personal/gaertner/miniball.html
там приложены статья и код, только автор контеста в них не особо вникал))
dp[i][j] = max{ dp[i-c[i]*k][j-1] + d[i]*k } for every k from 0 to a[j]/b[j], for which i-c[i]*k>=0
there should be
dp[i][j] = max{ dp[i-c[j]*k][j-1] + d[j]*k } for every k from 0 to a[j]/b[j], for which i-c[j]*k>=0
by the way, this isn't too important, but you have a mistake in the title of the post. .
Why is problem C is tagged with "CRT" ? It is simple DP i guess. Can it be solved as a CRT question ?
yes i also want to know this !
what is CRT
Can you please elaborate how dp is helping in probelm C??
The problem can be subdivided into problems where types of dough can be reduced as well as the summation of answer from different subproblems can be used to find the answer to the original problem(OPTIMAL SUBSTRUCTURE PROPERTY).
Hence divide the problem with 2 states: the amount of dough left and types of stuffing, total cases possible is O(1000*11) and each case can take at most O(100) time Since a[i]/b[i] is maximum 100 so total time is O(1000*11*100) = O(10^6) solvable within 1 sec. Don't forget to add memoisation in the recursion used.
Solution in C++
can anyone plz suggest some more problems like C
https://mirror.codeforces.com/blog/entry/20284
Scroll down to comments. You will get a list of Dp problems medium level. I also have started solving.
One more resource: SameerGulati Sameer Gulati's answer on Quora
Thanx
Solve all Atcoder Educational DP questions LINK.
Thanks. good editorial