A trigonometric week

The Oct 7 - Oct 13 week had TopCoder SRM 768 (problems, results, top 5 on the left, analysis). My solution to the medium problem turned out to be a bit simpler than the author's approach. Here is the problem statement: n players are competing in a tournament. Each player has an integer strength which is 1, 2 or 3. In one round of the tournament, we pick two random remaining players, and the one with the lower strength is eliminated. In case their strengths are equal, we eliminate one of them at random (each with probability 0.5). In the end only one player remains, and the order of elimination is the ranking of the players. What is the expected rank of a player with strength 2? Your input is three numbers, the number of players with strength 1, 2 and 3 respectively, each up to 2000.

The fifth Open Cup stage, the Grand Prix of Korea, took place on Sunday (problems, results, top 5 on the left, analysis). Team Polish Mafia was way ahead of everybody else this time, solving 10 problems to the second place's 8, and bringing the number of stage victories between the three strongest veteran teams to 2-2-1 (as a sneak peek into the present, no other team managed to win a stage in 2019). Congratulations!

In my previous summary, I have mentioned an AtCoder problem: you are given 3000 points on the circumference of the unit circle. What is the expected position of the center of the circle inscribed in a triangle formed by a random triple of those points?

A cubic solution is straightforward: iterate over all triples, find the center of the incircle, find the average of those. However, it will not fit in the time limit.

The most typical way to speed up this type of computation is to somehow decompose the inner expression into parts which depend on only one or two out of three points, and then depending on what "decompose" means exactly we can use partial sums, or FFT, or some other trick to find the sum while only iterating over points or pairs of points, therefore obtaining a quadratic solution.

At this point I've looked at the Wikipedia article to find a formula that can be decomposed. The barycentric coordinates sin(A):sin(B):sin(C) caught my eye for the following reason: since in this problem all points lie on a circle, the angle A only depends on the locations of the points B and C and not on the location of point A (this is a middle/high school geometry theorem; more precisely, there are two possibilities for the angle A depending on which side of BC does the point A lie). This is exactly the "depends on only two out of three points" property we're looking for.

The barycentric coordinates formula looks like

(x_A,y_A)*sin(CAB)/(sin(CAB)+sin(ABC)+sin(BCA))+... (the rest is symmetric terms for B and C)

We need to sum this over all triples, so the total coefficient next to (x_A,y_A) is the sum of

sin(CAB)/(sin(CAB)+sin(ABC)+sin(BCA))

over all values of B and C. Each individual sin() depends only on two points, but they are still combined together in one term, so we need to decompose further.

Let's denote the angle ABC as β, and the angle BCA as γ, the angle CAB can be found as π-β-γ, and since sin(π-β-γ)=sin(β+γ) we have

sin(β+γ)/(sin(β)+sin(γ)+sin(β+γ))

The main difficulty here lies in the fact that we have a sum in denominator, but we want a product, since those are easier to decompose. We can use another fact from middle/high school (which I googled of course), this time from trigonometry, and replace sin(β)+sin(γ) with a product like this:

sin(β+γ)/(2*sin((β+γ)/2)*cos((β-γ)/2)+sin(β+γ))

Now we have trigonometric functions of (β+γ)/2 and of β+γ, to make things simpler we can replace sin(β+γ) using another middle/high school formula to get:

2*sin((β+γ)/2)*cos((β+γ)/2)/(2*sin((β+γ)/2)*cos((β-γ)/2)+2*sin((β+γ)/2)*cos((β+γ)/2))

Here we get a confirmation that we are on the right track: the multiplier 2*sin((β+γ)/2) appears both in the numerator and in the denominator and cancels out! So we have just

cos((β+γ)/2)/(cos((β-γ)/2)+cos((β+γ)/2))

Now we can use yet another trigonometric formula, for the cosine of sum, to get:

(cos(β/2)*cos(γ/2)-sin(β/2)*sin(γ/2))/(cos(β/2)*cos(γ/2)+sin(β/2)*sin(γ/2)+cos(β/2)*cos(γ/2)-sin(β/2)*sin(γ/2))

The term sin(β/2)*sin(γ/2) cancels out in the denominator, so we have just:

(cos(β/2)*cos(γ/2)-sin(β/2)*sin(γ/2))/(2*cos(β/2)*cos(γ/2))

Or even simpler

1/2*(1-tan(β/2)*tan(γ/2))

Finally, this is decomposed enough. Even though β and γ are not chosen completely independently (the points have to be in the right order on a circle), for each particular value of β (in other words, after fixing the points A and C) we need to find a prefix sum of tan(γ/2) over a range of possible points B, therefore we can precompute those prefix sums after fixing the value of A and obtain a quadratic solution (here is my code).

I agree that this does look a bit like bashing the formula until some parts magically cancel out, but for me it felt like that both choosing the formula to bash (the one with angles, since those depend only on two points), and the way of bashing (trying to get a product instead of a sum in the denominator) were actually guided by the algorithmic constraints of the problem, and therefore were not so dependent on luck.

Thanks for reading, and check back for more!