## 10843 - Anne's game

Moderator: Board moderators

### 10843 - Anne's game

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?
27584NX
New poster

Posts: 6
Joined: Thu Jan 16, 2003 6:36 am
Location: Brazil

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.
mf
Guru

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

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
27584NX
New poster

Posts: 6
Joined: Thu Jan 16, 2003 6:36 am
Location: Brazil

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.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

Hi Abednego, can you share the dynamic programming method? Thanks
yiuyuho
A great helper

Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States

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

Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States

Look for 'Proofs from the Book'.
mf
Guru

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

Got it, Thanks!
yiuyuho
A great helper

Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States

### Re: 10843 - Anne's game

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;}`

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am

### Re: 10843 - Anne's game

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.
mf
Guru

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

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

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;}`

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

Posts: 80
Joined: Wed Jul 16, 2008 7:34 am

### Re: 10843 - Anne's game

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............
Articuno
Learning poster

Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10843 - Anne's game

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.
mf
Guru

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

### Re: 10843 - Anne's game

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............
Articuno
Learning poster

Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm

### Re: 10843 - Anne's game

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.
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/
abid_iut
Learning poster

Posts: 80
Joined: Wed Jul 16, 2008 7:34 am

Next

### Who is online

Users browsing this forum: No registered users and 1 guest