Olympiad 2020 / Олимпиада 2020 Q&A

[Tandemun]

Всё? Дедлайн? Или еще есть время?

[Artem.spb]

уже давно "всё", готовлюсь стартовать

[Artem.spb]

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

[IvanLis]

Несмотря на три часа ночи, тут всякие важные дела приключаются, так что стартую только сейчас.
Ivanlis решение не прислал, поэтому запускаю старое.

А почему так быстро все изменилось?
Да я предлагал установить сроки 24:00 с 26 на 27 декабря.
Но судя по сообщению, крайний срок 27 декабря.
Более конкретного указания на форуме не нашел, по этому и не присылал, хотя в принципе уже готово было.

На решение будет пара недель (до 26-27).
Пока чиню арбитра, пара идей для одобрения, если вам это поможет.

[mid150]

А почему так быстро все изменилось?
Да я предлагал установить сроки 24:00 с 26 на 27 декабря.
Но судя по сообщению, крайний срок 27 декабря.

Мне конечно, до фонаря, прислали вы решение или нет, но раз только вы его не прислали, получается, что только вы и не поняли, что срок сдачи до полуночи 27го (00:00 27.12.2020).

Более конкретного указания на форуме не нашел, по этому и не присылал, хотя в принципе уже готово было.

Раз у вас уже всё было готово, могли бы давно отправить, а так, получается с судьбой играли Зачем же до последнего тянули?
P.S.: у всех у нас есть различные дела, но отправить архив не так уж и много времени занимает)

[IvanLis]

Всё? Дедлайн? Или еще есть время?

Не я один эту неоднозначность не понял.
Свое решение отправил перед тем как написать пост утром.
В любом случае победит сильнейший

Мне конечно, до фонаря, прислали вы решение или нет, но раз только вы его не прислали, получается, что только вы и не поняли, что срок сдачи до полуночи 27го (00:00 27.12.2020).

Я именно так все и понял, только у меня, как надеюсь и у большинства людей, полночь 27 это 24:00, а не 0:00

[alerm]

Первые результаты.
Видео будет позже или сильно позже, что-то редактор на ноутбуке не хочет работать
3-1.PNG

Блин, наши муравьи колеблются около муравейника? Да как так-то я же вводил поправку, брал целое значение координат, что соответствовало ячейке, потом "делал шаг" и снова брал целые значения координат, смотрел сходил ли в какую сторону из первоначальной ячейки: если нет, то скорость домножал на 1, если перебирался в другую ячейку, то умножал на коэффициент, соответствующий разности высот. И только после этого, уже с новой скоростью, делал шаг

[IvanLis]

Блин, наши муравьи колеблются около муравейника? Да как так-то я же вводил поправку, брал целое значение координат, что соответствовало ячейке, потом "делал шаг" и снова брал целые значения координат, смотрел сходил ли в какую сторону из первоначальной ячейки: если нет, то скорость домножал на 1, если перебирался в другую ячейку, то умножал на коэффициент, соответствующий разности высот. И только после этого, уже с новой скоростью, делал шаг

Там погрешность накапливается именно при вычислении координат между Муравьем и Арбитром, и в один момент ты уже шаг делаешь, не 1.3 как рассчитал, а 0.5.
Долго с этим боролся, но побороть не смог, даже перейдя на расширенный формат числа.
В принципе у меня было все готово еще 25 декабря, есть видео залиты на YouTube, но пока доступ закрыт, открою в зависимости от решения организаторов.
Хотел еще сегодня погонять после работы пол дня, все проверить, я даже в совсем экстремальных условиях тестировал, на "шумовом" поле с размахом 0..255 и размером муравейника 3.

Без имени.png (2.02 КБ) 2456 просмотров

[IvanLis]

Вот мои мытарства по поводу вычислений, считай все время на это ушло.

В логическом массиве показано совпадение до 15 знака
1. Координата X
2. Координата Y
3. Направление
4. Длина шага


На гладком рельефе ошибка в 14 знаке сильно не влияет.
----------------------------


А вот если рельеф сложный, то эта самая ошибка потом выстреливает в длине шага, из за этого все ломается.


Вот 2 шага совпадают с точностью до машинного "0", а потом начинается расхождение в 15 знаке.
----------------------------


Переделал на EXT и CXT (расширенный формат числа)
Сначала все нормально, ошибка стрельнула примерно на 700 шаге.
----------------------------

В принципе, ник-то никого не обманывает: Numeric Data Types Table
Написано, что точность составляет для
DBL - 15 знаков
EXT - от 15 до 20 в зависимости от платформы вычисления

[IvanLis]

Тесты программы от 25 декабря, в принципе с тех пор времени дорабатывать не было, по этому сейчас играет именно эта версия (на видео, расстановка меток отключена). Муравьи как всегда бегают по спирали, но потребовалось время и глобальная переработка алгоритма, что бы они это делали с учетом рельефа. Я ожидал примерно таких полей, но тут главное попадание в муравейник при возвращении.
Поле 1200/900, размер муравейника 3.



версия с метками: _https://youtu.be/Kftiyr3MdXI

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

[alerm]

Тесты программы от 25 декабря

Очень хитро от середины кучки с едой отправлять муравьев

А метки зачем? я что-то по видео так и не понял

Иван, как обычно, долго запрягает, потом быстро едет...

Да он всю еду у меня утащил (ту, которая над нашим муравенйиком)

[IvanLis]

Очень хитро от середины кучки с едой отправлять муравьев

Там не совсем от середины, я сначала вычислял центр кучи по трем точкам, но потом отказался (во втором этапе уже было реализовано и на видео видно). Сделал некоторое упрощение, фактически муравей движется по окружности, вот по двум точкам я и вычисляю направление в центр. Каждый раз, когда движусь к еде, корректирую направление, что бы направляться в центр (аналогично и при движении в сторону муравейника), это и расстояние экономит и позволяет компенсировать уменьшение кучи. Когда еду беру, запоминаю точку и возвращаюсь снова в нее, если еды нет, то делаю N шагов дальше по заданному направлению.

А метки зачем? я что-то по видео так и не понял

Я метки не использую, можете меня как угодно называть, но это с целью сбить противника с направления. У этого SubVI и название соответствующее (угадайте где он).

До этого не использовал в надежде, что мой муравейник крутиться быстрее будет, делая ставку на скорость. Но два этапа показали, что чужие метки тормозят все муравейники, по этому я тоже, начал их ставить пока в режиме поиска нахожусь каждые М шагов. А вот когда еду нашел, то уже бегаю, на максимальной скорости, не теряя время.
Не знаю, на сколько это эффективно, но потом на видео и логах видно будет.

Вообще этот рваный рельеф (накопление ошибки) очень поломал всю мою математику, которую я использовал на 1 и 2 этапах. Причем ошибка предсказуемая, т.е. три запуска с одинаковыми исходными данными, повторяет все шаг в шаг. Я и со спецами (программистами) разговаривал, они сказали, что от этого никуда не уйти. Нужно или на числа с большой разрядностью уходить, но это тоже эффективно до определенного уровня. А по хорошему, нужно разбивать все на уровни квантования и работать с ними, иначе никак.
По этому в конечном варианте алгоритма, я добегал до предполагаемого места нахождения муравейника, и если его там не было, то начинал его искать, по спирали, аналогично поиску еды, только шаг спирали меньше.



А это настольная книга муравода

[Artem.spb]

Да он всю еду у меня утащил (ту, которая над нашим муравенйиком)

Негодяй :)
Своей полно, а он в чужой огород лезет...

[IvanLis]

Своей полно, а он в чужой огород лезет...

Свою я потом съем, когда зима настанет .

[alerm]

Но два этапа показали, что чужие метки тормозят все муравейники

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

Блин, у нас же всё равно муравей ищет еду, если вернулся на её место и не нашел. Надо было тоже самое добавить, но с поиском своего муравейника, если несколько ходов на месте стоят, так тупо и просто, эх я

Свою я потом съем, когда зима настанет .

Выгляни в окно