An OEIS week

TopCoder SRM 712 took place on Tuesday, April 18 (problems, results, top 5 on the left). The results remind me of the second SRM that I prepared myself - two accepted solutions on the medium, and none on the hard :)

The reason for such crushing difficulty of the medium problem was the fact that the most obvious solution did not work because of catastrophic cancellation in floating-point computations. I do not want to go into the details of this particular problem here, so I will refer you to the post-match discussion for the details of how my solution overcame this obstacle.

More generally, I think understanding how floating-point numbers work is not that hard, and it pays off not just in such black-and-white cases like this problem, but also in more subtle situations, for example when thinking about whether an eps is required or not in comparisons in a geometry problem, and how big it should be if it's required. I think at some point this misof's tutorial was the eye-opener for me with regard to floating-point computations, so I heartily recommend it. At the same time, it's quite likely that even more useful tutorials on floating-point numbers have been published since then, so please point those out in comments!

Yandex.Algorithm 2017 started with its Warm-up round on Saturday (problems, results, top 5 on the left, analysis). It was enough to solve any problem to advance, and thus the first place did not hold much tournament value; nevertheless, it was still the first place. Congratulations to kusas2018 on the victory!

Google Code Jam 2017 Round 1B followed in a little over an hour (problems, results, top 5 on the left, analysis). The problems were not as tricky as in Round 1A, and JAPLJ had to be really fast to beat the second place by less than a minute!

No April weekend is complete without an Open Cup round, this time the penultimate Grand Prix of Moscow Workshop (results, top 5 on the left, analysis). The SPb ITMO 1 team has clinched the first place in the overall standings with a win in this round - the first season in a while where Gennady's team could not win the Open Cup. Big congratulations to Ivan, Ilya and Vladimir!

Problem B was a nice mathematical puzzle that did not crack for our team: one needed to construct a completely multiplicative function f(x) such that f(x)=1 or -1, f(a*b)=f(a)*f(b), and that for each n between 1 and 1000000 the prefix sum f(1)+f(2)+...+f(n) does not exceed 20 by absolute value. Do you see a way?

And finally, Codeforces held the Elimination Round for another company-sponsored tournament: the Tinkoff Challenge (problems, results, top 5 on the left, analysis). LHiC held the first place despite failing one of the problems during the system test, thanks to being the only one to solve both problems E and F. Well done!

In my previous summary, I have mentioned several problems, and this AtCoder problem allows me to share an interesting experience, so I will explain it. We are given a long (10⁹) segment. Some (at most 10⁵) integer points on the segment are special. We consider all ways to take some set of non-special integer points on the segment. Each such set splits the segment into smaller segments. Let's find the product p of their lengths, and then compute the sum of the squares p² of those products over all ways. What number are we going to get, modulo 10⁹+7?

For quite some time, I had no clue how to approach it. I've started to think about an easier version: what if there are no special points? Even for that problem, I could not come up with a solution that's fast enough for 10⁹. However, I could come up with a somewhat straightforward O(n²) dynamic programming approach: to find the answer for a given length, we will simply iterate over all possibilities for the last segment and use the answers for smaller lengths that were computed previously.

I've implemented this solution quickly, obtained the answers for small values of n, and entered them into the OEIS search which yielded me this sequence. For a moment it seemed that the OEIS entry is not very helpful, but then I noticed the generating function (x+1)/(1-4x+2x²-x³), which is in a form of polynomial fraction, which means that the elements of the sequence correspond to a linear recurrence a_n=4a_n-1-2a_n-2+a_n-3. In order to see that, we can rewrite the equation for the generating function like this:

(a₀x⁰+a₁x¹+...)*(1-4x+2x²-x³)=(x+1)

Since the right part is a finite polynomial, so is the left part, and it means that the coefficient near xⁿ in that product is 0 for almost all values of n, and expanding the product allows us to find that the coefficient near xⁿ is a_n-4a_n-1+2a_n-2-a_n-3, which directly yields the recurrence.

Finding the 10⁹-th element of a linear recurrence is a standard task that can be solved using fast matrix exponentiation, so we have now solved the version of the problem without the special points. The answer is given by (some element of) the product Mⁿv where M is some matrix and v is some vector.

Now suppose we have exactly one special point y. We need to subtract the decompositions that use this special point, and that means that if f(n) is the answer without special points, then the answer with one special point is equal to g(n)=f(n)-f(y)*f(n-y). We can now rewrite it using the formula for f(n) that we have: g(n)=Mⁿv-f(y)*M^n-yv=Mⁿv-f(y)*MⁿM^-yv=Mⁿ(v-f(y)*M^-yv). In other words, g(n) has the same form: the n-th power of the matrix M times some vector!

It's not hard to generalize this to any amount of special points. I.e., with the second special point placed at z we will have h(n)=g(n)-g(z)*f(n-z) which transforms in exactly the same way, and so on. Each special point is handled in logarithmic time (to compute f(y) and M^-y), so the overall running time is O(mlogn), where m is the number of special points.

This story is quite the opposite to the approach I have shown in two previous posts: here we do not build any meaningful intuition about the problem, and instead try to almost mechanically build something that works using random facts found on the Internet.

Of course, this problem has a more sensible solution, which you can find in the official analysis. Thanks for reading, and check back soon!