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

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

Добро пожаловать на Алгоритм-2014 — открытый чемпионат Яндекса по программированию с оригинальными правилами, подарками, денежными призами и финалом в Берлине.

Если вы хотите побороться с лучшими программистами мира за призовой фонд в 540 тысяч рублей, ещё не поздно зарегистрироваться на чемпионат.

Регистрация открыта до конца квалификационного раунда.

Разминочный раунд пройдёт 16 мая в 21:00 по московскому времени, квалификационный — 25 мая. Подробную информацию о сроках проведения вы найдёте в расписании чемпионата.

Вот как проходил финальный раунд в прошлом году.

Желаем удачи!

PS: чтобы зарегистрироваться, аккаунт на Яндексе должен быть полным -- воспользуйтесь ссылкой

https://passport.yandex.ru/passport?mode=light2full

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

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

Start time links are broken, as the links contain month=M.

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

Is the contest rated?

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

In the registration page I saw the word "affiliation". What information I need to provide in this content?

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

Я правильно понимаю, что решив одну задачу в Разминочном раунде, пропускаешь Квалификационный?

По крайней мере стрелочка нарисована: http://contest2.yandex.ru/algorithm2014/schedule/

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

    "Разминочный раунд начнётся 16 мая в 21:00 и продлится 100 минут. Все участники стартуют и финишируют одновременно. Те из них, кто сдал хотя бы одну задачу, сразу попадают в отборочный этап."

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

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

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

The contest will take place, here on CodeForces?

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

In the registration page when I click on changing Date of Birth:  It takes me to some page which is in completely different language(different from english) after which I am unable to proceed. Kindly look into this matter.

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

    Why are you so stupid? Please click onto the Russian flag and change the language to English. BTW, your comment was posted into Russian version of CF.

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

      Actions that you offered are not so obvious. Let's do not offend each other. Everybody can make mistake or do stupid things, it does not mean that this person is stupid.

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

When I click on edit button of date of birth of registration page, I am redirected to this page where I am not able to follow anything since the language is not in english. Kindly look into this.

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

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

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

    Спасибо за замечание.

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

    https://passport.yandex.ru/passport?mode=light2full

    и конвертировать аккаунт. Тогда все получится =)

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

      Спасибо, получилось. Ох уж эти секретные ссылки :)

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

I have two questions for you:

  1. What I need to do with your passport link? I have already registered an Yandex account and when I open your link, I only saw my personal information.

  2. The contest rules said that: "Contestants submit their solutions into the contest system with the help of the software provided. Before submitting a solution, the contestant chooses the compiler that will be used by the contest system, which runs on Linux, to compile the solution." -> What is the required program? Where can I download it?

Thank you.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. The passport link is necessary for the owners of light accounts (i.e. authorised using social networks). As soon as you are registered, there is no need to do anything with the passport link.

    2. Rules refer to the contest environment as a provided software. You won't need to download or install anything, just use the online submission form. It should work well on Linux. =)

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

In the Registration form, there is a section which we must fill in ---->>> "Affiliation", I don't know what does it mean, can you help me?

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

As somebody said — some participant join to compete, other — to help with testing the server load. I am going to help with testing the server load at this competition :) At last RCC round help of people like me was invaluable :)

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

Link to the contest for those how is lazy as me

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

Успел словить Internal Server error. Ай-Ай Яндекс! :)

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

    Ещё пару раз видел эту надпись ближе к концу — это уже было менее приятно :(

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

      Всё — у меня лежит. Не скажу, что эти сильно повлияло на мои результаты, но уже минут пять обновляю страничку.

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

А только у меня иногда версия таблички старая за рандомную минуту показывается? То есть ф5, показывается табличка старая с рандомной минуты, ф5 и всё ок.

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

При обновлении Standings они периодически уходят назад во времени (при этом довольно существенно, минут на 30). Какой-то баг кеширования?..

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

    Значит не только у меня :)

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

      Да, такая проблема проявляется и у меня. Мы уже локализуем ошибку, спасибо большое за сообщение

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

      У меня такое бывало во время SNWS, но буквально 3 или 4 раза суммарно за все контесты, а сегодня едва ли не на каждом втором обновлении.

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

