Please help with PERMUT2(Ambiguous permutations)

help
,
1

How do I optimize my code?

It’s giving TLE.

Here’s my solution:
https://www.codechef.com/viewsolution/13888032

2

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.

3

Trying to approach problem in a little mathematical way.

Let for a given Permutation P, InversePermutation(P) is InvP

Condition on inverse Permutation

  • P [ InvP [ i ] ] = i

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)

Source

4

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

5

By bottle neck do you mean “that condition led to TLE” or “that solution led to AC, but wasted some time”??

1 Like
6

It’s just that it wasn’t needed. :slight_smile:

And definitely it led to using up of more time because there seem no other way for that TLE verdict.

1 Like
7

Thanks. The math approach helped me to visualize the problem in a unique way!

8

Thanks. :slight_smile:

1 Like