Ambiguous Permutations

when i press submit button its giving

the requested page could not be found......

whats wrong???

when i press submit button its giving

the requested page could not be found......

whats wrong???

the submit page is stilll not found

anshuman, don't worry about that error.  It doesn't acutally affect your submission.

it seems like no one got any problem with this problem...but i can't get the problem.

can someone pls explain what these different permutations actually are?

The statement itself explains pretty clearly.. what line don't you understand exactly?

how are the ambiguous permutation and the inverse permutation similar?

i know i'll feel stupid after reading the reply.

You mean this line from above?

You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility an inverse permutation.

can you give an example showing a permutation ,its inverse permutation and an ambiguous permutation similar to that?

a different example from one given above pls.

someone?

Original permutation = 1 3 2 4

It's inverse permutation is 1 3 2 4 and so it is ambiguous.

If Original permutation was 1 4 2 3, its inverse would be 1 3 4 2 and it would be non ambiguous.

The sample input and output arnt clear.......if possible someone can help me out.

hello all,

plz help me.m gttng right answer on my computer.But when I submit it says wrong answer.

Heres my code

#include<iostream>
using namespace std;

int main()
{
int n,i=0,flag=0;
cin>>n;
if(n!=0)
{
int *A=new int(n+1);
int *B=new int(n+1);
for(i=1;i<=n;i++)
{
cin>>A[i];
}
for(i=1;i<=n;i++)
B[A[i]]=i;
for(i=1;i<=n;i++)
if(A[i]!=B[i])
{
flag=1;
break;
}
if(flag==1)
cout<<"not ambiguousn";
else
cout<<"ambiguousn";
}
return 0;
}

i hv checked my code with the condition"There is exactly one space character between consecutive integers.". bt still gttng wrong answer.

plz help

my code is working properly on comp.. but m getting runtime error here.. can anyone help me out plz.

You are declaring far too much memory (200000 longs) on the stack. Use heap memory instead (ie declare them globally).

I have applied all sort of algorithm for execution efficiency.! Still its shows 'time limit exceeded'

whats wrong with my code?[python]

def qsort(L):
if L == []: return []
return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + qsort([x for x in L[1:] if x>=L[0]])

n=input()
arr=[]
for i in range(n):
arr.append(input())
arr=qsort(arr)
for i in arr:
print i

got it!!!!!!!

what is wrong with sample input 2inputs and 3 outputs

Nothing is wrong with the sample input. There are 3 inputs.

hey dude what is the flaw in this code?

plzz let me know...

#include<iostream>
using namespace std;
int y;
int a[100001][100001];
int b[100001][100001];
void algo(int a[][100001],int y){
int count =0;
for(int i=1;i<a[y][0];i++){
if(a[y][i]!=b[y][i]){
count =-1;
break;
}}
if(count==-1){
cout<<"not ambiguous"<<endl;
}
else{
cout<<"ambiguous"<<endl;
}
}
int main()
{

int z;
y=0;
while(cin>>z && z!=0){
a[y][0]=z;
int t;       
for(int i=1;i<=z;i++){
cin>>t;
a[y][i]=t;
b[y][t]=i;

}
y++;
}
for(int i=0;i<y;i++){
algo(a,i);
}
// system("pause");
return 0;
}

@prashant

You have declared too big arrays and moreover int z cannot store 10^5.

i am getting run time error while the code runs fine on my system....

how can i get where's the error??

how to declare large long int arrays that can hold integers prescribed in the problem....

please help!!!!

I have declared array containing the permutation like this

long int *A=new long int(100005);

GLOBALLY.

and am appending a string with the appropriate strings after checking for the required condition.

what could be the problem?

That isn't an array at all. Did you mean to use square brackets, ie [100005]?

Also, you really shouldn't be using cin/cout or waiting until the very end to output results. See the FAQ.

i meant to say that this is how i declare the storage for the permutation. Is this okay?? as this can be used as an array i misnamed it as array. I could not understand what do u mean by " you really shouldn't be using cin/cout or waiting until the very end to output results". can u please where in FAQ you wanted me to direct?

Just print out each result as you process it, rather than adding it to a string and waiting until the very end.

And no, that is not a correct way of declaring memory as I mentioned.

