Resul's blog

OMG is it possible ?!
By Resul, 10 years ago, In English

Why this solution got AC ?! I couldn't understand. Can someone hack this solution ?!

  • Vote: I like it
  • +39
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a totally normal solution

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

During the contest I wanted to do this and I wrote the solution but I was afraid to submit it :D

I think that nobody can hack a randomized solution purposely.

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +65 Vote: I do not like it

In fact rand() % n must be less than 32767, because codeforces is in WINDOWS. And the solution does this 3000000 times, the probability that [0,32767) is perfectly covered is very high, according to the editorial, either of the number of two candies will be less than , also less than 32767, therefore the solution is correct and cannot be hacked.

(2016.09.08 updated — now rand() in win10 will yield numbers in [0, 2^31)).

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Perfect solution XD

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

tohdon has already explained what's going here, I'll add that when you are using proper random generator such as mt19937, this solution fails on third test with TL (original 10606822) or WA (10606853, number of attempts divided by 4).

→ Reply