Show all threads Hide all threads Show all messages Hide all messages 
O(1) Formula  Sereja Slotin  1716. Alternative Solution  28 Jul 2017 20:45  3 
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*(yes1) + no*(no1))/n, where yes = s2*n and no = nyes 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. Why this formula is right? I solved problem by DP, but i can't prove this formula. 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)*((yes1)/n) + (no/n)*((no1)/n) The probability to fail the test is: q=1p There are n tests, so the expected count is: ans=n*q=n(yes*yes+no*(no1))/n 
wa 13  LastOne  1716. Alternative Solution  20 Jun 2017 22:59  2 
wa 13 LastOne 13 Jun 2017 00:51 You can try use these tests: 4999 12832 >2455.1680336 5000 12345 >2490.9210000 4987 9999 >50.7443353 1234 3456 >394.1183144 2976 6547 >952.8800403 3487 8000 >1448.9340407 4955 11111 >1820.5574168 456 968 >99.1228070 43 123 >10.4651163 1 2 >1 4 9 >2.2500000 3 9 >0 2 5 >1.5 2 4 >1 4399 13013 >352.6492385 4321 9923 >1803.1751909 4001 10500 >1877.1534616 4000 10001 >2000.4992500 4000 10000 >2000.5000000 4123 9999 >2015.9083192 
hint  Briana Banks  1716. Alternative Solution  9 Dec 2014 20:45  1 
hint Briana Banks 9 Dec 2014 20:45 i've been thinking at this problem for 2 weeks. can somebody give me a hint ? 
wa 11  Zhang Ye  1716. Alternative Solution  10 Aug 2014 19:50  4 
wa 11 Zhang Ye 27 Oct 2012 13:36 always wa at test 11,why? I can't figure out what the hint about! Why “If the order of tests is “YESNONO”, then Valentine's solution won't pass the second test only; if the order is “NOYESNO”, then it will pass none of the tests; if the order is “NONOYES”, the solution won't pass the first and the third tests.” Can you give me more detailed explanation？ Re: wa 11 IgorKoval [PskovSU] 6 Sep 2013 20:53 This is test #11: 5000 12500 Who have answer? Edited by author 06.09.2013 20:53 The answer for that is 2500.50 
Can anybody interpret the promblem for me? thx  ppchain  1716. Alternative Solution  13 Feb 2013 18:08  2 
The "YES" come from two ways:1) when there is not have answer.txt;2) when answer.txt contain it.but i can't figure out this related to pass test! pass test should be the output.txt's content is same to answer.txt. how to explain the hint's explanation? We answer "YES" if "YES" was right answer for previous test. 
I do not know how to solve it in C++.  Martin  1716. Alternative Solution  13 Feb 2013 18:06  3 
No matter when I used double or long double, my code still got TLE. Opt[Now][j][0] = Opt[Pre][j][0] + Opt[Pre][j][1] + Opt[Pre][j][3]; Opt[Now][j][1] = Opt[Pre][j  1][0] + Opt[Pre][j  1][2] + Opt[Pre][j  1][1]; Opt[Now][j][2] = Opt[Pre][j][2] + Opt[Pre][j][3]; Opt[Now][j][3] = Opt[Pre][j  1][2] + Opt[Pre][j  1][3]; I had to write a Pascal code using extended and got AC. Could anyone tell me how to AC in C++? I know solution which can be written on all allowable languages. I suppose, this solution won't get TLE. Becouse it is O(1). I know solution which can be written on all allowable languages. I suppose, this solution won't get TLE. Becouse it is O(1). 
Unexpected helphull problem  svr  1716. Alternative Solution  30 Aug 2010 12:34  6 
During 3 days I couldn’t find appropriate way to work with big binomials having lost of order or overflow. Simple and clever routine was found and gave satisfaction. Could you give any hint: what kind of "simple routine" have you found? I also have got overflow / lost of order? Is it possible to avoid such problem in O(N^2) solution? I don't know what your algo is, but my dynamic O(N^2) solution hasn't problems with overflows  all numbers is of order N Thanks! I've got AC with O(N^2) DP. Every value was not exceeding N. But it's still interesting  how did some people get AC with 0.015sec and minimum of memory. 
It's really better to think ten times before writing a solution...  messir  1716. Alternative Solution  26 Aug 2010 18:28  1 
