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

Автор altruist, история, 8 лет назад, По-русски

Приносим свои извинения за столь позднюю публикацию.

Tutorial is loading...
Асимптотика: O(1).
Автор идеи задачи: Vladik.
Разрабатывал задачу: Vladik.
Tutorial is loading...

Асимптотика: O(n2).
Автор идеи задачи: MikeMirzayanov.
Разрабатывали задачу: fcspartakm.

Tutorial is loading...

Автор идеи задачи: altruist.
Разрабатывал задачу: Vladik.
Асимптотика: O(n3 * m).

Tutorial is loading...

Автор идеи задачи: altruist.
Разрабатывал задачу: altruist.
Асимптотика: O(n).

Tutorial is loading...

Автор идеи задачи: MikeMirzayanov.
Разрабатывал задачу: altruist.
Асимптотика: O(n).

Tutorial is loading...

Автор идеи задачи: Vladik.
Разрабатывал задачу: Vladik.
Асимптотика: O(d * (N * M + K)), где d — размер алфавита.

Разбор задач Codeforces Round 394 (Div. 2)
  • Проголосовать: нравится
  • +119
  • Проголосовать: не нравится

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

Автокомментарий: текст был обновлен пользователем altruist (предыдущая версия, новая версия, сравнить).

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

Can someone provide more explanation about solving Div-2 E?

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

Problem C can be done in O(N*M) using dynamic programming.

http://codeforces.net/contest/761/submission/24322743

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

    can you please explain me your approach ? thanks in advance .

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

      It's quite similar to this problem. At state i, you just want to know

      • minimal cost to have 1 digit (or 1 lowercase or 1 special character) as well as
      • minimal cost to have 2 (1 digit & 1 lowercase, 1 digit & 1 special character, 1 lowercase & 1 special character) and finally,
      • minimal cost to have all of three characters.

      Because at the state i, you can't conclude anything, you have to store all of them to conduct the answer at final state.
      Check my solution. It's same ideal with Arkin, i think.

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

Простите, но мне тяжело понять решение F.

Я не понял этого формула:

a(x,y) - ? Если это символ в ячейки (x,y) исходной матрице,

Почему это не так: f(x,y) = sum( abs(i - a( x , y ) )*cnt(x,y,i), i = A..Z) ??

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

    Да, a(x,y) — символ ячейки в исходной матрице, формула будет исправлена, спасибо.

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

Can anyone explain me DP approach of problem C ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    A simpler approach for problem C would be to store the least index for each type (special,alpha,numeric) in each string if exists. you will have a matrix A[n][3]. now you need to find three indexes i,j,k such that A[i][0] + A[j][1] + A[k][2] is minimum. now simply use three nested for loops one inside another and check for the minimum while ensuring i != j != k, which takes O(N*M + N^3) time. Further optimized solution would be to pick the first minimum, second minimum, third minimum from each column and use the three for loops as mentioned above which will reduce the run time to O(N*M + 3^3) = O(N*M).

    Hope this helped you, Link to my code

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

Can someone explain to me why is [l - ai;r - ai] in problem D ?