А я последние 5 минут не могу отправить решение из-за ISE UPD: смог за 11 сек до конца

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

При попытке отправить решение на последней минуте: "Internal Server Error" после 30 сек задержки
UPD: особенно неприятен тот факт, что решение было правильное

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

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

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

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

Расскажите, как решать F?

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

    Если встретил 1, то ее нужно объединить со следующим числом и все. Если встретил x > 1, то нужно разбить на 1 и x — 1 и все.

    Коварный случай: 1 0 2

    Тогда разложение эквивалентно 2 0 1 1

    Но по условию второе не разрешается.

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

      Так рассказать решение можно, если я решил и хочу убедиться, что у меня такое же решение. А я не решил. Можешь поподробнее рассказать, пожалуйста?

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

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

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

    1/p + 1/q = 1 => q = p / (p — 1) = 1 + 1 / (p — 1)

    Далее надо проверить, если данное в условии число — p и {a_n} — разложение для него, то если a_1 > 1, то разложение для q — {0, 1, a_1 — 1, a_2, ....}, иначе — {0, 1 + a_2, a_3, a_4, ...}

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

      Можно с начала и чуть поподробнее? =)

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

        Рассмотрим данную нам дробь — она имеет вид 1/p, где p — это какая-то цепная дробь. Нам надо разложить число 1/q, где 1/q+1/p=1. Отсюда следует, что q = p/(p-1) = 1+1/(p-1). Таким образом, из определения цепной дроби, получаем, что если a1 > 1, то 1/q = 1/(1 + 1/((a1 — 1) + 1/(a2 + 1/(a3+... Ну и надо правильно обработать случай, когда a1=1.

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

Many thanks to all participants! We know and already working on issues of old monitor content and the internal server errors in the beginning and at the very end of the contest. If you faced any other problems, please, report them to the http://feedback.yandex.com/contest/

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

Если послать задачу не туда(Е в А, например), а потом этот же код послать туда куда надо, система ругается, что вы уже посылали этот код.

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

    У меня было ещё более странно — я (в последние минуты) заменил все int на long long, система меня тоже отругала, что я засылаю тоже самое решение. Может, конечно, система знала, что это не поможет, но я такого поведения не ожидал — побайтово код был другой. Неужели какая-то эвристика?

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

Как решать факториалы без длинки?

Две задачи сдавались методом "Зачем думать, если можно написать на джаве" :)

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

    А какая ещё, кроме В?

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

      Е. Там выходит что в 100! примерно 200 цифр, в третьей степени примерно 800, значит в сумме примерно 1000. Заходит за 120 мс

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

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

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

          Я еще долго думал что мне больше лень — писать на джаве или написать свою длинку :)

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

            или выводишь первые 10 элементов для каждого k, видишь закономерность, пишешь 13 if'ов

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

    А зачем там длинка? Кроме случая k = 0, нужны максимум две последние цифры.

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

      Нет, максимум одна)

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

      Объясни начинающим, почему две?

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

        Заметим, что факториалы, начиная с 10!, делятся на 100, поэтому, начиная с n = 10, последние две цифры меняться не будут. С меньшими n можно явно проверить, что все суммы не делятся на 100.

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

          eatmore, спасибо — мы говорили про разные вещи, но в итоге я понял, где у меня была ошибка :)

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

      А с этим вообще весело получилось: на контесте пробовал брать 30, и даже 36, цифр не заходило, попробовал 2 и все окей... И попробуй пойми в чем же баг... Может __int128 кривой?

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

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

    При сложении там получается немного — 9**3 = 729 * 100 = 72900.

    Но что-то у меня не сработало.

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

    Каждую степень факториала (слагаемое) представим в виде произведения простых делителей. Найдем максимальную степень десятки, на которую делятся все слагаемые и поделим на нее (достаточно смотреть на степени двойки и пятерки в слагаемом). Теперь есть слагаемые, которые не делятся на 10. Однако сумма все еще может. Поэтому просто считаем эту сумму по модулю 10^15. Выводим первую ненулевую цифру. На контесте получил WA31, в дорешке ОК через 3 минуты после конца.

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

      достаточно смотреть на степени двойки и пятерки

      достаточно смотреть на степени пятерки

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

        А, ну да. Степень пятерки всегда меньше.

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

    Я написал вычисление по модулю 109 и прогнал через все множество тестов. Везде получился ответ не 0, значит 9 последних цифр хватает. Заслал вслепую.

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

    Достаточно решить два случая:
    1) k = 0
    2) n <= 4, k > 0
    если n > 4, то ответ такой же, как и у n = 4.

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

