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

ИОИП. Второй отборочный раунд.
Автор PavelKunyavskiy, 14 лет назад, По-русски
Сегодня (30.01.10) прошел второй отборочный раунд на ИОИП. Предлагаю здесь обсудить задачи.
  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Было бы интересно узнать решение задачи С. 
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я BFSом набрал 40 балов(но решение точно неправильное)
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нечто бфс-подобное набирает 45. Решение за квадрат набирает 30, хотя обещали 60 за куб. Возможно что баги у жюри, но пока нет тестов сказать нечего.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Отправлял когда ложился сервер, но успел прочитать что у меня 100.
    Решение примерно такое:
    Каждая вершина будет принадлежать какой-то сосне. Если это вершина, в которой другая сосна-ветка крепится к стволу, то эта вершина принадлежит стволу. Храним уровни всех вершин, изначально - нули. Будем удалять листы в порядке убывания уровня. Сначала все листы - сосны уровня 0, и при переходе в предков, уровень предков станет 1, потому что у 0-сосен нету ствола. При всех других переходах возможны два случая:
    1. Переход из собственного ствола в него же. Т.е. все ветки текущей сосны уже удалены, или их не было, и сейчас алгоритм просто перемещается по стволу текущей сосны. Ясно, что уровень сосны менять не надо.
    2. Переход из одной сосны в другую. Иногда будут переходы от одной сосны к сосне-родителю. В этом случае надо увеличить уровень сосны-родителя на 1.
    Как узнавать какой случай сейчас рассматривается? Достаточно тривиально: если степень вершины-предка 2 или 1, то мы перемещаемся по стволу. Если степень вершины-предка 3 или больше, то это переход в сосну-родителя. Теперь просто обойдем в таком порядке все дерево и в итоге будет заполнен массив с уровнями сосен. Вывести максимум не составит труда.
    Для решения, которое укладывается по времени можно использовать сбалансированное дерево поиска, которое хранит параметры которые нам нужны (первичный: степень вершины, вторичный: уровень вершины). Выбирая каждый раз минимум из дерева поиска, можно будет за логарифм изменить предка этой вершины-минимум и соответственно удалить саму вершину-минимум. И так, пока дерево не опустеет.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      А можно объяснить как из условия понять что бамбук имеет уровень 1?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если бамбук - цепочка вершин в количестве более чем 2, то да:
        "Будем называть сосной нулевого уровня граф из двух вершин, соединенных ребром."
        "Сосна k-го уровня представляет собой путь, который называется стволом, к некоторым вершинам которого прикреплены сосны уровней не больших k−1."
        Не очевидно, но если обдумать, то становится понятно, что все вершины кроме одной - ствол, последняя - сосна-ветка. Основной упор стоит сделать на первую из двух цитат.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          Ну видимо если сильно придираться к условию, то согласен. Вообще из определения можно сказать так. Весь граф ствол, из него не торчит ничего поэтому уровень 0. И вобщем-то с этим сложно поспорить.
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Если убрать "Будем называть сосной нулевого уровня граф из двух вершин, соединенных ребром.", то бесспорно.
            → Ответить
        • 14 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
          В принципе я знаю много людей, которые посчитали что бамбук имеет уровень 0. Тем более, что не очень есть возможность задавать вопросы, на мой взгляд корректнее было бы засчитывать оба понимания.
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну я первые 11 попыток не мог понять это, и получал 80 баллов, сначала хотел написать им что у них баг, так-как более оптимальное решение проходит меньше. Но потом посмотрел что нулевой , это только один вариант. 
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              аааа!!!! вот оно что! Я как раз думал что бамбук имеет уровень 0. Писал динамику за линию (примерно как описывал ZoomZoom). Вот почему WA! 75 баллов именно из-за того что не понял этого. Спасибо за разъяснения - )
              → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            > корректнее было бы засчитывать оба понимания

            Мне кажется, не стоит об этом мечтать. В условии все четко написано. Хотя конечно по-хорошему надо было еще нарисовать на видном месте пример с бамбуком.
            → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче В(Улей) я вывел формулу 3n2 -3n + 1.
