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

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

Доброго времени суток, читатель.

Немного из того как я решал сотый раунд.

Началось с того, что я решил задачу А... скажем, за нормальное время (АС на 9 минуте).

Открыв задачу B и посмотрев на монитор, решил что её я буду решать позже. Прочитал задачу С и сразу подумал, что её следует решать с использованием какой-то структурки, наподобие priority_queue. Естественно я по-быстрому написал решение с stl-ной структурой priority_queue. Когда моё решение нормально отработало на тестах из условия, я сразу захотел потестить на большом примере. Естественно выбрал тест n=100000, а комы по одной штуке с размерами от 1 до 100000. Запускаю и... происходит что-то неладное... моё решение работает ооочень долго. Даже на похожем тесте, но с n=10000 моё решение работает около 8 секунд. Далее я подумал, может я не всё знаю о priority_queue и сделал тот же алгоритм, только с map. Результат оказался тем же. Ещё чуть погемороился и забил на эту задачу. 

Перешёл к задаче D. Уважаемая Наталья, я честно не представляю, как можно сразу не увидеть здесь тупой сорт и пробег по массиву. Мне кажется это самое очевидное решение, и как можно убедиться, правильное. Вобщем я ещё несколько минут пытался придумать что-то плохое в этом решении, ибо не верил своим глазам, что эта задача имеет номер D. Ничего плохого не увидел, закодил и сдал. Мне кажется, эта задача должна была иметь номер A.

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

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

Так вот. Мне кажется это когда-то обсуждали и связано это с режимом запуска, т.е. релиз или дебуг, но всё-таки ничего не понятно. Моё решение по задаче С у меня на компе долго работало. У меня стоит VS2010Pro. Моё решение практически идентично вот этому решению http://mirror.codeforces.com/contest/140/submission/999273 . И давайте будем опираться на него. Итак, если поменять строку (scanf("%d",&n);) на (n=100000;) а (scanf("%d",&x);) на (x=i+1;) то получится, что при запуске на сервере она работает 170 мс. Если же запустить у себя на компе, то работает такая программа невообразимо долго... Причём работает оочень долго уже на вот этом цикле 
for (map<int,int>::iterator it = a.begin(); it != a.end(); ++it){
q.push(PII(it->second,it->first));
}


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

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

»
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Про запуск на сервере - а можно в качестве теста отправлять генератор, как при взломе? Что-то я не нашел такой кнопочки, а иногда очень даже хотелось бы.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Можно же в код решения вшить генератор?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Можно, но отдельный генератор был бы удобнее.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, конечно, но это не всегда удобно. 
      Например, увидев в комнате код, который считывает 10^6 чисел через потоки, не всегда понятно - надо бежать ломать, или этот код на сервере за пол секунды обработается.
»
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Я тоже пишу в студии в дебаг режиме, но для таких случаев у меня есть компилятор g++ и волшебные макросы в фаре, которые компилируют решение с такой же строкой как на сервере.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Хм.. в g++ и правда в лёт работает... :( тем обиднее. Мда.. написал правильное решение и его не заслал.
»
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Во-во, кстати, фактически у меня то же самое было. Описываешь почти поминутно мои рассуждения, за исключением самих задач.
Я точно так же придумал быстренько А, только долго тупил что с чем надо сравнивать. Прочитал В, не вкурил, прочитал еще раз, не вкурил, прочитал еще раз, не вкурил, на время забил. Увидел что сабмитят все С, прочитал С, решил(только я решил ее сразу, бинпоиском по ответу). Вернулся к В, еще пару раз пытался вкурить, понял, что не вкуривается, заметил, что много кто имеет задачу D без В. Прочитал В, и реально не понял что она на месте задачи D делает. Искал минут 5 палево, пытался придумать тесты, доказал, что их придумать нельзя, потратил время на доказательство! Я очень редко что-либо полностью доказываю на контесте, но тут уж решил реально найти в чем палево(ну не может простая задача на жадность иметь букву D! Ну никак! Естественно нужно искать тесты). Доказал, отослал и все равно нервничал - может, что-то упустил в доказательстве? Вернулся к задаче В, еще раз 5 ее прочитал и только потом вкурил.  Условие, конечно, ужасное. Написал самое тупое решение, полное г..но, работающее за куб(!).
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Причём тут бин-поиск? Как проверить, что mid-ответ можно построить?
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится
      Пусть мы хотим проверить, можно ли собрать x снеговиков. Из всех шаров, которых больше, чем x, оставим ровно x. Посортим оставшиеся шары. Тогда шары i, i+x, i+2*x - разные. Т.е. если осталось >= 3*x шаров, то собрать x снеговиков можно. Иначе - нельзя.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Точно в Release запускал?
»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Попробуй тут выбрать Release и запустить по Ctrl+F5.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    и еще где-нибудь перед return 0 поставить cerr <<clock() <<endl;
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      Да я думаю там визуально будет видна разница.
      UPD. Но вообще для console debug наверное будет очень хорошо.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Помогло... Причём если поставить релиз и запускать по F5, то будет работать секунды 4, если по стрялF5 то в лёт. Блин... вот печаль... Почему если стоит дебуг, то по стрялF5 работает всё равно долго... Меня студия печалит :(
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
      Насколько я понимаю, то Ctrl+F5 == без дебага запускать.
      Ну а под compile mode debug компилируется без -O2, поэтому и тормоза.

      Ясное дело, что под релизом скорость тестить. :)
      Думаю к студии придираться сложно.

      Вот такой вот опыт, который, возможно, стоил футболки...
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Компилируйте из командной строки ровно тем же способом, что и Codeforces (в FAQ есть ссылка). Используйте ту же версию компилятора. Если работаете под Windows, то запускайте с помощью нашего микропроекта  http://code.google.com/p/runexe/ Есть аналогичный run.exe от ИТМО, но им пользоваться не рекомендую, так как он запускает решения (внимание! под системным отладчиком Windows!) и поэтому правильное решение может работать под ним в X раз дольше (например, я воспроизводил это недавно на современном MinGW, в решении просто довольно много STL). Кстати, не уверен, что такое поведение фиксится на онсайтах, проводимых ИТМО.

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

    Под системным отладчиком само по себе решение работает ровно столько же. И на Тимусе, кстати, запускается тоже под отладчиком. Проблема в том, что в этом режиме работает более медленный алгоритм освобождения памяти, поэтому может проходить значительное время между выполнением "return 0" и завершением программы. Лечится это изменением какого-то из флагов (вроде "Disable heap coalesce on free") утилитой gflags.exe ( http://technet.microsoft.com/en-us/library/cc738763(WS.10).aspx )

    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится
      /*Лечится это*/ void operator delete( void * ) {}; /*УХАХАХАХАХА*/
      /*UPD. Ну и такая же конструкция для delete[]*/
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Установил gvim на Windows 7 )). Куда нужно сохранять .vimrc ?
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    В папку, куда установлен Vim :) И на винде он вроде бы называется: "_vimrc"

    UPD: Там уже должен лежать, думаю

