Алексею, читателю хабры, удалось получить лучшее время (0.052) среди всех пользователей сайта uva.onlinejudge.org. Вот его решение. Мои поздравления!
Он также написал генератор тестов, возможно кому-нибудь понадобится.
Честно говоря, я сначала полагал, что такое решение должно быть значительно быстрее чем оба варианта из поста, но это оказалось не так. Думаю, что тут все дело в «не очень удачных тестовых наборах» под такой подход.
Я рад, что вы так быстро пришли к выводу, что с нашими граничными условиями на числа, можно обойтись не только без сортировки, но и без поиска. Но спешу вас огорчить: я проверял такой подход, он медленнее, чем первый вариант. Мою реализацию вашего подхода на C++ можно скачать тут и проверить. Accepted (0.488)
Предполагаю, что такой подход дает бешеный прирост производительности в случаях, когда у нас много разных чисел от 1 до 10000, но когда чисел мало, а разброс между ними большой (например два числа: 1 и 10000) и Q стремится к максимуму, то все преимущества сразу пропадают, потому что независимо от количества разных чисел нам все равно приходится работать с массивом в 10000 элементов.
Благодарю.
Магические константы и не совсем логичный код сделаны специально, чтобы ускорить работу алгоритма. Тем более, что с C++ я, мягко говоря, почти не знаком и изучаю его параллельно со своим хобби. Но я обещаю совершенствоваться со временем. Кстати, отмечу что эта задача не такая уж и очевидная, во всяком случае для меня.
Очень не сложная задачка, алгоритм поиска очень простой: Начиная от начальной точки помечаете не помеченные клетки доски, в которые можно добраться в 1 шаг цифрой 1, потом все клетки, в которые можно добраться конем из клеток с цифрой 1 помечаете цифрой 2 и т.д. В итоге получаете доску с размеченным числом шагов до любой клетки. По этим цифрам несложно было пройти путь обратно от конечной точки до начальной.
Мне кажется, что сегодня, если ты делаешь социальный продукт без большого стартового пинка в виде баксов, весь твой успех на много процентов зависит от случайности: будь то тебя случайно Джобс пропиарил, или по телевизору показали, или НЛО сделала инъекцию в мозг всем жителям планеты Земля с информацией о твоем проекте…
Проверка проводится по ряду тестов на сервере. Есть ограничение по времени работы программы (3 секунды), ну и наверное ограничение на память, хотя в условии об этом не говорится. Эта задача действительно достаточно простая, поэтому тут трудно превысить лимит времени или памяти. Здесь важно учесть все возможные подводные камни.
Рекомендую вам свое решение перекинуть на C++, java или Pascal и отнести на проверку, сразу станет ясно насколько оно удачно.
Я хотел развлечь тех, кому немного скучно, а клавиатура «чешется». Поверьте, не у всех такой скилл программирования олимпиадных задач, как у вас. Тем более задачу я выбирал случайным образом.
Он также написал генератор тестов, возможно кому-нибудь понадобится.
Предполагаю, что такой подход дает бешеный прирост производительности в случаях, когда у нас много разных чисел от 1 до 10000, но когда чисел мало, а разброс между ними большой (например два числа: 1 и 10000) и Q стремится к максимуму, то все преимущества сразу пропадают, потому что независимо от количества разных чисел нам все равно приходится работать с массивом в 10000 элементов.
Магические константы и не совсем логичный код сделаны специально, чтобы ускорить работу алгоритма. Тем более, что с C++ я, мягко говоря, почти не знаком и изучаю его параллельно со своим хобби. Но я обещаю совершенствоваться со временем. Кстати, отмечу что эта задача не такая уж и очевидная, во всяком случае для меня.
Рекомендую вам свое решение перекинуть на C++, java или Pascal и отнести на проверку, сразу станет ясно насколько оно удачно.