Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

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:

Software, international, olympaid, internet-olympaid, student, programming, informatics, problem, algorithm, solution


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


References
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