Блог пользователя e-maxx

Автор e-maxx, 13 лет назад, По-русски
Решение этой задачи состоит из двух этапов. Первый - научиться считать количество чисел со старшей цифрой 1 в отрезке [L;R]. Второй - по полученным данным (т.е. фактически по известным вероятностям того, что одна величина будет хорошей) решить задачу про K процентов.

Чтобы решить первую подзадачу, можно сгенерировать все отрезки хороших чисел и посмотреть, что останется после их пересечения с отрезком [L;R]. Отрезки хороших чисел имеют вид [1;1], [10;19], [100;199] и т.д., т.е. [10i;2· 10i - 1]. Посчитать, сколько же чисел содержится в их пересечении с отрезком [L;R] - тривиальная задача.

Значит, мы научились считать вероятность p[i] (i = 0... n - 1) того, что i-ая величина будет хорошей: эта вероятность p[i] равна отношению количества хороших чисел, которое мы только что считали, к величине R[i] - L[i] + 1.

Теперь перейдём ко второй части задачи. В ней требуется по полученным вероятностям p[i] того, что та или иная величина будет хорошей, посчитать вероятность того, что K процентов всех величин будут хорошими. Это делается методом динамического программирования: пусть D[i][j] - вероятность того, что среди первых i величин ровно j будут хорошими. Начальным состоянием является D[0][0] = 1, а переходы в динамике следующие:

D[i][j] = p[i - 1]· D[i - 1][j - 1] + (1 - p[i - 1])· D[i - 1][j].

Ответом на задачу будет сумма D[n][j] по всем j таким, что j / n ≥ k / 100.
Разбор задач Codeforces Beta Round 50
  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
проверьте формулу d[i][j] = p[i-1] * (d[i-1][j-1])  + (1-p[i-1]) * d[i-1][j]
в таком случае мы не учитываем p[n] и обращаемся к p[0]
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А я p[] от нуля занумеровал :-p
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      это же разбор для программистов а не для экстрасенсов;) такие вещи наверно надо писать 
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
елки-палки ну и халява.... А я придумал пересчитывать обратные вероятности, хз сколько искал как привести к общему случаю, а оказалась тупая динамика *WALL*
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Эта динамика уже встречалась на Beta Round 47:
http://codeforces.com/contest/50/problem/D

Кстати, кто знает, нет ли у нее какого-нибудь названия вроде "обобщенной схемы Бернулли"? Ведь то же самое, только вероятности различны.

Вот я очень долго не мог найти формулу для количества чисел с первыми единичками :) А помимо всего прочего, меня Петр по B поломал (я квадраты на 90 градусов не поворачивал), пришлось исправлять. А мог бы еще и обратно поломать, причем навсегда; я даже не предполагал, что можно допустить ошибку в сравнении, и на этот кусок кода, разумеется, не смотрел. Так вообще оказалось, что у меня в комнате как минимум три решения B с таким багом были.
Когда наконец уже придумал все в C, времени не оставалось дописать.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Мне кстати тоже приходила такая мысль, когда писал решение этой задачи - уж больно стандартно выглядит эта формула  PD[i - 1] + (1 - P)D[i - 1].

    Наверняка у математиков какое-нибудь слово придумано на этот случай :)

13 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится
hi

why you dont put any tutorial about problem A and problem B ?

although these are simple(maybee!) but i hope you put them ,

by the way , thanks.....
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
(Не знаю, куда писать, но:)
чекер ведет себя очень странно. Решение доходит до какого-нибудь теста, после чего чекер говорит что-нибудь вроде

"Test: #17, time: 2000 мс., память: 13208 Кб, exit code: 0, checker exit code: 0, verdict: TIME_LIMIT_EXCEEDED
Ввод
Вывод
Ответ
Checker Log"

то есть ввод пустой.

Одно и то же решение доходит до разных тестов, от 17 до 57, а потом случается вот такой тайм лимит.
Примеры посылок: 247931, 247935 , 247926
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Аналогичная ситуация:
    Test: #16, time: 910 мс., память: 262144 Кб, exit code: 0, checker exit code: 0, verdict: MEMORY_LIMIT_EXCEEDED
    Ввод
    Вывод 
    Ответ 
    Checker Log
     
    Примеры посылок: 247863, 247738, 247614.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I was just wondering, if the second part (DP) could be solved in < O(n^2). Is there any way?