Задача D какая-то хитрая? Там работает обычная Дейкстра с приоритетом сначала по сумме длины, потом по количеству ребер? Или Левит?

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

    Работает обычная Дейкстра.

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

    И обычный Форд-Беллман. Проделываем обязательно N - 1 итерацию и запоминаем, при каком i оптимальное расстояние до N по i рёбрам было минимальным в последний раз.

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

      Написал и Дейкстру, и Левита, и Форда... Где может быть подвох, ВА 2? Там есть подвох?

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

        У меня тоже не получилось — не прошёл тест 2, хотя минут 40 эту задачу "вылизывал", трейсил и по примерам прогонял. Даже условие раза три перечитывал.

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

        Показали бы код, мы бы посмотрели...

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

          Буду благодарен. Я сам ещё не разбирался, но буду. И в любом случае добью эту задачу. Так что посмотрите только если есть время.

          Три комметария: 1) Этой мой второй контест на C++, до этого был только Python. Последний раз до этого C++ видел в 2001 и без STL. 2) Дейкстру на C++ ни разу не писал. 3) То что везде long long — это я в последнюю минуту пробовал на авось.

          Буду рад комментариям по стилю/использованию типов данных. Спасибо!

          http://pastebin.com/iKKRPBiF

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

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

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

              Ну там не Дейкстра, а Форд-Беллман с очередью получился)

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

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

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

            Я вообще, если честно, не понимаю, что происходит у Вас в коде. Я сомневаюсь в целесообразности использования мапа для хранения списков рёбер. Естественней смотрелся бы простой массив векторов.

            Для Дейкстры Вам надо хранить множество ещё не финализированных вершин. Я не совсем понимаю, какое условие проверяется в 60 строчке. И ещё я не совсем понимаю, что за тройки чисел у Вас хранятся в очереди Queue и как эти значения связаны с N_length и N_numroads.

            В целом, будь даже Ваш код правильным, он, на мой вкус слишком сложен. Вот, что сдалось у меня: http://pastebin.com/mjf0p8mT

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

              То, что происходит в коде — это одна из модификаций SPFA. Хоть и написана не лучшим образом)

              Авторский баг — в считывании, там цикл по n, а надо по m.

              Если это исправить, то TL11. Если поменять типы на нормальные и немного соптимизировать код, то TL13 или TL14. Чтобы зашло — надо, обходить DFS'ом, а не BFS'ом, и не пихать в очередь лишнего. Когда поменял push_back на push_front и стал добавлять в очередь только те вершины, которые улучшаются, а не всех соседей сразу — АС за 0.45.

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

                Спасибо большое за комментарии. Буду работать над собой. :)

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

                Результат работы над собой:

                http://pastebin.com/Dmkuj9xC

                Теперь больше похоже на нормальный код? По тестам заходит, правда пробовал уже на Codeforces — 0.124.

                Ещё раз спасибо за комментарии!

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

      Дейкстру проще писать, потому что можно хранить рёбра в виде матрицы смежности.

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

    Я подумал, что если сделать дейкстру по паре (длина, рёбра), то может быть плохой случай. Так что написал обычную дейкстру по длине, а потом шёл от последней вершины рекурсивно и делал переход к предыдущей, если g[i][j] + d[i] == d[j]. По каждой вершине пройдёмся один раз, если сделаем кэширование.

    Вот код без кэша:

    private int getAns(int v) {
        if (v == 0) return 0;
        int ans = 0;
        for (Pair<Integer, Integer> p : g[v])
            if (d[v] == d[p.getKey()] + p.getValue())
                ans = Math.max(ans, getAns(p.getKey()));
        return ans + 1;
    }
    
