Permutation Cycles

All submissions for this problem are available.
We consider permutations of the numbers 1,..., N
for some N. By permutation we mean a rearrangment of the
number 1,...,N. For example
2 4 5 1 7 6 3 8
is a permutation of 1,2,...,8. Of course,
1 2 3 4 5 6 7 8
is also a permutation of 1,2,...,8.
We can "walk around" a permutation in a interesting way and here
is how it is done for the permutation above:
Start at position 1. At position 1 we have 2 and so we go to
position 2. Here we find 4 and so we go to position 4. Here we find
1, which is a position that we have already visited. This completes
the first part of our walk and we denote this walk by (1 2 4 1). Such
a walk is called a cycle. An interesting property of such
walks, that you may take for granted, is that the position we revisit
will always be the one we started from!
We continue our walk by jumping to first unvisited position, in
this case position 3 and continue in the same manner. This time we
find 5 at position 3 and so we go to position 5 and find 7 and we go
to position 7 and find 3 and thus we get the cycle (3 5 7 3). Next we
start at position 6 and get (6 6) and finally we start at position 8
and get the cycle (8 8). We have exhausted all the positions. Our
walk through this permutation consists of 4 cycles.
One can carry out this walk through any permutation and obtain a
set of cycles as the result. Your task is to print out the cycles
that result from walking through a given permutation.
Input format
The first line of the input is a positive integer N
indicating the length of the permutation. The next line contains
N integers and is a permutation of 1,2,...,N.
You may assume that N ≤ 1000.
Output format
The first line of the output must contain a single integer
k denoting the number of cycles in the permutation. Line 2
should describe the first cycle, line 3 the second cycle and so on and
line k+1 should describe the kth cycle.
Examples
Sample input 1:
8 2 4 5 1 7 6 3 8
Sample output 1:
4 1 2 4 1 3 5 7 3 6 6 8 8
Sample input 2:
8 1 2 3 4 5 6 7 8
Sample output 2:
8 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8
Author:  admin 
Tags  admin 
Date Added:  28072009 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, GO, HASK, ICK, ICON, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, 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. 
how can i print no of cycles
how can i print no of cycles at the starting of the output.??!!!!
Could you be more specific?
Could you be more specific?
You may assume that N 1000??
You may assume that N 1000??
N <= 1000
N <= 1000
if 1241 is first cycle then
if 1241 is first cycle then can we visit 4 once again in next cycle??
I hate thsi runtime error. I
I hate thsi runtime error.
I am not getting any error on my system
but when i upload i get this runtime error...
anyone can please help me out ...
code 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
int numbers;
int *per;
int *cycleList;
int i,temp,startNode;
int index;
int count;
while(1)
{
scanf("%d",&numbers);
if(numbers == 0)
break;
per = (int*)malloc(sizeof(int)*numbers);
for(i=0; i<numbers; i++)
{
scanf("%d",&per[i]);
}
cycleList = (int*)calloc(numbers,sizeof(int));
//find the cycles.
startNode = 0;
count = 0;
while(1)
{
index = startNode;
count++;
//STORE THE CYCLES
while(cycleList[index] == 0)
{
cycleList[index] = count;
index = per[index]1;
}
//Find the next not travelled node;
while(cycleList[startNode] != 0)
{
startNode++;
if(startNode >=numbers)
break;
}
if(startNode >=numbers)
break;
}
//Print the result;
printf("%dn",count);
startNode = 0;
temp = count;
for(i = 1;i<=count;i++)
{
//print one cycle
index = startNode;
printf("%d ",index+1);
index = per[index]1;
while(startNode != index)
{
printf("%d ",index+1);
index = per[index]1;
}
printf("%d n",index+1);
while(cycleList[startNode] <= i)
{
startNode++;
}
}
//free the memory;
free(per);
free(cycleList);
}
}
This problem is not accepting
This problem is not accepting C++(g++ 4.3.2)
@everyone what is the output
@everyone
what is the output for the input which is not circular
like 5
1 3 5 7 9
admin is the the input test
admin
is the the input test cases must circular..???
You are given a permutation.
You are given a permutation. That isn't a permutation.
is there is space between the
is there is space between the entered numbers.....???
@admin is there is space
@admin
is there is space between enter numbers???
is there is any space between
is there is any space between output eg: 1241 or 1 2 4 1
which one is correct output..??
pls help...
Read the sample input. It is
Read the sample input. It is there for a reason.
When I submitted the solution
When I submitted the solution to this problem, I got this error.
What does this mean?
:( internal error occurred in the system
cycles obtained using this
cycles obtained using this method are always disjoint...and disjoint cycles are commutative...then the order of the cycles to be printed in the ouput should not matter..does it???
if not..what should be the order??
(i want to confirm this before starting the problem)
The order to print them is
The order to print them is clearly described in the problem statement.
IS THERE NEED TO
IS THERE NEED TO PRINT
"SAMPLE OUTPUT 1:" OR NOT....??
PLS HELP
When I submitted the
When I submitted the solution to this problem, I got this error.
What does this mean?
:( internal error occurred in the system
Please check my
Please check my solution..
http://www.codechef.com/viewsolution/231756
I think there is a problem of newline or space in output with my code
Please check my
Please check my solution..
http://www.codechef.com/viewsolution/231756
I think there is a problem of newline or space in output with my code
Are there spaces between the
Are there spaces between the numbers(in input/output)???
@ Rahul  at least one
@ Rahul  at least one mistake is that your code can't work for N = 1000 for a rather obvious reason.
@abcd  N can be up to 1000  if there weren't spaces, how could you tell what the numbers were?
@Stephen Merriman Thanks!,but
@Stephen Merriman
Thanks!,but that wasn't mentioned in the question...
Sure it was; it says there
Sure it was; it says there are N integers on the line. If there were no spaces it wouldn't be N integers.
I swear its giving the right
I swear its giving the right answer, but still it shows wrong answer. My code:
code removed by admin
Do not post code here. You
Do not post code here.
You clearly haven't tested your code on large test cases with N=1000, say. Do so and your error will become obvious.
@Stephen: I apologise for my
@Stephen: I apologise for my mistake. Thanks.
@Admin : please help me in
@Admin : please help me in the code ..seem to be working fine with the test cases as well
<b>
http://www.codechef.com/viewsolution/246548
</b>
please help...really
@ admin yesterday i found
@ admin
yesterday i found that the responses to my submissions were followed by the size of the test cases. This was pretty useful in determining the mistakes in my submitted code. But for some reason this facility is not available today. It will be gr8 if you do something bout it.
hey can anyone tell wats
hey can anyone tell wats wrong with this, its working on my comp but am getting a runtime error when i submit the problem.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
*
* @author sanket
*/
class MyNumber{
public int value;
public boolean mark;
MyNumber(int value){
this.value = value;
mark=false;
}
}
public class Main{
private List list = new ArrayList();
private List list2 = new ArrayList();
private BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
private MyNumber num;
private int number,testCase,count2,count;
private Scanner scanf = new Scanner(System.in);
public void getInput(){
MyNumber k;
try {
testCase = Integer.parseInt(bf.readLine());
list.add(new MyNumber(0));
list2.add(new MyNumber(0));
for(int i=1;i<testCase+1;i++){
k=new MyNumber(scanf.nextInt());
list.add(i,k);
list2.add(i,new MyNumber(k.value));
}
} catch (IOException ex) {
System.out.println(ex);
ex.printStackTrace();
}
catch(UnsupportedOperationException us){System.out.println(us);}
catch(ClassCastException cs){System.out.println(cs);}
catch(IllegalArgumentException il){System.out.println(il);}
catch(NullPointerException nl){System.out.println(nl);}
}
public void getCount(){
count=0;
count2=0;
number=1;
try{
do{
num = (MyNumber) list2.get(number);
if(!num.mark){
num.mark=true;
number=num.value;
}
else{
number=0;
do{
number++;
num =(MyNumber)list2.get(number);
}while(num.mark);
count2++;
continue;
}
count++;
}while(count<testCase);
System.out.println(count2+1);
}catch(Exception ex){ex.printStackTrace();
}
}
public void getAnswer(){
count =0 ;
count2=0;
number=1;
try{
do{
num = (MyNumber) list.get(number);
if(!num.mark){
System.out.print(number);
num.mark=true;
number=num.value;
}
else{
System.out.print(number);
number=0;
do{
number++;
num =(MyNumber)list.get(number);
}while(num.mark);
System.out.println("");
continue;
}
count++;
}while(count<testCase);
System.out.print(num.value);
}catch(Exception ex){ex.printStackTrace();
}
}
public static void main(String[] args) throws java.lang.Exception{
Main p = new Main();
p.getInput();
p.getCount();
p.getAnswer();
}
}
Working for test cases but
Working for test cases but wrong answer, is it to compiler difference, i used g++ 4.3.2 but have to submit code in 4.0.08 as former is not accepted :(
i am not able to submit the
i am not able to submit the solution in c++. its saying you cant submit in this language. try link.
@Admin plz sir check my
@Admin
plz sir check my solution as i m not able to figure out as to what cud b d mistake...
http://www.codechef.com/viewsolution/363705
Plz ignore my above comment
Plz ignore my above comment as i m able to rectify my mistake...
my code is simple it give
my code is simple it give correct answer still it is said as wrong answer
#include<stdio.h> #include<stdlib.h> int main() { int n,*a,*visited,i,done=0,temp,count=0; scanf("%d",&n); a=(int *)malloc (sizeof(int)*(n+1)); visited=(int *)malloc (sizeof(int)*(n+1)); for(i=1;i<=n;i++) { scanf("%d",&a[i]); visited[i]=0; } temp=0; count=0; for(i=1;i<=n;i++) { if(visited[i]==0) { temp=i; while(!done) { //printf("%d",temp); visited[temp]=1; temp=a[temp]; visited[temp]=1; if(temp==i) done=1; } //printf("%dn",temp); done=0; count++; } } printf("%dn",count); //making visited 0 again for(i=1;i<=n;i++) visited[i]=0; for(i=1;i<=n;i++) { if(visited[i]==0) { temp=i; while(!done) { printf("%d",temp); visited[temp]=1; temp=a[temp]; visited[temp]=1; if(temp==i) done=1; } printf("%dn",temp); done=0; count++; } } return 0; }
you can't submit in this
you can't submit in this language for this problem. Try link.
this error is appearing
i am submitting problem in c++
:(
i dont know why i m gettin
i dont know why i m gettin wrong answer....plz check if there is any thin wrong with the code
#include<stdio.h>
int main()
{
int n,i,initial,current;
scanf("%d",&n);
int a[1000];
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
initial=0;
current=1;
while(initial!=n)
{
int flag=0,fl=0;
while(initial!=current )
{
if(flag==0)
{
current=initial;
flag=1;
}
if(a[current]!=1)
{
printf("%d ",current+1);
fl=1;
int k=current;
current = a[current] 1;
a[k] = 1;
}
}
if(fl==1)
{
printf("%d",initial+1);
printf("n");
fl=0;
}
initial++;
}
return 0;
}
i m gettin right answer for
i m gettin right answer for all test cases i hav tried,,,,,,,,,,,,i hav even tried the one input for n=1000
plz chek the code:
http://www.codechef.com/viewsolution/401968
i m gettin right answer for
i m gettin right answer for all test cases i hav tried,,,,,,,,,,,,i hav even tried the one input for n=1000
but i m gettin wrong answer here
plz chek the code:
http://www.codechef.com/viewsolution/401968
Can somebody point out the
Can somebody point out the why my code is giving RuntimeError.
http://www.codechef.com/viewsolution/456193
http://www.codechef.com/views
http://www.codechef.com/viewsolution/470046
this is the solution of user default1130(i copied just to test) for permutation cycles.in the successfull submission list you can see this solution is taking 0.0 sec and 0 size but when i run this solution on your server it shows 0.07 seconds and 5.4 mb size .you can confirm this by visiting this link http://www.codechef.com/status/PCYCLE,teacher.the id is 470046.
can anyone suggest me why this is happening?
different running time and size for executable compiled from same source?
i would really appreciate if admin has some explanation
i think there is some
i think there is some mistake.my rest of the text is not here in the comments.ok no prob i will write it again here.actually when i run the source of user default1130(top of the list) for this problem on your server it is showing running time =0.07 sec and size=5.4 mb.you can verify by this link
http://www.codechef.com/status/PCYCLE,teacher
id is 470046.But in your list running time and size is 0 for the same source..
just curious to know what could be the problem?
The problem why many people
The problem why many people are getting WA for this problem is that when the online judge checks the answer it has to be exactly the same as to what they have.
Over here before every new line 'n' after a permutation cycle there is a space.
If u have this space then only ur answer is accepted.
I think the people who have not left a space are corect and thier code should be accepted as majority of the question don't prefer lingering spaces.
#include<stdio.h>#include<std
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int num[100];
int n;
printf("Enter permutation no : ");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
printf("Enter the digit positive no. :");
scanf("%d",&num[i]);
if(num[i]<0)
{
printf("Error in input");
exit(0);
}
}
if(n==1&num[0]!=1)
{
printf("not ambiguous");
}else
{
for(int j=1;j<n;j++)
{
if(num[0]!=1)
{
printf("not ambiguous");
break;
}
else if(num[j]!=(i))
{
printf("not ambiguous");
break;
}
i;
}
if(j==n)
{
printf("ambiguous");
} }
return(0);
}
whats wrong with my
whats wrong with my code:
#include<stdio.h>
main()
{
int t,i,k;
scanf("%d",&t);
int j,num[1001],check[1001]={0};
for(i=1;i<=t;i++)
scanf("%d",&num[i]);
int total=0;
for(j=1;j<=t;j++)
{
if(check[j]==1)
continue;
check[j]==1;
k=num[j];
while(k!=j)
{ check[k]=1;
k=num[k];
}
total++;
}
printf("%dn",total);
for(j=1;j<=1000;j++)
check[j]=0;
for(j=1;j<=t;j++)
{
if(check[j]==1)
continue;
check[j]==1;
printf("%d",j);
k=num[j];
while(k!=j)
{printf("%d",k);
check[k]=1;
k=num[k];
}
printf("%d n",j);
total++;
}
return 0;
}
@Admin I have solved this
Can anyone please help me
@Admin Please help me with my
getting WA my code :
@admin Please tell that " IS
@admin Please tell that " IS
http://www.codechef.com/views
my code is producing outout
@all beware..if you're
@samkit.... Chef accepted
CrAp... The problem failed
http://www.codechef.com/views
for all those people solving
@Admin I have checked the
http://www.codechef.com/views
can anyone tell me whats
Why is my code at
Are we supposed to begin from
I am unable to view the
#include #include int
output for the test case