I have tried my program on my computer with a certain number of test cases and its working fine. But here it says wrong answer. Here is my code:

//PERMUT2

#include<stdio.h>

#include<stdlib.h>

#define SIZE 65536

int main()

{

unsigned int i, num[SIZE], t, test;

scanf("%d", &t);

for(i=0;i<t;i++)

{

scanf("%d", &num[i]);

}

for(i=0;i<t;i++)

{

if(num[i]==i+1)

test=1;

else test=0;

}

if(test)

printf("ambiguousn");

else printf("not ambiguousn");

return 0;

}

What made you choose the number 65536? Read the problem statemenr.

the code is working fine with my laptop but not here..can any body help me to figure out the problem plzzzzz

#include<iostream>
using namespace std;

int main()
{
int n;
int cntr=0;
cin>>n;
int a[n+1],b[n+1],c[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[j]==i){
c[i]=b[j];
}
}
}

for(int i=1;i<=n;i++){
if(c[i]==a[i]){cntr++;}
}
cout<<endl;
if(n!=0){
if(cntr==n){cout<<"ambiguous";}
else{cout<<"not ambiguous";}
}
return 0;
}

@sukhmeet

u consider only one input case at a time but there r several input case at a time.. u need to take input till value of n is not equal to zero...

read input/output format given in question again..

thanks devendra,

really bad eye of me. but now it says Time limit exceeded. I think rather than going for n^2 complexity I should try something faster.What say !!! let c... thnaks again btw

getting wrong answer for this code which seem to work fine with my inputs. Please suggest a case where it dosen't.

#include<stdio.h>

#define no_of_tests 100

int main(){

long unsigned int a=0,b=0,c=0,index=1,num=0;

char arr[no_of_tests],str[10];

int i,count=0;

while(1)

{

gets(str);

if(str[0]=='')

continue;

for(i=0;str[i]!='';i++)

c=10*c+(str[i]-'0');

if(c==0)

break;

for(i=1;i<=c;i++)

{

a=0;

while(fread(str,1,1,stdin))

{

if(str[0]=='1'||str[0]=='2'||str[0]=='3'||str[0]=='4'||str[0]=='5'||str[0]=='6'||str[0]=='7'||str[0]=='8'||str[0]=='9'||str[0]=='0')

a=10*a+(str[0]-'0');

else

break;

}

if(index>a)

{

b=b^index;

num=num^a;

}

else if(a>index)

{

b=b^a;

num=num^index;

}

index++;

}

if(b==0&&num==0)

arr[count]='a';

else

arr[count]='u';

b=0;

num=0 ;

index=1;

count++;

c=0;

}

for(i=0;i<count;i++)

{

if(arr[i]=='u')

printf("not ambiguousn");

else

printf("ambiguousn");

}

return 0;

}

Dear Admin

My program is working properly. I satsified all the limititing conditions as well. But still when i am submitting it, it is showing wrong. I couldn't find where the problem is can you please help me out.

^ Did you test your program on the sample input (the complete sample input) ?? Is the output from your program 'exactly' like its supposed to be ?

yes i checked for the complete sample input, the output is exactly like its supposed to be

Are you sure ?? ... output for each test case is on a new line, your program does that ?

yes

@Admin - Same problem - Correct on sample input, but says wrong answer.. I've declared all variables as long int in C++.. All outputs are on new line; please let me know where I have gone wrong.. BTW my complexity is n and not n^2 ! :-) ..

Your code gives the wrong answer on the majority of inputs; it was lucky to pass the sample input.  Giving you a test case would make things far too easy, but note that in order to be ambiguous the inverse permutation must have every element identical to the initial permutation.

Oh thanks Stephen, got it running..

@Stephen-my solution times out...

http://www.codechef.com/viewsolution/283745

any hints..plz.. ?

n can be up to 100000. Two nested loops up to 100000 has no chance of running in time. I'm afraid you'll have to think of a completely new idea.

@Stephen-

yup..i got AC finally..the problem was exactly what you pointed out..i managed to put it in one loop..

thnx :)

#include<stdio.h>

#define MAX 100001

#include<ctype.h>

int str_len,str_len2;

char temp[MAX];

char arr[MAX];

int len = 1;

int var,var2;

