Galochkin V.I. The tasks of the final round of the Interna tional Internet-Olympiad in Informatics and Programming for students of Russia and neighboring foreign in 2012

Abstract: The article contains the solution of all nine Olympiad tasks. The subjects of those tasks are related to the construction of rational data structures, integer arithmetic, computational geometry, graph computations, heuristics sele ction and extremes finding. An algorithm of finding the maximum bandwidth on graph edges for two nonintersecting paths if given. This algorithm with almost no change can be used to find two nonintersecting paths on a graph of minimum total cost. The article discloses a way to determine the possibility of a non-rotating separation of a flat geometric figure in a polygon shape cut. One of the problems has significantly increased the dimen sion of the source data com pared to the known problem. The article suggests a solution with two different ways of solving the task, depending on the dimension of the original data. The rest of the tasks are alike to well known, but require a different solution. Those are the problem of placing queens on the chessboard and the problem of optimum sawing lumber.

Keywords: