This was the Problem E for Codeforces Round 935. 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.
My idea:
Case 1: During binary search, let's say we visited mid1, mid2, mid3,..., midk. If index of x was not visited, then we can just swap x with final midk. This will require 1 operation and we are done (Actually it is true even if x was visited during binary search. This is how most of the people done).
Case 2: For the case where x was visited during binary search, I did a random swap (which costs 1 operation) and checked if the modified array can be solved in 1 more operation using Case 1. If yes, then I printed those 2 operations. Else I reverted back the random swap operation and continued this process.
Since we can visit at max log(n) mids in binary search. The probability of x being present in the visited mids is log(n).
A major difference in the two submissions that you gave is that the python code(252244930) restricts the random number generator to n, whereas the c++ code(252514656) does not. For an ideal random number generator, this wouldn't be an issue as random number generation should be an iid event, and both could potentially fail given enough runs. But both python and c++ use pseudo random number generation algorithms, so the range of generation can become a factor.
If you remove the random number from the solution idea, your code would work. You could simply iterate through the array and check if the BS algo works when x is swapped with a given index, tested here: 252544567