A week in memory of Leo

The Jun 25 - Jul 1 week presented the last of the last chances to progress in TopCoder Open 2018 with its Round 2C on Tuesday (problems, results, top 5 on the left, parallel round results with 2/3 shared problems, analysis). This round was ran in honor of Leopoldo Taravilse, who has tragically passed away recently. It was really sad to hear this news, and I express my sincere sympathy to Leopoldo's family and friends.

fruwajacybyk has squeezed out the first place through challenges from Min,lu and tozangezan who led after the coding phase. Well done!

Codeforces held its Round 493 on Sunday (problems, results, top 5 on the left, analysis). fjzzq2002 dominated the proceedings, solving all problems with 20 minutes to spare while everybody else could manage at most four. Congratulations on the impressive performance!

Problem D, after removing a somewhat artificial complication, boiled down to the following cute combinatorial puzzle: you are given a tree with n<=2000 vertices. How many cycles of length 1, 2, ..., k (k<=75) does it have, modulo 998244353? A tree does not have simple cycles, so we're interested in non-simple cycles of course. Two cycles that differ only by choosing the starting point and direction are still considered different.

In my previous summary, I have mentioned another Codeforces problem: you are given a prime modulo p up to 10⁹ and two numbers u and v between 0 and p-1. In one step, you can either add one modulo p, subtract one modulo p, or take inverse modulo p. You need to obtain v from u in at most 200 steps (the solution doesn't need to be the shortest).

This problem allows many approaches, so I'd like to share a bit more how my thinking went. I've started to write down which numbers we can get in a few steps, like u+1 or 1/(u+1) or 1+1/(u+1)=(u+2)/(u+1). Then I've noticed that if we represent our current number as x/y, then the three operations we have are x->x-y, x->x+y, and swap(x,y). This has strongly resembled the Euclidean algorithm, which can go from (x,y) to (0,gcd(x,y)) using those operations. Now I had a sketch of the solution: we'll represent u as (u*k mod p)/k, then apply the Euclidean algorithm to go from u to 0. Now we do the same for v, and since all operations are reversible, we can now go from u to 0 to v.

However, the Euclidean algorithm takes a small (logarithmic) number of steps only if we have the modulo operation available. With just subtraction, it can take a lot of steps - for example, if we pick k=1, then we'll start with u/1 and need u steps to get to 0 just subtracting 1 every time. So we need to choose k wisely so that the number of steps to get from u to 0 will not exceed 100.

First I tried to find k so that (u*k mod p)/k is as close to the golden ratio as possible, as the golden ratio is the case where the Euclidean algorithm proceeds in the fastest way. However, this did not work as sometimes just being close is not enough, and on last steps we still start making too many subtractions. But then I've realized that I can just try random values of k until I find one that works, and this ended up working flawlessly.

Thanks for reading, and check back for more!