Конкурс по труднорешаемым задачам для программистов

    Здравствуй, хабрачитатель.

    С недавних пор мне нравится проводить конкурсы для программистов-математиков, но эти конкурсы несколько отличаются от олимпиад по программированию, хотя бы тем, что я предлагаю задачи, не имеющие эффективного алгоритма решения. Кроме того, предлагаются задачи, которые либо вообще никто раньше не решал, либо решали очень мало, но серьёзных успехов не добились. Последняя особенность этих задач в том, что они так или иначе связаны с перечислительной комбинаторикой, той областью математики, которая в России была похоронена вместе с другими полезными областями науки «сами знаете когда». Но это менее важно.



    Примером такого конкурса является конкурс по задаче о расстановке 6 ферзей на шахматной доске размером n×n. Впервые она была решена именно в рамках моего конкурса (была получена явная формула числа всех конфигураций) и вызвала резонанс в среде тех исследователей, которые занимаются задачами перечислительной комбинаторики. Сама формула позволила исследователям этой задачи строить новые и более сильные гипотезы. Подробнее свою позицию по отношению к такого рода задачам я выражал на Хабре в этой статье.

    Другой конкурс, связанный с физикой полимеров, в будущем позволит показать исследователям в этой области, что решётки с дефектами тоже вполне поддаются обсчёту, как и решётки без дефектов, практически нереальные в реальном мире. Это было показано на примере расчёта «предгамильтоновых» циклов. Соответствующий конкурс был подкреплён статьёй про метод динамического программирования. Алгоритм, описанный в этой статье (при соответствующей реализации) на сегодняшний день является самым быстрым в мире (скромно, но так и есть). При более серьезной вычислительной мощности можно было бы говорить о получении существенных результатов в перечислительной комбинаторике… но мечтать не вредно. Короче говоря, этот конкурс тоже оказался полезным для науки.

    Теперь я провожу один конкурс «просто так», даже без призового фонда, и предлагаю решить не самые сложные задачи из моего репертуара. Зачем? Просто чтобы любители посоревноваться (разумеется, при наличии свободного времени) могли сразиться с другими такими же любителями. Предлагаемые задачи являются трудными (во всяком случае, не доказано существование эффективного алгоритма их решения), поэтому сражаться придётся не в классическом смысле (как на олимпиаде по программированию – на скорость и качество), а в смысле «у кого подход лучше». А у кого-то может мощности под рукой больше, тоже добро пожаловать. В любом случае, лично меня интересует не кто победит, а сам результат, полученный общими силами в процессе соревнования. Практика показала, что два последних моих конкурса оказались практически полезными для науки.


    Задачи



    Сам конкурс будет проходить на моём блоге, на котором помимо других конкурсов опубликованы посты с совершено отличным от программирования смыслом. Вы просто можете не обращать на них внимания, а сразу выбрать в меню раздел «Конкурсы». Дело в том, что создать отдельный ресурс для конкурсов я пока не могу по личным причинам и по причинам недостаточного опыта их проведения, поэтому пока будут тренироваться проведением их на блоге.

    Подробное описание задач приводится на страницах конкурса, здесь я кратко обозначу условия.


    Задача 1. Три в степени n


    Задано натуральное число n. Найти такое минимальное натуральное k, что число 3k содержит не менее n подряд идущих нулей в десятичной записи. Например, для n=1 ответом будет k=10, так как 310=59049 и это первая из степеней тройки, которая содержит один ноль. Для n=2 ответом будет k=35, так как 335=50031545098999707 и это первое из степеней тройки, содержащих два нуля.


    Задача 2. Димеры на цилиндре


    Есть известная задача о покрытии домино (ссылка на англ.), или задача о димерах. Смысл задачи в том, чтобы посчитать число способов замостить шахматную доску размером m×n доминошками размером 1×2, причём так, чтобы костяшки домино не накладывались друг на друга, не вылезали за края доски и полностью покрывали доску. Например, если n=m=2, то существует всего два способа (обе доминошки вертикально или обе горизонтально).

    Теперь давайте «свернём» нашу доску в цилиндр, соединив левую и правую границы. В этом случае любое покрытие можно представить следующим образом: если доминошка вылезает за левый край, то вторая её половинка появляется справа, и наоборот. Требуется посчитать число замощений такого квадратного шахматного цилиндра размером 2n×2n. Для n=1 ответ будет 5, а для n=2, ответ 121… Если не очень ясно, картинки есть на странице конкурса.


    Задача 3. Статистика циклов на квадратной решётке


    Задана квадратная решётка размером n×n. В ней можно обнаружить простые циклы длиной 4, 6, 8, и т. д. до самой большой возможной длины. [ Простой цикл – это цикл, который не имеет самопересечений ]. Например, на решётке размером 2×2 есть один цикл длиной 4. На решётке размером 3×3 есть 4 цикла длиной 4, 4 цикла длиной 6 и 5 циклов длиной 8, то есть ответом будет последовательность [4,4,5]. На решётке 4×4 ответом будет последовательность [9,12,26,52,76,32,6] (длины от 4 до 16). Требуется назвать ответы для n=5,6,…

    Итак, добро пожаловать всем участникам. Тех, кто не понимает смысл моих конкурсов и недоброжелателей прошу никак себя не проявлять. Удачи!

    PS. Да, было бы уместно опубликовать в блоге «Я пиарюсь», но мне не хватает для этого кармы. К «Спортивному программированию» этот пост тоже имеет отношение.
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 51
    • +1
      Вспомнил своего учителя информатики.
      Он нам постоянно давал похожие задачки. Которые даже на олимпиадах не решали.

      Cам их потом и решал )
      • 0
        Сейчас изучаю Питон. Он, мягко говоря, не самый быстрый, но мне будет интересно поставить свой личный рекорд именно на нем :) Уверен, что для победы в этом конкурсе надо выбрать язык пошустрее.
        Спасибо за задание.

        пс: Буду благодарен, если кто-то подскажет, как можно замерить скорость выполнения кода на питоне.
        • +2
          import time
          start = time.time()



          print «Time: » + str(time.time() — start)
          • 0
            Большое спасибо!
            • +1
              еще для красоты можно сделать из этого декоратор, и вешать его на интересующую функцию… Полезно изучить что это, при изучение питона)
            • +2
              Ну и «промышленным» методом замера скорости работы участков кода все-же являются профайлер docs.python.org/library/profile.html и иногда timeit для маленьких участков кода docs.python.org/library/timeit.html

              Ну и вообще вот этот раздел документации не лишним будет посмотреть docs.python.org/library/debug.html
              • 0
                По олимпиадам скажу, что лучшие решения не всегда получаются у участников, кто на «шустрых» языках пишет. Все зависит от вас, дерзайте
              • +1
                Правильной дорогой идем, товарищи:)
                • +1
                  отличненько, будет чем заняться в свободное время)
                  • +4
                    Похоже на ТопКодеровские марафоны
                    • +1
                      Кстати, для третьей задачи разве нет решения через динамическое программирование? Уж очень просится, учитывая ограничения в условии. Надо бы подумать…
                      • 0
                        Вообще-то есть, оно очень похоже на решение задачи о гамильтоновых циклах, ссылку на которое я дал в тексте.
                      • +2
                        Ага, моей первой мыслью было «ах, какой райтер» :-)
                      • +6
                        Решение первой задачи (перебор, Perl)
                        # perl -Mbigint -E '$n=7;while(3**$i++!~/0{$n}/){}say--$i//0'
                        


                        • +1
                          Не думаю, что в этой задаче подразумевается переборное решение. Уж больно долго оно будет работать для больших n (та даже относительно больших).
                          • 0
                            Если смотреть на уже решенные задачи, то там используется именно перебор. Так как эффективного алгоритма нет.

                            oeis.org/A006889
                            oeis.org/A131544

                            Результаты пока такие
                            n = 0; k = 0; t = 0.068s
                            n = 1; k = 10; t = 0.069s
                            n = 2; k = 35; t = 0.071s
                            n = 3; k = 148; t = 0.086s
                            n = 4; k = 332; t = 0.123s
                            n = 5; k = 540; t = 0.191s
                            n = 6; k = 540; t = 0.193s
                            n = 7; k = 7722; t = 1m45.413s;
                            • 0
                              Все правильно. Кто дальше сможет?
                            • 0
                              $ php test.php
                              Started on 06:14:07
                              n = 1; k = 10; time = 7.6055526733398E-5 s
                              n = 2; k = 35; time = 8.2969665527344E-5 s
                              n = 3; k = 148; time = 0.00039792060852051 s
                              n = 4; k = 332; time = 0.001060962677002 s
                              n = 5; k = 540; time = 0.0094020366668701 s
                              n = 6; k = 540; time = 0.0021681785583496 s
                              n = 7; k = 7722; time = 0.37158298492432 s
                              n = 8; k = 22793; time = 4.0056979656219 s
                              End on 06:14:12

                              Как-то так…
                              • 0
                                Все правильно, но эти ответы уже получил другой участник. См. на странице конкурса, там до n=12. По-видимому, автор написал бинарный код на каком-то из компилируемых языков.
                                • 0
                                  Интерес был именно посмотреть результаты языка РНР ;)
                                  Я абсолютно не сомневаюсь, что компилируемый язык справится с задачей гораздо быстрее.
                                  Хотя я сейчас запустил на работу n в бесконечность. Остановится тогда, когда кончится память моего ноута. Тогда я и успокоюсь.
                                  А пока могу привести отчеты по первым 10 результатам, если кому интересно.
                                  n=1
                                  n=2
                                  n=3
                                  n=4
                                  n=5
                                  n=6
                                  n=7
                                  n=8
                                  n=9
                                  n=10
                                  Когда будут новые результаты — отчитаюсь ;)
                                  • 0
                                    Понятно. Сомнение в ваших результатах вызывает только наличие десяти знаков после точки в оценке времени работы программы. Из этих 10 цифр правильных, самое большее 2-3. Или у вас «квантовый хнорометр» на основе атомов стронция установлен?: )

                                    Если честно, то доли секунды не нужны, если речь идёт о минутах, а скоро будет о часах счёта.
                                    • 0
                                      Это функция microtime уж не знаю как конкретно она работает, но результаты вроде как сходятся с засекаемым временем. Т.е.

                                      Started on 06:14:07
                                      … отброшу, т.к. в сумме меньше секунды…
                                      n = 8; k = 22793; time = 4.0056979656219 s //Примерно, 4 секунды.
                                      End on 06:14:12

                                      Т.е. 06:14:12 — 06:14:07 = 5 секунд
                                      Погрешность 1 секунда. Вроде, всё совпадает.

                                      Если, все таки еще есть сомнения, то я смогу по личной просьбе предоставить исходник программы тестирования. Запустите на своей машине, чтобы убедиться, что я не с потолка беру время.
                                      Да, забыл упомянуть, конфигурация на которой я запускаю: 1 ядро 2.2Гц. Параллельно работает гуглохром с 7 вкладками, Rythmbox и Transmission.
                                      • +1
                                        Да нет, я имел в виду, что 10 знаков после десятичной точки в секундах — это неправильно. Если вы пишите 4.0056979656219, то из этих цифр поверить можно только в 4.01 (если округлить). Остальные цифры — это лапша. Если вы не по нейронному пульсару измеряли.: )
                                        • 0
                                          Я просто привел вывод в необработанном виде. Так, как мне выдала программа. И, честно говоря, принципиально не знаю какая точность у внутренних компьютерных часов.
                                          Но, как Вы уже сказали, это не важно. Хотя наблюдение интересное, откуда же РНР берет лишние знаки, заведомо не измеряемые (ну или измеряемые только по нейронному пульсару).
                                          • 0
                                            Я не знаю, откуда это время берёт PHP, но самое точное, что мне когда-либо удавалось получить давало погрешность в 32 миллисекунды. То есть 3 знака после точки, плюс минус 0.032 с. Остальные цифры можете считать случайными.
                                            • 0
                                              Договорились ;)
                                              • 0
                                                Это виндовый GetTickCount. Сейчас есть более точные функции — QueryPerformanceCounter/QueryPerformanceFrequency которые постепенно проникают в другие языки программирования. Так что в будущем эти 0.032c уйдут как страшный сон.
                                                • 0
                                                  В принципе, даже более древний метод через timeGetTime, может дать погрешность всего в 1 мс. А так, да, QueryPerformanceCounter хорош, единственный минус: для надёжности надо привязывать поток к конкретному ядру.
                                                  • 0
                                                    Не могу согласиться, однажды я запускал одну и ту же программу 100 раз и замерял врямя этим способом, максимальная разница между запусками была около 32 мс.
                                                    • 0
                                                      Скорее всего забыли сделать timeBeginPeriod(1) до и timeEndPeriod(1) после. Помнится ещё на древнем железе были проблемы, то ли на Pentium MMX то ли на Athlon XP, но это было ну очень давно.
                            • 0
                              Не знаю, что вы хотели этим сказать, но там задачи другого плана. Ещё не забывайте про acm.sgu.ru
                              В своё время я много тренировался на этих двух серверах.
                            • 0
                              Во второй задаче есть ещё 3 «вертикальных» разбиения (наподобие тех «горизонтальных», что есть у Вас в блоге). Итого, получается 8.
                              • 0
                                Не внимательно читаете:
                                Теперь давайте «свернём» нашу доску в цилиндр, соединив левую и правую границы.
                            • НЛО прилетело и опубликовало эту надпись здесь
                              • 0
                                Ссылка не работает. Что-то мне не верится, что задача решена ими в том смысле, что они вывели какую-то формулу. Или вывели?
                                • НЛО прилетело и опубликовало эту надпись здесь
                                • 0
                                  С каких это пор тор стал планарным? Квадратную сетку (хотя бы 3x3) на торе можно вложить лишь в тор.
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  • 0
                                    Нет, в моём случае граф планарный, так как склеиваем только «лево» и «право». Вы знаете формулу для этого случая? В энциклопедии её нет, поэтому я смею надеяться, что эффективного решения задача не допускает. В противном случае это будет «жестокая лажа»…
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                      • 0
                                        Может быть, но я надеюсь, что формулы для задачи 2 ещё никто не вывел. Иначе её придётся снимать с конкурса, а меня можно будет обвинить в незнании классических результатов.

                                        Многие верят, что такая формула должна быть, но я ни разу не видел, чтобы её кто-то пытался вывести.
                                  • 0
                                    про нули была задачка на школьной олимпиаде
                                    • 0
                                      Вполне возможно, это вообще классическая задача, просто именно для 3^n я не нашёл ответов в Интернете, поэтому можно соревноваться.
                                      • 0
                                        было бы интересно посчитать втупую, т.к. являюсь админом одного вычислительного кластера. Если будет время — набросаю библиотеку для символьных вычислений и посчитаю.
                                        • 0
                                          А что у Вас за кластер? Есть сайт?
                                        • +1
                                          А почему не p^n сразу, кстати? Я серьёзно.
                                          • 0
                                            Не понял. Для разных p будут разные ответы. Мне нужно, чтобы ответы были одинаковыми для одних и тех же входных данных.
                                      • 0
                                        Конкурс завершён. Можно ознакомиться с итогами.
                                        Всем спасибо за явное и неявное участие.

                                        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.