SGARDEN - Editorial

editorial
, , , ,
21

another good editorial, which was written during the contest: http://math.stackexchange.com/questions/856302/count-the-whistles

22

Hey, @devuy11, the error in the pseudo code wrong_soltion
http://discuss.codechef.com/questions/47443/lcm-of-n-numbers-modulo-1097

23

Can anyone help me please to find out whatā€™s the mistake of my code?

Thanks in advance :slight_smile:

24

In challenge 1, is it that while iterating the cycle, in whichever indices bandit 1 (for example) goes, the bandits at these indices also follow the same number of iterations before reaching their original position? Is that why there is visited[s]=1 in the iteration loop?

25

Hi All , It will be of great help : if anyone can tell the bug in this code . I am getting WA : http://www.codechef.com/viewsolution/4331278

26

I have used the Exact Same Logic as described above.
Someone Please find the mistake in the code.
http://www.codechef.com/viewsolution/4337300

27

Hi guys, nobody has time to read your code. Iā€™d suggest you to generate test data and compare your output with testerā€™s solution and debug on your own pace.

  1. Python script to generate tests sgarden_gen.py

  2. Testerā€™s solution SGARDEN.cpp

  3. In linux you can compare two files with diff command. Simply run:

    diff my_output.txt correct_output.txt

Happy coding!

28

Sir my solution is giving tleā€¦why is it happeningā€¦
#include<stdio.h>
#define max 1000000007
long long int cal(long long int a[],long long int b[],long long int c[],long long int n,long long int ans)
{
long long int i,flag,flag1=0;
flag=0;
for(i=1;i<=n;i++)
{

			b[a[i]]=c[i];
		 }
		 for(i=1;i<=n;i++)
		 {
		 	c[i]=b[i];
		 	if(b[i]==i)
		 	{
		 		flag++;
		 	}
		 if(b[i]==a[i])
		 	 flag1++;
		 	// printf("%lld ",b[i]);
		 	
		 }
		 if(flag==n)
		   return ans;
		   if(flag1==n)
		   {
		    	ans++;
		     return ans; 
		   }
		else
		 {
		 	
		 	ans++;
		   cal(a,b,c,n,ans);
	     }

}
int main()
{
int t;
scanf("%d",&t);
while(tā€“)
{
long long int i,n,a[100005],b[100005],c[100005],ans=1;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=i;
c[i]=i;

	}
//	printf("%lld\n",count);

             ans=cal(a,b,c,n,ans);
			printf("%lld\n",ans%max);
}
return 0;

}

29

This was not very obvious to me. (x.y)modm==((xmodm).y)modm http://math.stackexchange.com/questions/5366/very-simple-question-but-what-is-the-proof-that-x-y-mod-m-x-mod-m-y-mod?rq=1

30

Why does it show wrong answer when output for all tried test cases is coming out correct?

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

31

Why canā€™t we do it like thisā€¦
I am getting right output for the sample test cases, but WA.

            int n,i,j,k; long long c=1;
	scanf("%d",&n);
	long long a[1000001],p[n],na[n];
	for(i=1;i<=n;i++){
		scanf("%ld",&a[i]);
		p[a[i]]=a[i];
	}//for
	//change the positions accordingly
	for(i=1;i<=n;i++){
		na[i]=p[i];
	}//for
		for(j=1;j<=n;j++)
		{

			if(na[j]==a[j]){continue;}
			else {for(k=1;k<=n;k++){na[k]=p[na[k]];}c++;}


			}//forj

	printf("%lld\n",c%1000000007);
32

for(i=1;i<=n;i++)
{
count=0;
j=i;
while(!visited[j])
{
visited[j]=true;
j=a[j];
count++;
}
if(count)
{
lcm=(lcm*count)/gcd(lcm,count);
}
}

Why does this give TLE?