A week modulo 3

TopCoder SRM 713 opened the last week of April (problems, results, top 5 on the left). Once again, nobody has managed to solve the hard problem. Endagorion was the fastest on the first two, and defended his lead during the challenge phase with a +50. Well done!

Yandex.Algorithm 2017 Qualification Round was available as a virtual contest for the whole Saturday (problems, results, top 5 on the left, analysis). Egor has dominated the round thanks to very fast problem solving, and the most appropriate strategy: get one problem accepted in the open to ensure qualification, and then submit the rest blindly to minimize the penalty time. Very well executed!

Russian Code Cup 2017 Qualification Round 3 also took place on Saturday (problems, results, top 5 on the left, analysis). -XraY- fought back after missing the top 200 in the first qualification round and solved all problems cleanly and so fast that his penalty time is more than 2x smaller than that of the second place - amazing!

The final Open Cup round of the 2016-17 season took place on Sunday, the Grand Prix of Ural (results, top 5 on the left, overall Open Cup results, top 5 on the left). Team Past Glory did not really leave much doubt as to who would win this round, solving 12 problems 1.5 hours before the end of the contest, and having all the time in the world to solve the tricky geometric problem F. Congratulations on the victory!

Problem E was a great example of a non-obvious problem that still requires almost pure creativity to solve, instead of mathematical theorems, algorithms or data structure knowledge. It is an interactive problem. You are given six six-sided dice, each having some digits and mathematical symbols written on it, as follows:

Die 1: = < > != <= >=
Die 2: 4 + - ( ( )
Die 3: 0 / / / 8 +
Die 4: 2 3 4 5 - )
Die 5: + - * / 1 9
Die 6: 6 7 + - ( )

You need to pick a die, then roll it (by interacting with the judge program), and record the symbol that appears. Then you can do it again, using either the same or a different die, and so on, doing at most 1000 rolls. At some point you need to stop rolling, and form a correct mathematical expression (equality or inequality) by concatenating all recorded symbols in some order. No need to optimize anything - just build any correct expression after at most 1000 rolls.

How would you approach this problem?

In keeping with the new trend of having multiple competitions at the same time, Google Code Jam 2017 Round 1C took place in the middle of the Open Cup (problems, results, top 5 on the left, analysis). It was EgorKulikov who followed Eryx's strategy from Round 1A this time, submitting the super tricky hardest problem much earlier than everybody else. Congratulations on the victory!

In my previous summary, I have mentioned another Open Cup problem: 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.

When trying to solve it, I was approaching it in the way that many recent "constructive" problems were meant to be solved: try a few things on the computer, maybe do some local optimizations, and it should work. However, I did not manage to find success on this path.

It turns out that there is a solution that can be easily done on paper without using any computer time. Let's define f(3k+1)=1, f(3k+2)=-1, f(3k)=f(k). The multiplicativity follows from the fact that powers of 3 do not impact the value of the function, and numbers 1 and 2 modulo 3 are the same as 1 and -1 modulo 3. Finally, almost all numbers in the prefix sum cancel out: if we look at positions not divisible by 3, 1 and -1 alternate, so the prefix sum of those positions is always 1 or 0. For positions divisible by 3, but not by 9, the same argument applies, and so on; thus each prefix sum will never exceed log₃1000000 (one for each power of 3), which is less than 20.

Thanks for reading, and check back soon for the last week's summary!