Комментарии 176
У вас что-то не так с размерностями: «с частотой 1 мбит».
А ещё «Начало передачи спутниками псевдослучайной последовательности и приема сигнала на земле — идеально совпадают»; поясните, пожалуйста, как синхронизировались часы? (отсутствие одновременности для разных систем отсчёта)
А ещё «Начало передачи спутниками псевдослучайной последовательности и приема сигнала на земле — идеально совпадают»; поясните, пожалуйста, как синхронизировались часы? (отсутствие одновременности для разных систем отсчёта)
Это эксперименты с БАК привели к тому, что мир плоским стал, или термояд?
Ещё вопрос. Случайная последовательность всегда приходит в сохранности, с точностью до бита?
На мой взгляд, было бы технологичнее развернуть систему наподобие ejudge, чтобы можно было онлайн проверять свои решения. А задачка интересная, жаль, что не смогу поучаствовать :)
Интересная задача, не ожидал, правда. Думал, полегче будет :)
to_string( (pos)%10000000/10 ) для pos = 13 вернет 1 или 0000001?
Можно присылать отдельно «быстрое решение» и «компактное»?
А я что-то не понял, откуда берется сдвиг? Тот пул нолей и единиц — это то, что отправляет каждый спутник, или уже сдвинутая посылка?
Спутники — фиксированны в точках, отдаленных от центра координат на расстояние от 10 до 20тыс км
Подскажите, минимальное расстояние до спутника 10км или 10тыс км?
А у вас приёмник в какой момент точно говорит значение бита кодовой последовательности? Скажем, приёмник находится на расстоянии в 200 метров от спутника, первым битом в принятой последовательности будет первый бит, или хвост?
НЛО прилетело и опубликовало эту надпись здесь
Координаты спутников точны или округляются до какого-то знака? Иными словами, можно ли в примере
И как именно считается время в случае, если программа использует больше одного ядра?
-1.07643e+007считать, что точные координаты спутника -107643000, -148409000?
-1.48409e+007
И как именно считается время в случае, если программа использует больше одного ядра?
Округляются.
Время — естественно считается «wall clock», иначе не было бы смысла использовать несколько ядер.
Время — естественно считается «wall clock», иначе не было бы смысла использовать несколько ядер.
А до какого знака округляются? И вверх, вниз или к ближайшему целому?
Округление как обычно — «к ближайшему» десятичному знаку.
Это не значит, что округление именно до целого числа, может быть десятки метров, может быть 0.1м.
Это не значит, что округление именно до целого числа, может быть десятки метров, может быть 0.1м.
Будут ли все координаты в одном входном наборе округлены до одинакового числа значащих цифр?
Как минимум, если в конце будут нули — в научной записи одного из значений может оказаться меньше цифр, так что я бы не стал сильно закладываться на такие детали.
Если мы знаем точное положение спутников, задача заключается в пересечении нескольких колец шириной 30 метров. А вот если, как в примере выше, положение спутников известно с точностью +-500 метров по каждой из осей, мы получаем ширину кольца больше 1км. И достичь высокой точности на таком тесте — задача уже совсем другая. Вы уверены, что это всего лишь деталь, на которую не надо закладываться?
Можете выложить оффсеты для тестовых примеров?
Можете объяснить следующую фразу:
То есть мы можем принимать сигнал от 10 млн. спутников в секунду одновременно?
сигнал мы принимаем с частотой 10 миллионов выборок в секунду
То есть мы можем принимать сигнал от 10 млн. спутников в секунду одновременно?
От одного спутника. Если он отправляет 1.1.0.1, то мы получим 1111111111.1111111111.0000000000.1111111111
Мне кажется, авторы перемудрили с заданием…
… а вот с точностью и однозначностью формулировок — явная недоработка.
Что такое «выборка» для меня до сих пор загадка, а додумывать как AterCattus — плохой вариант.
Честно, ждал задания, но, даже при 20-м прочтении я все еще не уверен что все понял правильно.
К тому же, на олимпиадах принято давать несколько примеров входных данных и ответы на них.
В общем, ждем новых и проработанных заданий по типу настоящих ТЗ в будущем.
Зы. Если вдруг, этим комментарием, я выиграю в номинации «самое коротное решение» — Вы знаете где меня искать;)
… а вот с точностью и однозначностью формулировок — явная недоработка.
Что такое «выборка» для меня до сих пор загадка, а додумывать как AterCattus — плохой вариант.
Честно, ждал задания, но, даже при 20-м прочтении я все еще не уверен что все понял правильно.
К тому же, на олимпиадах принято давать несколько примеров входных данных и ответы на них.
В общем, ждем новых и проработанных заданий по типу настоящих ТЗ в будущем.
Зы. Если вдруг, этим комментарием, я выиграю в номинации «самое коротное решение» — Вы знаете где меня искать;)
Полностью с Вами согласен, условие задания не совсем поняты, пример input/output есть:
Примеры файлов ввода/вывода — можно скачать тут: s.14.by/glonass-contest.zip
Почему додумывать-то.
Источник сигнала за секунду выдает 1кк значений, приемник — 10кк. Значит каждый исходный бит повторяется на приемнике 10 раз подряд.
Источник сигнала за секунду выдает 1кк значений, приемник — 10кк. Значит каждый исходный бит повторяется на приемнике 10 раз подряд.
Потому как многолетний опыт разработки подсказывает, что абсолютно любые выводы о требованиях к решению, сделанные путем логических выводов из ТЗ, ошибочны, где ошибкой является, как минимум, то что они не описаны в ТЗ, а требуют дополнительной работы от каждого исполнителя, вместо однократной от составителя ТЗ.
Разумеется,Москва не сразу стро.. ТЗ не сразу становится хорошим, но это не повод выкладывать его настолько сырой вариант.
Любая олимпиадная задача детерминирована на 147%, того же я ожидал и здесь.
Разумеется,
Любая олимпиадная задача детерминирована на 147%, того же я ожидал и здесь.
НЛО прилетело и опубликовало эту надпись здесь
Далее — 10млн цифр 0 или 1, принятая на земле псевдослучайная последовательность с этого спутника.
Алгоритм генерации псевдослучайной последовательности:
Если под генерируемым подразумевается не получаемая на земле последовательность, то задание вообще непонятным становится. А при допуске кривой формулировки все логично, имхо.
P.S. Я сначала начинал делать, поняв алгоритм именно как источник (и на используемом ЯП даже сходилось хорошо по формуле). Но на java всплыло, что pos/10 меняется раз в 10 шагов, что заставило, еще раз перечитав задание и комменты, поменять мнение о задаче.
НЛО прилетело и опубликовало эту надпись здесь
У меня для всех 7 последовательностей нашлись нужные смещения.
Но пока не устраивает скорость и нет 100% уверенности в коде) Завтра будут все перепроверять и пробовать «ускорять».
Но пока не устраивает скорость и нет 100% уверенности в коде) Завтра будут все перепроверять и пробовать «ускорять».
НЛО прилетело и опубликовало эту надпись здесь
(thedigest[0] >> 4) & 0x0F > 7НЛО прилетело и опубликовало эту надпись здесь
md5 выдает 128 бит (16 байт). Это 32 символа в hex.
Без наложения маски у вас в symbol получается значение первых двух символов строковой записи хеша.
Без наложения маски у вас в symbol получается значение первых двух символов строковой записи хеша.
А не проще ( 0xFF & thedigest[0] ) > 0x70
Зачем лишний сдвиг.Только у меня всё равно не получается последовательность, как в примере.
Зачем лишний сдвиг.Только у меня всё равно не получается последовательность, как в примере.
У меня как у Vayun, разве что наложение маски и сдвиг в обратном порядке. Что не существенно.
Просто наложение маски дает в результате первые два символа md5hex.
Просто наложение маски дает в результате первые два символа md5hex.
Да, вы правы — тут было не вполне ясно написано.
Я подкорректировал описание, надеюсь сейчас все стало понятнее.
Я подкорректировал описание, надеюсь сейчас все стало понятнее.
НЛО прилетело и опубликовало эту надпись здесь
со скоростью передачи 1 Мегабит (миллион бит в секунду), сигнал мы принимаем с частотой 10 миллионов выборок в секунду.
Псевдослучайная последовательность повторяется каждую секунду.
Я правильно понимаю, что длина последовательности которую передает спутник равна одному миллиону бит? Но если
pos — изменяется от 0 до 9999999.
то в итоге получается 10 миллионов бит? Или генерируется 10 Мбит, но передается только первый 1 миллион бит?
Читаю комментарии и понимаю, что я понимаю все меньше…
НЛО прилетело и опубликовало эту надпись здесь
Господа, это я глупый (я, честно — с горы у пал, сотрясение, ушибы, сижу болею), или что-то не так?
В условиях отсутствия помех, задача сводится к поиску опорного участка из 1М заранее известной выборки (сразу приводим 10М к 1М, т.к. нет помех и границы интервалов известны, а внутри-интервальный фазовый сдвиг сразу определяем по первому интервалу)? Что, очевидно, может быть сделано не более чем за один проход выборки спутника с максимальной точностью? Т.е. однократный проход трёх первых спутников всегда даёт максимальную точность, положения, которая упирается в точность double-арифметики?
P.S. Никто не хочет скооперироваться с java-гуру инвалидом?
В условиях отсутствия помех, задача сводится к поиску опорного участка из 1М заранее известной выборки (сразу приводим 10М к 1М, т.к. нет помех и границы интервалов известны, а внутри-интервальный фазовый сдвиг сразу определяем по первому интервалу)? Что, очевидно, может быть сделано не более чем за один проход выборки спутника с максимальной точностью? Т.е. однократный проход трёх первых спутников всегда даёт максимальную точность, положения, которая упирается в точность double-арифметики?
P.S. Никто не хочет скооперироваться с java-гуру инвалидом?
И очевидно, что нужно отбирать максимально-удалённые друга от друга спутники до декодирования.
НЛО прилетело и опубликовало эту надпись здесь
;)
Ну, прежде всего, если у нас всегда суперсэмплинг 1:10, то субинтевальный сдвиг (в пределах 10 бит входной последовательности) находится по первому изменению сигнала — так?
Дальше. Про разрешение сдвига — мне врачи много думать запретили, но опыт-то не пропьёшь :)
На кой чёрт Вам сдвигать всё? Рассказываю алгоритм оптимального поиска:
Берёте кодирующую последовательность (то, что md5 выдаёт, но без десятикратного повтора каждого интервала).
Находите максимальную по длине последовательность единиц и нолей — берёте то, что встречается меньше. Выбираете одну. Это опорная точка.
У нас всего 1М отсчётов ЗАРАНЕЕ ИЗВЕСТНОЙ кодирующей последовательности. Что смешно и мало.
Берёте контекст после опорной точки — некоторое количество бит, делающее последовательность уникальной в пределах кодирующей.
А теперь задача поиска фазового сдвига сводится к поиску длинной последовательности нолей/единиц (коих мало и делается быстро) и последующему сравнению короткого контекста — если контекст совпал, то опорная точка найдена и сдвиг известен с максимальной точностью. Если не совпал — продолжаете поиск длинной последовательности.
Это максимальной-возможно быстрый алгоритм, который ещё и абсолютную точность даёт.
Могу рассказать, как быстро искать контекст — практически со скоростью чтения массива памяти :)
Ну, прежде всего, если у нас всегда суперсэмплинг 1:10, то субинтевальный сдвиг (в пределах 10 бит входной последовательности) находится по первому изменению сигнала — так?
Дальше. Про разрешение сдвига — мне врачи много думать запретили, но опыт-то не пропьёшь :)
На кой чёрт Вам сдвигать всё? Рассказываю алгоритм оптимального поиска:
Берёте кодирующую последовательность (то, что md5 выдаёт, но без десятикратного повтора каждого интервала).
Находите максимальную по длине последовательность единиц и нолей — берёте то, что встречается меньше. Выбираете одну. Это опорная точка.
У нас всего 1М отсчётов ЗАРАНЕЕ ИЗВЕСТНОЙ кодирующей последовательности. Что смешно и мало.
Берёте контекст после опорной точки — некоторое количество бит, делающее последовательность уникальной в пределах кодирующей.
А теперь задача поиска фазового сдвига сводится к поиску длинной последовательности нолей/единиц (коих мало и делается быстро) и последующему сравнению короткого контекста — если контекст совпал, то опорная точка найдена и сдвиг известен с максимальной точностью. Если не совпал — продолжаете поиск длинной последовательности.
Это максимальной-возможно быстрый алгоритм, который ещё и абсолютную точность даёт.
Могу рассказать, как быстро искать контекст — практически со скоростью чтения массива памяти :)
Т.к. последовательность заранее известна всё становится весьма скучно.
При чтении из файла на лету кодируем в RLE. В таком представлении в этой конкретной последовательности есть 28 уникальных 2х-байтовые кусков. Если сделать табличку, то можно гарантированно находить смещение просмотрев худшем случае только 23% последовательности.
При чтении из файла на лету кодируем в RLE. В таком представлении в этой конкретной последовательности есть 28 уникальных 2х-байтовые кусков. Если сделать табличку, то можно гарантированно находить смещение просмотрев худшем случае только 23% последовательности.
А если уникальные куски будут начинаться с длинной последовательности, то сравнение ещё упрощается. И нет смысла, несколько опорных точек искать — всё равно, скорее всего, нужно будет отсекать «лишние» спутники, а для этого нужно читать весь файл. При таком кодировании расходами на поиск опорной точки можно пренебречь — расходы на файловый ввод/вывод и декодирование будут больше. Соответственно, искать фазу по одной точке всегда.
И 2 байта для java плохо. Лучше int (4 байта), т.к. он там быстрее.
И лучше RLE-NZ — не различать ноли и единицы — уникальность не потеряется, т.к. всё равно можно использовать int или long, т.к. в java они быстрее работа. И класть результат RLE в тетрады.
И 2 байта для java плохо. Лучше int (4 байта), т.к. он там быстрее.
И лучше RLE-NZ — не различать ноли и единицы — уникальность не потеряется, т.к. всё равно можно использовать int или long, т.к. в java они быстрее работа. И класть результат RLE в тетрады.
Ну вот, коллега, вы раскрыли все мои карты! :) Аналогичный алгоритм уже сейчас у меня дает 50мс на спутник на i5 в один поток. Теперь, наверное, введут ограничение и требование вводить для каждого спутника salt, мешающий проанализировать последовательность до начала работы.
P.S. Уважаю программистов старой закалки, которые не начинают работу, пока не выстроят всю логическую цепочку в голове.
P.S. Уважаю программистов старой закалки, которые не начинают работу, пока не выстроят всю логическую цепочку в голове.
Как-то медленно — нужно кэшированием чтения, чтением из файла, кодированием данных поиграться. Кстати, крайний случай, когда сдвиг практически равен длине последовательности и происходит «заворот» маркера, не забыли обрабатывать и отладить?
Делаю чтение из файла сразу с проверками, без кеширования данных. Возможно, если пускать файл через stdin и поиграться с буферами, то будет чуть быстрее. Ну и я не уверен в скорости Java 1.6 на Mac OS X vs 1.7 на Windows. «Заворот» обрабатываю тем, что ищу сразу два паттерна — 19 единиц и 18 нулей. «Разрезана» может быть только одна из них, а т.к. находятся они в последовательности очень удачно (одна в первом миллионе, другая в седьмом), то никогда не приходится перебирать целиком весь массив при корретных вводных данных. Из логичных оптимизаций еще напрашивается сделать поиск промежуточных паттернов и многопоточную обработку. Но вообще, положа руку на сердце, соревноваться «кто быстрее найдет паттерн в массиве» как-то не спортивно, изначальная задача наверняка подразумевала, что сколько-то вызовов md5 прийдется сделать во время работы.
Даже если последовательность неизвестна достаточно будет посчитать rolling hash, и пробежаться от начала до конца. Правда в таком случае с двумя спутниками уже ничего не найдешь.
А причём два спутника? rolling hash мне в голову приходил, но мне показалось, что его реализация будет не быстрее поиска по патерну.
Я имел в виду BufferedInputStream. Мне кажется, что поиск одной последовательности будет быстрее. А если последовательность не найдена, то она разрезана — обрабатывать отдельно, но это крайне редкий и, скорее всего, не возможный случай.Дело в том, что если правильно всё написать, то бОльшая часть затрат времени всё равно уходит на чтение и декодирование файла, так что имеет смысл делать максимально-быстрый поточный алгоритм, а это значительно быстрее с одним патерном.
И это только половина дела. Наверное даже меньшая. Там дальше танцы с поиском оптимального набора спутников, либо огород с обработкой данных сразу от всех спутников (кстати, это два совершенно разных пути). И ещё приседания с точностью, так как во множетсве случаев всё упирается в точность double, но, по-моему, оно решается подбором очерёдности расчёта и коэффициентов.
И это только половина дела. Наверное даже меньшая. Там дальше танцы с поиском оптимального набора спутников, либо огород с обработкой данных сразу от всех спутников (кстати, это два совершенно разных пути). И ещё приседания с точностью, так как во множетсве случаев всё упирается в точность double, но, по-моему, оно решается подбором очерёдности расчёта и коэффициентов.
Использую BufferedReader. Не удивлюсь, если само чтение из файла и занимает 49.9 мс из 50. В таком случае поиск нескольких паттернов может быть полезным из-за более раннего выхода из цикла. Проверим.
Вот это уже добавляет интереса в соревнование. Завтра попробую несколько вариантов, тут есть разные хитрости, особенно с учетом использования i7-3820 c HT, т.е. с 8ю потоками.
И это только половина дела. Наверное даже меньшая.
Вот это уже добавляет интереса в соревнование. Завтра попробую несколько вариантов, тут есть разные хитрости, особенно с учетом использования i7-3820 c HT, т.е. с 8ю потоками.
Ранний выход, это хорошо, но файл всё равно должен быть прочитан весь, так что ранний выход даёт мало относительного прироста — я именно это имел в виду. И кстати, русских букв в файле быть не может, так что самописное чтение файла, как байтового потока, с самописным выделением строк и особенно декодированием строк последовательности даст значительный прирост. Стандартные функции чтения имеют значительный оверхед на работу с кодировками символов и перекодированием UTF16. Да и с буферами там сложности. При самописном же чтении можно обойтись одним байтовым буфером на ткущую строку в 10М+2 символов и работать прямо в нём.
А зачем файлу быть прочитанным целиком, если нам известен размер каждого блока +-10 байт? Это ведь две мантиссы с экспонентами + 10кк цифр, можно с помощью различных seek сразу выделить каждому потоку нужный сегмент файла, вернее, System.in потока. Тут как раз будет важно первым заходом получить примерные координаты по 2-4 спутникам (по количеству ядер) и следующим шагом выбрать максимально удаленные, если временная квота позволяет. А вот работа сразу с byte это хорошая мысль, спасибо. Активно использую это в Nomad Reader, а тут как-то сразу не пришло в голову.
Если хочется максимальной скорости любой ценой, то readAllBytes и вперед парсить вручную. На Си на один спутник уходит ~1мс, так что улучшать есть куда)
Не верно. Вы не учитываете, как оно на более низком уровне работает — библиотеки и ОС. Подобная оптимизация только только замедлит. А seek это вообще адово медленная операция. По ка вы seek сделаете, я уже последовательность прочитаю.
Мне кажется, что нет смысла примерные координаты считать — имеет смысл читать всё, либо делать отсечку по количеству спутников (если спутников много), а потом отбор по используемым спутникам сделать. Расчёт координат как раз мгновенно на фоне всего остального будет. А вот выбор спутников для расчёта будет соизмерим со временем чтения файла и поиска фаз.
Мне кажется, что нет смысла примерные координаты считать — имеет смысл читать всё, либо делать отсечку по количеству спутников (если спутников много), а потом отбор по используемым спутникам сделать. Расчёт координат как раз мгновенно на фоне всего остального будет. А вот выбор спутников для расчёта будет соизмерим со временем чтения файла и поиска фаз.
Ну как же так, коллега? На среднестатистическом винчестере с 100мб/с вы будете 100 спутников считывать порядка 10 секунд. А если их будет 200, 500? Последовательно разумно читать 3-5 спутников по 10мб, затем делать их анализ, а параллельно прыгать по файлу через seek (даже если его вызов займет по 10мс на спутник, это примерная скорость для современных HDD) и выбирать наиболее полезные дополнительные спутники по координатам.
А если же подача данных через System.in означает автоматическое прекеширование входящих данных и замер скорости будет именно алгоритма, то вообще мы не о том говорим.
А если же подача данных через System.in означает автоматическое прекеширование входящих данных и замер скорости будет именно алгоритма, то вообще мы не о том говорим.
Данные гарантированно будут в дисковом кеше, чтобы тестировать решение а не диск (скорость его мне и так известна, 500Мб/сек).
Добавлено в описание.
Добавлено в описание.
Всё верно, если бы был файл, то используем MappedByteBuffer и читаем только то что надо. Но по условию всё читается из стандартного ввода, так что остается предполагать hot cache, иначе 99.9% времени будет занимать чтение входных данных и конкурс не имеет смысла)))
ограничение есть на максимальное расстояние от центра координат в 6000км,
на скорости света это задержка существенно меньше секунды, а значит хвосты от разных спутников будут гулять в районе начала последовательностей, и даже до середины не дойдут…
Расстояние между спутниками даже такой задержки не дадут.
на скорости света это задержка существенно меньше секунды, а значит хвосты от разных спутников будут гулять в районе начала последовательностей, и даже до середины не дойдут…
Расстояние между спутниками даже такой задержки не дадут.
Если точнее, то максимальное расстояние между спутником и приёмником 20'000+6'378=26'378 км, это расстояние свет проходит за 0.0879875 секунды, а значит, максимальное смещение — 879'875 отсчётов, что, конечно, существенно меньше 10'000'000. Так что анализировать достаточно первый мегабайт, остальное можно скипать. Если читать все 10Мб, возможно, будет заметный провал в производительности: кэш третьего уровня в i7 только 8Мб.
Как быстро найти опорную точку? Ну, например кодировать входную последовательность (после деления кол-ва отсчётов на 10, конечно же) в RLE.
Т.е. вместо единиц и нолей ставите их количество. Скорее всего единица там или ноль вообще не нужно знать. Количество уменьшаете на 1 закатываете 4-битную тетраду long-слова. Если единиц или нолей подряд больше 16, то пишете 16.
Например:
111011000111111 будет представлено, как 0x20125
Жизненный опыт говорит, что при такой относительно короткой кодирующей последовательности будет существовать множество уникальных контекстов, помещающихся в слово long (16 изменений сигнала — это много) в таком кодировании.
Дальше экодер преобразует входную последовательность в long-числа, а компаратор сравнивает с искомым контекстом, как сравнение чисел long на равенство. На каждом следующем шаге энкодер сдвигает начало сравниваемой последовательности к следующему изменению сигнала.
Скорость получается адова.
Т.е. вместо единиц и нолей ставите их количество. Скорее всего единица там или ноль вообще не нужно знать. Количество уменьшаете на 1 закатываете 4-битную тетраду long-слова. Если единиц или нолей подряд больше 16, то пишете 16.
Например:
111011000111111 будет представлено, как 0x20125
Жизненный опыт говорит, что при такой относительно короткой кодирующей последовательности будет существовать множество уникальных контекстов, помещающихся в слово long (16 изменений сигнала — это много) в таком кодировании.
Дальше экодер преобразует входную последовательность в long-числа, а компаратор сравнивает с искомым контекстом, как сравнение чисел long на равенство. На каждом следующем шаге энкодер сдвигает начало сравниваемой последовательности к следующему изменению сигнала.
Скорость получается адова.
Не дописал:
А учитывая, что у нас искомый контекст начинается с длинной последовательности нолей/единиц, энкодер вообще на каждом шаге пропускает кучу данных, пока не встретится последовательность нужной длинны.
Если в крации, то ищем окном с привязкой начала окна к длинной последовательности и кодированием NRZ-RLE
А учитывая, что у нас искомый контекст начинается с длинной последовательности нолей/единиц, энкодер вообще на каждом шаге пропускает кучу данных, пока не встретится последовательность нужной длинны.
Если в крации, то ищем окном с привязкой начала окна к длинной последовательности и кодированием NRZ-RLE
Чтобы не перебирать спутники и достичь максимальной точности ограничиваем кол-во используемых спутников, и отбираем те, которые образуют многоугольник максимальной площади. Естественно, до начала декодирования из сигнала.
Т.к. с перебором многоугольников чёрт ногу сломит, то, например, ограничиваем кол-во спутников кратным трём и сводим задачу к поиску n-треугольников треугольников максимальной площади из заданного набора вершин. Сверху прикрутить оптимизацию и фильтрацию по-вкусу.
6 или 9 спутников будут давать очень хороший результат, IMHO.
Т.к. с перебором многоугольников чёрт ногу сломит, то, например, ограничиваем кол-во спутников кратным трём и сводим задачу к поиску n-треугольников треугольников максимальной площади из заданного набора вершин. Сверху прикрутить оптимизацию и фильтрацию по-вкусу.
6 или 9 спутников будут давать очень хороший результат, IMHO.
В условиях отсутствия помех достаточно данных любых двух спутников, главное определить сдвиг, только вот условия задачи несколько размыты, для определения этого сдвига.
Вон выше уже алгоритм расписан — чего размыто-то? Кроме того, если спутники далеко, то даже точное определение фазы даёт точность десятки метров. А если спутники рядом, то они дают две точки пересечения, плюс, точность падает до нескольких сотен метров. Т.е. нужно три и более спутников, отстоящих на максимальное расстояние.
Всё упирается в перебор спутников и точность double-арифметики.
Всё упирается в перебор спутников и точность double-арифметики.
Два спутника дадут вам 2 возможные точки. В общем случае нужно 3 спутника.
А java 64-бита? А то сильно разные производительности в разных случаях у них.
Как считается delta? Евклидово расстояние до правильной точки?
В какую сторону округляется задержка времени при вычислении сдвига последовательности?
Будет ли промежуточное тестирование? Хотя бы на подмножестве тестов.
Так 2 теста лежат — берите и тестируйте :-)
Т.е. нет.
Т.е. нет.
В этих тестах неизвестно настоящее положение ответа (то есть нельзя посчитать delta) и нет параметров системы, на которой будет финальное тестирование (то есть нельзя посчитать время работы).
Ну и промежуточные результаты повысили бы интерес :)
Ну и промежуточные результаты повысили бы интерес :)
НЛО прилетело и опубликовало эту надпись здесь
Этот тот тест, где в ответе ожидалось что-то вида "-1.81683e+006 -1.74334e+006"?
А то у меня там вышло
-1816744.990 -1743348.485 (погрешность 85.431)
Для кучи второй
3069326.513 -2594044.901 (погрешность 8.271)
Погрешность считал относительно значений в test*.out
А то у меня там вышло
-1816744.990 -1743348.485 (погрешность 85.431)
Для кучи второй
3069326.513 -2594044.901 (погрешность 8.271)
Погрешность считал относительно значений в test*.out
НЛО прилетело и опубликовало эту надпись здесь
Не могу понять, как у вас вышла такая малая погрешность в первом варианте.
Повторю тест вручную:
1. Находим в test1.in через текстовый редактор нашу последовательность. Для первого спутника она в колонке 619127, для второго 529102
2. Вычисляем задержку в секундах для обеих спутников делением на скорость света и умножением на 10м через Wolfram Alpha, выходит 1.85609605144166E7 и 1.58620789112716E7 соответственно. Числа точные, потому как тут было только умножение.
3. Считаем точки пересечения. Тоже воспользуемся Вольфрамом. Результат: (-1.61583x10^7, 75872.4) | (-1.81668x10^6, -1.74336x10^6)
Первая точка вне пределов Земли, ее отбросим. Остается "-1.81668e+006 -1.74336e+006", что дает нам Delta = 151.327, т.е. ~151 метр. Программа у меня высчитала с double точностью точку с дельтой 156, но я не понимаю, как там можно было получить 85. Допустим, можно было бы сказать, что у вас более точная константа c, но с 1983 года изменено определение метра и теперь это 1/299792458 от скорости света. Других теорий у меня не осталось
Повторю тест вручную:
1. Находим в test1.in через текстовый редактор нашу последовательность. Для первого спутника она в колонке 619127, для второго 529102
2. Вычисляем задержку в секундах для обеих спутников делением на скорость света и умножением на 10м через Wolfram Alpha, выходит 1.85609605144166E7 и 1.58620789112716E7 соответственно. Числа точные, потому как тут было только умножение.
3. Считаем точки пересечения. Тоже воспользуемся Вольфрамом. Результат: (-1.61583x10^7, 75872.4) | (-1.81668x10^6, -1.74336x10^6)
Первая точка вне пределов Земли, ее отбросим. Остается "-1.81668e+006 -1.74336e+006", что дает нам Delta = 151.327, т.е. ~151 метр. Программа у меня высчитала с double точностью точку с дельтой 156, но я не понимаю, как там можно было получить 85. Допустим, можно было бы сказать, что у вас более точная константа c, но с 1983 года изменено определение метра и теперь это 1/299792458 от скорости света. Других теорий у меня не осталось
У меня другие смещения высчитываются.
А расстояния, соотвественно, 18560930.535 и 15862048.932. Близко к вашему варианту, но другие.
P.S. Со скоростью света у меня все ок :)
А расстояния, соотвественно, 18560930.535 и 15862048.932. Близко к вашему варианту, но другие.
P.S. Со скоростью света у меня все ок :)
... (double)299792458 ...Ага! В текстовом-то редакторе колонки не с нуля считаются, а с 1 :) Значит и смещения на единичку меньше должны быть. Это я заработался уже. Спасибо!
Аналогично — что-то хреновата точность.
Для третьего тестового набора (3_hi_precision) пока что так:
3420804.238 -1950286.68 (погрешность 11.906)
3420804.238 -1950286.68 (погрешность 11.906)
Я хотел бы выразить несогласие с ответом из test1.out.
Значение -1.81683e+006 -1.74334e+006 это одна из точек пересечения окружностей, образованных идеальными радиусами двух спутников (на картинке справа). В более-менее реальной гео-локационной задаче если у нас только два спутника, то логично было бы взять среднюю точку между двумя пересечениями, а не одну из крайних. Вопрос звучит так: стоит подогнать результат под тестовый пример (т.е. взять одну из этих точек), либо можно использовать в такой ситуации центральную точку?
Значение -1.81683e+006 -1.74334e+006 это одна из точек пересечения окружностей, образованных идеальными радиусами двух спутников (на картинке справа). В более-менее реальной гео-локационной задаче если у нас только два спутника, то логично было бы взять среднюю точку между двумя пересечениями, а не одну из крайних. Вопрос звучит так: стоит подогнать результат под тестовый пример (т.е. взять одну из этих точек), либо можно использовать в такой ситуации центральную точку?
картинка
НЛО прилетело и опубликовало эту надпись здесь
Ну так может подразумевалась любая из двух точек пересечения? и если я вставлю туда среднюю точку, то не пройду простейший тест из 2х спутников :)
Я беру все подходящие точки (в вашем случае их две) и считаю среднее положение. Опять же в вашем случае получится как раз средняя точка.
НЛО прилетело и опубликовало эту надпись здесь
> В случае, если однозначное вычисление координат невозможно — допустимо вывести любое из решений.
Означает ли это что в случае двух спутников правильных точек будет две и delta будет равна расстоянию до ближайшей из них?
Означает ли это что в случае двух спутников правильных точек будет две и delta будет равна расстоянию до ближайшей из них?
А если есть одна связная область из допустимых точек, в которой существуют две точки, удалённые более чем на 1 км или, вообще, не существует точки, максимальное удаление до которой меньше 1 км, то ответом считать любую точку из этой области?
Ответом можно считать вообще любую точку на земле. Вопрос лишь в ошибке, и будет ли ответ с такой ошибкой засчитан.
Ошибка рассчитывается до ближайшей «идеальной» точки, полученной геометрическим образом на основе знания идеальных, не округленных параметров задачи.
Т.е. обеспечить ошибку 0 вы не сможете, но можете уменьшить математическое ожидание ошибки.
Ошибка рассчитывается до ближайшей «идеальной» точки, полученной геометрическим образом на основе знания идеальных, не округленных параметров задачи.
Т.е. обеспечить ошибку 0 вы не сможете, но можете уменьшить математическое ожидание ошибки.
Если разместить два (да хоть двести два) спутника внутри окружности радиуса один метр, область допустимых решений будет представлять собой здоровое слегка деформированное кольцо и шансов попасть рядом с правильным решением будет крайне мало, хоть какую мегаматематику применяй. Есть надежда, что набор тестов не содержит подобных невменяемых конфигураций :-)
lany дело говорит, в общем случае невозможно написать программу, проходящие все возможные тесты хоть с какой-то вменяемой вероятностью. Это печалит, потому что не понятно, где проводить границу между «сложный тест» и «ну, такого в тестах не будет». Это особенно важно для тех, кто пишет mincode, потому что точность для этих участников не главный приоритет, а значит им нехорошо просто говорить: «сделай как можно лучше».
Вам не нужно пройти все возможные тесты с очень маленькой ошибкой, вам достаточно пройти их лучше конкурентов :-)
Но ваши чувства я понимаю — в 99% олимпиадных задач приучают именно к математически строгому идеальному решению.
В жизни же обычно получается как в этой задаче…
Но ваши чувства я понимаю — в 99% олимпиадных задач приучают именно к математически строгому идеальному решению.
В жизни же обычно получается как в этой задаче…
Проблема не в идеальности/не идеальности, а в невозможности пройти предложенный lany тест. С этой фразой факт невозможности попасть в +-1км плохо соотносится: «за самое компактное решение, проходящее все тесты (по времени и требуемой точности) 1 BTC.» То есть, если составить сильный набор тестов, то в этой номинации просто не будет победителя.
НЛО прилетело и опубликовало эту надпись здесь
С тем что был факап я согласен — правда в другом месте, с округлением координат. Это существенно усложняло задачу и делало её намного более мутной — и это пришлось исправить через день после начала с изменением тестов.
А в случае с генерацией последовательности — это обычное дело, на соревнованиях постоянно кто-то фиксируется на своем понимании какого-то нюанса условий и не может вырваться — это самые сложные для нахождения ошибки. Даже если бы я сказал «первые 4 бита» или даже «первый бит хэша» — все равно остался бы вопрос «big endian» или «little endian», требовавший бы проверок различных вариантов.
А в случае с генерацией последовательности — это обычное дело, на соревнованиях постоянно кто-то фиксируется на своем понимании какого-то нюанса условий и не может вырваться — это самые сложные для нахождения ошибки. Даже если бы я сказал «первые 4 бита» или даже «первый бит хэша» — все равно остался бы вопрос «big endian» или «little endian», требовавший бы проверок различных вариантов.
На MD5 вообще наплевать. Задача могла формулироваться как «берётся некая последовательность, которая неизвестно как сгенерирована, но всегда постоянная». Её же можно из любого сэмпла вытащить. Надо только взять известный output, посчитать радиусы и смещения. Зачем над этим биться часами — вообще не понимаю.
А после завершения будут опубликованы все или хотя бы некоторые решения?
Мне вот лично было бы весьма интересно посмотреть на лучшие решения да и вообще на подходы к решению задачи.
Мне вот лично было бы весьма интересно посмотреть на лучшие решения да и вообще на подходы к решению задачи.
Судя по прошлому соревнованию — да.
НЛО прилетело и опубликовало эту надпись здесь
Я целился, а что?
Чтобы показать, что компактность кода это бред (оценивать надо не кольчество символов, а результирующий байткод), я послал две версии — на 6000 байт, с комментариями, нормальными названиями, стилем и пр., и ее же, минифицированную до нечитаемости и размера чуть менее 3кб. Выкинуты все лишние пробелы, переносы строк, комменты, константы, сокращены переменные до 1-2 букв. Код из читабельного и реюзабельного стал «черным ящиком». Если кто-то в команде будет писать в таком стиле, то я первый отгрызу ему руки. Надеюсь, что всеобщее безумие с «ЦУП в 30 строк» и подобные номинации рано или поздно сойдут на нет.
Для сравнения, недавно товарищ писал мультиметр для AVR на C, но пытался обойти без флоатов и sprintf/dtostr, чтобы вместиться в 8кб памяти. В программе можно было написать десяток строк без существенного изменения бинарника, но dtostr(amp * 1.257f / 10000.0f) добавляло сразу 2кб к результату. На собственные супер-оптимальные ftoa/ioa и целочисленные вычисления без вспомогательных классов ушла львиная часть времени, но в результате и код читабелен, и размер проги после компиляции около 4кб.
Для сравнения, недавно товарищ писал мультиметр для AVR на C, но пытался обойти без флоатов и sprintf/dtostr, чтобы вместиться в 8кб памяти. В программе можно было написать десяток строк без существенного изменения бинарника, но dtostr(amp * 1.257f / 10000.0f) добавляло сразу 2кб к результату. На собственные супер-оптимальные ftoa/ioa и целочисленные вычисления без вспомогательных классов ушла львиная часть времени, но в результате и код читабелен, и размер проги после компиляции около 4кб.
Байткод сравнивать тоже под вопросом. Если компилируется на стороне проверяющего, то возникает вопрос, какие ключи используются: вставлять ли информацию о номерах строк и именах локальных переменных. По дефолту она есть, и тогда ужимание в одну строку и использование однобуквенных переменных всё равно уменьшит результат. Но если даже отключить всю отладочную инфу, в пул констант лягут имена полей и методов (они в любом случае должны быть доступны в рантайме, ибо рефлекшн), поэтому их тоже конкурсанты будут сокращать. Могут проводиться и другие странные оптимизации: например, использование
String.valueOf(x).concat(" ").concat(String.valueOf(y))
Ключи обсудить заранее вообще не проблема. Поля и методы в минимальном коде тоже будут минимальными, без вложенных классов и дженериков.
А вот читабельность это отдельный вопрос — ваш пример с x + " " + y во-первых очень просто описать людским языком в комментах (к тайм-критикал коду так вообще часто делается), во-вторых, в некоторых случаях будет скомпилирован в такой же байт код (в гипотетическом Java 15 или другом рантайме), а в-третьих, еще быстрее и компактнее будет в виде StringBuilder, который вполне читабелен.
А вот читабельность это отдельный вопрос — ваш пример с x + " " + y во-первых очень просто описать людским языком в комментах (к тайм-критикал коду так вообще часто делается), во-вторых, в некоторых случаях будет скомпилирован в такой же байт код (в гипотетическом Java 15 или другом рантайме), а в-третьих, еще быстрее и компактнее будет в виде StringBuilder, который вполне читабелен.
Почему быстрее и компактнее в виде StringBuilder? Именно StringBuilder и будет создан по дефолту из x+" "+y. Эта строка в байткоде превратится в new StringBuilder().append(x).append(" ").append(y).toString(). Не факт, что это будет быстрее и уж точно не компактнее, чем два concat'а. От рантайма это вроде как не зависит, а на некоторые гипотетические случаи странно закладываться: в конкурсе подразумевается конкретная версия Java. В Java 15 наверняка будут свои способы извратиться с целью сократить байткод.
Я всё к тому, что идея оценивать результирующий байткод тоже не идеальна в плане получить красивое приложение. Опять же я в своём решении пользовался вложенными классами (правилами это не запрещено). Для них будет создан отдельный .class-файл со своим констант-пулом, где куча констант будет пересекаться с константами главного класса. Это сразу существенно удлинняет суммарный размер сгенерированных .class-файлов. Если бы я добивался наименьшего размера .class-файлов, я бы, естественно, запихал всё в один класс, пожертвовав структурированностью.
Я всё к тому, что идея оценивать результирующий байткод тоже не идеальна в плане получить красивое приложение. Опять же я в своём решении пользовался вложенными классами (правилами это не запрещено). Для них будет создан отдельный .class-файл со своим констант-пулом, где куча констант будет пересекаться с константами главного класса. Это сразу существенно удлинняет суммарный размер сгенерированных .class-файлов. Если бы я добивался наименьшего размера .class-файлов, я бы, естественно, запихал всё в один класс, пожертвовав структурированностью.
С SB будет 4 вызова функции, как и с конкатами. Будет ли лишний промежуточный класс создаваться — хз, наверное будет. И, думаю, будет работать быстрее за счет отсутствия переаллокаций. Можно перепроверить, но это не критично, я к тому, что экономия в пару байт, еще и в ущерб скорости, еще и та, что могла бы быть изначально оптимизирована компилятором — очень сомнительное место. Нормальный человек так делать станет лишь если это очень-очень-очень нужно. В случае же «компактного кода» реально на конкурс получить программу в один метод и 3-5 длинных строк с goto, однобуквенными переменными и пр. — такой себе аналог байткода.
О, вызовы функции — это мелочи, а вот промежуточных объектов там немало. Дефолтная аллокация 16 байт, для результата из нашей задачи переаллокация будет почти наверняка. Конкаты безусловно выгоднее, если вам надо миллион раз склеить строки попарно. А если с конвертацией чисел в строку и по три — тут я не уверен. Так или иначе, а разница в быстродействии в любую сторону совершенно эфемерна, если эта строчка выполняется один раз: её будет абсолютно не видно на фоне погрешности измерений. Это надо правильный микробенчмарк делать с разогревом. А вот экономия байт в класс-файле с конкатом существенная: речь идёт о десятках байт. Можете сами проверить. Если б я участвовал в конкурсе на минимальный размер .class-файла, я бы безусловно вставил конкаты. Естественно, в реальном коде я бы так не делал. Поэтому конкурсный код с минимизацией хоть исходника, хоть .class-файлов будет выглядеть ужасно, это в любом случае изврат. Думаю, все понимают разницу между программированием на конкурсе и реальным программированием :-)
НЛО прилетело и опубликовало эту надпись здесь
Видимо вторник понятие растяжимое :)
Ну BarsMonster же не сказал, какой конкретно вторник имеется в виду :-)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Майское хабрасоревнование: делаем свой ГЛОНАСС