what about ternary search in this task?



Edited by author 01.10.2020 22:01

f(x) = (x-7)^2 + (x-4)^2 + (x-5)^2
Find x such that f(x) (cost function) is a minimum.

df/dx = 2(x-7) + 2(x-4) + 2(x-5) = 0
3x = 7+4+5
x = (7+4+5)/3

The biggest hurdle is the problem statement itself!

solution on the surface, take a look at the arithmetic mean P

Those who are getting WA4 when using C#, please use the following format to print out the output. The type of variable sum is double and individual numbers read in the second line are also converted to double first before adding them together.

Console.WriteLine("{0:F6}", sum / cases);

In the fine tradition of "digging deeper," I wanted to understand the solution to this problem more completely.   I mean, when I read the problem statement, it did not jump out at me instantly that the value of x that minimizes

 f(x) = k/n * ((x-a1)^2 + (x-a2)^2 + ... + (x-an)^2) is the artihmetic mean of a1...an

If you look at the example, you may think "Aha!  The output is the average of the input!"  But the solver must beware, test writers just love to mislead by simple example cases that do not reveal the entire subtlety of the problem.   They'll get you with one of those WA#12s if you're not careful.

So I dusted off my calculus and recalled that to calculate the min/max of a function, find the derivative of f(x) and set it to zero, and then solve for x.  So here we go...

f(x) = k * (x^2 -2(a1)x + (a1)^2 + x^2 -2(a2)x + (a2)^2 + ... + x^2 -2(an)x + (an)^2) / n
      = k (x^2 - (2/n)(a1 + a2 + ... + an)x + ((a1)^2 + (a2)^2 + ... + (an)^2)/n

so we have
f'(x) = k(2x - (2/n)(a1 + a2 + ... + an))
setting to zero and solving for x gives

x = (a1 + a2 + ... + an) / n

Voila!  Not a guess, but good solid derivation.   Oh, and we can be sure that this is minimum rather than a maximum because the function is an upward opening parabola (since we assume that k is positive).


Edited by author 04.10.2012 01:16

deleted

Edited by moderator 11.08.2022 18:56

Edited by author 09.09.2019 23:30

double res = ...;
cout << setprecision(6) << fixed << res;

Задача - бомба!
Подсказка - производная...

Edited by author 07.09.2017 16:41

Edited by author 07.09.2017 16:41

If you have WA4 java. Put 10^7  instead of 10^6

f(x) = k * (x^2 -2(a1)x + (a1)^2 + x^2 -2(a2)x + (a2)^2 + ... + x^2 -2(an)x + (an)^2) / n
      = k (x^2 - (2/n)(a1 + a2 + ... + an)x + ((a1)^2 + (a2)^2 + ... + (an)^2)/n

so we have
f'(x) = k(2x - (2/n)(a1 + a2 + ... + an))

question: what is k?
(explaining from previus post)

Edited by author 05.05.2016 14:53

Edited by author 05.05.2016 14:54

cycle for,no more.

import java.util.Scanner;
public class easys {
 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int sum = 0;
        int curr = 0;
        double result = 0.0;
        for(int i=0;i<N;i++){
            curr = in.nextInt();
            sum = sum + curr;

        }
     result = (double)sum/N;
        System.out.printf("%.6f",result);

    }

}

import java.util.Scanner;

public class AcmTimusRu {
    public static void main(String argv[]) {
        String[] nf = new String[0];

        Scanner s = new Scanner(System.in);

        double somme = 0;
        double n = s.nextLong();

        for (int i = 0; i < n; i++) {
            somme += s.nextLong();
        }

        System.out.print((somme / n));
    }

}

import java.text.NumberFormat;
import java.util.Scanner;

public class Heatingmain
{
    public static void main(String argv[])
    {
        NumberFormat nf = NumberFormat.getInstance();
        nf.setMaximumFractionDigits(6);
        nf.setMinimumFractionDigits(6);

        Scanner s = new Scanner(System.in);

        double somme=0;
        double n = s.nextLong();

        for (int i = 0; i < n; i++) {
            somme += s.nextLong();
        }

        System.out.print(nf.format(somme/n));
    }


}

Edited by author 25.11.2010 03:26

#include <iostream>
#include <cstdio>

using namespace std;

int main()
{
    int N;
    double sum;
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
    {
        int p;
        scanf("%d", &p);
        sum += (double)p;
    }
    sum /= double(N);
    printf("%.6lf", sum);
    return 0;
}

Well, i started to store input in array like this

...
int [] hatches = new int[n+];
...

After that converted them into double. That ended with WA4

changed to double [] hatches = new double[n+];
and i got ACed.