Solutions for previous problems

I can't resist to complete my previous questions with answers.

First, about the integral of f' squared being not less than the integral of f squared.

Read more

First, I'll write the proof:

0<=int((f'(x)-cot(x)*f(x))^2)=int(f'(x)^2)-2*int(f'(x)*f(x)*cot(x))+int(cot(x)^2*f(x)^2)=A-2B+C, where cot(x) is cos(x)/sin(x).

Let's simplify each of A,B and C by itself. The most interesting is B:

B=int(f'(x)*f(x)*cot(x)), and integration by parts yields B=f(3)*f(3)*cot(3)-f(0)*f(0)*cot(0)-int(f(x)*f'(x)*cot(x)+f(x)*f(x)*(1-cot(x)^2))=-B-int(f(x)*f(x)*(1-cot(x)^2)), thus -2B=int(f(x)*f(x)*(1-cot(x)^2)), and substituting that to the original inequality we get 0<=A-2B+C=int(f'(x)^2)+int(f(x)^2*(1-cot(x)^2))+int(f(x)^2*cot(x)^2)=int(f'(x)^2)-int(f(x)^2), q.e.d.

We've used that 0=f(0)*f(0)*cot(0) (well, we don't have cot(0) really, but we should interpret this as a limit from right), but that's easy because f(0)=0 and it has a derivative, thus is at most linear around zero, thus f(0)*f(0) is at most quadratic, and cot(x) is 1/linear, thus together they still stay at most linear.

This proof won't work if we substitute 3 with something larger than pi (because cot won't be defined at pi, and that integration by parts wouldn't be possible), and it helps to see that if we replace 3 with pi exactly, then equality would be achieved when f(x)=K*sin(x) (one can see from the above proof that when 3 is 3, equality is possible only if f(x) is always zero), and moreover, when 3 is replaced with something more than pi (say, k), then sin(x*pi/k) would provide a counterexample.

But what's bad (and interesting :)) about this proof is that starts from the end. It takes a seemingly weird combination of f'(x) and f(x), and that combination turns out to be exactly what we need. But how do we invent that? I don't know. As Jedal points in comments to the original problem statement, this has to do with f'(x)^2-f(x)^2 having some physical meaning when f(x) is a position of a body attached to a spring as a function of time, and sin(x) being the real trajectory of that body, thus delivering the extremum of that function. But I can't say I understand much of that.

Second, about the problem being solvable faster than O(n^2).

Read more

When we look closer at the sum being calculated, we see that everything except gcd is a polynomial on w and h, and sum of poly(w,h) over w from 0 to n is a polynomial over h and n, and repeating that for h, we'll get a polynomial over n and m that can be evaluated in O(1). But how to deal with gcd? We're looking at a sum of (n-w+1)*(m-h+1)*gcd(w,h). Let's iterate over w, then this is reduced to sum of (m-h+1)*gcd(w,h). Since we're already doing O(n) iterations and want to be under O(n^2) total, we need to do that sum faster than O(n). And here's how: let's group its terms where gcd(w,h)=k. Since k is a divisor of w, there can be only so much of those (I can't invent an exact formula now), so if we count all the terms with gcd(w,h)=k in O(1), then we're done. We need to count the amount of values for h such that gcd(w,h)=k, and the sum of those values. When we replace "gcd(w,h)=k" by "k divides gcd(w,h)", the answer is simple - we just need to examine values of form k*a, where a is integer. But then, we can obtain the values we need via inclusion-exclusion principle, and while this isn't O(1), it's still fast enough: the number of iterations for each w will be comparable to the amount of pairs (a,b) such that a divides b and b divides w, which is still much less than w (for each p^k in the prime decomposition of w we get (k+1)*(k+2)/2 choices for a and b, which is much less than p^k for large p's).

Phew. That was long, difficult to understand, impractical, and whatever (and quite probably wrong somewhere).

And last but not least, here is the screencast from SRM 422. It might be funny when I try to Google the solution for the hard problem, and when I fix my solution in last minutes by adding many random tries until a second runs out :)

Read more

Streaming: http://77.41.63.3/topcoder/screencast/srm422/stream.html. I believe you need at least Flash 9 to view that.
Download: http://77.41.63.3/topcoder/screencast/srm422/srm422.avi or http://77.41.63.3/topcoder/screencast/srm422/srm422.mov or (when my server goes down)http://narod.ru/disk/3267201000/srm422.avi.html (this is in Russian, but the only thing you need to do is to solve the CAPTCHA just above the green button, and then press the green button; there might also be a checkbox on Firefox and IE asking to install a toolbar - uncheck it). The file is about 50M.

If you have problems viewing, please tell - I'm still trying to figure out the right setup for this.