A Bresenham's week

The May 11 - May 17 week started with Codeforces Round 641 (problems, results, top 5 on the left, analysis). It was quite challenging for some contestants, and nobody could solve more than 4 problems out of 7. Um_nik solved his four in just one half of allotted time and won the round, congratulations!

TopCoder SRM 786 followed on Friday (problems, results, top 5 on the left, analysis). bqi343 had a 50-point lead after the coding phase, and increased it to 100 points during the challenge phase. Congratulations on the victory! These 5 qualification points have also made him a huge favorite to qualify to the TCO from the third online stage.

On Saturday Google held Code Jam 2020 Round 2 (problems, results, top 5 on the left). Placing in the top 1000 was the main goal in this round, but still Benq's jump to the first place with just five minutes remaining in the round was quite impressive, well done!

Open Cup 2019-20 Grand Prix of Serbia wrapped up the week on Sunday (results, top 5 on the left). Teams Polish Mafia, USA1 and NNSU Almost Retired solved 12 problems each, and the deciding factor was Polish Mafia's significantly fewer incorrect attempts. Congratulations on the win!

It was not announced before the round, but this Grand Prix was the last one of the Open Cup 2019-20 season (overall standings, top 10 on the left). The standings were very close at the top, but in the end we have a new champion. For only the second time since 2013, the champion team's last name list does not include Korotkevich :) Congratulations to the team USA1, and looking forward to even more competition at the top in the coming season!

In my previous summary, I have mentioned an Open Cup problem: a string of 0s and 1s is called balanced if the number of 1s in any two its circular substrings of the same length differs by at most 1. A circular substring of a string s is any string with the length not exceeding the length of s that can be read after we write s on a circle; in other words, it's either a normal substring of s, or a suffix of s concatenated with a prefix of s with total length not exceeding the length of s. You are given a string consisting of 0s, 1s and ?s. How many ways are there to replace each ? with a 0 or a 1 such that the resulting string is balanced? The length of the given string is at most 1024.

This setting reminded me of Bresenham's line drawing algorithm, so I tried to get balanced strings like this: let's draw a line from point (0,0) to point (x,y), then let's keep walking starting from point (0,0). We walk like this: if we are below the line, then we go up (increase the y-coordinate by 1), and if we are above the line, then we go right (increase the x-coordinate by 1). If we are on the line, then we go up unless the line is horizontal (y=0), in that case we always go right. We will reach the point (x,y) in x+y steps, and let's write down a 0 every time we go right, and a 1 every time we go up.

Intuitively, such strings should be balanced, as we're always walking very close to the line and all substrings of the same size should represent almost the same vector. Circular shifts of a balanced string are also balanced, so we need to also consider the circular shifts of the strings we get that way. It's not at all clear if there are other balanced strings, though. Imagine how happy I was when I found out that considering only such strings gets correct answers on all samples, and then was accepted by the judging system!

The resulting code is very simple, since the strings we get for different pairs (x,y) are all different, so we just need to find the period of each such string to determine the number of its different circular shifts, and do not need to otherwise check the strings we get for repetitions.

This was one of those rare cases where submitting a solution solely based on intuition and without having even a sketch of a proof worked out :)

Thanks for reading, and check back for more!