int value;

int main(void)

{

temp[0]= ' ';

while( len > 0 && len <= 100000)

{

int i=1;

int flag=1;

scanf("%d",&len);

if(len == 0)

break;

fflush(stdin);

fgets(arr,MAX,stdin);

str_len = strlen(arr);

for(var = 0; var<str_len-1; var++)

{

if(!(isspace(arr[var])))

{

temp[i]=arr[var];

i++;

}

}

str_len2 = strlen(temp);

for(var2 = 1; var2 < str_len2; var2++)

{

value = (temp[var2]-48);

if((temp[value]-48) != var2)

flag = 0;

}

if(flag)

printf("ambiguousn");

else

printf("not ambiguousn");

}

return 0;

}

Can someone plz simplify thils question. How do we get inverse permutations?

I am getting Runtime Error..Please Someone HELP!!

@Vidura Yashan: Maybe you can read this article http://mathworld.wolfram.com/InversePermutation.html

this program is providing the expected output as given according to sample input and question logic,but i am getting always wrong answer response.If it is wrong then please provide the specific error description.

#include<stdio.h>

#include<malloc.h>

int main()

{

unsigned long n,*in,*inv,i;

int flag;

do

{

flag=1;

scanf("%lu",&n);

in=(unsigned long *)malloc(sizeof(unsigned long)*n);

inv=(unsigned long *)malloc(sizeof(unsigned long)*n);

for(i=0;i<n;i++)

{

scanf("%lu",&in[i]);

if(in[i]>n)

i--;

}

for(i=0;i<n;i++)

inv[in[i]-1]=i+1;

for(i=0;i<n;i++)

if(in[i]!=inv[i])

{ flag=0;

break;

}

if(flag==0)

printf("not ambiguous");

else if(flag==1&&n!=0)

printf("ambiguous");

free(in);

free(inv);

}while(n!=0);

return 0;

}

It doesn't even give the right answer for the sample input. Read the FAQ if you do not know how to test your code properly.

is out of memory a compile error???

#include<iostream>

using namespace std;

int main()

{ unsigned int num[100000], per[100000];

float n;

while(1)

{ cin>>n;

if(n==0)

break;

for(float i=;i<n;++i)

cin>>num[i];

for(i=0;i<n;++i)

per[num[i]]=i;

int flag=0;

for(i=0;i<n;++i)

if(num[i]!=per[i])

flag=1;

if(flag==0)

cout<<"ambiguous"<<endl;

else

cout<<"not ambiguous"<<endl;

}

return 0;

}

will some1 please point out compile errror in my code!!!

Anyone please explain me what is the meaning of

"internal error in the system "...

my code is running correctly on my PC....

what does this mean??? am confused!!

