ambiguous permutation

general
1

import java.io.*;
import java.util.Scanner;

public class test {

    public int search(int i,String a[])
    {
        
       for(int j=0;j<a.length;j++)
       {
           
           if(Integer.parseInt(a[j])==i)
           {
               
               return j+1;
           }
           
       }
        return 0;
    }
    public static void main(String[] args)throws IOException {
    
        int count=1;
        test ob = new test();
        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        
        while(true)
        {
            
            if(Integer.parseInt(br.readLine()) ==0)
            {
                break;
            }
            String str = br.readLine();
            String a[] =  str.split(" ");
         
         for(int i=0;i<a.length;i++)   
         {
             
             if(Integer.parseInt(a[i])==ob.search(i+1, a))
             {
                 count=1;
                 continue;
                 
             }
             count=0;
         }
         
         if(count==1)
         {
             System.out.println("ambiguous");
         }
         else
         {
             System.out.println("not ambiguous");
         }
            
        }
        
    }
}

its exceeding time limit :frowning:

i dont understand… plz help

2

Your logic is O(n^2) , try to optimize it further. In 10 seconds the cluster used by codechef can hardly perform these many operations.

  • Here’s a simple logic :

     while(1)
 {
     scanf("%d",&n);
     bool flag=true;
     for(int i=1; i<=n; i++)   scanf("%d",&a[i]);
     for(int i=1; i<=n; i++)
     {
         if(a[a[i]]!=i)
         {
             flag=false;
             break;
         }
     }
     if(flag)  printf("ambiguous\n");
     else printf("not ambiguous\n");
 }
4 Likes
3

import java.io.*;
import java.util.Scanner;

 class test1 {


    public static void main(String[] args)throws IOException {
    
        int count=1;

        BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
        
        while(true)
        {
            
            if(Integer.parseInt(br.readLine()) ==0)
            {
                break;
            }
            String str = br.readLine();
            String a[] =  str.split(" ");
         
         for(int i=0;i<a.length;i++)   
         {
             
          
             
        if(Integer.parseInt(a[Integer.parseInt(a[i])-1])==i+1)
        {
            count=1;
        }
             else
        {
            count=0;
        }
             
         }
         
         if(count==1)
         {
             System.out.println("ambiguous");
         }
         else
         {
             System.out.println("not ambiguous");
         }
            
        }
        
    }
}

i did but getting wrong ans ???

4

this is your AC code…LINK…you missed a break statement after setting count=0!!!

2 Likes