Конкурс на самое быстрое решение задачи о назначениях завершён. Подведём итоги.
Читать далееArchive for the ‘ Конкурс ’ Category
Задача о назначениях — итоги
Author: ZealintОкт 15
Задача о назначениях — Конкурс
Author: ZealintОкт 1
Предлагаю принять участие в очередном конкурсе по программированию. Как уже говорилось раньше, я предлагаю трудные задачи: либо труднорешаемые в прямом смысле, либо простые, но такие, для которых нужно не только подобрать хороший алгоритм, но и сильно оптимизировать код. На этот раз предлагается второй вариант, то есть задача для сражения выбрана сама по себе достаточно простая — задача о назначениях, но ограничения достаточно большие.
Читать далее6 ферзей на тороидальной доске — итоги
Author: ZealintИюн 21
Конкурс завершён досрочно, поскольку Андрей Халявин предоставил необходимое количество чисел (и даже больше – 81 шт.), которых оказалось достаточно для проверки гипотезы. Здесь я объясню, что из этого всего получилось. Забегая вперед сообщу, что гипотеза о виде рекуррентного соотношения хоть и была правильной, но соотношение имело не минимальный порядок. Минимальный порядок будет 124, а не 142. Так же я объясню, как из 142 получить 78 для этой задачи, благодаря чему и удалось решить её так быстро. Для понимания объяснений читатель должен быть немного знаком с производящими функциями.
Читать далее6 ферзей на тороидальной доске — конкурс
Author: ZealintИюн 9
Предлагаю отдохнуть от метода матрицы переноса и перейти к задаче более переборной. Как понятно из названия, предлагаю снова заняться проблемой расстановки 6 ферзей, но на этот раз не на обычной доске, а на тороидальной. Прежде чем возразить, что похожая задача уже была и что повторяться не хорошо, ознакомьтесь с моими аргументами в её пользу, которые записаны ниже в этом посте. Я никогда не выбираю задачу по принципу «просто так».
Читать далееСтатистика распределения циклов — итоги
Author: ZealintАпр 24
Конкурс по распараллеливанию алгоритма задачи о подсчёте статистики распределения циклов по длинам завершён. Подведём итоги.
Читать далееСтатистика распределения циклов — конкурс
Author: ZealintАпр 10
Предлагаю принять участие в седьмом любительском конкурсе по программированию. Вам будет предложено написать программу, работающую на GPU и на двух ядрах CPU. Конечно, вовсе не обязательно участвовать с программой, написанной для видеокарты, вы можете задействовать только процессор. Но идея соревнования заключается в том, кто лучше сможет запрограммировать трудную для распараллеливания программу на видеокарте. Побеждает тот, чья программа окажется самой быстрой.
Читать далееМаксимальный поток, баян и блуждания на прямой – итоги
Author: ZealintМар 14
Конкурс про баян завершён и я, как обычно, позволю себе высказать собственные соображения о том, что происходило. Для начала хочу прояснить один момент: в некоторых местах я пишу, что задачи сложные (и что их с наскока не решить), а в других местах я много раз указывал, что задачи 1 и 3 являются халявой, при этом сложной я называл только задачу 2. Казалось бы, что я сам себе противоречу. А на самом деле имеется в виду следующее (на примере задачи 3): решить задачу 3 сложно в том смысле, что для неё сложно отыскать решение для достаточно большого входного параметра k. А простая она в том смысле, что для многих начальных значений k=5,6,7 (с которых предлагалось начать) и даже, наверное, k=8 эта задача решается тривиально. То есть принять участие в конкурсе мог любой человек, кто понял смысл прошлого конкурса — про решение целочисленных систем линейных уравнений. Теперь давайте по порядку.
Читать далееМаксимальный поток, баян и блуждания на прямой — конкурс
Author: ZealintМар 1
Предлагаю принять участие в очередном любительском конкурсе по спортивному программированию. В очередной раз приза не будет — участие предполагается только для своего удовольствия, и если у Вас есть свободное время и желание посоревноваться. Как обычно, я провожу конкурсы по трудным задачам, то есть таким задачам, которые с наскока не берутся. По крайней мере, в своё время я их решил не сразу. Поэтому и время проведения предполагается 10 дней или больше, если этого не хватит.
Читать далееЦелочисленная система линейных уравнений — итоги
Author: ZealintФев 10
Конкурс на самое быстрое решение целочисленной системы линейных уравнений завершён. Вынужден признать, что это был самый скучный конкурс из всех, которые я проводил. Было довольно много участников, но у половины программы работали неправильно, а у остальных – слишком медленно и не укладывались в 600 с. Как минимум, предполагалось, что кто-то дойдёт то отметки в 5-10 с, но, к сожалению, этого не произошло. Значит я вынужден буду объяснить, как этого добиться. В этом посте подведём итоги, и я выскажу мои мысли по поводу данного мероприятия, а в следующем ждите подробного описания нормального метода решения поставленной задачи.
Читать далееЦелочисленная система линейных уравнений — конкурс
Author: ZealintФев 1
В честь дня рождения моего блога предлагаю принять участие в очередном любительском конкурсе для программистов-математиков. Я обещал в прошлый раз, что конкурс будет по параллельным вычислениям, однако по техническим причинам его придётся пока отложить на неопределённый срок. Вместо этого будет простой конкурс с простой (с точки зрения теории сложности) задачей.
Читать далее