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

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

Друзья, привет!

Через несколько часов Вам посчастливится участвовать в знаменательном раунде Codeforces Round #27 для участников Div. 21, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Игорь Кудряшов (Igor_Kudryashov), Павел Холкин (HolkinPV). Как всегда с нами были Геральд Агапов (Gerald), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).

Как вы все прекрасно знаете, только сегодня вы сможете поучаствовать в этом раунде в конкурсе, не упустите такую возможность! Другого раунда Codeforces Round #27 вы не увидите нигде! :)

Традиционно всем удачи, полных решений и удачных взломов!

UPD: Распределение баллов по задачам стандартное: 500, 1000, 1500, 2000, 2500.

UPD: Соревнование закончено, всем спасибо за участие. Надеюсь вам понравилось, но не забывайте, что нас еще ждет системное тестирование.

UPD: Уже опубликована предварительная версия разбора на русском языке

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

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

стоимость задач динамическая?

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

    в сообщении, пришедшем мне на e-mail написано, что раунд будет проведен по оригинальным правилам Codeforces. То есть нет, не динамическая система)

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

I'm predicting most of the problems will have jokes on 2-powers

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

Good luck to all! :-)

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

using dymantic score or something else?

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

can you talk about Score distribution. hope short and clear statements. Finally ,Thanks for preparing this contest.

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

Судя по номеру будет много математики ;)

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

    Лишь бы реализаций поменьше.

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

      в нашем дивизионе умение четко и остро писать реализацию важнее математики (:

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

А какой конкурс?

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

hoping for short and precise statements...

may it b overall a gud cntst..:)

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

Скучно как-то. Вот на topcoder по поводу power-of-two даже стоимости задач соответствующие делали: 256, 512, 1024...

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

    здесь не цирк, чтобы вас веселить

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

      Не понимаю, зачем его минусовать? он же правду говорит.

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

        Просто dangerous тролль.

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

          кто тут у нас заговорил? этот тот кого обидели, не оценив его понт, этот тот, кто плачится из-за вклада?

          видимо вас сильно угнетают мои комментарии, по вашему повод, раз вы не поленилесь написать это в мой адрес

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

оффтоп. Почему минусуют личностей, желающих всем удачи?

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

    может потому что хотят видеть сообщения по-существу.

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

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

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

      Потому что это тоже оффтоп.

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

        тут много чего оффтоп. Кстати, этих людей уже заплюсили:)))

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

Nothing New!!! :P Everything is traditionally traditional!!! :D

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

Points should be: 512(2^9), 2*512, 3*512, 4*512, 5*512. :)

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

Смайлик в анонсе принесет всем удачу на контесте :-)

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

Главный герой первой задачи это Qwerty821 или это совпадение?

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

Хороший контест, чтобы почувствовать себя умным, но медленным.:(

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

как решалась Е? аккуратной жадиной?

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

I cannot understand why this solution does not hack successful on the test case 1000 1 1000 1000 for problem B div 2.

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

    Very dangerous to try a hack like this, using errors about size of the array. Maybe it will fail for system test, but you can't be sure what will be returned by this kind of code. Only hack codes with bigger problem of size.

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

    A similar question has been asked before: http://mirror.codeforces.com/blog/entry/2799#comment-57306

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

      Thank You..I learned something on the cost of 2 unsuccessful hacks (-100 points)

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

        but dude in that n can be at max 1000 and he was having bound of 1001 which i think should work fine......

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

          Look carefully what happens if x = n or y = n.

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

            according to me nothing would happen..... if we have A[n+1] then whats the problem with A[n]

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

              The code is running for each value of x and y,two inner loops (x to < x+3) and (y to < y+3)..Now for x=y=1000 , it is incrementing the values at array indices [1002][1002] also ..Thats were I thought it should give runtime error as Array Index out of bounds exception..But As andreyv says it fixes some page memory buffer for its excution , although I am not clear of its concept totally..So I said I would rather not take risk in furthur contests which such hacks

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

    was your hack for the size of the array or because he didn't continue taking the input and returns when solution found?

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

Спасибо за замечательный контест))))

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

