Блог пользователя Ripatti

Автор Ripatti, 13 лет назад, По-русски

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
там приложены статья и код, только автор контеста в них не особо вникал))

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Еще наверно Е можно делать за O(n^4), но при этом O(n) в среднем. Решая аналогично алгоритму для 2d случая.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I think there is a mistype in the solution for the C problem. Instead of the

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
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is O(n2) algorithm optimal for problem B? I mean, can we construct the boolean array in O(n)?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I'm sorry I have some questions on analysis of problem E.
1) Now let's consider flat plane and choose one straight line in it. Set for every point of this line a minumum of function f1 of line thatpasses through this point and is perpendicular to choosen line

Do you mean the line  in the whole space or just in this flat plane as mentioned above. But if it is in the flat plane, there can only be one line  perpendicular to choosen line?

2) If f2 is not convex, we can find at least two local minimums. Let's choose two neighbour of them. We can find this two minimums on the plane and drawn through them new line

 two neighbour of them, what does  the them refer to? Two local minimums or sth else? What's more, I don't know how to choose them, only in the line or in the plane? 

Many thanks.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I am not able to formulate solution for problem E.Tell what I should study before going for developing solution to this problem
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Авторское решение задачи Е просто и понятно, но может кто-нибудь мне обосновать корректность решений вида
  1. int main()
  2. {
  3.         scanf("%d",&n);
  4.         for(int i = 0; i < n; i++)
  5.                 scanf("%lf%lf%lf",&x[i],&y[i],&z[i]);

  6.         double d = 1;
  7.         double xx=0,yy=0,zz=0;
  8.         for(int i = 0; i < 20000; i++)
  9.         {
  10.                 double t=-1;int id = 0;
  11.                 for(int j = 0; j < n; j++)
  12.                 {
  13.                         double dis = sqr(x[j]-xx)+sqr(y[j]-yy)+sqr(z[j]-zz);
  14.                         if(dis>t)
  15.                         {
  16.                                 t = dis;
  17.                                 id = j;
  18.                         }
  19.                 }
  20.                 xx += (x[id]-xx)*d;
  21.                 yy += (y[id]-yy)*d;
  22.                 zz += (z[id]-zz)*d;
  23.                 d *= 0.999;
  24.         }
  25.         printf("%.10f %.10f %.10f\n",xx,yy,zz);
  26. Почему данный алгоритм будет работать? В основном, большинство сдавших использовали именно эту идею, а не
  27. тройной поиск минимума функции одной переменной. То есть в данном алгоритме, мы просто итеративно со все уменьшаю-
  28. щимся шагом идем от исходной точки, до самой удаленной. Но почему, таким образом, мы с заданной точностью придем к единственной точке
  29. минимума выпуклой функции.
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    в случае достаточной гладкости минимум выпуклой непреривной функции можно искать через градиентний спуск. В нашем случае функция только непрерывна и выпуклая, но минимум таких функций можно искать субградиентным спуском. Со стороны реализации они практически не отличаются, а вот теор. часть у них отличается(в последнего посложнее будет). В интернете достаточно литературы об этом.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
nice tutorial, thanks for it. .
by the way, this isn't too important, but you have a mistake in the title of the post. .
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is problem C is tagged with "CRT" ? It is simple DP i guess. Can it be solved as a CRT question ?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you please elaborate how dp is helping in probelm C??

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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++

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone plz suggest some more problems like C

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks. good editorial