10883 - Supermean

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

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Supermean

Post by temper_3243 » Sun Jul 31, 2005 6:20 am

I wrote 2 for loops. I was getting TLE.
i made up the formula as (a+nc1*b + nc2*c + nc3*d.......+ nc1*m + n)/2^n-1

For n=50000, we have 50000 C 20000 . How are we going to find such a big number.

How do you solve the problem supermean ?

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Jul 31, 2005 8:02 am

There is a minor mistake in your formula: It's n in the nCr but n-1 in 2^(n-1).

50000C25000 is extremely large. But 50000C25000/2^50000 is not. Meanwhile, nCr/2^n is small enough to ignore it for r close to 0 or n. I used a single for-loop to compute your formula. Use a double to store nCr/2^n. However, nC0/2^n is smaller than the smallest value of double, so don't divde the nCr by 2^n when r is small. As r increases, nCr becomes larger, divide it by power of 2 gradually. When r is close enough to n/2, you can use the nCr/2^n to compute the weighted sum.

(I know the above english description is terribly poor. Sorry.)

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10883 - Supermean

Post by Riyad » Sun Jul 31, 2005 2:17 pm

hi everybody,
can any one tell me what is the smart way of solving this problem Super mean ........i assumed something like this ............
let the numbers in the sorted order are
a0 a1 a2 .................an

so i came across a formula for finding super mean which is

a0 + nC1 a1 + nC2 a2 + ..............nCn an
-------------------------------------------------
2^n

but i could not find out the value of the above term as the highest limit of n was 50,000..........so any help is appreciated ...........

Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Cosmin.ro
Learning poster
Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

Post by Cosmin.ro » Sun Jul 31, 2005 2:37 pm

You can find one nCk from nCk-1 by a multiplication and a division, also at each step when you do the sum you can divide the sum and the coeficient by 2 so that the at each step the coeficient doesn't exced 1.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Sun Jul 31, 2005 10:02 pm

Cosmin.ro wrote:You can find one nCk from nCk-1 by a multiplication and a division, also at each step when you do the sum you can divide the sum and the coeficient by 2 so that the at each step the coeficient doesn't exced 1.
Hi, would you mind giving me an example of your algorithm?

Thx in advance.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Sun Jul 31, 2005 10:57 pm

Antonio Ocampo wrote:
Cosmin.ro wrote:You can find one nCk from nCk-1 by a multiplication and a division, also at each step when you do the sum you can divide the sum and the coeficient by 2 so that the at each step the coeficient doesn't exced 1.
Hi, would you mind giving me an example of your algorithm?

Thx in advance.
Code to compute 200C100 / 2^99 (written directly here, no guarantees it works ;) )

Code: Select all

int power = 99;
long double result = 1.0;
for (int i=1; i<=100; i++) {
  result *= 201 - i;
  result /= i;
  while (power && result > 1) { result /= 2; power--; }
}
while (power) { result /= 2; power--; }
(Omit the lines with "power" to get a code computing 200C100. This would overflow, thus we have to divide it by the powers of 2 during the computation.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10883

Post by htl » Sat Aug 06, 2005 4:40 pm

I passed the sample input but got WA. Is it the precision problem?

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Aug 06, 2005 7:03 pm

You should try some large input.

My output for the following input is 50.500:
10000 numbers: First 100 numbers are 1. The following 100 numbers are 2 and so on... The last 100 numbers are 100.

And the output for the following input is 257.191:
1000 numbers: the n-th number is 123456789%n (n from 1 to 1000)

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

Post by mf » Sat Aug 06, 2005 7:22 pm

Your second input does not follow the problem's restrictions.
My contest's solution sorts the input before processing, and prints 184.857.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Aug 06, 2005 8:07 pm

Oops... sorry about that :wink:

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

10883

Post by jagadish » Sat Aug 06, 2005 9:03 pm

Does the solution involve approximation of binomial coefficients? Does sorting have any significance ?
give me a hint plz..
if u can think of it .. u can do it in software.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Aug 06, 2005 9:10 pm


lukasP
New poster
Posts: 3
Joined: Mon Aug 08, 2005 12:44 pm
Location: Pezinok, Slovakia

Post by lukasP » Mon Aug 08, 2005 12:55 pm

I have used logarithm to solve this problem. log(nCi)=log(nC i-1)+log(n-i)-log(i).

The smallest number is about 2^-50000. But log(2^-50000)=-34657.359 and there is no problem with precision. If log(nCi)+(n-1)*log(0.5) is small enough, you can ignore it.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Aug 08, 2005 1:20 pm

And in my AC code, I don't need any approximations at all (except, maybe, the floating-point precision problem). I used the concept of binomial coefficients too. :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Tue Aug 09, 2005 9:14 am

Soory, I have read the thread above.
pass all the input.
But get WA all the time
Could someone give some critical input/output?
Thx

Post Reply

Return to “Volume 108 (10800-10899)”