Е решается бинпоиском по массиву, отсортированному по возрастанию количества затрачиваемого топлива, роботов, которые могут кого то везти и пересчитываем ответ???

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

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

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

      Как найти число роботов?

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

      ну да по сути, я просто отсортировал всех "претендентов" по увеличению топлива и перебираю границу самого правого которого возьму. функцию проверки не успел сделать =(

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

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

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

      вот вот, также решал, какого-то хрена не зашла

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

        Еще можно его не брать, а брать с нулевой вместимостью, но дешевых (как до меня дошло за 10 секунд до конца контеста :)

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

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

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

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

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

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

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

      Можно много где набажить, у меня упадет на таком тесте:
      6 1 100
      2 0 2
      2 0 2
      0 1 2
      0 1 2
      0 1 2
      0 1 2

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

Мне показалось, или контест продлили на пару минут из-за лагов?

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

I hope next time there'll be more fluent English in the description of problems. I know that many authors aren't native speaker but today's problems are just a bit of difficult to understand. Besides how long will the system test be?

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

I think I'm not the only one who miss if x = 0 so I failed on preetest 3 :) Edited : On problem A

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

System test has begun, finally!

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

в Д, походу, были слабые претесты

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

Приветствую!
Подскажите пожалуйста как нужно писать ( или где можно об этом прочесть) генератор для взлома на С++ и не получать:
-FAIL Expected EOF (stdin)
-FAIL Expected EOLN (stdin)
Благодарю.
UPD: вопрос решен — моя ошибка, а именно выводил более чем М запросов ( задача В ). Теперь понял почему EOF expected.

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

    Вывести в конце пустую строку?

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

      То есть последние два символа файла имеют вид "\n\n"?
      В таком случае я получил
      FAIL Input can't finish with empty line, but the last line is empty

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

        Например, если надо вывести одно число, то правильно 1\n, а не 1.

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

          Совпадает ли это с результатом исполнения кода cout<<1<<endl;?

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

            Да

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

              В таком случае я получал -FAIL Expected EOF (stdin) в задаче В, что можно сделать?

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

                Не перепутать n и m? :)

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

                  Если с n и m все прекрасно? (=
                  UPD: моя ошибка — выводил больше чем М запросов. Теперь понял почему EOF expected.

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

    В конце строк не должно быть пробелов, последний символ файла должен быть \n

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

Спасибо за классный контест. Задачи интересные, мне понравилось.

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

Тестирование завершено?

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

Cool contest guys! Imo little bit easier than last ones.

I have to criticize the task description of task A though. It repeatedly uses the term "cost" to describe the score of the problem. If this is not clear... cost has a negative connotation, decreasing the cost with time thus means that we get a higher score with time. Really confused me there.

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

Комната 22, тестирование по двум решениям задачи С зависло.

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

So unlucky. The test size of C is 10^5 but I mistaken it as 10000. I missed my AK this time, such a pity. The good thing is my E is AC.

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

How to solve Problem D div 2?

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

    Assume there are three balls one going with velocity vx, other with velocity vy, and third with velocity vz. Now at the time of 2nd ball colliding with Door, find where are the two other balls.

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

    First observe that reflection does not change ball's speed in dimensions so you can easily calculate the time that ball gets to y=0, T. Now calculate X and Z of the ball after T seconds. Now you need to find its position inside corridor. Notice that X,Z dimensions are independent. Consider final X of the ball without reflection is X0 and after being reflected once and changing its side, final X of ball without any further reflection is X1. By laws of reflection, X0 and X1 are symmetrical to each other by the wall which ball was reflected by so if it hit X = (a) line then you can calculate X1 as : X1 = 2 * a — X0 and if it hit X = 0 line, X1 will be -X0. And go on from this point until X and Z are inside the corridor. These actions can be done by some easy while loops. I hope this explanation's been helpful for you. If you need further information on this solution, please let me know.

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

    D was quite easy today, look at my submission (sorry, no time for comments in contest), only solve() is important...

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

в комнате 3 задача B повисла, если это поможет

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

The English seems much less comfortable than SRM.......

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

As soon as i posted this comment system test ended. really sry.

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

http://mirror.codeforces.com/contest/203/submission/1860447

почему такое решение получает WA7? У друга посмотрел, у него такой же ответ и тест пройден...

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

    Комментарий чекера wrong output format Unexpected end of file — int32 expected

    Может быть, дело в этом?

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

    Вывод программы — это не «Ответ», а, собственно, «Вывод», и в данном случае он пустой.

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

решил 3ю задачу как на разборе. не прошел 37 тест почему? там ограничения должны же вместиться в ИНТ!

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

    Попробуй тест

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

    открой тесты да посмотри, на чем валится твой сабмит. У тебя там именно переполнение, надо было работать с лонгами)

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

      А меня взломали, не прошло по времени. Не подскажешь, почему?)

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

        кажется у тебя квиксорт без оптимизации, в худшем случае работает за квадрат http://mirror.codeforces.com/blog/entry/4818#comment-98244

        Хорошо на Яве писать Arrays.sort() или Collections.sort() (:

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

          Arrays.sort() для примитивных типов работает за квадрат

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

            в 7й разве?

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

              Исходников не видел, но вроде бы да. Ведь там такой же квиксорт, только разделение на подзадачи более сбалансированное (пруф). Правда, мне кажется, она может влезть в 2 секунды на худшем тесте.

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

                спасибо)

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

                Кстати сказать, в 2 секунды на худшем тесте влезает и на шестой жабе (когда я тестил год назад — на 10^5 отрабатывало за 1.8с).

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

                  Не влезает, я успешные взломы делал на Codeforces твоим генератором. Наверное, у тебя компьютер слишком быстрый.

                  На Java 7 тоже не влезает, 90000 элементов работает в запуске чуть больше 2 секунд.

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

                  Если речь про эту задачу, то там ТЛ 1 секунда.

                  Так значит сортировка в седьмой жабе имеет худшую константу? Просто я те 1.8с получил тоже в запуске.

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

                  Например еще 140C - Новогодние снеговики, там TLE 2 секунды. Смотрите тут взлом 30160.

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

              Да, работает за квадрат. Я исходники видел, алгоритм там тоже полностью детерминированный. Надо и под седьмую жабу написать как-нибудь антиквиксорт :).

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

