Задача о назначениях - конкурс для программистов

[Zealint]

По традиции продолжаю проводить конкурсы по решению задач по программированию.

На этот раз объектом соревнования является хорошо известная задача о назначениях. Задача имеет множество формулировок, но давайте остановимся на одной из них. Задаётся квадратная матрица $\bigl(C_{ij}\bigr)$ порядка $n$. Нужно выбрать в этой матрице $n$ чисел так, чтобы в каждой строке и в каждом столбце выбранным было ровно одно число, а сумма выбранных чисел была бы минимально возможной. Например,

$$ C=\begin{pmatrix} 1&2&\underline{3}\\ \underline{3}&6&9\\ 2&\underline{4}&6\\ \end{pmatrix} $$

В этой матрице подчёркнуты выбранные числа. Их сумма равна 10 и меньше быть никак не может.

Задача имеет множество алгоритмов решения. В Интернете можно отыскать множество исходников. Но какова их цена? Думаю, не очень высокая. Чтобы победить в конкурсе, написав самую быструю программу, потребуется написать что-то своё.

Ограничения: $1 \leq n \leq 2\,000$, $|C_{ij}|\leq 1\,073\,741$ и целые. Программа должна уложиться в 15 минут.

Конкурс проводится, как обычно, здесь. Приглашаются все желающие.

Завершение конкурса планируется на 15 октября 2011 г.

[venco]

Цитата:

ВНИМАНИЕ. В случае работы на Linux вам придется добавить в программу свой таймер, который в конце работы должен вывести время работы (секунды + сотые) в поток ошибок. К сожалению, замерять правильно время работы в Linux я иначе не умею.

И тут мне карта пошла!

[drozdov_mihail]

А какова премия? Вот я нашел предложение на несколько тысяч баксов: http://software.intel.com/ru-ru/forums/ ... 7&o=a&s=lr

[Zealint]

drozdov_mihail в сообщении #488339 писал(а):

А какова премия?

Награда за труд - проделанная работа.

Цитата:

Вот я нашел предложение на несколько тысяч баксов: http://software.intel.com/ru-ru/forums/ ... 7&o=a&s=lr

Page not found.
Вообще, у меня в списке есть несколько задач, за которые там же или в других местах могли бы заплатить побольше. Я их уже решил, но им не предлагал. И пока не собираюсь, пусть помучаются сами. А там видно будет.

venco писал(а):

И тут мне карта пошла!

В смысле? Вы вроде полтора года назад в конкурсе по матрицам не жаловались... Тем более, если на C++ сможете сообразить, я прямо у себя откомпилирую.

[drozdov_mihail]

Zealint в сообщении #488354 писал(а):

drozdov_mihail в сообщении #488339 писал(а):

А какова премия?

Награда за труд - проделанная работа.

6 класс: вассал моего вассала, не мой вассал.

Zealint в [url=http://dxdy.ru/post488354.html#p488354]сообщении #488354[/url писал(а):

Page not found.

У меня открывается-, попробуйте так: _http://software.intel.com/ru-ru/forums/showthread.php?t=76597&o=a&s=lr

Zealint в сообщении #488354 писал(а):

Вообще, у меня в списке есть несколько задач, за которые там же или в других местах могли бы заплатить побольше. Я их уже решил, но им не предлагал. И пока не собираюсь, пусть помучаются сами. А там видно будет.

Если не секрет, кто поболе может обещать и за какие задачи?

[Zealint]

(Оффтоп)

drozdov_mihail в сообщении #488361 писал(а):

6 класс: вассал моего вассала, не мой вассал.

Да мне как-то все равно, честное слово : ) Особенно если учесть, что я не работу в прямом смысле предлагаю, а развлечение для интересующихся. Также, как и 8 раз до этого.

Цитата:

У меня открывается-, попробуйте так: _http://software.intel.com/ru-ru/forums/showthread.php?t=76597&o=a&s=lr

Не хочет. Сразу сюда попадаю: http://software.intel.com/error.php
Может я не умею Интернетом пользоваться?

[drozdov_mihail]

Zealint в сообщении #488375 писал(а):

drozdov_mihail в сообщении #488361 писал(а):

У меня открывается-, попробуйте так: _http://software.intel.com/ru-ru/forums/showthread.php?t=76597&o=a&s=lr

Не хочет. Сразу сюда попадаю: http://software.intel.com/error.php
Может я не умею Интернетом пользоваться?

Все может быть: у моих коллег открывается.

[Shadow]

Думаю, метод потенциалов для решения транспортной задачи тут подходит идеально. Ограничения: суммы всех рядов и столбцов=1, коэффициенты-елементы масива. Опорный план - метод наименьшего элемента.

Оказывается, есть алгоритмы и получше. Каков смысл давать в конкурсе задачи, которых можно найдти в интернете

[Shadow]

venco писал(а):

И тут мне карта пошла!

В смысле? Вы вроде полтора года назад в конкурсе по матрицам не жаловались... Тем более, если на C++ сможете сообразить, я прямо у себя откомпилирую.[/quote]

(Оффтоп)

