Eng During last 365 days Approved articles: 2078,   Articles in work: 295 Declined articles: 804 

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

Published in journal "Software systems and computational methods", 2012-1 in rubric "Educational software systems", pages 17-27.

Resume: 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: Software, international, olympaid, internet-olympaid, student, programming, informatics, problem, algorithm, solution

This article can be downloaded freely in PDF format for reading. Download article

1. Men'shikov, F. V. Olimpiadnye zadachi po programmirovaniyu / F. V. Men'shikov. SPb.: Piter, 2003. 315 s.
2. Porublev, I. N. Algoritmy i programmy. Reshenie olimpiadnykh zadach / I. N. Porublev, A. B. Stavrovskiy. M.: Izd. dom Vil'yams, 2007. 480 s.
3. Skiena, S. S. Olimpiadnye zadachi po programmirovaniyu. Rukovodstvo po podgotovke k sorevnovaniyam / S. S. Skiena, M. A. Revilla. M.: KUDITs-OBRAZ, 2005. 416 s.
4. http://24forums.ru/forum/topic_768.
5. http://e-maxx.ru/algo/segment_tree.
6. http://queens.cspea.co.uk/csp-q-1stsols.html.
7. http://ru.wikipedia.org/wiki/Dvoichnyy poisk.

Correct link to this article:
just copy this link to clipboard