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

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

Всем привет!

Рад пригласить Вас принять участие в раунде #115, который является рейтинговым для участников обоих дивизионов. Как и год назад, в этом раунде Вам предстоит помочь геймеру Васе cориентироваться в виртуальном мире компьютерных игр: похвастаться перед друзьями своими достижениями, определить кто "нуб", а кто "хардкорный" игрок, уничтожить Главного Злодея, сыграть пару раундов в Plane of Tanks и разобраться с толпой очень плохих гномов. В общем, получить массу удовольствия!

Авторами контеста являются Геральд Агапов (Gerald), Евгений Лазарев (undef) и Алексей Шмелев (ashmelev). Помощь при подготовке раунда оказали Владислав Епифанов (vepifanov) и Мария Белова (Delinur).

В этом раунде Вам будет предложено 6 задач, вместо обычных 5, а так же продолжительность увеличена с 2 до 3 часов.

P.S. Вы наверно все заметили странное соревнование под названием: "RazMERiq 2012 (Private Contest)". На базе проекта Codeforces и задачах этого раунда пройдет онсайт-соревнование в Нижнем Новгороде (большое спасибо Михаилу Мирзаянову за предоставленную возможность!). Регистрироваться на "RazMERiq 2012 (Private Contest)" для участников раунда #115 не надо :)

UPD: в этом раунде будет использована динамическая стоимость задач.

UPD2: ввиду неточности условия в задаче 175B - Plane of Tanks: Pro и последующего исправления условия, пожалуйста, сообщите Gerald если Ваше решение упало на 4-ом тесте исключительно из-за поправки условия. В сообщении укажите номера посылки.

UPD3: разбор задач.

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

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

А станут ли когда-нибудь private-контесты обычной вещью? Было бы классно создавать свои запароленные контесты/тренировки, чтоб проводить собственные соревнования здесь, на Codeforces.

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

    Это наша идея! Не примазывайтесь ;-)

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

      По-моему, эта идея возникла чуть ли не с момента образования Codeforces. Странно считать ее своей.

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

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

        Это была лишь шутка. Думаю, что смайл в конце на это явно намекает.

        Конечно же, возможность проводить контесты на платформе Codeforces очень удобна! И она явно бы поспособствовала развитию олимпиадного движения там, где нет инфраструктуры для проведения соревнований. И я уверен, что такая возможность появится рано или поздно.

        А вообще, я был приятно удивлен, что администрация пошла нам на встречу и сделала отдельный контест для онсайта. Удивлен потому, что CF с этого ничего ровным счетом не имеет (кроме лишних проблем с организацией и информированием участников где надо регистрироваться а где нет:) ). А нам позволит провести онсайт по интересным правилам (не достаточно уже приевшимся правилам ACM ICPC), на высоком уровне и при минимальной головной боли связанной с технической составляющей соревнования. Спасибо им еще раз за это!

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

    тык

    если не секрет, какой смысл в закрытых тренировках? Или я не так понял "private-контест"?

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

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

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

What is the meaning of private contest?

I mean who can participate in that contest?

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

разбалловка задач ???

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

