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

Полуфинал ВКОШП(Интернет тур, СПб, Ижевск, Грузия, Казахстан, Узбекистан)
Автор imslavko, 13 лет назад, По-русски

Кто может поделиться решением задач F и H?

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

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

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

спойлер

→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    ответ

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

    ответ.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Мы попробовали все возможные эпсилоны от 1e-2 до 1e-9.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Давайте, перейдем в личные сообщения, чтобы не спойлирить лишний раз.
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Интернет тур был сегодня. Завтра просто онлайн трансляция, которую можно написать как тренировку.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Паша абсолютно прав.
      Интернет-олимпиады являются тренировочным соревнованием, особенно трансляции. Для команд, которые завтра хотят потренироваться, в их же интересах не смотреть заранее результаты и тем более разбор. Хотя ожидаемо, что завтра могут быть читеры (но непонятна их выгода).
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
В F написал ДП по параметрам (x,y,l,k) - координаты края квадрата, длина стороны и сколько клеток можно изменить. Если посчитать то состояний не много.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я насчитал 2200 * 1600 состояний, так сколько их на самом деле?
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Мне кажется, более приятна следующая рекурсия:

    Пусть мы имеем некоторый квадрат со стороной n. Разобьем его на четыре маленьких и рекурсивно посчитаем для каждого, какого размера мы можем достичь за каждое число изменений. Получается четыре вектора размера O(n2 / 8). Сформировать ответ для исходного квадрата несложно - просто поочередно "слить" вектора за O(3n4 / 64). Итого T(n) = 4T(n / 4) + O(3n4 / 64), что я поленился раскрыть.
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    возможно не в тему, но хотел у спросить, Александрия (ну или хотя бы ваша ЛИТ)  поедет на финал? а то по предыдущим годам сложилась традиция: Украинцы проходят отбор, потом не едут и таким образом не дают места в финале другим участникам...

    P.S. забыл про лс

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Думаю логично что большинство команд с Украины не ездят, не дешево.
      По поводу нашего участия в этом году, пока-что ничего сказать не могу.
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Если-бы на 100% были-бы уверены что не поедем то не участвовали-бы.
          Кстати отвечать за всех не могу , мы писали отбор первый раз.
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Парень, релаксуй, с нами связывались организаторы по этому вопросу. Если мы не поедем, то места не пропадут. 
          → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
 А как решать E, я понял что там будет максимум всего 200 P( потому что выгоднее выбирать с меньшей стоимостью катридж, который рассчитан на P страниц), как дальше от этого плясать? 
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Строгого доказательства я не знаю, но у нас зашло следующее:
    Считаем честно до 100000 динамикой, а потом добиваем до нужного числа, чем-то "вкусным" =) 

    Вкуснота считается по формуле: стоимость/кол-во страниц. 
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      мы считали вообще до 10000, хватает
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      кст, Вань, а че у вас 10 задач? или у Перми свой набор задач?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        у нас были 9 задач как и у всех
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          а точно, не туда посмотрел, а где пермский монитор можно посмотреть?
          → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а можно ли поподробнее про то, как добирать до нужного числа после подсчёта динамикой?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        самым выгодным вариантом, то есть с максимальным отношением стоимость/кол-во страниц
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Пусть "самый лучший" картридж имеет номер opt. Тогда существует оптимальное решение, в котором количество картриджей, отличных от самого лучшего, не больше popt. Действительно, пусть pi - вместимость картриджей, покупка которых оптимальна. Если их как минимум popt, то найдется подмножество, сумма которого делится на popt (общеизвестный факт), а его можно заменить на несколько popt.
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а мы, видимо, пихнули что-то типа meet-in-the-middle
    → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

Забавно, что результат победителей в Санкт-Петербурге и Гомеле абсолютно совпадает.
Правда, на самом деле, у всех гомельских участников надо от времени отнять количество_решенных_задач*60.
Какие-то были проблемы в связи с не переходом на зимнее время.

→ Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
А где писали отбор Московские команды?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А когда будут известны результаты, т.е. кто прошёл на финальный раунд, а кто нет?
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

уже доступны разборы:

http://neerc.ifmo.ru/school/archive/2011-2012/ru-olymp-team-spb-2011-analysis.rar

тетсы:

http://neerc.ifmo.ru/school/archive/2011-2012/ru-olymp-team-spb-2011-archive.rar

и окончательные результаты СПб:

http://neerc.ifmo.ru/school/archive/2011-2012/ru-olymp-team-spb-2011-standings.html

→ Ответить
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
http://neerc.ifmo.ru/school/spb/standings-spb.html - посмотрите на last success, а затем на общий результат этой команды. Думаю, ребята были счастливы =)
→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

По результатам интернет-отбора на финальный тур приглашаются 14 лучших команд.

Команды, приглашенные на ВКОШП :

http://neerc.ifmo.ru/school/russia-team/listTeamsFinal.jsp

→ Ответить