Doubt in Randomised algorithm solution for problem E of Codeforces Round 935 (Div 3).

Revision en2, by copyPasteCoder, 2024-03-21 02:00:05

This problem as E problem for the contest. For this problem, while going through comments I found ankan2526 has a alternative and easy solution by randomly picking an index, swapping it with index of x and checking if this swap is an answer. But I didn't understand why will this algorithm halt or even give an AC in 2s. I applied the same concept but got a TLE. My submission.

Please tell where I got wrong, and how this submission works perfectly fine. Also, please comment any good links for learning the complexity analysis of such algorithms.

Tags doubt, #random, #constructive algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English copyPasteCoder 2024-03-21 08:11:46 72
en4 English copyPasteCoder 2024-03-21 02:01:34 34
en3 English copyPasteCoder 2024-03-21 02:01:02 12 Tiny change: 'This [problem](https://' -> 'This was the [Problem E](https://'
en2 English copyPasteCoder 2024-03-21 02:00:05 68
en1 English copyPasteCoder 2024-03-21 01:55:45 972 Initial revision (published)