Do you know that the quicksort you use in cpp is also random?
Having such a disgusting attitude towards learning, I will genuinely not be surprised if you get stuck with this rating ladder for a long long time.
PS: Go fuck yourself.
Do you know that the quicksort you use in cpp is also random?
Having such a disgusting attitude towards learning, I will genuinely not be surprised if you get stuck with this rating ladder for a long long time.
PS: Go fuck yourself.
jajajaja ⌠come on man, donât be so angry! According to your Rating Chart, on average, you are getting better, so there is a chance that you are learning something from one contest to another and perhaps randomness (or paying attention to statements) was the subject of this.
Most of them are but not all.
Lost the bet. Party?
Bro I also felt really annoyed when I couldnât mathematically prove that we could get 100% correct answer even though there were so many ACs on thisâŚ
I really didnât think questions like these were asked in CP contests âŚ
I wasnât expecting to see 70pts when I submitted a (seemingly stupid & unproved ) solnâŚXDâŚand then 100ptsâŚI am glad I didnât give up XD XD
Yes but only the time complexity will vary based on randomness, but the final array will always be 100% correctly sorted.
But in this LAZERTST , there was a really really really small chance of getting wrong answerâŚbdw do you know how the setter generated truly random numbers (not pseudo random numbers)???
I saw him tossing an unbiased coin multiple times before few days.
I think he was generating a binary number with 30 bits for making subtask 2. I am not sure about how he handled cases when number exceeds 10^9.
The final answer in this question can be deterministic as well. If we find that answer to our query is smaller than m/2, then we can ask few more queries to find correct answer.
Maybe check m/4 and 3m/4 and proceed further if required.
The number of queries required will still be 10 with very high probability.
The answer will still be 100% correct.
I donât think so. If you tried printing a random Y instead of M/2, you would receive WA.
The constraints were decided in such a manner that random solution passes with probability of around 1e-4(I was worried to be honest that if it received many random solutions some would pass), and correct solution fails with a probability around 1e-5.
I think probability of failing was much more lesser than that.
29AeWp - Online C++0x Compiler & Debugging Tool - Ideone.com
I have made this code to generate 10^6 random 100 size arrays and it passes all of them.
Doesnât that mean that probability should be less than 10^{-5}
Are you sure ?
Edit : I have tried it running it 10^8 times. Still it passes all of them. Is probability 0 ? XD
I have used testlib for generating random numbers.
I donât really remember the exact number, also you should consider the number of queries(100).
Also since the test cases were generated only once, so y=M/2 cannot ever fail(so I guess we can ignore 1e-5 and all )
Probability that difference between two randomly generated numbers b/w 1 to M is less than (M+1)/2 is
\sum_{i=0}^{(M-1)/2} (M-i) = 1/8*(1 + M)*(1 + 3*M)
P = 2*1/8*(1+1/M)*(3+1/M)
Putting M=10^9 , P =2* 0.375.
I am not sure if actual probability is P^{100} but it is at most P^{50}.
P^{50} = 5*10^{-7}
Let me know if I am missing anything.
a really really really small chance of getting wrong answer
I mean getting wrong answer with correct solution
correct solution fails with a probability around 1e-5.
Yes, I was referring to thisâŚ
Then you clearly never solved these type of problems before.
ahem ahem. Contradiction - 100
@infinitepro Once I post this type of normal ill word in my comment and I feel it is not good so I deleted my comment. But someone post my deleted history and @admin suspend me for oneday.
My post was like this:
I think you are not worth of it. so you maybe thats why you got WA.
You should focus on problem solving more Too much activity on discuss will not help you
And you should stop possessing multiple IDs before I ban your main account .
Seriously, this multiple account thing is getting out of hand and we will be taking strict action against it.
@tor_baap Thanks for the advice. I will try. Acually, you know as student of class 11 and as victim of Bangladesh education system It is so difficult to me. I love programming but my brother always said Stop it until you get chance in a good university like BUET. I think he is right. I should listen it.