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

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

Всем привет!

Кто может рассказать решение задач А и D? У меня и в А и в D WA2 почему-то.

Спасибо

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

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

Понятно, что номерами пользователей будут степени простыx pa, где a — некоторая степень двойки, а p — некоторое простое. Поэтому номера групп будем раскладывать именно в виде таких степеней.

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

    Если честно, то никак не понятно. Но, спасибо за решение.

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

D — надо разложить на множители, а потом для каждого простого разложить кол-во его вхождений по степеням двойки

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

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

    Как сдать D с первой попытки, при этом поняв условие?

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

      Условие довольно четкое, по-моему. Это единственный расклад, при котором все положительные числа больше 1 являются айдишниками чего-то

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

        Да, действительно, условие -- четкое. Нехорошо только то, что главная сложность этой задачи: понять условие, а не решить.

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

          Может быть, чисто формально оно и четкое, но это не отменяет того факта, что оно непонятное. Я бы не хотел, чтобы подобные условия встречались в дальнейшем где бы то ни было.

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

      да это что-то из рода фантастики, условие ваще укуренное, зачем давать такое г? из условия вообще никак не понятно, что число, которое может быть идентификатором группы, не может быть идентификатором человека (т.е. число 12 — не может быть идентификатором человека, это них непонятно), из него как раз следует наоборот. побольше бы таких условий.

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

        Да ладно. Прекрасное условие, в котором почти сразу понятно, что от тебя хотят. Почти очевидно из условия, что один номер не может соответствовать как группе, так и человеку одновременно, и что искомое разбиение единственно. Такие мелочи можно додумать и самому. Пожалуй соглашусь — побольше бы таких условий.
        Что Вам не нравится с числом 12, я так и не понял.
        И задача хороша, свежая такая, как раз для такого типа соревнований.

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

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

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

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

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

              Вы братья или раздвоение личности?

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

              Если внести еще несколько предложений, разъясняющих условий

              да, давайте создадим сложность задачи за счет ее понимания, отличный ход.

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

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

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

                В случаях, когда человек считает, что вариант додумать условие — не один, обычно ему говорят "No comments".

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

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

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

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

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

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

                  не понимаю вас. вы предлагаете додумывать условие?

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

                  Нет, не предлагаю. Я утверждаю, что в условии этой задачи достаточно информации для ее решения. Все-таки, ее сдали не десять человек, в частности, сабмитами вслепую.

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

                  но вы в предыдущем сообщении написали

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

                  и вариант додумать условие — один

                  что-то вы противоречите сами себе, брат мой

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

                  в этой же задаче, нифига ничего не четко, лучше бы правда ребус дали

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

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

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

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

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

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

                  ps. завтра лещиков тебе надаю по-братски

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

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

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

                Если бы цель была избежать любых неверных пониманий условия, думаю, автор без труда с этим бы справился.
                Но на контесте, где есть возможность выбора между отправкой вслепую и по АСМ-правилам такая задача вполне имеет право на существование. Судя по результатам, немало торопыжек получили свои крестики, не полностью осознав, что от них хотят в этой задаче.

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

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

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

    В D ещё надо отсортировать. Я забыл и у меня WA2

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

А как решать B?

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

A — dfs, храним макс. путь вниз и количество таких путей в поддереве, пока обходим граф — обновляем ответ.

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

    Я решал так: len -- диаметр графа, запускаю bfs() с произвольной вершины, и те вершины, до которых кратчайшее расстояние равно максимуму -- это вершины, которые могут быть началом диаметра. Обозначаю их кол-во a. Среди них с произвольной вершины опять запускаю bfs(), и те вершины, до которых кратчайшее расстояние равно максимуму -- это вершины, которые могут быть концом диаметра. Обозначаю их кол-во b. И вывожу ответ len + 1 и a·b. Но получаю WA2, в чем моя ошибка?

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

А почему таблица менялась уже после конца контеста? Был реджадж?

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

    14:00 — последний момент старта

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

      Странно, я, кажется, после 16 уже таблицу смотрел. Хотя, на время тогда внимание не обратил.

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

    Точно был реджадж по С. У меня сначала был RE8, а потом стал AC.

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

Может я конечно не замечаю очевидных вещей, но можно ли как-то сдать задачи после контеста?

Сообщает при посылке: "You can send only UPSOLVING submission after contest end", но как это сделать я так и не понял.

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

    Можно, если отправлять через вкладку "Посылки", а не через страницу задачи.

    UPD: А вообще у меня работает и через страницу задачи.

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

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

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

А можно это как то порешать-подорешивать, если я пропустила контест? Мне просто пишется, что соревнование завершено и отправка решений запрещена(даже условия увидеть не могу...)

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

    Да, можно просто начать виртуальный контест точно так же как и в основное время.

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

      Прости за глупый вопрос, но как это сделать? Потому что на этой странице я не нашла соответствующей кнопки, а где искать ее в другом месте я не знаю...

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

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

        При регистрации на contest2.yandex почему-то пишет, что нельзя отправлять решения, но, если зарегистрироваться на contest.yandex, все окей.

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

          А вот я до сих пор не могу дорешивать даже на contest.yandex.ru, выдаётся та же ошибка, только на английском.