10843 - Anne's game

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

27584NX
New poster
Posts: 6
Joined: Thu Jan 16, 2003 6:36 am
Location: Brazil
Contact:

10843 - Anne's game

Post by 27584NX » Tue May 10, 2005 6:30 pm

Is this problem really about counting Connected Labelled Graphs with n vertices and n-1 edges?
I had came up with a permutation which (after factoring the numerator and denominator) ended up being wrong.
Is there any clue for this problem?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue May 10, 2005 6:39 pm

There's a simple formula: n^(n-2).
It gives the number of distinct spanning trees in a complete graph on n vertices, and is called Cayley's formula.

27584NX
New poster
Posts: 6
Joined: Thu Jan 16, 2003 6:36 am
Location: Brazil
Contact:

Post by 27584NX » Tue May 10, 2005 7:31 pm

Well, thank you very much.
Now I think the problem is reduced to simply going over a loop and getting results % 2000000011.
I'm going to look up why this formula works!
Thanks again,
Daniel

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun May 15, 2005 9:30 pm

There is a book called "The Book", which has 7 beautiful proofs that this formula works. In this problem, the numbers are small enough that a fairly complicated dynamic programming solution works, too.
If only I had as much free time as I did in college...

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Tue Jun 05, 2007 6:37 pm

Hi Abednego, can you share the dynamic programming method? Thanks :D

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Tue Jun 05, 2007 6:54 pm

I looked it up on amazon, I don't think I can find "The Book", who's the author?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jun 05, 2007 6:59 pm

Look for 'Proofs from the Book'.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Wed Jun 06, 2007 3:41 am

Got it, Thanks!

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10843 - Anne's game

Post by newton » Wed Oct 15, 2008 7:45 am

why WA.
please give me some critical input output.
my code

Code: Select all

#include <cstdio>

int getMod(int a,int b,int c){
	int i,n = a;
	if(a == 1 || a == 2)
		return 1;

	for(i = 1; i< b; i++){
		a *= n;
		a %= c;
	}
	return a%c;
}

int main(){
	int b,i,test;
	//freopen("in.txt","rt",stdin);
	scanf("%d",&test);
	for(i = 1;i <= test; i++){
		scanf("%d",&b);
		printf("Case #%d: %d\n",i,getMod(b,b-2,2000000011));
	}
	return 0;
}
advanced thanks

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10843 - Anne's game

Post by mf » Mon Oct 20, 2008 1:49 am

newton wrote:why WA.
Integer overflow.
please give me some critical input output.
This problem has only 100 inputs which can be easily generated - "(echo 100; seq 1 100) | ./your_program". Have you even tried running your program on them and simply looking at the results? Negative numbers in the output would have surely ringed a bell.

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 10843 - Anne's game what is the problem??

Post by abid_iut » Sun Nov 30, 2008 7:06 pm

where is the problem for this code
and what should i do to solve the problem
here is the code:

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
	long n,num,i,m,p;
	scanf("%ld",&num);
	for(int it=0;it<num;it++){
		scanf("%ld",&n);
		p=n;
		if(n==1 || n==2){printf("1\n");continue;}
		m=n-2;
		for(i=1;i<m;i++){
			p=p*n;
			p=p%2000000011;
		}
		printf("%ld\n",p);
	}
	return 0;
}

please help
i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10843 - Anne's game

Post by Articuno » Mon Dec 01, 2008 10:23 am

Hi Abid,the problem in your code is you are using too straightforward approach. In this problem your program must have the ability to calculate (100^98)%2000000011. It is not possible if you just loop from 1 to 98 and store the result of multiplication in a variable. It will be a overflow.You have to use dynamic programming. I will give you some hint: Power(X,N) can be represented by the following formula:


power(X,N) =

{ 1, if N=0;
{ X*power(X,N-1), if N is odd;
{ power(X,N/2)^2, if N is even;

I have use this formula to solve the problem. It is a recursive as you can see. But it will also overflow if you do not combine it with the following idea:
That the ans will be ans%2000000011.
So.....the trick is:

"(X*Y)%M can be written as ((X%M)*(Y%M))%M ". So in the above formula you have to use this idea too if u want to get AC.
Otherwise the program will not work i think.
I hope it helps.
Good luck.
Last edited by Articuno on Mon Dec 01, 2008 5:27 pm, edited 2 times in total.
May be tomorrow is a better day............ :)

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10843 - Anne's game

Post by mf » Mon Dec 01, 2008 12:12 pm

Articuno wrote:In this problem your program must have the ability to calculate (100^98)%2000000011. It is not possible with traditional looping.
What's so impossible in a few hundreds of multiplications and divisions?
Modern CPUs do billions of those operations in mere seconds.

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10843 - Anne's game

Post by Articuno » Mon Dec 01, 2008 5:24 pm

Well mf, thank u for your comments. In my reply to abid_iut, what i meant was :
if you do this type of thing:

Code: Select all

ans=1;
for(i=1;i<=98;i++)
{
   ans=ans*100;
}
If i am right it will cause an overflow. In abid_iut's code, he does the similar thing and thus he is not getting the correct answer as there is an overflow. Yes, i may be wrong as i'm new in programming but in this case,i think u misunderstood me for my poor english.

I was not talking about machine's capability. I was talking about program's capability. You can not just use a loop to multiply 100 for 98 tmies and store it in a variable...it will certainly be a overflow.That's what i meant. Hope u understand and forgive me for my poor english.
Goodluck.
[I will also edit that part of my reply :( ]
May be tomorrow is a better day............ :)

abid_iut
Learning poster
Posts: 82
Joined: Wed Jul 16, 2008 7:34 am

Re: 10843 - Anne's game

Post by abid_iut » Mon Dec 01, 2008 5:54 pm

hi Articuno
thankx for ur help but still it's not giving the correct ans.
for small numbers it is OK but for big numbers....... :(
is this the way u told me to do or i missed something.
please help if there is any mistake and tell me where i am wrong.
here is the code:

Code: Select all

#include<stdio.h>
#include<math.h>

int main()
{
	long N,X,i,m,p,num,ans;
	scanf("%ld",&num);
	for(int it=0;it<num;it++){
		scanf("%ld",&X);
		N=X-2;
		if(X==1 || X==2){printf("1\n");continue;}
		for(i=1;i<=N;i++){
			if(i%2==0){
				ans=pow(X,(N/2))*pow(X,(N/2));
				ans=ans%2000000011;
			}
			else if(i%2!=0){
				ans=X*pow(X,N-1);
				ans=ans%2000000011;
			}
		}
		printf("%ld\n",ans);
	}
	return 0;
}

i love to wait... wait for better... and better will come...
http://akanoi.webs.com/

Post Reply

Return to “Volume 108 (10800-10899)”