но это СЛИШКОМ сложная задача для малоизвестного конкурса ради интереса ;)
сойдемся на этом.
Но если там настолько «в лоб», что моё решение с обходом в глубину показалось «оптимизацией», то как-то это несерьёзно, имхо)
но ведь ваш ответ был неправильным, почему вы говорите «моё решение» и рассуждаете о несерьезности задачи? вы же её не решили
Задача точно решаемая за реальное время на среднем PC даже в лоб! Когда пройдет полная неделя я расскажу свой алгоритм. Поверьте, он не сложен. Возможно вам мешает груз знаний. Попробуйте подойти к задаче совершенно с другой стороны. Может вам будет проще, если скажу, что не знаком с дискретной математикой и соответственно не использовал этих знаний при решении
во входном файле только связи. Через один объект может проходить несколько маршрутов, и в нескольких связях может участвовать один объект, как в качестве начала так и в качестве конца связи.
barker,
значит всё-таки алгоритм был оптимизирован с самого начала! Ваша скорость меня поражает! Интересно обсудить после окончания. Ответы я еще не проверял. Проверю сегодня вечером, завтра утром скажу, есть ли победитель. Пусть будет какая-то интрига ;)
barker,
я тоже сильно удивлен в такой скорости решения, подумал, что вы сразу оптимизировали алгоритм или частично использовали БД. По моим подсчетам решение «совсем в лоб» должно привести к огромному количеству циклов, и хранение временных вариантов должно быть ощутимым
barker, Блин тогда я жёстко затупил в ответе, я почему-то решил, что первое число не длина маршрута, а их количество. Сбило ваше указание "(маршруты, если их несколько)". Зачем тогда это? Или условие было на вашем сайте изначально другое?
Мда, вот косяк…
если ошибка будет только в длине (в первых 4 байтах)- ваш ответ будет засчитан
Хотя оно в любом случае не проканало бы, потому что сейчас проверил, Java через DataOutputStream.writeInt пишет целое число с обратным порядком байт: «00 00 00 01», о чём я вам и говорил выше, собственно. Надо чётко определять подобные тонкости :\
это не имеет значения. объекты и нагрузка идентифицируются 4 байтами, и не имеет значения какой тип какого языка вы используете, главное, чтобы вы читали и писали данные в одном порядке. Но если вы прочитали из файла объект 00 00 00 01, а записали в выходной файл как 01 00 00 00 — то это естественно ошибка
если у решающего что-то важное воспринимается неоднозначно значит возникнет вопрос, без которого дальнейшее решение невозможно. Речь же не о изменении условий задачи в процессе решения, а об уточнениях
Пример выходного файла можно? Так не очень понятно, как он должен выглядеть
для ответа
связь 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-2 конечный будет 2.
А в связи 2-3 начальным будет 2.
То есть любой путь длины 2 — это цикл? :)
Вы как Штирлиц в том анекдоте с числом 33 :)
нет, по определению надо как минимум 2 связи, чтобы получить замкнутый маршрут
На самом деле оказалось, что вышеобсуждаемых проблем нет в принципе :) И если бы вы сразу сказали сколько точно должно быть маршрутов (а их достоверно точно можно посчитать), то ничего из того, что писалось выше никому не пришло бы в голову писать. Верно ведь?
Верно, многих обсуждаемых проблем нет, но приходится их обсуждать, чтобы не давать подсказок о том, что содержится в ответе :)
сойдемся на этом.
Но если там настолько «в лоб», что моё решение с обходом в глубину показалось «оптимизацией», то как-то это несерьёзно, имхо)
но ведь ваш ответ был неправильным, почему вы говорите «моё решение» и рассуждаете о несерьезности задачи? вы же её не решили
P.S. Кавер на Билли Джоела зачетный :)
имеется 2 ответа,
анализ 1-го ответа:
является ли файл файлом маршрутов: нет
анализ 2-го ответа:
является ли файл файлом маршрутов: да
количество связей маршрута: 264
является ли маршрут незамкнутым: да
является ли маршрут вариантом ответа: да
но длина маршрута не максимальна, в файле есть маршруты больше, не всё так просто.
Пока верных ответов нет, конкурс продолжается
значит всё-таки алгоритм был оптимизирован с самого начала! Ваша скорость меня поражает! Интересно обсудить после окончания. Ответы я еще не проверял. Проверю сегодня вечером, завтра утром скажу, есть ли победитель. Пусть будет какая-то интрига ;)
я тоже сильно удивлен в такой скорости решения, подумал, что вы сразу оптимизировали алгоритм или частично использовали БД. По моим подсчетам решение «совсем в лоб» должно привести к огромному количеству циклов, и хранение временных вариантов должно быть ощутимым
ваш ответ получил, спасибо
принимаю к сведению. Это может повлиять только на первые 4 байта, поэтому в ответе в первых 4х байтах варианты допускаются
совет принят, прошу прощения за неудобства
Блин тогда я жёстко затупил в ответе, я почему-то решил, что первое число не длина маршрута, а их количество. Сбило ваше указание "(маршруты, если их несколько)". Зачем тогда это? Или условие было на вашем сайте изначально другое?
Мда, вот косяк…
если ошибка будет только в длине (в первых 4 байтах)- ваш ответ будет засчитан
Хотя оно в любом случае не проканало бы, потому что сейчас проверил, Java через DataOutputStream.writeInt пишет целое число с обратным порядком байт: «00 00 00 01», о чём я вам и говорил выше, собственно. Надо чётко определять подобные тонкости :\
это не имеет значения. объекты и нагрузка идентифицируются 4 байтами, и не имеет значения какой тип какого языка вы используете, главное, чтобы вы читали и писали данные в одном порядке. Но если вы прочитали из файла объект 00 00 00 01, а записали в выходной файл как 01 00 00 00 — то это естественно ошибка
Воот… Т.е. заказчик уточнил спецификацию слегка задним числом. А так всё хорошо начиналось…
почему же? задача уточнена в ходе переговоров :)
для ответа
связь 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
А в связи 2-3 начальным будет 2.
То есть любой путь длины 2 — это цикл? :)
Вы как Штирлиц в том анекдоте с числом 33 :)
нет, по определению надо как минимум 2 связи, чтобы получить замкнутый маршрут
Верно, многих обсуждаемых проблем нет, но приходится их обсуждать, чтобы не давать подсказок о том, что содержится в ответе :)
а почему не 1-2-3-4-1-2-5-6-1?
конечный объект связи 4-1 является начальным объектом связи 1-2