»
13 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится
Например, в std::vector сложность ни то пуша ни то чего-то в этом роде в дебаге в 2010 версии квадратичная. Приоритетная очередь построена поверх вектора, так что если у вектора в дебаге действительно пуш квадратичный, то и у приоритетной очереди в дебаге пуш будет квадратичный. Почему это так, и как эту очень полезную фичу выключить, объяснялось в этом видео:
http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Stephan-T-Lavavej-Advanced-STL-3-of-n

Кстати, чувака на видео зовут Stephan T. Lavavej, и я сячитаю, что иметь такое ФИО инженеру в STL очень круто :о)

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    У меня возник вопрос по поводу пуша в векторах.

    Насколько я представляю, если вектору не хватает места, после .push_back()'a вектор за линию ищет новое место в памяти и размер массива становится в два раза больше. Получается, если не делать vector.resize() в начале программы, за N вызовов push_back()'a будет произведено NlogN операций.

    А как происходит такая же операция, если у нас есть массив векторов (vector <smth> v[N], либо vector<vector<smth>>), и какому-то отдельному вектору не хватает памяти? Получается, будут перенесены все N векторов за квадрат, или в библиотеке это реализовано как-то по-другому?

    Кто знает, поясните пожалуйста этот вопрос. Если я не прав - укажите, где.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      За линию он не ищет новое место в памяти, а копирует туда старые значения. 
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Интересная у вас арифметика. За n операций push_back будет операций, т.е. стоимость одного push_back - O(1).

      Второе ваше утверждение -  какая-то трава, что значит "каждому отдельному вектору не хватает памяти"? Или вы думаете, что если одному вектору из массива её не хватает, перевыделяться будет весь массив? Откуда вообще вектору знать, что он в каком-то массиве? Разумеется, перевыделяется только один вектор (в памяти они хранятся не подряд, если что).
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Все ясно. Первое действительно было глупо, а во втором я думал, что векторы хранятся в памяти именно подряд.
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    этот мужик рвёт шаблоны =)
    UPD: Лямбда-функция? В моём C++?
    for_each(V.begin(), V.end(), [](int x) { cout << x << " "; });
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно Eclipse вместе с CDT поставить, он намного быстрее и компилирует и выполняет код, чем VS (использует g++ компилятор как на сервере). Правда, ставить замучаешься, но потом программировать также удобно, как и на VS.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    но потом программировать также удобно, как и на VS.

    Дебаггер если вообще не нужен, то да. Но тогда зачем вообще среда разработки.
    Проще тогда уж поставить Qt Creator.

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

      Нет, в последней версии CDT 8.0 дебаггер очень даже неплохой. Он конечно не сравнится с VS, но если привыкнуть, отлаживать программу становится легко.

      UPD: а в QT Creator можно спокойно просмотреть содержимое вектора?