Но почему-то у меня всего 66 балов. Вроде бы правильно, int64 использовал, проверял на примерах, к примеру, на N=109 ответ равен 2999999997000000001, кажется?!
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    да, чтото такое
    странно
    на С++ если писать в intах получаешь 50 баллов (даже если объявлять int n ; long long ans)
    66 не знаю откуда могло взяться
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Использовал n^3-(n-1)^3 и питон. 100 баллов. 
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ну да, сокращаются 3 степени и остается то что нужно )))))  ( thank you, cap )
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Это и есть 3n2 -3n + 1. Но у меня 66
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Например вы могли выводить int64 как %I64d. или  как %d. 
          → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          3n <-это должно быть в int 64
          3n2 <-  это тоже
          int n;
          int64 res=3*n*n-3*n+1 не будет работать
          int64 res=3LL*n*n-3*n+1 тоже
          int64 res=3LL*n*n-3LL*n+1 <- будет

          или сразу int64 n;
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Но у него на N=10^9 выводит! А значит и на меньшие должно выводить
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится
              Хм, да, тогда без поллитры сорса не разбершься
              → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня прошла на 100:
    формула = (n*(n-1))/2*6+1
    Дело в том, что при каждой i-ой оболочке прибавляется i*6 шестиугольников.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В принципе это и есть 3n2 -3n + 1. Но у меня 66 балов?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        да, все эти формулы очевидно тождественно равны
        abza_ktl, посмотрите тесты и узнаете
        потом еще здесь отпишитесь плз, а то мне самому интересно :)
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        long long не забыл?
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Использовал точно такую же формулу и получил 100. Возможно ошибка в реализации.
        → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а показ количества баллов по посылке это баг или сегодня были немного другие правила чем в первом отборочном раунде?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Говорят, что баг.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      странно, в предыдущих контестах вроде такой баг был вначале, а потом исправляли
      странно что сегодня не исправили
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
у вас тоже в клиент не заходит?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решали задачу D?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я на 60 сдал за квадрат. если нужно напишу как
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мысль первая. Если отрезок вложен в отрезок, то надо чтобы вложенный сидел ближе к выходу. Иначе все равно.
    Мысль вторая. в отрезок может быть вложен только меньший по размеру, поэтому посортировали по длине - получили вторую строку ответа.
    Дальше взяли RMQ или фенвика и посчитали количество пересечений. Это делается так. Посортировали события. Если кто-то сел или встал - то вязли сумму на отрезке, потом изменили соответствующее значение на 1 или 0.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      я ставил следующего по времени входа чувака (i-го) на место n-i (нетрудно убедиться в правильности этого алгоритма)
      при удалении чувака считал скольких он пройдет, идя к выходу
      писал в конце, не успевал написать rmq (хотя скорее поленился), поэтому считал втупую за линию количество людей которых нужно пройти
      с rmq получится решение на 100
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        У меня почему-то ниче не открывается. Наверно кривые руки. Не можете посмотреть, сколько у меня баллов(Лахтанов Иван).
        → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если не сложно, поясните как врубиться в декартово дерево, и для чего оно используется в этой задаче на понятном  языке. Спасибо.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        http://habrahabr.ru/blogs/algorithm/101818/
        Вот тут неплохо объясняется.
        → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Хотелось бы уточнить, правильно ли я думаю: просортировав по длине мы получаем очерёдность расположения пассажиров, а найдя количество течек пересечения временных отрезков отвечаем на первый пункт задачи.  Так ли это?


      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я сдал на 100 вроде. Решение такое:
    Посортим всех по времени захода. Утверждается, что если рассадить их в обратном порядке
    (т.е. v[i]-того человека сажать на (1000 - i) место), то это будет нужной рассадкой.
    Очевидно, что по факту у нас есть отрезки на прямой, и нам надо посчитать количество пересечений этих отрезков. Я делал это с помощью декартового дерева. Наверно, можно легче.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Подскажите подробнее , как Вы использовали декартово дерево в этой задаче. И вообще как разобраться с этим декартовым деревом? Почитал RMQ, Фенвика там считаются какие-то суммы на отрезке, а здесь что?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Попробую объяснить. Заметим, что количество неудобств равно количеству пересечений отрезков(именно пересечений, без вложений!).Возьмем наш массив пассажиров, отсортированный по времени входа. Будем обрабатывать наших пассажиров с 0 по N - 1. Пусть мы сейчас обрабатываем участника с номером i. Тогда в декартовом дереве мы храним времена выхода пассажиров с 0 по i - 1. Понятно, что отрезки (вход-выход) пассажиров с 0 по i - 1 пересекают отрезок(вход-выход) i-того пассажира только если их конец лежит между началом и концом i-того отрезка. А количество таких концов очень легко найти с помощью декартового дерева. Вот и все.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вы очень подробно описали своё решение. Спасибо. Но, хотелось бы уточнить и понять, в том ли направлении я думаю. Мы сортируем участников по времени входа. Потом по времени выхода строим декартово дерево. А как Вы определяете вторую строку ответа. Другие мои мысли: если просто нарисовать отрезки на плоскости для каждого участника (т.е. например для первого начало (1,1) -  конец (1,8)  и т.д. , то что остается только перебрать каждый с каждым и посмотреть на их пересечение. А Вы в своём решении смотрите на  пересечение  (вход-выход), а где это пересечение не могу понять. Что-то я до конца не могу разобраться с этой задачей. Если Вам не сложно нарисуйте схематически рисунок для теста, чтобы понять какое это дерево и где то пересечение о котором Вы говорите. Сам я что-то туплю в этом. Спасибо.
          → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Результаты вышли
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А С как решать?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Уже был этот вопрос. См.выше.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Покажите кто-нибудь 100 % решение задачи D на Паскале. Спасибо.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
За 10-15 минут до конца было почти нереально  отправить решение. Наверное там что-то поломалось. Обидно за 20 баллов(
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    да уж, сегодняшний контест был сплошным багом....
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
а кто еще кроме меня получил не 100 по С,  потому что бамбук имеет уровень 1?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    75 именно из-за этого. - (
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      45. У меня из-за этого еще несколько больших уменьшались на 1.
      → Ответить
      • 14 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        45?? xD у меня тоже так было. Я в шоке быстренько закоментил пару строк и получилось 75 =D. Всё таки приятный баг с баллами.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          для меня скорее неприятный получился:)
          все задачи у меня с первого раза сданы на столько, на сколько рассчитывал
          так что из-за бага меня обогнало несколько человек наверно :)
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            >> а я набрал 40 баллов выводом единицы :D
            т.е. ты на это сразу рассчитывал?? xD
            → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
кто нибудь может откомпилить check.java на задачу D и залить куда нибудь?пожалуйста, очень надо!
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Сколько баллов надо чтобы пройти на 3 тур
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Думаю скажут через пару дней.
    Скорее всего немного, снова баллов 150-200
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а сколько в прошлом году было участников?
      в этом уже прошли 120 человек, так что можно спрогнозировать уже сейчас в приницпе :)
      → Ответить
      • 14 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        http://neerc.ifmo.ru/school/ioip/standings-2010.html
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          около 200
          значит, отбор по 2му туру будет человек 80 
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            организаторы считают что большинство тех кто должен пройти уже прошел в 1 туре. и в принципе правильно считают)
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              А еще они могли квоту увеличить
              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Очный тур (по прошлому году), проводится в Питере, Москве и тд... Не все смогут приехать... В Беларуси (по результатам прошло не менее 15 человек) за день до ИОИП заканчивается республиканская олимпиада (и не факт что кто-либо организует место для ИОИП в Минске или тд, если это вообще возможно), так что скорее всего доехать до Питера (в Москве обычно учавствуют только москвичи) не получится :(. Думаю проходной балл будет меньше 200 для 2-го тура
                → Ответить
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Возможно, я думаю. У нас в городе делали. А вообще разумно что со второго раза должно быть меньше человек, т.к конкуренция ниже)
                  → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно с этой олимпиадой в университет поступить?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Насколько я понимаю, эта олимпиада в любом случае дает 100 баллов по информатике и некоторые вузы могут засчитывать эту олимпиаду как вступительное испытание или даже зачислять. Все это по выбору университета.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    в ИТМО точно можно!
    если будешь победителем - добро пожаловать на все факультеты
    2,3-ий диплом - ограничения на некоторые факультеты или допол. экзы
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
5дней...
Почему в четвертой задаче "Маршрутное такси" во вторых выходных файлах 1ый пассажир сидит на 10ом месте? Если по условию "Все места расположены в ряд и пронумерованы от 1 до n", а n во вторых входных файлах равняется пяти.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Там банальная ошибка)вместо 10-ки конечно же должна быть 5-ка)
    → Ответить