Комментарии 82
Кто вас научил «так» ставить задачи программистам?
Видимо так написано для тех, кто незнаком с дискретной математикой.
Задание можно упростить:
Найти максимальный маршрут на взвешенном связном графе, заданном таблицей 32-х битных чисел в формате узел1, узел2, вес.
Выходные данные:
32 бита длина маршрута
список связей маршрута в виде последовательности строк входной таблицы.
Задание можно упростить:
Найти максимальный маршрут на взвешенном связном графе, заданном таблицей 32-х битных чисел в формате узел1, узел2, вес.
Выходные данные:
32 бита длина маршрута
список связей маршрута в виде последовательности строк входной таблицы.
* путь максимального веса, конечно же
По-моему вес в задаче никак не учитывается, только 4 байта лишних жрет у каждого ребра.
И ищется путь именно максимальной длины.
И ищется путь именно максимальной длины.
Да, действительно макс длины.
Тогда даже неинтересно.
ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B
При начальных условиях что все ребра имеют вес = 1 + при возникновении цикла просто стопорить выполнение. и переходить к следующей вершине.
Тогда даже неинтересно.
ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B
При начальных условиях что все ребра имеют вес = 1 + при возникновении цикла просто стопорить выполнение. и переходить к следующей вершине.
веса в задаче нет. 4 байта «информационной нагрузки» должны быть перенесены в ответ с каждой связью
Вы в курсе, что в ответе во многих случаях бесконечное число маршрутов? Берем максимальный маршрут и добавляем произвольные ребра в конец. Длина новых маршрутов точно такая же (поскольку они становятся замкнутыми), а добавить ребра можно бесконечным числом способов, если из конечной вершины достижим какой-либо цикл.
halyavin,
не очень понял, что вы имеете ввиду. Предположу «ребро» это «связь» в терминах задачи. Предположу, что вы имеете ввиду, что длинна замкнутого маршрута бесконечна, и кроме того один замкнутый маршрут может быть записан в несколько способов.
Пример: Маршрут из объектов 1,2,3,4,5,1 можно записать как 1,2,3,4,5,1,2,3,4,5,1… и это одно и тоже что и 3,4,5,1,2,3,4,5,…
Если вопрос в этом, то ответ такой:
длина этого маршрута 5, т.к. до повторяющегося объекта 5 связей. Если 5 это максимальная длина из всего множества маршрутов, то в ответ должны попасть 5 маршрутов:
1,2,3,4,5
2,3,4,5,1
3,4,5,1,2
4,5,1,2,3
5,1,2,3,4
не очень понял, что вы имеете ввиду. Предположу «ребро» это «связь» в терминах задачи. Предположу, что вы имеете ввиду, что длинна замкнутого маршрута бесконечна, и кроме того один замкнутый маршрут может быть записан в несколько способов.
Пример: Маршрут из объектов 1,2,3,4,5,1 можно записать как 1,2,3,4,5,1,2,3,4,5,1… и это одно и тоже что и 3,4,5,1,2,3,4,5,…
Если вопрос в этом, то ответ такой:
длина этого маршрута 5, т.к. до повторяющегося объекта 5 связей. Если 5 это максимальная длина из всего множества маршрутов, то в ответ должны попасть 5 маршрутов:
1,2,3,4,5
2,3,4,5,1
3,4,5,1,2
4,5,1,2,3
5,1,2,3,4
Я имею в виду, что если граф, например, 1->2; 2->3; 3->1. То у нас есть маршруты длины 2: 1->2->3, 1->2->3->1, 1->2->3->1->2, 1->2->3->1->2->3,… Все маршруты кроме первого по вашему определению замкнуты (поскольку в связи 3->1 конечный объект совпадает с начальным объектом первой связи) и их длина равна длине начальной части 1->2->3, т.е. 2.
И длина указанного вами выше маршрута — 4, поскольку первая связь у которой конечный объект совпадает с каким-либо начальным — 5->1. До нее 4 связи, саму связь 5->1 по вашему определению мы не учитываем.
И длина указанного вами выше маршрута — 4, поскольку первая связь у которой конечный объект совпадает с каким-либо начальным — 5->1. До нее 4 связи, саму связь 5->1 по вашему определению мы не учитываем.
Желающих «научить» прошу не комментировать. Пожалуйста, проигнорируйте топик
«Отличный» подход! Вы опубликовали статью на Хабре, так что будьте любезны выслушать критику.
А то слишком хорошо устроились! Мало того, что нахаляву пиарите свой сайт, так еще и отрицательных комментов видеть не хотите.
А то слишком хорошо устроились! Мало того, что нахаляву пиарите свой сайт, так еще и отрицательных комментов видеть не хотите.
soulburner,
не конструктивную критику не хочу, и очень прошу от нее воздержаться. Я ничего не пиарю, размещаю пост на хабре, так как здесь много программистов, которым, возможно интересно поучаствовать. Если вы не входите в их число, пожалуйста, проигнорируйте этот топик
не конструктивную критику не хочу, и очень прошу от нее воздержаться. Я ничего не пиарю, размещаю пост на хабре, так как здесь много программистов, которым, возможно интересно поучаствовать. Если вы не входите в их число, пожалуйста, проигнорируйте этот топик
Я ничего не пиарюПростите! И как я мог подумать, что целью человека с ником ttools, является пиар сайта ttools.ru и завлечение туда хабрааудитории.
И как мне такое в голову могло придти?!!!
soulburner,
Простите! И как я мог подумать, что целью человека с ником ttools, является пиар сайта ttools.ru и завлечение туда хабрааудитории.
так и есть, топик создан для привлечения хабраудитории, я так и пишу. Но причем здесь пиар? Я ничего не получу, если вы перейдете на сайт и даже поучаствуете в конкурсе. Только дополнительную работу по обработке ответов
Простите! И как я мог подумать, что целью человека с ником ttools, является пиар сайта ttools.ru и завлечение туда хабрааудитории.
так и есть, топик создан для привлечения хабраудитории, я так и пишу. Но причем здесь пиар? Я ничего не получу, если вы перейдете на сайт и даже поучаствуете в конкурсе. Только дополнительную работу по обработке ответов
Честно пытался начать делать задачу. Даже файл распарсил и составил мэпы по входам/выходам. Замутить поиск по дереву с сохранением длины маршрутов пар вершин теперь дело техники (лаба 1-2 курса универа).
На самом деле это средней сложности задача на графы. Но с заковыками и непонятками. За интерес в такое играть неохота. Соревноваться конечно круто, но смысл в чём? Таких задач можно сотни придумать. К тому же задание слишком некорректно, особенно с учётом того, что «обработка будет автоматически». Что значит «4 байта длина маршрута», как оно кодируется? В каком порядке байтов? От старшего к младшему? Или наоборот? Допустим, я пишу на Java и читаю четырёхбайтовый int через DataInputStream, есть сомнение, что мой бинарный вывод будет такой же как у вас в вашей платформе.
Про нечёткость определения маршрутов выше сказано. При недостаточно разреженном графе маршрутов будет и правда если не бесконечное количество, то достаточно неопределённое. При наличии зацикленных тоже непонятно, каждый цикл добавляет кучу маршрутов. А если зацикленный маршрут самый длинный, то сколько их? Столько, сколько вершин в этом цикле? Как-то нелогично это всё, имхо.
На самом деле это средней сложности задача на графы. Но с заковыками и непонятками. За интерес в такое играть неохота. Соревноваться конечно круто, но смысл в чём? Таких задач можно сотни придумать. К тому же задание слишком некорректно, особенно с учётом того, что «обработка будет автоматически». Что значит «4 байта длина маршрута», как оно кодируется? В каком порядке байтов? От старшего к младшему? Или наоборот? Допустим, я пишу на Java и читаю четырёхбайтовый int через DataInputStream, есть сомнение, что мой бинарный вывод будет такой же как у вас в вашей платформе.
Про нечёткость определения маршрутов выше сказано. При недостаточно разреженном графе маршрутов будет и правда если не бесконечное количество, то достаточно неопределённое. При наличии зацикленных тоже непонятно, каждый цикл добавляет кучу маршрутов. А если зацикленный маршрут самый длинный, то сколько их? Столько, сколько вершин в этом цикле? Как-то нелогично это всё, имхо.
Ок, про цикл понятно (выше ответили, пока писал). Но всё равно
Пример: Маршрут из объектов 1,2,3,4,5,1 можно записать как 1,2,3,4,5,1,2,3,4,5,1… и это одно и тоже что и 3,4,5,1,2,3,4,5,…И что, все эти похожие маршруты писать в произвольном порядке? Или «одно и то же» означает, что не надо писать?
barker,
Длиной замкнутого маршрута считается количество связей до связи, в которой конечный объект является начальным объектом другой связи маршрута, не включая данную связь.
записать данный маршрут можно только как
1,2,3,4,5
2,3,4,5,1
3,4,5,1,2
4,5,1,2,3
5,1,2,3,4
если 5 — это максимальная длина, значит в ответ должны попасть все эти маршруты плюс остальные, если есть, такой же длины не из этого маршрута
Длиной замкнутого маршрута считается количество связей до связи, в которой конечный объект является начальным объектом другой связи маршрута, не включая данную связь.
записать данный маршрут можно только как
1,2,3,4,5
2,3,4,5,1
3,4,5,1,2
4,5,1,2,3
5,1,2,3,4
если 5 — это максимальная длина, значит в ответ должны попасть все эти маршруты плюс остальные, если есть, такой же длины не из этого маршрута
прошу прощения, длина всех этих маршрутов конечно же 4
Ок, я решил и отправил файл. Дошло?
На самом деле оказалось, что вышеобсуждаемых проблем нет в принципе :) И если бы вы сразу сказали сколько точно должно быть маршрутов (а их достоверно точно можно посчитать), то ничего из того, что писалось выше никому не пришло бы в голову писать. Верно ведь?
На самом деле оказалось, что вышеобсуждаемых проблем нет в принципе :) И если бы вы сразу сказали сколько точно должно быть маршрутов (а их достоверно точно можно посчитать), то ничего из того, что писалось выше никому не пришло бы в голову писать. Верно ведь?
Верно, многих обсуждаемых проблем нет, но приходится их обсуждать, чтобы не давать подсказок о том, что содержится в ответе :)
Верно, многих обсуждаемых проблем нет, но приходится их обсуждать, чтобы не давать подсказок о том, что содержится в ответе :)
связи
1->2
2->3
3->4
4->1
2->5
5->6
6->1
Какой ответ?
1->2
2->3
3->4
4->1
2->5
5->6
6->1
Какой ответ?
НЛО прилетело и опубликовало эту надпись здесь
4 связи.
Длиной замкнутого маршрута считается количество связей до связи, в которой конечный объект является начальным объектом другой связи маршрута, не включая данную связь.
Длиной замкнутого маршрута считается количество связей до связи, в которой конечный объект является начальным объектом другой связи маршрута, не включая данную связь.
НЛО прилетело и опубликовало эту надпись здесь
если маршрут для ответа 1-2-3-4-1, то в ответ должно попасть
1-2-3-4
2-3-4-1
3-4-1-2
4-1-2-3
1-2-3-4
2-3-4-1
3-4-1-2
4-1-2-3
НЛО прилетело и опубликовало эту надпись здесь
Потому что конечный объект связи 4-1
равен начальному объекту связи 1-2
равен начальному объекту связи 1-2
НЛО прилетело и опубликовало эту надпись здесь
Есть связь 4-1. То, что 1 — конечный объект в этой связи написано в условии.
Аналогично с начальным.
Аналогично с начальным.
С другой стороны в связи 1-2 конечный будет 2.
А в связи 2-3 начальным будет 2.
То есть любой путь длины 2 — это цикл? :)
А в связи 2-3 начальным будет 2.
То есть любой путь длины 2 — это цикл? :)
НЛО прилетело и опубликовало эту надпись здесь
Цитата:
Входной файл содержит список связей в формате:
4 байта идентификатор начального объекта
4 байта идентификатор конечного объекта
4 байта информационная нагрузка связи
Входной файл содержит список связей в формате:
4 байта идентификатор начального объекта
4 байта идентификатор конечного объекта
4 байта информационная нагрузка связи
НЛО прилетело и опубликовало эту надпись здесь
Начало маршрута — это начало первой связи маршрута.
Конец маршрута — это конец последней связи маршрута.
Как-то так :)
Далее я согласен, что условие несколько размытое.
Но в комментариях ниже уже ответили, что циклов в ответе быть не может.
Конец маршрута — это конец последней связи маршрута.
Как-то так :)
Далее я согласен, что условие несколько размытое.
Но в комментариях ниже уже ответили, что циклов в ответе быть не может.
НЛО прилетело и опубликовало эту надпись здесь
kaladhara,
Воот… Т.е. заказчик уточнил спецификацию слегка задним числом. А так всё хорошо начиналось…
почему же? задача уточнена в ходе переговоров :)
Воот… Т.е. заказчик уточнил спецификацию слегка задним числом. А так всё хорошо начиналось…
почему же? задача уточнена в ходе переговоров :)
1 в данном случае это начальный и конечный объект. конечный объект одной из связей маршрута является начальным объектом другой связи маршрута
kaladhara,
а почему не 1-2-3-4-1-2-5-6-1?
конечный объект связи 4-1 является начальным объектом связи 1-2
а почему не 1-2-3-4-1-2-5-6-1?
конечный объект связи 4-1 является начальным объектом связи 1-2
MiXei4,
связи
1->2
2->3
3->4
4->1
2->5
5->6
6->1
Какой ответ?
5,6,1,2,3,4
связи
1->2
2->3
3->4
4->1
2->5
5->6
6->1
Какой ответ?
5,6,1,2,3,4
Пример выходного файла можно? Так не очень понятно, как он должен выглядеть
Пример выходного файла можно? Так не очень понятно, как он должен выглядеть
для ответа
связь 1:
1->2 (информационная нагрузка FFFFFFFF)
2->3 (информационная нагрузка EEEEEEE)
3->4 (информационная нагрузка DDDDDD)
файл будет выглядеть так:
02 00 00 00 01 00 00 00
02 00 00 00 FF FF FF FF
02 00 00 00 03 00 00 00
EE EE EE EE 03 00 00 00
04 00 00 00 DD DD DD DD
для ответа
связь 1:
1->2 (информационная нагрузка FFFFFFFF)
2->3 (информационная нагрузка EEEEEEE)
3->4 (информационная нагрузка DDDDDD)
файл будет выглядеть так:
02 00 00 00 01 00 00 00
02 00 00 00 FF FF FF FF
02 00 00 00 03 00 00 00
EE EE EE EE 03 00 00 00
04 00 00 00 DD DD DD DD
Блин тогда я жёстко затупил в ответе, я почему-то решил, что первое число не длина маршрута, а их количество. Сбило ваше указание "(маршруты, если их несколько)". Зачем тогда это? Или условие было на вашем сайте изначально другое?
Мда, вот косяк…
В любом случае длина маршрута однозначно вычисляется количеством последующих 12-байтных узлов, но при вашей «автоматизированной» обработке оно не проканает, да, потому что у меня первые 4 байта другие.
Хотя оно в любом случае не проканало бы, потому что сейчас проверил, Java через DataOutputStream.writeInt пишет целое число с обратным порядком байт: «00 00 00 01», о чём я вам и говорил выше, собственно. Надо чётко определять подобные тонкости :\
Мда, вот косяк…
В любом случае длина маршрута однозначно вычисляется количеством последующих 12-байтных узлов, но при вашей «автоматизированной» обработке оно не проканает, да, потому что у меня первые 4 байта другие.
Хотя оно в любом случае не проканало бы, потому что сейчас проверил, Java через DataOutputStream.writeInt пишет целое число с обратным порядком байт: «00 00 00 01», о чём я вам и говорил выше, собственно. Надо чётко определять подобные тонкости :\
Т.е. я хочу сказать, что у вас подразумевается запись вашего файла в little-endian, хотя это стало ясно только из этого вашего примера. Но это совсем неочевидно. В бинарных форматах файлов и разных там протоколах как раз част big-endian. Прошу это принять с сведению.
Маршрут не изменится, кстати, так что ответ от этого не меняется. Потому что как ни читай целые числа, они всё равно разные будут для разных точек, хотя целочисленная интерпретация номеров вершин на самом деле другая, но связи не рушатся. Но вот с первыми 4 байтами провал, конечно.
Маршрут не изменится, кстати, так что ответ от этого не меняется. Потому что как ни читай целые числа, они всё равно разные будут для разных точек, хотя целочисленная интерпретация номеров вершин на самом деле другая, но связи не рушатся. Но вот с первыми 4 байтами провал, конечно.
barker,
Блин тогда я жёстко затупил в ответе, я почему-то решил, что первое число не длина маршрута, а их количество. Сбило ваше указание "(маршруты, если их несколько)". Зачем тогда это? Или условие было на вашем сайте изначально другое?
Мда, вот косяк…
если ошибка будет только в длине (в первых 4 байтах)- ваш ответ будет засчитан
Хотя оно в любом случае не проканало бы, потому что сейчас проверил, Java через DataOutputStream.writeInt пишет целое число с обратным порядком байт: «00 00 00 01», о чём я вам и говорил выше, собственно. Надо чётко определять подобные тонкости :\
это не имеет значения. объекты и нагрузка идентифицируются 4 байтами, и не имеет значения какой тип какого языка вы используете, главное, чтобы вы читали и писали данные в одном порядке. Но если вы прочитали из файла объект 00 00 00 01, а записали в выходной файл как 01 00 00 00 — то это естественно ошибка
Блин тогда я жёстко затупил в ответе, я почему-то решил, что первое число не длина маршрута, а их количество. Сбило ваше указание "(маршруты, если их несколько)". Зачем тогда это? Или условие было на вашем сайте изначально другое?
Мда, вот косяк…
если ошибка будет только в длине (в первых 4 байтах)- ваш ответ будет засчитан
Хотя оно в любом случае не проканало бы, потому что сейчас проверил, Java через DataOutputStream.writeInt пишет целое число с обратным порядком байт: «00 00 00 01», о чём я вам и говорил выше, собственно. Надо чётко определять подобные тонкости :\
это не имеет значения. объекты и нагрузка идентифицируются 4 байтами, и не имеет значения какой тип какого языка вы используете, главное, чтобы вы читали и писали данные в одном порядке. Но если вы прочитали из файла объект 00 00 00 01, а записали в выходной файл как 01 00 00 00 — то это естественно ошибка
Да, разумеется, если я читаю в big-endian, то и пишу я в big-endian. Внутри алгоритма номера у меня конечно другие получаются, но в итоге они обратно сериализуются «правильно». Хотя я уже сейчас быстренько обёртки на Data[I/O]Stream накалякал и перезапустил алгоритм, но раз вы делаете допущение, то ок. Конечно, всё так же осталось, кроме первого числа.
Кстати, не очень понятно почему вы говорили о том, что вычисления тяжёлые, алгоритм у меня на таком нехилом кол-ве данных работает примерно полминуты. Но это почти в лоб решалось, к тому же очень нарочито по-ООП-шному. Я прямо сейчас вижу как его сильно заоптимизировать.
Кстати, не очень понятно почему вы говорили о том, что вычисления тяжёлые, алгоритм у меня на таком нехилом кол-ве данных работает примерно полминуты. Но это почти в лоб решалось, к тому же очень нарочито по-ООП-шному. Я прямо сейчас вижу как его сильно заоптимизировать.
barker,
я тоже сильно удивлен в такой скорости решения, подумал, что вы сразу оптимизировали алгоритм или частично использовали БД. По моим подсчетам решение «совсем в лоб» должно привести к огромному количеству циклов, и хранение временных вариантов должно быть ощутимым
я тоже сильно удивлен в такой скорости решения, подумал, что вы сразу оптимизировали алгоритм или частично использовали БД. По моим подсчетам решение «совсем в лоб» должно привести к огромному количеству циклов, и хранение временных вариантов должно быть ощутимым
Ну, вообще, там цикл в самом алгоритме фактически один — перебор путей из конкретной вершины в другие) А дальше просто обход в глубину. Что ж там вложенного и ресурсоёмкого? В лоб — это уж не совсем «в лоб», конечно)) Позже по-возможности выложу алгоритм и код, мне не жалко)
Некое подобие БД — один мэп списков (связей из этой вершины) и один список списков (последовательность связей, т.е. путей) — используется, конечно, куда без этого. В память нагрузилось сравнительно немного. Сначала, когда я начал по-дурости хранить все выходные законченные пути, там рухнуло всё вместе с JVM, это да.
Некое подобие БД — один мэп списков (связей из этой вершины) и один список списков (последовательность связей, т.е. путей) — используется, конечно, куда без этого. В память нагрузилось сравнительно немного. Сначала, когда я начал по-дурости хранить все выходные законченные пути, там рухнуло всё вместе с JVM, это да.
barker,
значит всё-таки алгоритм был оптимизирован с самого начала! Ваша скорость меня поражает! Интересно обсудить после окончания. Ответы я еще не проверял. Проверю сегодня вечером, завтра утром скажу, есть ли победитель. Пусть будет какая-то интрига ;)
значит всё-таки алгоритм был оптимизирован с самого начала! Ваша скорость меня поражает! Интересно обсудить после окончания. Ответы я еще не проверял. Проверю сегодня вечером, завтра утром скажу, есть ли победитель. Пусть будет какая-то интрига ;)
И как результаты?
На текущий момент (15.03.2011 17:30)
имеется 2 ответа,
анализ 1-го ответа:
является ли файл файлом маршрутов: нет
анализ 2-го ответа:
является ли файл файлом маршрутов: да
количество связей маршрута: 264
является ли маршрут незамкнутым: да
является ли маршрут вариантом ответа: да
но длина маршрута не максимальна, в файле есть маршруты больше, не всё так просто.
Пока верных ответов нет, конкурс продолжается
имеется 2 ответа,
анализ 1-го ответа:
является ли файл файлом маршрутов: нет
анализ 2-го ответа:
является ли файл файлом маршрутов: да
количество связей маршрута: 264
является ли маршрут незамкнутым: да
является ли маршрут вариантом ответа: да
но длина маршрута не максимальна, в файле есть маршруты больше, не всё так просто.
Пока верных ответов нет, конкурс продолжается
Я отправил ответ. Хотя я так до конца условия и не понял, честно говоря.
А мне интересно, а почему существует несколько объектов с одинаковым идентификатором?
0043595E 00435968 DD406B53 vs 0043595E 0103EAF7 0000015D
00F3C466 00F3C46B 4EA80AD3 vs 00F3C466 00F3C466 F81F6EFD
00FE4CC9 00FE4CCA 926E73B3 vs 00FE4CC9 00FE4CC9 2D13A897
0008F9D0 00FC272B 0000021B vs 0008F9D0 0008F9C9 954084D3
00F3C466 00F3C46B 4EA80AD3 vs 00F3C466 00F3C466 F81F6EFD
00FE4CC9 00FE4CCA 926E73B3 vs 00FE4CC9 00FE4CC9 2D13A897
0008F9D0 00FC272B 0000021B vs 0008F9D0 0008F9C9 954084D3
во входном файле только связи. Через один объект может проходить несколько маршрутов, и в нескольких связях может участвовать один объект, как в качестве начала так и в качестве конца связи.
Выяснилось, что все сложнее, чем казалось. Проблема NP полная, а под рукой вычислительного кластера нет.
Original song The longest Time
Original artist Billy Joel
— Woh, oh-oh-oh
Find the Longest Path
Woh oh-oh
Find the Longest Path
If you said P is NP tonight
There would still be papers left to write
I have a weakness
I'm addicted to completeness
And I keep searching for the longest Path
The algorithm I would like to see
Is of Polynoimal Degree
Buts its elusive,
Nobody has found conclusive
Evidence that we can find the Longest Path
I have been hard
Working for so long
I swear its right,
But he marks it wrong
Somehow I'll feel sorry when its done
GPA 2.1,
Is more than I hoped for
Garey, Johnson, Karp and other Men (and Women)
Try to make it Order n log n.
Am I a math fool
If I spend my life in Grad School
Forever following the Longest Path.
Woh oh-oh-oh
Find the longest path
Woh oh-oh-oh
Find the longest path
Original song The longest Time
Original artist Billy Joel
— Woh, oh-oh-oh
Find the Longest Path
Woh oh-oh
Find the Longest Path
If you said P is NP tonight
There would still be papers left to write
I have a weakness
I'm addicted to completeness
And I keep searching for the longest Path
The algorithm I would like to see
Is of Polynoimal Degree
Buts its elusive,
Nobody has found conclusive
Evidence that we can find the Longest Path
I have been hard
Working for so long
I swear its right,
But he marks it wrong
Somehow I'll feel sorry when its done
GPA 2.1,
Is more than I hoped for
Garey, Johnson, Karp and other Men (and Women)
Try to make it Order n log n.
Am I a math fool
If I spend my life in Grad School
Forever following the Longest Path.
Woh oh-oh-oh
Find the longest path
Woh oh-oh-oh
Find the longest path
Задача точно решаемая за реальное время на среднем PC даже в лоб! Когда пройдет полная неделя я расскажу свой алгоритм. Поверьте, он не сложен. Возможно вам мешает груз знаний. Попробуйте подойти к задаче совершенно с другой стороны. Может вам будет проще, если скажу, что не знаком с дискретной математикой и соответственно не использовал этих знаний при решении
P.S. Кавер на Билли Джоела зачетный :)
P.S. Кавер на Билли Джоела зачетный :)
Уважаемый читатель! Если ты читаешь эту запись через 300 лет после ее опубликования (может чуть раньше или чуть позже) знай, что в 2011 году эта задача считалась сложной, и я не знаю никого (кроме себя), кто смог бы ее решить менее, чем за одну неделю. Тактовая частота процессора среднего компьютера в наше время составляла 3 Ггц, среднее количество процессоров одного компьютера равнялось четырем. Если получится решить задачу, сообщи пожалуйста мне, и, если я буду еще жив, напишу на страницах своего блога, насколько ты крут ;)На самом деле это задача максимум на один вечер для любого приличного студента программистской специальности. И в 2011 и даже, как помнится, в 2000 году эта задача не была сложной и тянула на среднюю лабу по структурам и алгоритмам ОД или просто дискретки в целом. Делать никто не стал, не потому что задача слишком сложная или все тупые, а потому что «это никому не надо» больше чем «интересно ради интереса». Это совершенно не сложная задача в целом, но это СЛИШКОМ сложная задача для малоизвестного конкурса ради интереса ;)
Выложите потом своё решение, как обещали, будем изучать. Но если там настолько «в лоб», что моё решение с обходом в глубину показалось «оптимизацией», то как-то это несерьёзно, имхо)
но это СЛИШКОМ сложная задача для малоизвестного конкурса ради интереса ;)
сойдемся на этом.
Но если там настолько «в лоб», что моё решение с обходом в глубину показалось «оптимизацией», то как-то это несерьёзно, имхо)
но ведь ваш ответ был неправильным, почему вы говорите «моё решение» и рассуждаете о несерьезности задачи? вы же её не решили
сойдемся на этом.
Но если там настолько «в лоб», что моё решение с обходом в глубину показалось «оптимизацией», то как-то это несерьёзно, имхо)
но ведь ваш ответ был неправильным, почему вы говорите «моё решение» и рассуждаете о несерьезности задачи? вы же её не решили
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Конкурс для программистов №2