ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1716. Альтернативное решение

O(1) Formula
Послано Sereja Slotin 19 окт 2016 23:30
I don't know why there were so many submitted O(n^2) DP solutions. Here is a simple formula for this problem:
answer = n - (yes + yes*(yes-1) + no*(no-1))/n, where yes = s-2*n and no = n-yes are the total numbers of occurrences of corresponding strings in answer.txt.
You can easily derive this if you try to think of probability of the same verdict for two arbitrary consecutive tests.
Re: O(1) Formula
Послано Felix_Mate 21 июн 2017 15:06
Why this formula is right? I solved problem by DP, but i can't prove this formula.
Re: O(1) Formula
Послано Mahilewets 28 июл 2017 20:45
For any test,  the probability to answer correctly is:

the probability that the test is  the first test and the answer on that test is "yes"
plus
the probability that the answer is on that test is "yes" and the answer on the previous test is also "yes"
plus
the probability that the answer on that test is "no"  and the answer on previous test is also "no"

That is:
p=(1/n) *yes/n + (yes/n)*((yes-1)/n) + (no/n)*((no-1)/n)

The probability to fail the test is:

q=1-p

There are n tests,  so the expected count is:
ans=n*q=n-(yes*yes+no*(no-1))/n
Re: O(1) Formula
Послано Jerrywang 16 окт 2022 18:18
This is so clear. Thank you.