2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Задача о назначениях - конкурс для программистов
Сообщение01.10.2011, 13:58 


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

На этот раз объектом соревнования является хорошо известная задача о назначениях. Задача имеет множество формулировок, но давайте остановимся на одной из них. Задаётся квадратная матрица $\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 г.

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение01.10.2011, 16:11 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение01.10.2011, 18:19 
Заблокирован


20/07/11

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение01.10.2011, 18:57 


26/01/10
959
drozdov_mihail в сообщении #488339 писал(а):
А какова премия?

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

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

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

venco писал(а):
И тут мне карта пошла!

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение01.10.2011, 19:22 
Заблокирован


20/07/11

169
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 писал(а):
Вообще, у меня в списке есть несколько задач, за которые там же или в других местах могли бы заплатить побольше. Я их уже решил, но им не предлагал. И пока не собираюсь, пусть помучаются сами. А там видно будет.
Если не секрет, кто поболе может обещать и за какие задачи?

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение01.10.2011, 19:45 


26/01/10
959

(Оффтоп)

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
Может я не умею Интернетом пользоваться?

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение01.10.2011, 20:08 
Заблокирован


20/07/11

169
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
Может я не умею Интернетом пользоваться?

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение02.10.2011, 13:30 


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

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение02.10.2011, 14:42 


26/08/11
2057
venco писал(а):
И тут мне карта пошла!

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение02.10.2011, 15:35 


26/01/10
959
Shadow в сообщении #488577 писал(а):
Оказывается, есть алгоритмы и получше. Каков смысл давать в конкурсе задачи, которых можно найдти в интернете

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

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

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

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение02.10.2011, 15:40 
Заблокирован


20/07/11

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

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

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение02.10.2011, 18:47 


26/01/10
959
drozdov_mihail в сообщении #488623 писал(а):
Дык Zealint говорил выше, что у него такого типа решенных задач на 600-ый мерс хватит, но он от него отказывается

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение02.10.2011, 21:29 
Заблокирован


20/07/11

169
Zealint в сообщении #488729 писал(а):
drozdov_mihail в сообщении #488623 писал(а):
Дык Zealint говорил выше, что у него такого типа решенных задач на 600-ый мерс хватит, но он от него отказывается

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

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение02.10.2011, 21:47 


26/01/10
959
drozdov_mihail в сообщении #488858 писал(а):
Ваши слова: "Вообще, у меня в списке есть несколько задач, за которые там же или в других местах могли бы заплатить побольше....

И где здесь написано, что
drozdov_mihail писал(а):
что у него такого типа решенных задач

???

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

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

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

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

 Профиль  
                  
 
 Re: Задача о назначениях - конкурс для программистов
Сообщение02.10.2011, 21:52 
Админ форума
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group