CodeChef March Long 2020

99

lol XD…no seriously…how did you create the test data??? @vivek_1998299

1 Like
100

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.

101

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.

102

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.

103

:thinking:

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 :blush:)

2 Likes
104

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.

105 
 a really really really small chance of getting wrong answer

I mean getting wrong answer with correct solution :sweat_smile:

correct solution fails with a probability around 1e-5.

Yes, I was referring to this…

106

Then you clearly never solved these type of problems before.

107

ahem ahem. Contradiction - 100
:stuck_out_tongue:

4 Likes
108

@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.
109

You should focus on problem solving more :slightly_smiling_face: Too much activity on discuss will not help you :slightly_smiling_face:

2 Likes
110

And you should stop possessing multiple IDs before I ban your main account :slight_smile: .

Seriously, this multiple account thing is getting out of hand and we will be taking strict action against it.

5 Likes
111

@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.

112

@vijju123 Sir, Did you tell this to me or @infinitepro or @tor_baap ?

113

Definitely NOT me.
Or wait! Does he know?!.. XD

114

I think he told this to @tor_baap, because he told it as reply of @tor_baap.

115

Bro I think you sholud listen to your brother.Getting a good college is absolute necessity in country like India,Bangladesh,China.

3 Likes
117

can anyone tell me what’s wrong with my solution for ENGXOR
[CodeChef: Practical coding for everyone]

118

You have not added the fast input - output method. Maybe that can be the reason for the TLE in the 2nd Sub - Task of your code. Try adding -
ios_base::sync_with_stdio(false);cin.tie(NULL);

1 Like
119

Thanks :grinning:
It worked.