»
11 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

А можно будет увидеть тесты?

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

Can someone find the mistake in this code for A? I am puzzled :(

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

    There are two:

    1) rook can't attack through white king.

    Test: a3 a5 a1. Right answer: normal. Your: check.

    2) black can capture white rook.

    Test a3 b1 a1. Right answer: check. Your: checkmate.

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

      Thanks a lot, I realize my answer was far from correct and now, I feel stupid :P I guess this problem requires careful implementation, something which I suck at.

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

    c1 a1 h1

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

    a5 a1 a8

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

Can I participate in the qualification round If I did not write the warm-up round?

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

У кого-нибудь есть в B меньше чем 10 строк кода?

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

    А у тебя решение на 10 строк?

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

    Ужала свое решение до 9 строк, можно и еще ужать, но и так уже достаточно некрасиво :)

    import sys, re
    a = re.split ('[\W_]', sys.stdin.readline().lower())
    b = re.split ('[\W_]', sys.stdin.readline().lower())
    c = sys.stdin.readline().strip().lower()
    a, b = a.count(c), b.count(c)
    n = int (sys.stdin.readline())
    a, b, i = b - a, a, 0
    while b < n: a, b, i = b, a + b, i + 1
    print i if b == n else 'Impossible'
    
    
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve problem E that factorial??

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

    For k = 0, answer will be the last non-zero digit the number n+1. Let d[n][k] is the answer. Then for n > 3 , d[n][k] = d[4][k].

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

    Bruteforce in Python, just keep the last 10M digits for chosen reasonable M (feel free to use M = 10). No thinking required.

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

      Actually M = 3 is enough :P

      PS: I just noticed, you mentioned last 10M digits, you mean the last M digits :D

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

        Yeah, last M digits. But the more you choose, the more confident you can be.

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

    You can use BigInteger in java.

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

I don't have any clue why this code is giving wrong answer. Can anyone please find out the bug in it?
http://pastebin.com/jB6H3b7W
A small request to Yandex Algorithm organizers. It will be very helpful if you can provide the test cases or editorials. Thanks in advance.

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

