ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1716. Alternative Solution

O(1) Formula
Posted by Sereja Slotin 19 Oct 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
Posted by Felix_Mate 21 Jun 2017 15:06
Why this formula is right? I solved problem by DP, but i can't prove this formula.
Re: O(1) Formula
Posted by Mahilewets 28 Jul 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
Posted by Jerrywang 16 Oct 2022 18:18
This is so clear. Thank you.