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

The March Cook-off on www.CodeChef.com
Автор Anton_Lunyov, 14 лет назад, перевод, По-русски
Приглашаю всех поучаствовать в мартовском коротком контесте на CodeChef.
Контест продлится 2,5 часа. Начало в воскресенье 20 марта в 19:00 по московскому времени.
В этот раз автором задач буду я. Это уже мой второй контест на CodeChef.
В прошлый я был автором два месяца назад в январе.
Контест будет состоять из 5 задач различного уровня сложности.
Первые 10 участников не из Индии получат призы от организаторов.

UPD. Для участвия в контесте необходимо просто зарегистрироваться на сайте и ждать начала :).
  • Проголосовать: нравится
  • +88
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится
Знаете ли вы что...
Гена участвовал в 4-х из 7-ми коротких контестов на CodeChef и все их выиграл.
А именно, 1-й, 3-й, 6-й и 7-й.

Пример ссылки http://www.codechef.com/rankings/COOK07,
меняя номер попадете на результаты другого контеста.

P.S. Пишу это только чтобы пост висел в прямом эфире.
Будет очень не хорошо, если он оттуда уйдет.
Анонсы должны быть в прямом эфире даже если их не комментируют.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    В это время Гена как раз будет ехать на республиканскую олимпиаду по информатике, так что есть вакантное первое место =)))
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      республиканская в Беларуси - это всебелорусская или региональная/областная? :)
      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      В любом случае удачи Гене на республиканской олимпиаде!
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    есть более простой способ поднять статью вверх прямого эфира: открываем "редактировать статью" и жмём "сохранить изменения"

    не пользовался, но должно работать =)
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Я об этом думал. Но боюсь, что тот кто уже видел этот пост, может не понять, в чем прикол и минусануть чего доброго.
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Во сколько контест начинается по Киевскому времени ?
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Надо организаторов "уговаривать" на призы для топ20 или топ30; уровень соревнований с каждым месяцем поднимается, а призов больше не становится. Было ведь вначале для топ20...


→ Ответить
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Жаль, что пересекается с Unknown Language Round #2
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    ой, по мне так жаль что "Unknown Language Round #2" пересекается с кодчефом)))))
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я зарегистрировался на CodeChef, но никак не могу найти кнопку регистрации на контест. Она там вообще есть? (Всмысле нужна ли отдельная регистрация на сам контест?)
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Антон, нервничаешь волнуешься или для тебя это уже привычное дело?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Не то что бы привычное. Но почти не волнуюсь. Я больше волнуюсь перед обычными контестами, особенно если по его результатам где-то там можно упасть в рейтинге.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Какая любопытная черепашка =)))
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
А сколько обычно задач на Codechef?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    " Контест будет состоять из 5 задач различного уровня сложности. "
    цитата из текста поста.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всем удачи! 10 мин до начала.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А в контест как вообще можно зайти? С главной страницы?
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
http://www.codechef.com/COOK08/
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А ввод вывод какой?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не могу никак найти как посмотреть ранклист? киньте кто нибудь ссылку плиз)
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
http://www.codechef.com/rankings/COOK08
Но обновляется он довольно редко.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за контест, хоть и написал не очень. Интересно как решать палиндромы и математическую задачу.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Скоро выложат разбор (на английском).
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Присоединяюсь, отличный контест) 
    Тоже хочется знать как решать палиндромы и математическую задачу, а также почему перебор в задаче про поваров проходит?
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Ну наверное потому-что если ты заходишь в некое состояние, то ты обязательного его добавишь в ответ(если в нужном порядке все делать).
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ах да точно, если захожу добавляю. Блин я идиот( 
        → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Гер ну это как бы не перебор, т.е. это перебор за асимптотику О(ответ * (чё-то там))
      → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мне тоже понравился. Хорошие задачи. +1 автору
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за контест. Понравились задачи Grouping Chefs и Palindrome Palindrome.
А как надо решать задачу Exponential Commutativity?
Есть идея представлить n и m в виде g^a, g^b и получить что-то вроде b^(-1) g^b = a^(-1) g^a (mod p). Но дальше пока не додумал.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А расскажи как задачу про палиндромы решать, я правильно понимаю ты же её решил?
    → Ответить
    • 14 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится
      Да, сдал.
      Делал так, сначала для каждой позиции i (0..n - 2) посчитаем максимальный палиндром четной длины, серединой которого являются i и i + 1. Пусть p[i] длина палиндрома.
      Красивые подстроки будут находится в позициях где p[i] >= 2.
      Теперь рассмотрим все такие позиции, где p[i] >= 2. Чтобы узнать сколько красивых подстрок имею середину i, i + 1 надо посчитать количество таких палиндромов:
      1) середины которые лежат в интервале i - p[i]/2..i-1
      2) заканчиваются не раньше i (т.е. i + p[i] >= i)
      Это можно сделать фенвиком сначала во все i, где p[i] > 0 поставить 1, а затем в некоторые ставить 0 (когда доходим до какой-то позиции j == i + p[i])

      Палиндромы находил хэшами и бинпоиском.
      Ассимптотика: O(n * log(n)) получилась.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        я так быстро сообразить не смог, целый час ковырял её, и только под конец написал и фенвика, и кучу, уже даже тестить начал, но...

        кстатит палиндромы находятся проще (за линию в пару строк) - на е-максе уже давным давно лежит.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          Ну как за линию находить я знал, но надо было вспоминать, поэтому решил хэшами - там думать не нужно =). К тому же все равно итоговая ассимптотика O(n * log(n)) получается.

          → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Спасибо всё, понятно =) 
        → Ответить
      • 14 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Дорешать можно будет?
        UPD. Не сюда.
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        у меня тоже O(n * log(n)) но TL. Решение приинципе такое же, только юзал дерево отрезков и еще для того чтобы ставить 0 я сортил концы максимальных палиндромов)
        → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хорош контест, прям баланс к сегодняшнему опенкапу))))
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Разбор
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Антон, задача Exponential  Commutativity очеееень крутая задача. Сегодня с утра разобрался с ней, действительно прекрасная задача на теорию чисел. =) Не знаешь, можно ли где-нибудь еще порешать подобные математические задачи (возможно твоего авторства =) )?  
 
→ Ответить