News

Find Shortest Linear Recurrence using Berlekamp-Massey

Kamil Debowski from Poland was a special guest and IT guru of CodeIT's final for season 2022/2023. Kamil has been doing competitive programming for many years and he's been a finalist in a lot of international competitions. He has the ranks of Legendary Grandmaster on CodeForces and Target on Topcoder. He's the author of more than 300 problems for international coding competitions. He also has a YouTube channel where he goes by the nickname "Errichto" and in his videos he analyzes various algorithms and problems from competitions. His channel has more than 300 000 subscribers and his videos have been watched more than 12 million times.

At CodeIT's Guru lecture Kamil talked about Linear recurrences and algorithms that solve them quickly. One of the highlights of his presentation was the Berlekamp-Massey algorithm. This algorithm can identify and solve for values in linear recurrences very fast. Kamil compared this technique to two other known methods for finding linear recurrences: Gaussian elimination and Matrix multiplication. In many scenarios Gaussian elimination or Matrix multiplication would yield the right values for a problem, but in cases where the constraints to the problem are higher, then Berlekamp-Massey shines.

In the lecture Kamil gives several examples from personal experience and competitions that can be solved with Berlekamp-Massey. In the end, he shows two code snippets with implementations of the algorithm and shares advice how contestants can use it effectively in practice.

You can watch a full recording of the lecture here: