Pull to refresh

Comments 20

Конечно, правила не запрещают участвовать в Формуле-1 на самосвалах. Но все почему-то используют болиды.

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

Согласен, что тесты, оценивающие сложность подобным образом, реализовать в целом труднее. Но если не принимать во внимание затраты на их реализацию, разве не была бы такая система оценки качества решений более точной и достоверной?
А участникам будет даже полезно прийти к осознанию, что масштабируемые проблемы в принципе не будут решаться наращиванием железа и ассемблерными вставками, если в основе лежит алгоритм с O(n2)+ сложностью.

А по поводу собственно проблемы — Вы не думаете, что создание булевого массива и простая проверка в нем на наличие символа была бы намного быстрее, чем использование хэша? Задача то совсем хэша не требует.
Простите, не очень понял. Вы предлагаете оперировать кодом символа, как числовым индексом, чтобы присваивать True соответствующим ячейкам, а потом один раз посчитать количество True в массиве?
Я, кстати, пробовал запускать решение на Ruby без работы с хешем (то есть, второй результат переставал подсчитываться). Скорость выполнения улучшилась с 1400ms до 1100ms, что по-прежнему слишком далеко от C++.
Ну приблизительно так, поскольку в задаче множество символов счетно, то хэш нам не особо нужен, линейный массив его вполне заменяет.
Если для проверки есть ли символ в коде использовать словарь, то проверка каждого набора кода за линейное время решается.

Верно! Есть ли способ решить быстрее? Мы ведь, если не ошибаюсь, нахождением пересечения множеств занимается тут.

Что-то мне кажется, что языки типа Ruby и PHP в этом конкурсе разве что просто до кучи, чтобы дать поучаствовать кому-то просто интереса ради, не соревнуясь.
Я участвовал ради интереса на PHP. В первый раз даже футболку получил.
А вот во второй раз я не смог сдать ни одной задачи — был и TL и, кажется, какая-то проблема с чтением строк, которой раньше не было.
В этот раз на первой задаче я опять получил TL.
Очень неинтересно участвовать, когда у тебя сплошные TL :) Особенно когда ты знаешь, что на другом языке это решение пройдёт с запасом даже на слабом компе…
Немного знаком с внутренней кухней подготовки олимпиадных задачек, хотя это относится больше к олимпиадам для школьников.

Мысль номер один, если компания например внутри больше пишет на c++/java и например хантит таких разработчиков, то компании не выгодно ориентироваться при разработке задач пишущих на более медленных языках.

Далее, действительно разработчики задач, периодически сталкиваются с такой проблемой, то что решение за квадрат на c++ работает например почти как решение за n log n на python. Да, обычно удается решить эти проблемы, небольшой корректировкой условия задачи, и придумыванием качественных тестов. Но не всегда.

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

Так же обычно на более медленных языках, все же можно соптимизировать задачу, до такой степени что она не будет получать TL. Но тут надо понимать, что творится под капотом у самого языка взамен того, что бы реализовывать что-либо самому на более низкоуровневых языках.

И последнее, отвечая на предложение с вашей колокольни. Это к сожалению не сработает, потому что бывают решения у которых не детерминированная сложность. Решения которые например работают за отведенное время но оптимизируют результат, такие как банальный перебор, метод отжига, генетические алгоритмы, и.т.д. И эти решения тоже считаются решениями.
Если мы будем пытаться вычислять сложность используемого в решении алгоритма, то тут и ошибиться просто, и что с такими решениями делать не понятно, и в итоге из строгой системы судейства получим систему из костылей (имхо).
Хорошая олимпиадная задачка не должна сильно зависеть от языка программирования. Если на одном языке она решается в 3 строки, а на другом приходится выдумывать собственные структуры данных и лезть под капот, то с этим надо что-то делать. Иногда для какого-то конкретного языка увеличивают ограничение по времени, например. В случае с простой задачей можно просто снизить общие ограничения в тестах и тд.

Решение олимпиадных задач и «хороший разработчик» — это разные вещи.

Спасибо за развернутый ответ!
Согласен, что, скорей всего, можно укладываться в Time Limit и на "медленных" языках. Но тут встает дилемма — тратить дополнительное время на упреждающую сверх-оптимизацию, или сдавать обычное (не наивное, адекватное) решение с риском получить штрафное время за превышение. Лично для себя я сделал вывод, что олимпиады придётся писать на "быстрых" языках.


Что касается, оценки сложности, вот простейшая методика, которая мне видится жизнеспособной:


  • Допустим у нас три теста, входных данных в каждом из них n1=100, n2=1000, n3=10000
  • Решение прошло три теста за времена t1, t2, t3
  • И если t3/ t2 >> t2/t1 значит ресурсоемкость решения неудовлетворительная

P.S. Возможно, найду время и напишу прототип, чтобы проверить методику на практике.

Пожалуйста, скажите мне, что название статьи случайно, и не содержит в себе скрытых намёков…
Практически прямым текстом написано. Какие уж тут намеки.

Я не участвовал в этом разогревочном раунде, не знаю Ruby, но, может, мои пять копеек будут полезны.


Ну, по порядку.


  1. Вполне реально сдать эту задачу на Ruby или другом скриптовом языке из представленных так, чтобы она уложилась по времени. 2 секунды! Это же очень много для тупого линейного алгоритма (а как минимум прочитать придётся все данные, так что быстрее линейного в этой задаче ничего нет).
  2. Все языки равны, но некоторые — равнее. Там, где в C++ можно написать не слишком оптимальный ввод-вывод или ещё что-то подобное, и это скомпенсируется скоростью работы, на Ruby (Java, PHP, Python) нужно быть более аккуратным, например.
  3. В вашем решении вы считываете вход целиком в массив. Зачем? Это ведь очевидно ухудшает скорость и не даёт никаких преимуществ по сравнению с чтением и выводом результата построчно.
  4. Вы итерируетесь по символам в строке. Однако, раз вы пишете на Ruby, то должны знать, что char и byte в нём — совершенно разные вещи (кодировка, внутренне представление, вот это всё). И итерироваться по byte быстрее. В пределах задачи даже не очень понятно, зачем использовать char.
  5. Использовать для проверки вхождения символа в строку массив, а не хеш — ну, просто здесь не обязателен хеш (по факту, мало влияет на скорость)
  6. В обоих ваших решениях на Github есть ошибка. Вы неправильно обрабатываете концы строк. И, видимо, вы сами сгенерировали "правильный" ответ к 17 тесту, поскольку он не правильный. Понять это просто, если, например, посмотреть на последнюю строку output.txt. Там стоит "36 0", но в секретном коде только 35 символов.
  7. В архиве, предоставленном жюри, есть и корректные тесты с правильными ответами, и чекер для проверки — почему вы не используете их?

Итак, поменяв чуть-чуть в соответствии с вышеуказанным ваше решение, я получил на своей машине результат ~0.45 сек. на 17 тесте вместо 1.2-1.4 сек. Это очень близко к вашему результату на C++ (хотя, конечно, его точно так же можно улучшить). Но это уже достаточно большой отрыв от указанного TL, чтобы можно было легко сдать.


Все изменения прислал вам в виде pull request. Ещё туда добавил оригинальные файлы и фикс решения на C++ (без улучшений, просто чтобы проходили оригинальные тесты).


Это всё можно считать упреждающей оптимизацией, да. Но по факту — это базовые вещи, касающиеся любого инструмента и культуры программирования. Да, даже олимпиадное программирование требует владения инструментом на некотором уровне. И да, там даже есть свои трюки на тему скорости, которые иногда стоит применять. И да, писать на C++ или хотя бы Java такое проще (но, опять же, народ не из топа спокойно и на других языках сдаёт — и ничего, норм).

