Ambiguous Permutations

All submissions for this problem are available.
Some programming contest problems are really tricky: not only do they
require a different output format from what you might have expected, but
also the sample output does not show the difference. For an example,
let us look at permutations.
A permutation of the integers 1 to n is an
ordering of
these integers. So the natural way to represent a permutation is
to list the integers in this order. With n = 5, a
permutation might look like 2, 3, 4, 5, 1.
However, there is another possibility of representing a permutation:
You create a list of numbers where the ith number is the
position of the integer i in the permutation.
Let us call this second
possibility an inverse permutation. The inverse permutation
for the sequence above is 5, 1, 2, 3, 4.
An ambiguous permutation is a permutation which cannot be
distinguished from its inverse permutation. The permutation 1, 4, 3, 2
for example is ambiguous, because its inverse permutation is the same.
To get rid of such annoying sample test cases, you have to write a
program which detects if a given permutation is ambiguous or not.
Input Specification
The input contains several test cases.
The first line of each test case contains an integer n
(1 ≤ n ≤ 100000).
Then a permutation of the integers 1 to n follows
in the next line. There is exactly one space character
between consecutive integers.
You can assume that every integer between 1 and n
appears exactly once in the permutation.
The last test case is followed by a zero.
Output Specification
For each test case output whether the permutation is ambiguous or not.
Adhere to the format shown in the sample output.
Sample Input
4 1 4 3 2 5 2 3 4 5 1 1 1 0
Sample Output
ambiguous not ambiguous ambiguous
Author:  admin 
Tags  admin 
Date Added:  1122008 
Time Limit:  10 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 
when i press submit button
when i press submit button its giving
the requested page could not be found......
whats wrong???
when i press submit button
when i press submit button its giving
the requested page could not be found......
whats wrong???
the submit page is stilll not
the submit page is stilll not found
getting a strange
?...') #1 /var/www/html/codechefbeta/codechef/modules/node/node.module(673): codechef_judge_nodeapi(Object(stdClass), 'validate', Array, NULL) #2 /var/www/html/codechefbeta/codechef/modules/node/node.module(809): node_invoke_nodeapi(Object(stdClass), 'validate', Array) #3 /var/www/html/codechefbeta/codechef/modules/node/node.pages.inc(65): node_validate(Array, Array) #4 /var/www/html/codechefbeta/codechef/includes/form.inc(766): node_form_validate(Array, Array) #5 /var/www/html/codechefbeta/codechef/includes/form.inc(714): form_execute_handlers('validate', Array, Array) #6 /var/www/html/codechefbeta/codechef/includes/form.inc(579): _form_validate(Array, Array, 'answer_node_for...') in /var/www/html/codechefbeta/codechef/sites/all/modules/codechef_judge/codechef_judge.module on line 48
anshuman, don't worry about
anshuman, don't worry about that error. It doesn't acutally affect your submission.
it seems like no one got any
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
The statement itself explains pretty clearly.. what line don't you understand exactly?
how are the ambiguous
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
You mean this line from above?
You create a list of numbers where the ith 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
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?
someone?
Original permutation = 1 3 2
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
The sample input and output arnt clear.......if possible someone can help me out.
hello all, plz help me.m
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
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
my code is working properly on comp.. but m getting runtime error here.. can anyone help me out plz.
You are declaring far too
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
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!!!!!!!
got it!!!!!!!
what is wrong with sample
what is wrong with sample input 2inputs and 3 outputs
Nothing is wrong with the
Nothing is wrong with the sample input. There are 3 inputs.
hey dude what is the flaw in
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
@prashant
You have declared too big arrays and moreover int z cannot store 10^5.
i am getting run time error
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
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.
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
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
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
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
What made you choose the number 65536? Read the problem statemenr.
the code is working fine with
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
@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
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
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
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
^ 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
yes i checked for the complete sample input, the output is exactly like its supposed to be
Are you sure ?? ... output
Are you sure ?? ... output for each test case is on a new line, your program does that ?
yes
yes
@Admin  Same problem 
@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
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
Oh thanks Stephen, got it running..
@Stephenmy solution times
@Stephenmy solution times out...
http://www.codechef.com/viewsolution/283745
any hints..plz.. ?
n can be up to 100000. Two
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
@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
#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_len1; 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
Can someone plz simplify thils question. How do we get inverse permutations?
I am getting Runtime
I am getting Runtime Error..Please Someone HELP!!
@Vidura Yashan: Maybe you can
@Vidura Yashan: Maybe you can read this article http://mathworld.wolfram.com/InversePermutation.html
this program is providing
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
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
is out of memory a compile error???
#include<iostream> using
#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
Anyone please explain me what is the meaning of
"internal error in the system "...
my code is running correctly on my PC....
:( internal error occurred in
what does this mean??? am confused!!
Is there anything special
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
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
@ 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] == n1){
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
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
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
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
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
#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
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
I got Error ..... :)
very lame part of me !
@ admin ...i get the right
@ admin ...i get the right answer on my pic but get a wrong answer on code chef ..please check
why those are not
why those are not working?
http://www.codechef.com/viewsolution/431575
http://www.codechef.com/viewsolution/431319
@admin I couldn't get the
@admin I couldn't get the problem.
"You create a list of numbers where the ith 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
@ 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
@admin
see the following soln has been submitted successfully
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
will u please explain me why..??
whats wrong with code
can anybody please xplain in
can anybody please xplain in deep how the inverse permutation is calculated, with xample?
heylo,,, can some body plz
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";
}
}
i,ve checked the sample
i,ve checked the sample
i,ve checked the sample
AAARGH!!!!!!!whats
can someone put tutorial for
Admin or anyone, please see
can someone please help i'm
ambiguous permutation
/sources/tested.c: In
Can anyone tell me what is
what is wrong in this...? If
I could not understand this
y is this code : def
I am getting the correct
import java.io.*; class
One of the simplest programs
Can you please tell me what
why is this program giving
Can anybody help me with this
Got it but execution time is
I am getting wrong output,
@admin I am getting a wrong
Getting NZEC..... plz point
NZEC Removed.... by removing
I was wondering what function
a[a[i]1]==i+1; isn't this
just one simple condition
I get a runtime Run time
why it is giving me wrong
Getting 'wrong answer' after
how is 5 1 2 3 4 an inverse
while(1) { i=1;
why is it showing wrong
#include unsigned long
Getting TLE, code:
I am getting runtime error
hey admin , please tell me
did it !!!!!!
someone please xplain me d
i really cant understand how
@gchandel6
Hi, Can anyone please tell
Hello everyone, kindly help
Shouldn't it be ambiguous if
I changed the code now, and
Sorry forgot to paste the
Hello, I understand that
I'm getting this error:
@eitvik agarwal  you should
@aragar I have changed my
Well, you haven't changed
I wrote a code, using
int main() { long int i; int
Program is exceeding time
int main() { unsigned int
Can anyone Give some more
Why is this showing time
Dear Admin same problem
@Admin tried for the sample
A nice solution and
Shows "The language selected
www.codechef.com/viewsolution
http://www.codechef.com/views
http://www.codechef.com/views
hmm iv checked my code
finally got itt! :D
My program gives correct
please answer why i am
plse tell what's wrong in my
#include int main() { int
#include int main() { int
can someone please explain
why it is showing runtime
Several test cases means ?
how we input data in a
Dear friends, i am getting
What is a inverse
http://www.codechef.com/views
Plzz tell me whyyy i'm
@atomos check ur array size
cant we check it by taking
I am getting runtime error.
I'm not able to understand
https://www.codechef.com/view
So my code
Who wants to understand the