Charles Explorer logo
🇬🇧

Beads on a string

Publication at Faculty of Mathematics and Physics |
2019

Abstract

The article from the series dedicated to problems of Mathematical Olympiad - category P (programming) discusses different solutions of one practice competition problem. The task is to assemble the longest necklace from a sequence of multicolored beads, in which the beads are arranged according to their colour shades.

Each bead can be threaded to the left or to the right, or we can omit it. The algorithm builds on the known task of selecting the longest increasing subsequence from a given sequence of numbers.

Competing students were acquainted with a solution of this task in the school round of the competition. Besides the detailed analysis of the problem, we find in the article three basic variants of the solution with different time complexity.

Two of these solutions are written in the form of a sample program.