Is there anything special that should be kept in mind for this problem? it seems preetty straightforward for me but can`t seem to find where my code could fail.

Thx,

SB.

There's nothing special in the problem. Your method of reading an integer then trying to store it in a char seems pretty special to me though :)

@ Stephan: Can you figure out where am I going wrong? Here's the code...

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n;

String currentLine = null;

while (in.hasNext()) {

n = in.nextInt();

if (n == 0) {

System.exit(0);

} else {

int[] a = new int[n+1];

for (int i=1; i<=n; i++){

a[i] = in.nextInt();

}

if (isAmbiguous(n, a))

System.out.println("ambiguous");

else

System.out.println("not ambiguous");

}

}

}

public static boolean isAmbiguous(int n, int[] a){

boolean answer = false;

if(n == 1){

if(a[1] != 1)

answer = true;

}

else if(n == 2){

if (! (a[1] == 1 && a[2] == 2))

if (! (a[1] == 2 && a[2] == 1))

answer = true;

}

else if(a[1] == 1 || a[n] == n)

answer = true;

else if (a[1] == n){

for(int l = 2; l <= n; l++){

if(a[l] != (l - 1)){

answer = true;

break;

}

}

}

else if (a[n] == n-1){

for(int m=2; m<=n; m++){

if(a[m] != (m+1)){

answer = true;

break;

}

}

}

else

answer = true;

return answer;

}

}

I'm a bit confused about the question. Do the original permutations have to be ordered (ie 2 has to have 1 and 3 on either side of it)? In other words, can there be input permutations like 1,5,2,4,3 or not?

The problem defines a permutation as any ordering of the numbers 1 to N. Not just a few of them.

I'm still confused. Can 1,5,2,4,3 be a potential permutation? From the examples it seems like it cannot but I just want to double check

Yes, it can. There is nothing in the examples that says it cannot or puts any restriction on what permutations are allowed.

#include<stdio.h>

int main()

{

long int a[100000],n,i;

while(1)

{

scanf("%ld",&n);

if(n==0)

break;

for(i=0;i<n;i++)

{

scanf("%ld",&a[i]);

}

for(i=0;i<n;i++)

{

if(i+1!=a[a[i]-1])

break;

}

if(i==n)

printf("Ambiguousn");

else

printf("Not Ambiguousn");

}

return 0;

}

If it were correct, it wouldn't say wrong answer. It says wrong answer, therefore it is incorrect. (In fact, it even fails on the sample input).

I got Error ..... :)

very lame part of me !

@ admin ...i get the right answer on my pic but get a wrong answer on code chef ..please check

why those are not working?

http://www.codechef.com/viewsolution/431575

http://www.codechef.com/viewsolution/431319 

@admin I couldn't get the problem.

"You create a list of numbers where the i-th number is the position of the integer i in the permutation." What does it mean and how did you create 5 1 2 3 4 from 2 3 4 5 1 ?

@ stephen

@admin    m getting wrong answer   please help
#include<stdio.h>

int a[100001];
int main()
{
int t,i;
int n,c=0;
scanf("%d",&t);
while(t>0)
{
scanf("%d",&n);
if(n==0)
break;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
{
if(i==a[a[i]]||a[i]==i)
c++;
}

if(c==n)
printf("ambiguous");
else
printf("not ambiguous");
t--;
c=0;
}

return 0;
}

@admin

see the following soln has been submitted successfully

1. #include <stdio.h>
2. main()
3. {
4.       int n,i,j;
5.       while(1)
6.    {  
7.       scanf("%d",&n);
8.       if(n==0) exit(0);
9.       if(n>=1&&n<=100000)
10.       {
11.         int a[n],b[n];
12.         for(i=1;i<=n;i++)
13.         {
14.           scanf("%d",&a[i]);
15.         }
16.         for(i=1;i<=n;i++)
17.         {
18.           b[a[i]]=i;
19.         }
20.         for(i=1;i<=n;i++)
21.         {
22.           if(a[i]!=b[i])
23.           break;
24.           else
25.           continue;
26.         }
27.         if(i==n+1)
28.         printf("ambiguousn");
29.         else
30.         printf("not ambiguousn");
31.       }
32.    }
33. }

but mine with almost same logic is wrong..(in c++)

#include<iostream>

using namespace std;

main()
 {
   int n;
  int flag;
  
 
 
  while(n!=0)
   {
    cin>>n; 
   
     
         flag=1;
     int a[n];
       int b[n];
  for( int i=1;i<=n;i++)
      {
      cin>>a[i];
     }
    
      for( int i=1;i<=n;i++)
         b[a[i]]=i;
   
     for( int i=1;i<=n;i++)
   {
    if(a[i]!=b[i]) 
      {
   flag=0;
   break;
  
      }
     
   }
   
    if(flag==1)
  {
   cout<<"ambiguous"<<endl;
   
  } 
  else
   {
   cout<<"not ambiguous"<<endl;
  }
  
 
  
 
   }
 
  return 0;
 }

will u please explain me why..??

whats wrong with code

can anybody please  xplain in deep how the inverse permutation is calculated, with xample?

heylo,,, can some body plz look to my code and tell me the error coz m getting "wrong answer"....and for the test cases discussed here its working correctly...

#include<iostream>

using namespace std;

int main()

{

int n;

int a[100001],b[100001];

int i,f;

while(1)

{

cin>>n;

if(n==0)

break;

f=0;

for(i=1;i<=n;i++)

{

cin>>a[i];

b[a[i]]=i;

}

for(i=1;i<=n;i++)

{

if(a[i]!=b[i])

{

f=1;

break;

}

}

if(f==1)

cout<<"not ambiguous";

else

cout<<"ambiguous";

}

}