|
|
what about ternary search in this task? Edited by author 01.10.2020 22:01 Well I tried to do so but got wa4. I also looked at that guy's solution where he just takes the average of all p[i]. And I still cannot understand why it's right bcz, like, it's squared distance not just linear... Edited by author 29.07.2022 12:21 It's because of the first derivative. I tried it, and get WA4. I suspect I have a bug but idk where. I did some more digging. For those interested, try running your ternary search against the following test case (and then compare with the avg approach): ``` 20 9 8 5 12 5 6 89 45205 3554 1585 554422 654235 545324 548835 456432 804654 234758 444 5668 56435 ``` This in both cpp and python gives the wrong answer. By switching to the `Decimal` library in python, I was able to move past 4, and get TLE on 5. Using gmp in cpp might get you to AC, but I think the takeaway here is to only use ternary search when you can set the problem up to have an answer close to 0. 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 You may also see it in this way: the variance of samples x1..xn is the one that minimizes the sum of (xi-a)^2. I guess it's extremum, isn't it? We haven't learnt that makes it a little difficult( Edited by author 16.04.2016 23:55 I didn't know any extremums and others but now I know a little with this site: mathprofi.ru You are great, thank you! I haven't studied calculus yet, so i came up with the quadratic equation and it turns out to be correct, yet I don't even know how to prove it. А мне жалко стану, которая до сих пор живёт так( Да боже. Вы, тупые нытики, даже на сайте с программированием ноете. Как же вы задолбали уже. Никто так не живёт 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); } } public class HeatingMain1457_Accepted { public static void main(String[] args) { PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out)); Scanner x = new Scanner(System.in); short n = x.nextShort(); double s = 0; for (int i = 0; i < n; i++) { s += x.nextInt(); } writer.printf("%.6f", s / n); writer.close(); } } 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 The solution is to use format method of String class !!! System.out.print(String.format("%.6f",somme)); But still don't understand why the format method of NumberFormat class doesn't work !!! Edited by author 25.11.2010 03:30 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)); } } #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; } Man you're awesome! I'm sure your solution is the best among 3000 others! Not true.You should initialize sum = 0 or it will be a trash number. Edited by author 09.09.2012 18:47 Edited by author 09.09.2012 18:47 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. |
|
|