online-judge.uva.es

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

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.

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.

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.

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

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

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)

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.

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

Oops... sorry about that :wink:

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

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

There are two threads discussing this problem:
http://online-judge.uva.es/board/viewtopic.php?t=8586
http://online-judge.uva.es/board/viewtopic.php?t=8591

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.

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:

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

by mf » Tue Aug 09, 2005 11:18 am

Some simple cases:

Code: Select all: 5 1 0 1 -1 1 1 1 -555.5559 1 555.5559

Output:

Code: Select all: Case #1: 0.000 Case #2: -1.000 Case #3: 1.000 Case #4: -555.556 Case #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.1383833008 Case #2: -7.5212485514 Case #3: -5.4755549144 Case #4: -22.0564143198 Case #5: -14.7081045826 Case #6: 2.1670052646 Case #7: -2.8371366794 Case #8: -64.6690314518 Case #9: -2.8069371800 Case #10: -6.3711452901 Case #11: -0.1070479581 Case #12: 9.9847964413 Case #13: -4.9372260331 Case #14: -5.3130527357 Case #15: 5.2135842771 Case #16: 3.0378944456 Case #17: 5.2404084182 Case #18: -8.1282949430 Case #19: 1.4519873897 Case #20: 0.7415996176

And here's output from another accepted program, which uses double, and approximation by logarithms:

Code: Select all: Case #1: -5.1383659629 Case #2: -7.5212348259 Case #3: -5.4755465033 Case #4: -22.0564002421 Case #5: -14.7080626664 Case #6: 2.1670022202 Case #7: -2.8371272209 Case #8: -64.6689788484 Case #9: -2.8069336197 Case #10: -6.3711423685 Case #11: -0.1070486464 Case #12: 9.9847738878 Case #13: -4.9372089784 Case #14: -5.3130318235 Case #15: 5.2135703089 Case #16: 3.0378827475 Case #17: 5.2403945592 Case #18: -8.1282549736 Case #19: 1.4519816612 Case #20: 0.7415916422

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

by **windows2k** » Tue Aug 09, 2005 11:41 am

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

online-judge.uva.es

10883 - Supermean

10883 - Supermean

10883

10883

Who is online