Подскажите, откуда может быть такое исключение, где я натупил http://mirror.codeforces.com/contest/203/submission/1856933 java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeLo(Unknown Source) at java.util.TimSort.mergeAt(Unknown Source) at java.util.TimSort.mergeCollapse(Unknown Source) at java.util.TimSort....

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

Finally over. Ranked 31 in official participants. Not so bad, but have mistaken the test size of C is so awful. When'll the Rating be updated?

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

задача C: на c# ни у кого не прошел тест 53 по TLE. проверил свое решение локально на 100000 строчках — меньше секунды. баг?

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

    Возможно антиквиксорт тест? Когда-то читал, что Petr когда-то получил ТЛЕ из-за того, что квиксорт на C# работает за квадрат, причем получил на онсайте.

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

      Печально. А можно как-нибудь получить полный текст этого теста?

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

        Думаю, нет. Зато можно рандомно перемешать массив, и посортировать уже его.

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
        по-моему там все парные числа от 1..max.На паскале ето можно легко исправить рандомизацией. 
            procedure sort(l,r: longint);
              var
                 i,j,x,y: longint;
              begin
                 i:=l;
                 j:=r;
                 x:=a[l+random(r-l)];
                 repeat
                   while a[i]<x do
                    inc(i);
                   while x<a[j] do
                    dec(j);
                   if not(i>j) then
                     begin
                        y:=a[i];
                        a[i]:=a[j];
                        a[j]:=y;
                        inc(i);
                        j:=j-1;
                     end;
                 until i>j;
                 if l<j then
                   sort(l,j);
                 if i<r then
                   sort(i,r);
              end;
        l+random(r-l) вместо (l+r) div 2
        

        UPD. 946517 74 тест

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

    Попробуй заюзать метод чтения данных с этой отправки.

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

    Этот Mono у меня уже в печёнках сидит :E Много контестов я уже завалил из-за его тормозов. А теперь выясняется, что у него еще и сортировка глючная.

    Уважаемые авторы Codeforces, поставте нам микрософтовский .NET! Очень просим

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

      А Вы в курсе, что Array.Sort() в официальном(!) майкрософтовском(!!) .NET 4.0(!!!) написан ровно так, как первоначально объясняют квиксорт школьникам из параллели C на ЛКШ, т.е. с выбором опорного элемента через (l + r) / 2? Правда, школьникам в параллели С (в отличие от индусов из майкрософта) сразу же объясняют, что не хрен так делать.

      UPD. Насчет того, что в дотнете "школьный" квиксорт, я ошибся (см. мои посты ниже).

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

        У вас ложное представление о том, как реализован Array.Sort() в .NET вообще и в 4.0 в частности...

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

        Смотрите исходники внимательнее. Там выбирается медиана из трёх элементов. Хотя это тоже не гарантия, я в курсе, но хоть что-то.

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

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

          Я лично декомпилировал mscorlib.dll и смотрел реализацию квиксорта. Вот как там реализована та самая функция Array.GetMedian():

          // System.Array
          [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
          private static int GetMedian(int low, int hi)
          {
          	return low + (hi - low >> 1);
          }
          
          

          Если вас обоих это не убедило — возьмите ILSpy и сами проверьте.

          UPD. Да, я ошибся, медиана действительно находится (берутся первый, средний и последний элемент). Но такой квиксорт завалить все равно не сложнее, чем обычный.

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

            Я не знаю куда вы там смотрели и при помощи чего. Простой тест. Вы можете написать код метода GetBadArray, который бы вызывал квадратичное время выполнения Array.Sort()? Если там простой квиксорт, которому учат в школе, то вам это не составит труда. Причем можете попробовать как в .NET 2.0 так и 4.0...

            class Program
            {
            	static void Main()
            	{
            		int[] array = GetBadArray();
            		System.Array.Sort( array );
            	}
            	static int[] GetBadArray()
            	{
            		...
            	}
            }
            
            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится

              Я где-то нагугливал уже готовый антиквиксорт для C#, работает через компараторы, но ладно, сейчас сам напишу, подождите полчасика...

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

              Если там (l+r)/2, то вот вам тест: http://paste.ubuntu.com/1075047/

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

              Писал в два раза дольше, нежели обещал, но вот генератор, работает за линию :).

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

                На 2.0 у меня выдает:

                100000
                1918,8083
                15,6001
                

                На 4.0:

                100000
                33,0019
                24,0014
                
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Странно...

                  Десктоп (проц P4 640 3.2 GHz, ОЗУ DDR1-400, .NET 4.0 без SP):

                  100000
                  3683,358
                  17,577
                  

                  Ноут (проц Core i5 430M 2.26 GHz, ОЗУ DDR3-1333, .NET 4.0 SP1):

                  100000
                  2246,4039
                  15,6
                  

                  Codeforces, вкладка "Запуск":

                  100000
                  1937,562
                  15,6255
                  

                  Вы ничто ни с чем не перепутали?

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

                  Я кажется понял... У меня стоит .NET Framework 4.5 RC, который патчит сборки 4.0.

                  Т.е. у меня версия файла mscorlib.dll такая: 4.0.30319.17626. У вас видимо номер билда отличается... Когда я декомпилил mscorlib, то увидел там интросорт, но добавлен он видимо только с этого 4.5 апдэйта...

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

