10883 - Supermean

[mf]

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.

[windows2k]

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

[mf]

I've sent you modified code by private message.

[sunnycare]

hi every kind man
i have taken your advisers.
but got WA...
it has spoiled me whole day....
so i need your help .....
my prog is here..

Code: Select all

//10883 Supermean
#include <cstdio>
#include <cmath>
//#include <ctime>
using namespace std;
double a[50000];
long test,tst,n,i,j;
void f()
{
    double nCr;
    long i;
    double s=0;
    double z=(n-1)*(double)log10((double)2);
    
    nCr=0;
    double tmp=log10(a[0])-z;
    if(tmp>-7)
        s+=(double)pow((double)10,tmp);
    for(i=1;i<n;i++)
    {
        nCr+=(double)log10((double)(n-i)/(double)i);
        tmp=nCr-z;
        
        if(tmp>-15)
            s+=a[i]*(double)pow((double)10,tmp);
        
    }
    a[0]=s;
}
int main()
{
    //clock_t beg;
    scanf("%ld",&test);
    //beg=clock();
    for(tst=1;tst<=test;tst++)
    {
        
        scanf("%ld",&n);
        for(i=0;i<n;i++)
            scanf("%lf",a+i);
        f();
        printf("Case #%d: %.3lf\n",tst,a[0]);
    }//printf("process cost time:%d\n",clock()-beg);
}

[mf]

The first number in the given sequence may be negative or zero. And you're taking its logarithm in this line:

Code: Select all

double tmp=log10(a[0])-z;

[sunnycare]

thanks...
ac now.

[alirezanoori]

Hi,
I've read these posts and came with a solution, but I have a minor problem with the 2 ^ n part.
Could you please take a look at my code and help me?
Thanks in advance.

Code: Select all

#include <iostream>
#include <cmath>
using namespace std;

double arr[50000];
int n;

long double newComb(long double oldCm, int n, int i)
{
	if(i == 0)
		return 1;
	if((n + 1 - i) == 0)
		return 1;

	long double oldLog = log(oldCm);
	long double log2 = log((long double)(i));
	long double log1 = log((long double)(n + 1 - i));
	long double newLog = oldLog + log1 - log2;
	return exp(newLog);
}

void process()
{
	long double Cm = 1;
	long double sum = 0;
	n--;
	long double pw = pow((long double)2.0, n);
	for(int i = 0; i <= n; i++)
	{
		Cm = newComb(Cm, n, i);
		sum += Cm / pw * arr[i];
	}
	cout << fixed << showpoint << setprecision(3) <<  sum << endl;
}

int main()
{
	int tc;
	cin >> tc;
	for(int i = 0; i < tc; ++i)
	{
		cin >> n;
		for(int j = 0; j < n; ++j)
			cin >> arr[j];
		cout << "Case #" << i + 1 << ": ";
		process();
	}

    return 0;
}

[helloneo]

Hi,
I've read these posts and came with a solution, but I have a minor problem with the 2 ^ n part.

Maybe somehow you can use n * log(2) instead of calculating pow(2, n)

[alirezanoori]

And how could I do that?

[alirezanoori]

Well, I managed to convert the formula to this format:
result = Sigma exp(log(a) + log(nCi) - (n * pow(2.0))
It works really great for positive numbers, but when it comes to negative numbers, program fails (because of log(a) part).
Any suggestions?

[helloneo]

Well, I managed to convert the formula to this format:
It works really great for positive numbers, but when it comes to negative numbers, program fails (because of log(a) part).
Any suggestions?

How about this way..?

Code: Select all

if (a[i] > 0)
    result += exp(log(a[i]) ....);
else
    result -= exp(log(-a[i]) ....);

[alirezanoori]

Well, I changed my code to this, still WA!

Code: Select all

long double newComb(long double oldLog, int n, int i)
{
	if(i == 0)
		return log(1.0);
	if((n + 1 - i) == 0)
		return log(1.0);

	long double log2 = log((long double)(i));
	long double log1 = log((long double)(n + 1 - i));
	long double newLog = oldLog + log1 - log2;
	return newLog;
}


void process()
{
	long double Cm = log(1.0);
	long double sum = 0, cur;
	n--;
	double pw = n * log(2.0);
	for(int i = 0; i <= n; i++)
	{
		Cm = newComb(Cm, n, i);
		if(arr[i] > 0)
		{
			cur = log(arr[i]) + Cm - pw;
			sum += cur;
		}
		else
		{
			cur = log(-arr[i]) + Cm - pw;
			sum += exp(cur);
		}
	}
	cout << fixed << showpoint << setprecision(3) <<  sum << endl;
}

[sitz]

Hi!
I tried this problem with algorithm mentioned here: http://www.algorithmist.com/index.php/UVa_10883
which is: ((n-1)C0 * a1 + (n-1)C1 * a2 + .....+(n-1)Cmid-1 * a mid + ... + (n-1)C0 * an) / 2 ^ (n-1)

As we have nCr = nCn-r, so, i just modified the algorithm to this:
((n-1)C0 * a1 + (n-1)C1 * a2 + .....+(n-1)Cmid-1 * a mid + ... + (n-1)Cn-1 * an) / 2 ^ (n-1)

i.e. sum of products of coefficients with the given numbers, but, it gives WA ( I'm using double for storing nCr and modular exponentiation for 2^(n-1)

Also, can it be done without using logarithms

Regards,
-SITZ

[Sabiha_Fancy]

I am trying to understand this problem but failed. Can anyone explain how to solve this problem ?

[brianfry713]

"What's a supermean," you ask? I'll tell you. List the n given numbers in non-decreasing order. Now compute the average of each pair of adjacent numbers. This will give you n - 1 numbers listed in non-decreasing order. Repeat this process on the new list of numbers until you are left with just one number - the supermean.

First sample input n = 1 so the input number is the supermean.
Second sample input n = 2 so the supermean is the same as the average.
Third sample input: 1 2 3 becomes 1.5 2.5 then 2
Fourth sample input: 1 2 3 4 5 becomes 1.5 2.5 3.5 4.5 then 2 3 4 then 2.5 3.5 then 3