How do I optimize my code?
It’s giving TLE.
Here’s my solution:
https://www.codechef.com/viewsolution/13888032
How do I optimize my code?
It’s giving TLE.
Here’s my solution:
https://www.codechef.com/viewsolution/13888032
Create a separate array.Say f and set a counter variable starting from 1.While traversing the whole array note that f((a(i)))=counter.Every iteration you increment the value of the counter and at last check the both array.If they are same i.e. ambiguous otherwise not ambiguous.
Trying to approach problem in a little mathematical way.
Let for a given Permutation P, InversePermutation(P) is InvP
Condition on inverse Permutation
P is ambiguous
Iff P == InvP
or P[i] == InvP[i] , for all i
Applying P on both side
P[P[i]] == P[InvP[i]] , for all i
or P[P[i]] == i , for all i. (from Condition of Inverse Function)
Just check if
P[P[i]] == i , for all i. (from Condition of Inverse Permutation)
A few things which were unnecessary, you didn’t have to use 2 arrays a and p, just a single array was all needed. Also There was no need to compare both the arrays completely at the end (this was also a bottleneck of your solution)
I just modified your code a bit.
Here’s the working code : https://www.codechef.com/viewsolution/13891453
By bottle neck do you mean “that condition led to TLE” or “that solution led to AC, but wasted some time”??
It’s just that it wasn’t needed.
And definitely it led to using up of more time because there seem no other way for that TLE verdict.
Thanks. The math approach helped me to visualize the problem in a unique way!
Thanks.