Знаю, что, наверное, заминусят, но, блин, 12 часов — это же так рано >_<

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

    Видимо из-за онсайта — их обычно рано проводят.

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

      Причина не важна, важно следствие — контест в 12 часов, из-за чего не смогу в нем участвовать :\

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

    Топкодер в 6 часов — нормально, а КФ-раунд в 12 — рано. Где логика?

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

    Совпадает со вторым туром РОИ, что, мягко говоря, совсем не удобно для участников :(

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

Will the problems be ordered by expected difficulty?

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

По субъективной оценке жюри, задачи будут располагаться в традиционном порядке возрастания сложности или же случайном?

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

It will be rated round?

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

почему в Б поменяли условие? Если мне кажется, что я сделал плохие попытки из-за этого, виноват остаюсь я?

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

    Пожалуйста, обратите внимание на UPD2 исходного поста.

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

I cannot DECODE the statement of problem B...

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

У меня не заходит на турнирную таблицу.

UPD. Уже все ок.

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

Можно уже говорить "спасибо" авторам за идеально сбалансированный проблемсет, или еще подождать до окончания контеста?

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

    думаю, можно еще за всякие правки в условии по ходу раунда...

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

    Нормальный раунд. D и (особенно) E, на мой взгляд, — очень интересные задачи. +Претесты не очень сильные, а значит все, кто исчерпал свои возможности в решении могли вдоволь ломать других. Что плохого в том, что для 80% участников много решит скорость и взломы?

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

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

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

        Время от времени, и такое имеет место быть, не так ли?

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

          вроде не говорят, что такого не бывает. говорят, что это не совсем хорошо.

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

          Да, такое бывает, впрочем, хорошо бы стремиться, чтобы такого не было.

          PS: Я с шашкой наперевес на авторов не бегу.

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

          Что ж, все 3 мои решения уже прошли систесты. Следовательно, "со стороны" выглядит так, будто для меня соревнования закончились на 25 минуте. Есть еще дополнительные условия, мол "я решал четвертую, решил идейно правильно, но не смог отдебажить быстрые переходы в динамике, чтоб проходило 5000-10000 итераций, а не 100-200", и все такое... Но это все уже детали.

          Грубо говоря, я прорешал все, что мог, за 25 минут. И у меня, наверное, будет даже плюс к рейтингу.

          Если кто-то считает, что это нормально, когда контест длиной 3 часа достаточно решать 25 минут — что же, это его мнение, у него есть на это право...

          Юбилейный 88000 комментарий. Мелочь, а приятно:)

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

            А какая итоговая сложность? Ведь вроде быстрее O(HP1 * HP2 * D * (R-L)) нельзя. Итерации уже некуда лепить.

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

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

              (HP2+HP1)D(R-L)

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

                Я пытался сделать (HP2+HP1)D на динамиках (т.е. считаем для обеих вероятность того, что после a выстрелов у танка остается b жизни) и потом D*D на подсчете ответа (в динамике сразу считаем вероятность убития на определенном шаге, потом перебираем все возможные пары "первый убьет второго выстрелом А (если доживет), второго первого выстрелом В (если доживет)).

                Тут D — число итераций.

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

                  Я писал что-то такое же, только ответ не за D*D а просто за D.

                  Что-то типа считаем вероятность убить за k шагов, умноженную на вероятность дожить до k-го выстрела.

                  Не пропихнул, думаю есть косяки, ибо я сперва думал они в 0 еще не стреляют и потом уже исправлял. Такое решение как минимум на 3 теста дальше пихалось)

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

              А можно и без итераций. Мне, правда, один символ надо было в решении поменять, чтобы прошло. Но у меня сложность O(HP1 * HP2 * 30 * 2 * 30 * 2).

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

                У меня нету итераций. У меня HP1 * HP2 * 30 * 2

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

                  Там система за линию решается?

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

                  Да, там нужно было выразить один элемент, а потом просто пройтись и почитать все остальные через следующий. Выразить можно просто: постепенно раскрывая скобки.

                  Код: 1536975

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

                  Ясно, я за квадрат делал оптимизированным Гауссом. Работает всего в 2 раза дольше :)

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

          В переводе это означает "_у меня 35 место, самое высокое в моей жизни, ну не могу же я обливать грязью такой контест_".

          Мы поняли)))

          А тем временем оценка поста о матче тонко намекает на мнение сообщества...

          Codeforces Round #114: +207

          Codeforces Round #115: +44

          feel the difference

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

            Радует, когда узнаешь, что за тобой следят люди. А вообще, думаю, ты понимаешь, что мне не составит труда (довольно логично!) объяснить мотивацию твоих постов, начиная со слов "в переводе это означает...".

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

        Да, к сожалению, таких участников очень много. Авторы контеста считали, что задачи D и E сдаст намного больше народу, а лидеры решат первые 5 задач за 1.10-1.30 и смогут что-нибудь с F сделать. Сложной теории в D и E знать не надо, реализация тоже несложная, поэтому задачи вполне по силам даже некоторым участникам второго дивизиона. Однако, реально сложность этих задач оказалась выше, чем мы полагали.

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

      E — просто зашкаливающе интересная задача, перебор с (!) неасимптотическими оптимизациями. Какая красивая и новая идея, просто rocket science :)

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

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

        Мне, как любителю ТД, понравилась сама задача:) Плюс ко всему, я реально не знаю как оптимизировать в этом случае перебор. После контста будет разбор, а значит там напишут, как все-таки оптимизировать ее, а значит я научусь чему-то новому. Как это может не радовать участника моего уровня?

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

        Авторское решение задачи E не требует неасимптотических оптимизаций и использует пару идей кроме полного перебора. Собственно, и разбор для этой задачи получился самым большим (из A-E).

        Если хочется больше идей в контесте — то как раз можно подумать над более "честным" решением вместо написания перебора, который не гарантируется, что пройдет :)

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