поехал как-то василий иваныч в англию, опыт перенимать. возвращается,
встречает его петька. а василий иваныч выходит из самолета весь в
малиновом смокинге, за ним штук двадцать чемоданов несут,
из багажного отсека 600-й "мерс" выгружают...
- откуда столько денег, василий иваныч?!
- да понимаешь, петька, сели мы с ихними лордами в очко
сыграть. один и говорит: "очко!". я ему:
"покажи!". а он мне: "ну что вы ,василий иванович, мы же
тут все джентльмены!".
вот тут мне карта и пошла...

[Zealint]

Shadow в сообщении #488577 писал(а):

Оказывается, есть алгоритмы и получше. Каков смысл давать в конкурсе задачи, которых можно найдти в интернете

Давайте я объясню, хотя делал это не меньше 10 раз в разных местах. Пора давать ответ FAQ, так как вы стали последней каплей : ) [в хорошем смысле]

(1) Да, можно найти в интернете и я сам это специально написал в объявлении. Но цена тех исходников, которые вы найдёте в Интернете разве лишь немногим больше нуля. Цель в том, чтобы авторам пришлось оптимизировать что-нибудь, а для этого скачать исходник недостаточно. Можем проверить: скачайте и посмотрите, что будет. Уложится ли программа в 15 минут (да, такие исходники я видел), и будете ли вы победителем, если не приложите усилий по её оптимизации?

(2) Когда я даю задачи, исходники для которых найти нельзя, начинаются странные вещи. Участвует один человек, может два. Потом кто-нибудь со стороны ругается, что я даю задачи, которые непонятно как решать. А поскольку я ищу "оптимальную формулу" проведения конкурсов, пробую разные варианты, в том числе и такой. Можете посмотреть мой первый конкурс, интерес к которому все равно был, несмотря на тривиальность в постановке задачи.

Цитата:

поехал как-то василий иваныч в англию, опыт перенимать. возвращается,
встречает его петька. а василий иваныч выходит из самолета весь в
малиновом смокинге, за ним штук двадцать чемоданов несут,
из багажного отсека 600-й "мерс" выгружают...
- откуда столько денег, василий иваныч?!
- да понимаешь, петька, сели мы с ихними лордами в очко
сыграть. один и говорит: "очко!". я ему:
"покажи!". а он мне: "ну что вы ,василий иванович, мы же
тут все джентльмены!".
вот тут мне карта и пошла...

Понял. Не слышал этого анекдота. Поясню.
Смысл делать свой таймер есть, так как глазом все равно видно, более менее честно он выводит время или нет. С точностью до 3-х десятых секунды я это сделать сумею, можно не сомневаться. Если вдруг у кого-то программа будет работать быстрее, то мы можем увеличить ограничения по $n$. Натуральный ряд длинный : )

[drozdov_mihail]

Shadow в сообщении #488577 писал(а):

Думаю, метод потенциалов для решения транспортной задачи тут подходит идеально. Ограничения: суммы всех рядов и столбцов=1, коэффициенты-елементы масива. Опорный план - метод наименьшего элемента.

Оказывается, есть алгоритмы и получше. Каков смысл давать в конкурсе задачи, которых можно найдти в интернете

Дык Zealint говорил выше, что у него такого типа решенных задач на 600-ый мерс хватит, но он от него отказывается - пока!: это где я давал ссылку на задачу, за решение которой 5000 баксов предлагают.

[Zealint]

drozdov_mihail в сообщении #488623 писал(а):

Дык Zealint говорил выше, что у него такого типа решенных задач на 600-ый мерс хватит, но он от него отказывается

Нет, я такого не говорил. Вы ошибаетесь. И ведь сейчас будете доказывать, что говорил, но не сможете... Не советую даже начинать, знаете же, чем закончится : )

[drozdov_mihail]

Zealint в сообщении #488729 писал(а):

drozdov_mihail в сообщении #488623 писал(а):

Дык Zealint говорил выше, что у него такого типа решенных задач на 600-ый мерс хватит, но он от него отказывается

Нет, я такого не говорил. Вы ошибаетесь. И ведь сейчас будете доказывать, что говорил, но не сможете... Не советую даже начинать, знаете же, чем закончится : )

Ваши слова: "Вообще, у меня в списке есть несколько задач, за которые там же или в других местах могли бы заплатить побольше. Я их уже решил, но им не предлагал. И пока не собираюсь, пусть помучаются сами. А там видно будет". Побольше, как я понимаю, учитывая ваши непомерные амбиции,- это 50 тысяч баксов. Т.е. 50000 баксов помножить на "несколько задач" = 600-ый мерс? Это у меня такая ирония: думаю, что вам и на "горбатого" не хватит.

[Zealint]

drozdov_mihail в сообщении #488858 писал(а):

Ваши слова: "Вообще, у меня в списке есть несколько задач, за которые там же или в других местах могли бы заплатить побольше....

И где здесь написано, что

drozdov_mihail писал(а):

что у него такого типа решенных задач

???

Задачами такого типа я вообще не занимаюсь. В общем, как обычно, не составляет труда показать, что вы опять написали чепуху. Зачем?

Цитата:

Это у меня такая ирония: думаю, что вам и на "горбатого" не хватит.

Конечно не хватит, я же не продаю свои решения. И не собираюсь в ближайшее время.

И вообще, заканчивайте оффтоп. Я на ваш вопрос ответил.

[Toucan]

drozdov_mihail, двухнедельный бан за непрекращающийся оффтопик и переход на обсуждение личности собеседника.