Disclaimer: The content might only be beneficial for people with rating less than 1600
Today, I want to share with you a very cool thing I learned in Problem C in the last Div.3 contest.
Prerequisite: Please read the problem if you haven't already.
I prepared a 13 minutes video on youtube to show you what I learned, and hopefully you will learn something too.
Enjoy the video!
The probability of the algorithm generating a correct permutation is the same as the number of derangements of length n divided by the number of permutations of length n in the worst case (all zeros).
When n tends to infinity, this probability is 1/e (see Wikipedia page liked above for details). Which means that the expected number of tries is e. Now our n is at most 2*10^5 and not infinity, but even then, the probability is very close to 1/e.
From this we can conclude that the algorithm has an expected complexity O(e*n) or O(n) since e is a constant.
Also, using random_shuffle on codeforces to shuffle an array of size greater than 2^15 (32768) can lead to getting wrong answer or getting hacked, instead you should use shuffle() and your custom random function. Read more about it here.
Thanks for the valuable information. I actually didn't know the complexity of this thing. Now it is clear. I genuinely thank you for sharing this
What's up with all the code above the main function? I'm a beginner so that really confused me, is it necessary for the solution of this problem?
It is absolutely not necessary for the solution, I use that code for debugging purposes.