10883 - Supermean

Moderator: Board moderators

10883 - Supermean

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster

Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET

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.
Cosmin.ro
Learning poster

Posts: 95
Joined: Thu Aug 21, 2003 12:02 am

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?

Antonio Ocampo
Experienced poster

Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

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?

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.

misof
A great helper

Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

10883

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

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

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)

Cho
A great helper

Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

My contest's solution sorts the input before processing, and prints 184.857.
mf
Guru

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

Cho
A great helper

Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

10883

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

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

Cho
A great helper

Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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.
lukasP
New poster

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

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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Observer
Guru

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

pass all the input.
But get WA all the time
Could someone give some critical input/output?
Thx
windows2k
Experienced poster

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

Some simple cases:
Code: Select all
`5101-1111-555.55591555.5559`

Output:
Code: Select all
`Case #1: 0.000Case #2: -1.000Case #3: 1.000Case #4: -555.556Case #5: 555.556`

Input generator:
Code: Select all
`#include <stdio.h>#include <stdlib.h>unsigned r = 123456; int T = 20, a[65536], i, n;int R(unsigned m) { r = r * 1812433253 + 1; return (r >> 4) % m; }int C(const void *p, const void *q) { return (*(int *)q - *(int *)p); }int main() {  for(printf("%d\n",T);T--;) {    for(printf("%d\n",n=1+R(50000)),i=n;i--;)a[i]=R(2000000)-1000000;    qsort(a,n,sizeof(a[0]),&C);    while(n--)printf("%s%d.%.3d%c",(a[n]<0)?"-":"",abs(a[n]/1000),abs(a[n])%1000,n?' ':'\n');  }  return 0;}`

Output from my first program (uses long double, and binomial identities), to 10 decimal places:
Code: Select all
`Case #1: -5.1383833008Case #2: -7.5212485514Case #3: -5.4755549144Case #4: -22.0564143198Case #5: -14.7081045826Case #6: 2.1670052646Case #7: -2.8371366794Case #8: -64.6690314518Case #9: -2.8069371800Case #10: -6.3711452901Case #11: -0.1070479581Case #12: 9.9847964413Case #13: -4.9372260331Case #14: -5.3130527357Case #15: 5.2135842771Case #16: 3.0378944456Case #17: 5.2404084182Case #18: -8.1282949430Case #19: 1.4519873897Case #20: 0.7415996176`

And here's output from another accepted program, which uses double, and approximation by logarithms:
Code: Select all
`Case #1: -5.1383659629Case #2: -7.5212348259Case #3: -5.4755465033Case #4: -22.0564002421Case #5: -14.7080626664Case #6: 2.1670022202Case #7: -2.8371272209Case #8: -64.6689788484Case #9: -2.8069336197Case #10: -6.3711423685Case #11: -0.1070486464Case #12: 9.9847738878Case #13: -4.9372089784Case #14: -5.3130318235Case #15: 5.2135703089Case #16: 3.0378827475Case #17: 5.2403945592Case #18: -8.1282549736Case #19: 1.4519816612Case #20: 0.7415916422`

If you get similar answers and still WA, post you code here.
mf
Guru

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

mf wrote:Output from my first program (uses long double, and binomial identities), to 10 decimal places:
If you get similar answers and still WA, post you code here.

I also use long double , get the same result as yours.
Here is my code
Code: Select all
`AC . cutted`
Last edited by windows2k on Tue Aug 09, 2005 12:09 pm, edited 1 time in total.
windows2k
Experienced poster

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

Next