What's the idea behind problem C?

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

    Just use greedy approach:)

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

      I tried always picking the figure that would give me the smallest number of points if I take only a number of them that would take me to the next p_i. This failed.

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

        UPD: You need choose just the least thing by cost.

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

          Thanks! That was my first thought too, but then sent a solution with that idea and failed. Turns out that I understood the statement wrong: I thought that if p_1 = 1 and p_2 = 2 and I destroy 1 figure then I need another 2 figures to reach p_3. But yeah, they are cumulative.

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

What is the solution to problem F? I tried to solve it, but i got TLE on pretest 7( I used dijkstra algorithm for every query )

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

    That's way too slow. You'd need something around O(n log n) or O(n log^2 n) or O(n sqrt(n)), not O(n^2 log n) ;)

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

Ребята, вы не поверите. Мне наконец-то надоело учавствовать в соревнованиях! :-) Объявляю передых.

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

"Don't be a slowpoke" round :),

btw I liked it.

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

    Btw, I hated it :). On an ordinary round there wouldn't be such a huge difference between our places.

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

    There probably should be a medium problem (between C and D in difficulty). Otherwise, for the people who solve ABC, it boils down only to speed.

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

а что меняла поправка во второй задаче?

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

    прохождение 4 претеста из-за условия. Надо было поменять <= на < или наоборот

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

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

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

There is a bug in standings. I can't view them in each division separately.

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

хм... странно в ABC Паскале выводит -1, в FPC — WA 1000001

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

    Используйте FPC на своей локальной машине, и да будет Вам счастье :). А еще лучше сразу меняйте язык на что-нибудь более приличное.

    P.S. Желающим помянуть про Гену: я это уже сделал за вас.

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

      Другие языки не спасают от толпы компилятров(или вы только ТОТ САМЫЙ язык приличным считаете?)

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

        Намек про смену языка — это уже лирическое отступление, не имеющее никакого отношения к проблемам с компиляторами.

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

      Юзаю ABC потому что там проще копипастить готовый код и сохранять программу, да и загружается он быстрее дельфи. Хотя имеются в наличии все три компилятора.

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

А рейтинг будет пересчитываться по отдельности для див-1 и див-2? Исходя из расстановки по комнатам, логично предположить, что да. Но всё же...

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

Несмотря на то, что я слил, контест очень понравился. Спасибо.

P.S.

const int MAX_AMMO = 40000; -> const int MAX_AMMO = 10000;
TL -> AC.
Facepalm

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

    Хоть кому-то понравился :)

    Задача C для тебя была проще, чем для большинства остальных участников, не так ли?

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

А зачем закрывать результаты приватного контеста?

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

I'm not looking for excuses, but the statements are really hard to understand sometimes. Examples:

Problem A: "In the first example the best result, obtained by artem is ..." (This would make you think that artem obtained the best result) They probably meant "In the first example, the best result obtained by artem is ...". (For me, that comma makes a difference)