For Problem A I am unable to find any errors with my code. Can anyone please find out the mistake in it?
http://pastebin.com/jB6H3b7W
A small request to Yandex organisers. Kindly provide the test cases or editorials for the problems. Thanks in advance.

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

    try f2 h2 h5 upd: try f5 h2 h5

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

      It's showing "Check".
      Also if the just the white king is attacking black king at its current position and not the rook then what should be the answer "Check" or "Strange". I tried it both ways still it's giving wrong answer. Thanks for the test case but I think the code is giving right answer for this.

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

        No, in this test answer is "Checkmate".

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

          Thanks for pointing out the test case. I wasn't checking for the piece going off the board. my bad.

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

          The answer is "Check" for this test case. But it helped me notice the stupid mistake I have been doing. Thanks.

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

        Queen? King, no? If the kings are mutually attacking, then the position's Strange (it shouldn't be possible within chess rules!), wherever the rook is. The rules in the problem statement are listed in order of priority and make sense to anyone who knows the rules of chess.

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

          Sorry for the typo there. Yaa got that. Sorry for such a naive question. Thanks.

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

      try f5 h2 h5

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

    I'd recommend you never, ever write code like this again. One little mistake while copy-pasting will throw all your work away. If the most primitive concept in the problem is the point, you most probably need a pair<int, int> or a struct with two fields. If you need to copy your code 8 times with small corrections, you most probably should think about looping over a constant array of 8 elements, rather than copy-pasting and adjusting indices by hand. (I'm trying to help, sorry if it sounds offensive.)

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

      @udalov Thanks for pointing it out. I will take care of it in future.
      Doesn't sound offensive at all. I am open to all kind of suggestions.
      Thanks again.

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

      While this way eliminates the risk of missing just one element to rewrite, it has other risks. Sometimes, there are problems which do a lot of operations on one 2D array in each direction; this can be solved by rotating/flipping that array and only doing a lot of operations on another array, but you need to pay attention to the order in which you use the elements of that other array; the more complex the operations are, the harder this is, and it gets harder much faster than copy-pasting and naming your 16 variables differently, because it requires heavy thinking about every line of code (and you need to think in indices instead of words). It's easy to be off by 1 in some formula, and these mistakes are harder to find than copy-pasting ones (find and replace).

      If the algorithm's doing something simple multiple times with small variations (or it's not too many times, it's not good to copy-paste. If it's something complex, it's debatable.

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

Did B really have tests for large integer arithmetic? This seems totally unfair because solutions in Java will be like 3 times shorter than ones in C++, which is probably why such problems are avoided in other contests.

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

    As a Python lover I can equally say that giving computation intensive problems with short TL is totally unfair, because same solution in C++ is 10 times faster. My point is that every language has its weak sides, even C++.

    I don't see any rule limiting you from developing your own small class for working with BigIngeters. To have it just in case. To be honest this is what I am doing now :)

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

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

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

Добавил в тренировки 2014 Яндекс.Алгоритм - Разминочный раунд. Конечно, слепые попытки учитываются как просто попытки в ACM-ICPC-режиме.

Ох уж мне эти собранные вручную архивы:

  • В задаче A какие-то кривые tex-файлы условий: например, нет сэмплов (может не хватает еще чего-то?)
  • В задаче F часть решений использует ocf.in/ocf.out, а часть — стандартный ввод-вывод.
  • В задаче Е авторское решение не проходит тест 31: fact_snark.c валится с вердиктом wrong answer expected '4', found '3'.

Еще мне кажется, что такие архивы должны содержать olymp.sty, а еще лучше готовые скрипты для сборки PDF-условий.

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

    А еще задача C даже в английском интерфейсе имеет название "Окружности-2" (http://contest2.yandex.ru/algorithm2014/contest/502/problems/C/).

    Что характерно, tex-файлик с условием содержит правильное название, что скорее всего говорит о каком-то копи-пейсте в при настройке.

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

    Еще некруто, что не внесли клары в условия. Например, этот:

    Во фразе "...каждому вещественному числу x соответствует единственная цепная дробь..." следует заменить вещественные числа на рациональные.

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

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

    В задаче F часть решений использует ocf.in/ocf.out, а часть — стандартный ввод-вывод.

    Те, которые с консолью, содержат в названии подстроку "_cc".

    Проблема стандартизации поддержки нескольких форматов задачи в одном архиве (graders / file / console input-output, ioi / acm scoring), к сожалению, до сих пор не решена :( ... Есть идеи по этому поводу?

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

Can I participate in the qualification round if I didn't participate in the warm-up round?

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

can someone explain to problem E on factorial. I see the solution but somewhat unable to get why for N > 4 , we take N = 4

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

I am unable to open the yandex links. Does this happen only with me?

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

I am unable to open the yandex links. Does this happen only with me?

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

I can't find any working link for the contest, for hours. I guess the qualification round is running now, but I can't find a link for the contest.