10883 - Supermean
Moderator: Board moderators
-
- Experienced poster
- Posts: 105
- Joined: Wed May 25, 2005 7:23 am
Supermean
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 ?
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 ?
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.)
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.)
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
Riyad
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
-
- Experienced poster
- Posts: 131
- Joined: Sat Jul 17, 2004 4:09 am
- Location: Lima, Per
Hi, would you mind giving me an example of your algorithm?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.
Thx in advance.
Code to compute 200C100 / 2^99 (written directly here, no guarantees it worksAntonio Ocampo wrote:Hi, would you mind giving me an example of your algorithm?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.
Thx in advance.
![;)](./images/smilies/icon_wink.gif)
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--; }
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)
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)
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
http://online-judge.uva.es/board/viewtopic.php?t=8586
http://online-judge.uva.es/board/viewtopic.php?t=8591
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:](./images/smilies/icon_wink.gif)
![:wink:](./images/smilies/icon_wink.gif)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org