Problem C: "The number of figures of type ki and figure cost ci is known for each figure type" (I first thought that ki was a type.) I think it should have said "The number of figures of type i is ki and they all have the cost ci"

Or maybe it's just me and in that case I apologise.

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

Really love problem E: Tower Defence. I think people who have played it before may figure out the solution very soon -- at least true for me.

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

One of the unluckiest contests for me happened like this:

Problem D: I did a DP solution plus binary search. Got Wrong Answer for forgetting '<' should be '<='. Even worse, after fixing that, this code got TLE and adding inline optimizations saved the day.

Problem E was even more unfortunate. When I was reading this problem, the Internet connection in my room went down. After trying in 10 minutes but no avail and 3 unsuccessful attempts in finding a wifi connection, I hurried to my university (it is about 500 meters far from my room). Finally, it was 30 seconds too late before I was able to submit my solution (quite close to the expected solution, although it was wrong anyway).

Now I see how difficult it is to reach Grandmaster Level (or red) in Codeforces. Not only do algorithmic skill and coding ability are required, your physical condition must be good as well :)

Anyway, I really like this contest (15 rating loss is not a big deal) because it brought me a memorable day :)

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

(http://www.codeforces.com/contest/175/submission/1533074) A bit unlucky. In problem A I used atoi to convert string to number and check if it is greater than 1000000 like this atoi(a.c_str()) > 1000000. The problem is if the number is out of range atoi returns INT_MAX or INT_MIN. In my system it was returning INT_MAX, so it passes all test cases, but in codeforces i think it returned INT_MIN and someone hacked my solution. Anyway how do you hack someone's solution if the behavior of some function is undefined?

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

    Anyway how do you hack someone’s solution if the behavior of some function is undefined?

    There is "Custom test" tab

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

For problem c, my submission is giving the wrong answer for the first test case. But in ideone and my system, it's giving the correct answer. What the problem? (http://www.codeforces.com/contest/175/submission/1535400) (http://ideone.com/dUFwZ)

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

    I'm using Dev C++, and my system also have an incorrect output for that code. It seems that after the second loop, when the p is 6 and the nFigures is 2, the value of i is 1 (i++). Now, i>=SZ(v), but since we're still in the while(p>0) loop, and p is still greater than zero (value of p is still p-nFigures = 4), it won't break the while(t--) loop. So, in would access the value of v[1], which doesn't exist.

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

Или я слепой, или где разбор?

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

    Мог бы хоть кто то мотивировать, за что минус ставит?

    p.s. Или все из за того что все привыкли к хорошему (к разборам в течении 10-15 минут после раунда, иногда даже до систестов).

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

      По-моему, это ты слишком привык к хорошему и все тебе подавай, не?

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

        Вы хотите сказать что это только я к хорошему быстро привыкаю?

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

Опубликован разбор задач A-E

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

Are there any editorials for this round?

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

Вопрос: теперь все раунды будут проходить с динамической стоимостью задач?
И будет ли в таком случае применяться к задачам random_shuffle?
Вообще, идея хорошая, избавит комменты от бесконечных вопросов вида: "какие баллы за задачи?".

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

    Может, стоит отныне давать автору контеста выбирать способ разбалловки?

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

Опубликован разбор задачи F

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

Having a weird behavior with C++0x over here in problem B.

I have submitted those 2 codes: 6314097 & 6314111, one of which got a WA and the other got accepted, the only difference was the line cerr << better << " " << least << endl;, which should not affect the output, not the variables. I tried to know why that might happen, but seems to hit a dead end.

Any clue to what I might be missing over here.

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

    That's probably precision issues. 1.0 / 10.0 != 0.1, at least, you shouldn't assume that and always compare doubles assuming that each number can be stored with some small error only. For example:

    const double eps = 1e-8;
    
    // if (a == b)
    if (fabs(a - b) < eps)
    
    // if (a < b)
    if (a < b - eps)
    
    // if (a <= b)
    if (a <= b + eps)
    

    UPD: usually (un)commenting debug output affects optimizer, which can easily affect precision of floating-point operations.

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