Привет, Codeforces!
Меня зовут Олег Василенко, я работаю в компании 3DiVi — стартапе, который занимается решением задач компьютерного зрения. Мы решили провести небольшой контест, состоящий из одной оптимизационной задачи на поиск ближайших точек с символическим призом в 5000 рублей за первое место.
Подробности здесь: http://www.3divi.com/rus/index.php/contest
P.S. Это наш первый опыт проведения соревнования по программированию, поэтому просьба сообщать о найденных проблемах, предложения и замечания также приветствуются.
А где условие задачи? :)
Условие задачи снаружи недоступно, необходимо зарегистрироваться в системе. Внутри системы условие задачи можно просмотреть, нажав на вкладку с надписью "А" (не очень удачный дизайн используемой системы тестирования — ejudge, не нашлось настройки для отображения списка задач по-другому).
Видимо это и есть первое предложение/замечание.
Правда, что расстояние в трехмерном пространстве определяется стандартной евклидовой метрикой? Это не совсем очевидно, учитывая, что ввод задается сеткой.
Да, расстояние определяется именно евклидовой метрикой.
По вопросу может возникнуть куча вопросов, вот самые важные:
- какая метрика?
- деление в формулах целочисленное?
- какая нумерация столбцов/строчек?
- как считается результат участника?
1) Метрика евклидова
2) Все деления в формулах рассматриваются как операции над вещественными числами
3) Нумерация строк и столбцов изображения начинается с 1, т.е. номер строки принадлежит отрезку [1...n], номер столбца — отрезку [1...m]
4) Результат участника считается так, как указано в регламенте соревнования :
"... Участник получает балл за прохождение каждого теста, равный разности между ограничением на время выполнения на одном тесте (20 секунд) и временем выполнения решения участника на данном тесте. Если решение участника не проходит данный тест, то участник получает 0 баллов за этот тест.
... Итоговый балл решения считается как среднее арифметическое баллов, полученных данным решением по каждому из тестов, округленное до целого значения. Итоговый балл участника равен наибольшему из итоговых баллов его решений."
При этом время выполнения программы подсчитывается в миллисекундах (и баллы в таблице результатов тоже).
Физик во мне негодует!
Фраза "Участник получает балл за прохождение каждого теста, равный разности между ограничением на время выполнения на одном тесте (20 секунд) и временем выполнения решения участника на данном тесте." очень странная. По началу фразы, можно подумать, что за 1 тест можно получить не больше одного балла, но продолжение противоречит этом. К тому же как можно приравнивать время и баллы?
По всей видимости имелось ввиду, что участник получает по баллу за каждую секунду (или миллисекунду?) оставшуюся до TL, и 0 баллов, если не успел отработать. Как правильно?
Конечно сути это не меняет, но нельзя же так.
Как скоро должно приходить письмо с подтверждением регистрации?
Если регаешься на еджадже, то всегда смотри спам.
Спасибо, и правда упало в спам, а я жду :)
Из положения: «Указанная в п.5.1 денежная сумма включает в себя НДФЛ» Наверное, в п.7.1?
Да, действительно, в пункте 7.1, небольшая опечатка. Спасибо за замечание.
Опечатка исправлена.
Хороший контест, почаще бы такие!
Видимо я занял первое место с учетом только конкурсных участников, и даже могу рассказать что я написал.
Забиваем на сложные и стрёмные Cover tree и 3D Voronoi diagram.
Строим тупое kd-tree c midpoint splitting rule, т.е смотрим по какой координате наш bounding box самый широкий и режем по середине. Если разрез слишком уж тривиальный(<n/8 точек оказалось по одну стороны), то чуть-чуть сдвигаем линию разреза так что бы примерно половина точек была с одной стороны.
Чтобы быстро считать (x0 - x1)2 + (y0 - y1)2 + (z0 - z1)2 юзаем SSE. (Точки только float, никаких double, только тогда мы можем делать 4 умножения за одну инструкцию).
Дописываем быстрый буфферизированый ввод вывод int'ов и float'ов, получаем еще небольшой прирост производительности. (Всё-таки там ~3.5Mib IO). (Там можно еще и при построение дерева использовать MINPS/MAXPS, Но судя по всему на тестах построение дерева занимает ~3% всего времени).
Теперь осталось побаловаться с
inline, __attribute__((optimize("Ofast"))), __attribute__((hot)), __attribute__((__target__("arch=???"))), __attribute__((__target__("fpmath=???"))), выравниванием данных в памяти, расположением массивов, порядком циклов, раскрытием рекурсии в цикл с goto, и всё.???????
PROFIT!
Также мне крайне интересно что написал участник под ником 12341234?
я дальше 19654 поиск в ширину не смог упихать) Уточнения для приближенной точки как делал?
Спасибо! Постараемся проводить контесты почаще.