Show all threads Hide all threads Show all messages Hide all messages |
O(1) Formula | Sereja Slotin | 1716. Alternative Solution | 16 Oct 2022 18:18 | 4 |
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. 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)*((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 This is so clear. Thank you. |
It's really better to think ten times before writing a solution... | messir | 1716. Alternative Solution | 16 Oct 2022 17:40 | 2 |
Yes, that is. It must be true. This is also a good manner. |
Problem for Copying (Markdown) | remmymilkyway | 1716. Alternative Solution | 15 Oct 2022 12:35 | 3 |
# Alternative Solution Valentine is a veteran of programming contests and he's been working in the program committee for many years. He is very busy this week: the bike is under repair, some problems with Indian colleagues have to be solved, and five student groups are to be examined in philosophical problems of mathematics at the university. To crown it all, the new chairman of the program committee asked Valentine to write an alternative solution for one of the problems of the forthcoming contest. Valentine was so busy that he had no time to read the problem statement. He only glanced at the output format and understood that it was required to output either `YES`, or `NO`. Fortunately, Valentine was well acquainted with the testing system used in the contest. The system successively runs a solution on all tests of a problem, and for each test the checking process goes as follows. The input is copied to the file input.txt. Then the solution is launched. It reads the input from the file input.txt and writes the result to the file output.txt. When it finishes, the correct answer is copied to the file answer.txt. If the contents of the files answer.txt and output.txt match, the test is assumed to be passed; otherwise, the test is not passed. Valentine decided to write a program that would operate as follows. If the folder containing the program doesn't contain the file answer.txt (i.e. the program is run on the first test), then the program outputs `YES`. Otherwise, the program outputs the contents of the file answer.txt. Valentine plans to tell the chairman of the program committee that there is a nontrivial mistake in his program, and this mistake, fortunately, shows itself when the program is run on the excellent hard tests prepared by the author of the problem. However, first Valentine has to estimate the number of tests that his solution won't pass. Valentine doesn't have access to the tests, but he knows the number of tests and the total size of the files with answers. He also knows that the size of the file with the answer `YES` is 3 bytes, the size of the file with the answer `NO` is $2$ bytes, and all the variants of the order of tests are equally probable. Help Valentine to calculate the average number of tests that his solution won't pass. ## Input The only line contains two integers $n$ and $s$ ($1 \le n \le 5000$; $2n \le s \le 3n$) which are the number of tests and the total size of the files with answers, respectively. The numbers are separated with a space. ## Output Output the average number of tests that Valentine's solution won't pass, accurate to $10^{-5}$. ## Sample ### input ``` 3 7 ``` ### output ``` 2.0000000 ``` |
A simple solution | dannyneptune | 1716. Alternative Solution | 15 Oct 2022 12:34 | 7 |
Let a=s-2n,b=3n-s. Then the answer is (2ab+b)/n. Try it, you won't regret it! I saw no one comment, so I would comment myself. This is so marvelous an editorial. A thousand thanks to the author(me)! :-) Still no one commenting, I guess I'm not a celebrety. :-( Can I get 50 comments? Yes, if I do this forever. You should write it in markdown: Let $a = s - 2n$, $b = 3n - s$. Then the answer is $\frac{2ab+b}{n}$. Try it, you won't regret it! Try it, you won't regret it! Edited by author 15.10.2022 12:35 A million thanks to remmymilkyway, the first person other than me to comment!!!!!!!!!!!!1 |
O(1)solution | hyman00 | 1716. Alternative Solution | 15 Oct 2022 12:23 | 1 |
|
O(1) | zwqzwq | 1716. Alternative Solution | 23 Aug 2021 08:52 | 1 |
O(1) zwqzwq 23 Aug 2021 08:52 a is the number of NO ; b is the number of YES ans=a/n+(n-1)*(a/n)*(b/(n-1))+(n-1)*(b/n)*(a/(n-1)) =a/n+2ab/n =a*(1+2b)/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 “YES-NO-NO”, then Valentine's solution won't pass the second test only; if the order is “NO-YES-NO”, then it will pass none of the tests; if the order is “NO-NO-YES”, 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. |