11609 - Teams

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

Moderator: Board moderators

Post Reply
sharath
New poster
Posts: 6
Joined: Tue Sep 16, 2008 9:21 pm

11609 - Teams

Post by sharath » Thu Jul 30, 2009 1:17 pm

The problem says that output has to be printed result modulo 1000000007, I dont understand why this value and moreover for n=3, the number of ways the coach can choose his team is:
First for k = 1, He has 3 ways,
for k = 2, He has 6 * 2 (For different captains) ways,
for k = 3, He has 1 * 3 (For different captains) ways,

So totally he has 3+12+3 = 18 ways, then 18 modulo 1000000007 is 18 itself. I don't understand how the output is given as 1.
Let me know if I have understood the problem correctly.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11609 - Teams

Post by emotional blind » Fri Jul 31, 2009 9:18 pm

The first line of the input represents the number of cases in the input.

User avatar
Psh
New poster
Posts: 7
Joined: Tue Jul 06, 2010 9:52 pm
Location: Bangladesh
Contact:

11609 ' Why WA !!

Post by Psh » Tue Jul 06, 2010 10:04 pm

Code: Select all

#include<stdio.h>
#include<math.h>
#define mod 1000000007

int main()
{
    int n,i;
    unsigned long m,p;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
         scanf("%lu",&m);
         p=pow(2,(m-1));
         printf("Case #%d: %lu\n",i,(m*p)%mod);
    }
    return 0;
}
Last edited by Psh on Thu Dec 01, 2011 2:53 pm, edited 1 time in total.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11609 ' Why WA !!

Post by sohel » Wed Jul 07, 2010 12:12 pm

What's your output for the input -> 1000000000
pow(2,(1000000000-1)) .. this statement won't work due to overflow.

User avatar
Psh
New poster
Posts: 7
Joined: Tue Jul 06, 2010 9:52 pm
Location: Bangladesh
Contact:

Re: 11609 ' Why WA !!

Post by Psh » Wed Jul 07, 2010 12:34 pm

Thanks!!
I've fixed it. Got that point.
i Quit for a fresher start

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 11609 ' Why WA !!

Post by sazzadcsedu » Wed Jul 07, 2010 12:46 pm

Can U imagine what is the value of pow(2,m-1) where m=1000000000. Value of pow(2,31) is 2147483648.So i think you
can understand what pow(2,999999999) will return. So you have to write your own power function
where the intermediate result is mod(%) by 1000000007. And you can't avoid TLE by iteratively
calculating power, like using a for loop till N.There is a nice divide and conquer algorithm for calculating (b^p)%m ,where
b is base,p is power and m is mod.Try this.
Last edited by sazzadcsedu on Wed Jul 07, 2010 7:01 pm, edited 1 time in total.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

User avatar
Psh
New poster
Posts: 7
Joined: Tue Jul 06, 2010 9:52 pm
Location: Bangladesh
Contact:

Re: 11609 ' Why WA !!

Post by Psh » Wed Jul 07, 2010 12:48 pm

Yes, Bro..
I'm trying it now Bigmod method.
i Quit for a fresher start

User avatar
Psh
New poster
Posts: 7
Joined: Tue Jul 06, 2010 9:52 pm
Location: Bangladesh
Contact:

Re: 11609 ' Why WA !!

Post by Psh » Wed Jul 07, 2010 1:13 pm

Now I've got Accepted.
Thanks for helping. :)
i Quit for a fresher start

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Re: 11609 - Teams

Post by nymo » Wed Feb 09, 2011 5:23 pm

I think, the answer is: summation of k * nCk for k = 1 ... n [nCk = n Choose k]
Can someone tell me how to get a closed form?
regards,
nymo

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11609 - Teams

Post by plamplam » Fri Oct 14, 2011 11:20 pm

It's easy to derive this summation formula...after deriving this, why don't you write down all the values of this summation from n = 1 to n = 7 on paper? May be you will notice a pattern. If you do notice a pattern may be you will understand why and how such a pattern exists. Good luck.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Re: 11609 - Teams

Post by richatibrewal » Fri Nov 07, 2014 5:44 pm

I am not getting the required output: I m using the summation of k*nCk

Code: Select all

#include<cstdio>
using namespace std;
#define mod 1000000007;
int main()
{
    int n,i,j,c=0,num,k;
    long long int sum,res;
    scanf("%d",&n);
    while(n--)
    {
        c++;
        sum=0;
        scanf("%d",&k);
        for(i=1;i<=k;i++)
        {
            res=i;
            num=k;
            for(j=1;j<=i;j++)
            {
                res=res*num;
                res=res/j;
                num--;
                res=res%mod;
            }

            sum=sum+res;
            sum=sum%mod;
             //printf("%d  %lld  %lld\n",i,sum,res);
        }
        printf("Case #%d: %lld\n",c,sum);
    }
    return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11609 - Teams

Post by brianfry713 » Wed Nov 19, 2014 1:18 am

Your code is getting TLE. Try input:

Code: Select all

1
1000000000
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 116 (11600-11699)”