How could I decrease my execution time (PERMUT2)

general
, ,
1

This is my solution: https://www.codechef.com/viewsolution/15889681

I am getting TLE as my code takes about 19 sec to execute. Could someone suggest me, on how could I optimize my approach (or the code) so as to make it fit in 10 sec ??

Thanks a lot! :slight_smile:

2

The problem here is that your are executing if(array[k]==j){inverse[j-1]=k+1;}repeatedly which is not needed here. You just check it once and if it is true then break it like this if(array[k]==j){inverse[j-1]=k+1;break;}.
Think that there is only one element in array which will be same as j in inner for loop at a time so why check for all. So just execute inner for loop till ‘if’ becomes true and add break statement there as i explained above.

1 Like
3

It can be done in a single iteration as well. After all, all you have to check is that the value at index i is the index of value i. OR in other words-

for(i=1;i<=n;i++)
	    {
	        if(arr[arr[i]]!=i)
	        {
	            flag=1;
	            break;
	        }
	    }
	    if(flag==1)
	       cout<<"not ambiguous"<<endl;
	   else
	        cout<<"ambiguous"<<endl;

You need to do away with that nested loop of yours, its taking a lot of time in useless operations. Try solving using a single for loop. :slight_smile:

1 Like
4

Yes @arnavvarshney this can be done in O(n) just as @vijju123 has explained

1 Like
5

You were getting tle as you were doing it in O(n*n)

1 Like