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

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

Привет всем. Прошёл первый отборочный тур ИОИП. предлагаю обсудить задачи здесь.

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

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

Уже можно обсуждать?

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

    Да вроде конец.

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

      Не знаю У меня кнопка сабмит работает

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

        у меня вот что. OVER, 300:00 of 300:00

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

          Как решать D на 100?

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

            Ну у меня пока 40. Когда будут резы узнаем 100 или нет. Дп с параметрами номер бита, биты чисел x, y, z и меньше ли x r, меньше ли y r, меньше ли z r,больше ли x l,больше ли y l, больше ли z l.

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

            Заметим, что какая-либо пара x и y однозначно задает z. Переберем в какой позиции x и y начинают отличаться от L или R (это тоже перебираем). Проверим, что сгенерированный префикс z попадает в [L; R]. Будем потихоньку идти и добавлять очередные биты в x и y, поскольку они уже однозначно лежат в интервале [L; R], нужно проверять z. Будем пересчитывать количество способов получить текущую позицию. Если новый бит у z однозначно определяет, что z лежит в интервале [L; R] добавим в ans 2^(кол-во оставшихся бит) * (кол-во способов попасть в данную позицию), если же нет, то префикс z все еще совпадает с префиксом L или R, продолжаем генерировать последовательность. O(log^3).

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

Результаты уже появились. Ссылка на архив тестов и решений жюри не корректна :( Как решать С на 100?

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

    Где появились?

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

    -

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

    Я решал С так. Я не уверен что на 100, т.к. сделал маленькие массивы но идея такая Будем хранить в сете числа которые написаны на квадрате Найдем минимум потом дфс находим такие числа которые на 1 меньше текушего (если рассматриваем в бфс чисор то выкидываем его из сета), заходим в них рекурсивно итд Запоминаем максимальную глубину дфса

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

      -

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

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

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

      Можно заметить, что при обработке клеток, начиная с самой маленькой, никаких дфсов/бфсов не нужно. Можно просто завести массив, в котором будет храниться ответ для каждой клетки, изначально все ответы равны 1. Тогда, при обработке с самой маленькой, мы будем смотреть на соседние, и если они на единицу меньше текущей, то в ответ текущей будем записывать максимум из текущего ответа и ответа для соседней + 1. Очевидно, что, если из данной клетки переходов в меньшие нет, то для неё ответ равен 1, иначе меньшие соседние клетки мы уже обработали. Получаем быстро пишущееся решение за O(n*m*log(n*m)).

      С другой стороны, если использовать дфс/бфс в решении, то можно не сортировать клетки, а просто запускать обход из тех клеток, где мы ещё не были. В обходе всё почти так, как и у вас, только мы для каждой посещённой вершины запоминаем ответ. В итоге получаем решение за O(n*m).

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

    Заметим, что у нас есть несколько ациклических графов. Несложно посчитать такую динамику:f[i][j] — это максимальный по длине путь, заканчивающийся в клетке i,j. Код под спойлером.

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

      Ваше решение прошло на 100? Просто у меня идея похожая, но только 60. Вот я бы хотел узнать почему мое решение неправильное. http://pastebin.com/vSB4XbXK

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

        Да, 100.

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

        я решал БФСом, реализация оказалась простой.
        вот код

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

        Эммм... Сначала релаксируется текущая динамика, а только потом, если мы еще не посчитали dp[newx][newy], считаем?

        Так или иначе мог быть stack overflow.

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

        Мое решение один в один совпадает с Вашим и тоже получило 60 баллов :(

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

          Если ваше решение совпадает один в один то вас должны были дисквалифицировать)))

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

Контест какой-то баянистый был...

Первая задача — элементарна.

Вторая задача — фигню надо писать.

Третья задача — стандартный алгоритм.

Четвертая задача — стандартное ДП.

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

    Это был отборочный раунд, которые традиционно легче обычных контестов. Ждём тебя на следующих личных олимпиадах.

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

Привет всем.

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

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

Добавьте, пожалуйста, кто-нибудь тренировку по Первому отборочному туру ИОИП.

Спасибо. :)

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

    Поддерживаю

    Проверю, правда ли что там трабла с размером массива или с чем то другим