please somebody tell me whats wrong with my comparator in problem C.I cannot figure out for which values it cannot make a decision..Here the code

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

Problem E was nice.it has more thinking rather than just coding. thank you all

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

    I agree with you. It has nothing to do with advanced algorithms and data structures, but remains as a challenging problem. In order to solve this problem, one must observed that if a robot with c larger than 0 is chosen then all robots with c larger than 0 can be chosen. It took me over 30 mins to figure out how to solve this problem.

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

Can Anyone Describe me why I stayed blue in rating?? I became 24th and solved four problems. I ask this because people with lower rank became purple!

The contest was great. Thanks a lot to problems authors! ;)

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

Hello, excuse me for the question but this is my first competition in this website and i kept having wrong answer on 7th pretest in task E. So i tried to find my mistake but i couldn't, so after the competition is over, i was wondering if there is any possible way to check what the pretest was, and see why my program mistaked there. Thank you in advance :)

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

    Hello! Click here and scroll to the bottom of the page. But there is not way to see full test.

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

    I encountered the same problem as yours during the contest, and then I figured out that using long long instead of integer can solve this. Hope this helps.

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

В задаче С в QuickSort было поставлено x:=m[(l+r) div 2] ТЛ. Просто поменял на x:=m[l+Random (r-l)] все прошло!!!

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

    А в чем проблема? В такой задаче было бы странно не сделать антиквиксорт теста для разбиения пополам.

    UPD: господа несогласные, прокомментируйте ваше мнение, минусовать все горазды.

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

Y U no put small clear problem statements :)

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

I got a strange result with my code on D, on test case 31:

-1.#IND000 -1.#IND000

On my pc it gives the expected result, I had to add a test to verify if the vz (or vy or vx) is 0 and ignore calculations on them to get accepted, here is my submission:

http://mirror.codeforces.com/contest/203/submission/1861627

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

1861821 Can you tell me why I got a TLE on problem B ?

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

rofl @ pretest 3 of task A... this guy boasted he has a score of ZERO? WTF is wrong with him :)

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

when we can get THE EDITORIAL!!