Блог пользователя LLI_E_P_JI_O_K

Автор LLI_E_P_JI_O_K, 11 лет назад, По-русски

Привет, Codeforces!

Меня зовут Олег Василенко, я работаю в компании 3DiVi — стартапе, который занимается решением задач компьютерного зрения. Мы решили провести небольшой контест, состоящий из одной оптимизационной задачи на поиск ближайших точек с символическим призом в 5000 рублей за первое место.

Подробности здесь: http://www.3divi.com/rus/index.php/contest

P.S. Это наш первый опыт проведения соревнования по программированию, поэтому просьба сообщать о найденных проблемах, предложения и замечания также приветствуются.

  • Проголосовать: нравится
  • +36
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А где условие задачи? :)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Условие задачи снаружи недоступно, необходимо зарегистрироваться в системе. Внутри системы условие задачи можно просмотреть, нажав на вкладку с надписью "А" (не очень удачный дизайн используемой системы тестирования — ejudge, не нашлось настройки для отображения списка задач по-другому).

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      Видимо это и есть первое предложение/замечание.

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Правда, что расстояние в трехмерном пространстве определяется стандартной евклидовой метрикой? Это не совсем очевидно, учитывая, что ввод задается сеткой.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Да, расстояние определяется именно евклидовой метрикой.

»
11 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

По вопросу может возникнуть куча вопросов, вот самые важные:
- какая метрика?
- деление в формулах целочисленное?
- какая нумерация столбцов/строчек?
- как считается результат участника?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    1) Метрика евклидова

    2) Все деления в формулах рассматриваются как операции над вещественными числами

    3) Нумерация строк и столбцов изображения начинается с 1, т.е. номер строки принадлежит отрезку [1...n], номер столбца — отрезку [1...m]

    4) Результат участника считается так, как указано в регламенте соревнования :

    "... Участник получает балл за прохождение каждого теста, равный разности между ограничением на время выполнения на одном тесте (20 секунд) и временем выполнения решения участника на данном тесте. Если решение участника не проходит данный тест, то участник получает 0 баллов за этот тест.

    ... Итоговый балл решения считается как среднее арифметическое баллов, полученных данным решением по каждому из тестов, округленное до целого значения. Итоговый балл участника равен наибольшему из итоговых баллов его решений."

    При этом время выполнения программы подсчитывается в миллисекундах (и баллы в таблице результатов тоже).

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится -12 Проголосовать: не нравится

      Физик во мне негодует!

      Фраза "Участник получает балл за прохождение каждого теста, равный разности между ограничением на время выполнения на одном тесте (20 секунд) и временем выполнения решения участника на данном тесте." очень странная. По началу фразы, можно подумать, что за 1 тест можно получить не больше одного балла, но продолжение противоречит этом. К тому же как можно приравнивать время и баллы?

      По всей видимости имелось ввиду, что участник получает по баллу за каждую секунду (или миллисекунду?) оставшуюся до TL, и 0 баллов, если не успел отработать. Как правильно?

      Конечно сути это не меняет, но нельзя же так.

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Как скоро должно приходить письмо с подтверждением регистрации?

»
11 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Из положения: «Указанная в п.5.1 денежная сумма включает в себя НДФЛ» Наверное, в п.7.1?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Да, действительно, в пункте 7.1, небольшая опечатка. Спасибо за замечание.

    Опечатка исправлена.

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Хороший контест, почаще бы такие!

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    Видимо я занял первое место с учетом только конкурсных участников, и даже могу рассказать что я написал.

    1. Забиваем на сложные и стрёмные Cover tree и 3D Voronoi diagram.

    2. Строим тупое kd-tree c midpoint splitting rule, т.е смотрим по какой координате наш bounding box самый широкий и режем по середине. Если разрез слишком уж тривиальный(<n/8 точек оказалось по одну стороны), то чуть-чуть сдвигаем линию разреза так что бы примерно половина точек была с одной стороны.

    3. Чтобы быстро считать (x0 - x1)2 + (y0 - y1)2 + (z0 - z1)2 юзаем SSE. (Точки только float, никаких double, только тогда мы можем делать 4 умножения за одну инструкцию).

    4. Дописываем быстрый буфферизированый ввод вывод int'ов и float'ов, получаем еще небольшой прирост производительности. (Всё-таки там ~3.5Mib IO). (Там можно еще и при построение дерева использовать MINPS/MAXPS, Но судя по всему на тестах построение дерева занимает ~3% всего времени).

    5. Теперь осталось побаловаться с inline, __attribute__((optimize("Ofast"))), __attribute__((hot)), __attribute__((__target__("arch=???"))), __attribute__((__target__("fpmath=???"))) , выравниванием данных в памяти, расположением массивов, порядком циклов, раскрытием рекурсии в цикл с goto, и всё.

    6. ???????

    7. PROFIT!

    Также мне крайне интересно что написал участник под ником 12341234?

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      я дальше 19654 поиск в ширину не смог упихать) Уточнения для приближенной точки как делал?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо! Постараемся проводить контесты почаще.