Вы совершенно правы!


Как я уже писал выше, использование хешей в составленном тогда мною решении хоть и не оптимально, но не существенно — полное исключение работы с ним уменьшило время выполнения всего на 0.3с.
Полагаю, столь большое ускорение (с 1.4с -> до 0.4с) Вашего решения на Ruby, с фактическим приближением по скорости решения на C++, связано главным образом с оптимизацией работы с STDIN. (Ну и работа с байтами вместо символов, хотя привычнее рассуждать, раз строки, значит юникод, значит оперируем символами) В моём решении существовало два этапа — преобразование сырых данных из STDIN с сохранением в промежуточные переменные, и, непосредственно, работа с ними.


Ваше решение вселяет в меня надежду, что Ruby может потягаться в таких ситуациях с Си =)


P.S. чуть подправил compare.sh, а то не собирался

Больше всего влияет на скорость исполнения замена работы с char на byte.


Улучшения по работе с IO дают прирост 0.2-0.3 сек на данном тесте. Но, к слову, если бы было более жёсткое ограничение по памяти, то аккуратная работа с IO имеет ещё больше смысла, далеко не во всех задачах получится прочитать весь вход в массив.


Проверить очень просто:


Если вернуть итерацию по char и сравнивать ch == code[i], то получаем время ~1.0 сек. Это связано с тем, что code[i] создаёт новую строку каждый раз + индексация Unicode-строки работает медленнее, чем индексация честного массива.


Если вернуть итерацию по char, но все символы из code заранее положить в массив code_chars, соответственно, сравнивать ch == code_chars[i], то получаем время ~0.75 сек. Тут мы избавились от создания новых строк каждый раз, но сравнение строк всё равно осталось, вероятно, оно работает медленнее, чем сравнение чисел.


(Все рассуждения — довольно общие, я действительно не знаю, как работает Ruby, просто посмотрел доки только что).


То есть, решая более общую задачу (для произвольных строк Unicode-символов стоит использовать char и Hash, конечно), вы получите и большее время работы. Это вполне логично. Но в исходной задаче есть ограничения на входные данные, на символы, из которых состоят строки. Грамотно воспользовавшись этими ограничениями, вы получите достаточно быстрый алгоритм. Ну и логично, что решение большей части олимпиадных задач так или иначе предусматривает работу с ограничениями (одно дело посчитать 10!, и совсем другое — 10000!).


P.S. Да, точно, ту строку в compare.sh добавил в самом конце и не проверил — очепятался, спасибо.

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


Кстати, забавная вещь, только что выяснил, #rstrip работает немного быстрее #chomp, хотя для работы с STDIN рекомендуется второй вариант, как более каноничный. И что еще забавнее, вариант t.rstrip!.each_byte.with_index do… работает аж на 5%~ быстрее, чем t.rstrip.each_byte.with_index do ..., хотя казалось бы, второй вариант это более правильный method chaining и вообще Ruby way… Вероятно это объясняется, что при #rstrip! не копируется новая строка в памяти, а уменьшается счетчик длины текущей. Полезно наверное знать и помнить такие частности, но иногда излишнее заглядывание под капот отвлекает. Нужны менее дырявые абстракции :)


Кстати, сейчас поразмыслил, Ваш вариант хоть и проходит все указанные тесты, но имеет некоторую слабину: игнорируется передаваемое общее число комбинаций-попыток, и значит STDIN будет читаться до победного конца. Достаточно добавить одну лишнюю строчку в конце входных данных, не увеличивая передаваемое число комбинаций-попыток, и проверка провалится.

Ну, в олимпиадных задачах мы полагаемся на корректность входных данных и их формата, поэтому так написал.
Но, конечно, можно и счётчик строк с выходом из цикла по достижении tries_count добавить, временной сложности это особо не добавит :)

Only those users with full accounts are able to leave comments. Log in, please.