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

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

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

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

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

P.S. Пишу это только чтобы пост висел в прямом эфире.
Будет очень не хорошо, если он оттуда уйдет.
Анонсы должны быть в прямом эфире даже если их не комментируют.
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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


→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
Жаль, что пересекается с Unknown Language Round #2
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Я зарегистрировался на CodeChef, но никак не могу найти кнопку регистрации на контест. Она там вообще есть? (Всмысле нужна ли отдельная регистрация на сам контест?)
→ Ответить
16 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
Антон, нервничаешь волнуешься или для тебя это уже привычное дело?
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится
А сколько обычно задач на Codechef?
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Всем удачи! 10 мин до начала.
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А в контест как вообще можно зайти? С главной страницы?
→ Ответить
16 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится
http://www.codechef.com/COOK08/
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А ввод вывод какой?
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Не могу никак найти как посмотреть ранклист? киньте кто нибудь ссылку плиз)
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится
http://www.codechef.com/rankings/COOK08
Но обновляется он довольно редко.
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за контест, хоть и написал не очень. Интересно как решать палиндромы и математическую задачу.
→ Ответить
16 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за контест. Понравились задачи Grouping Chefs и Palindrome Palindrome.
А как надо решать задачу Exponential Commutativity?
Есть идея представлить n и m в виде g^a, g^b и получить что-то вроде b^(-1) g^b = a^(-1) g^a (mod p). Но дальше пока не додумал.
→ Ответить
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    А расскажи как задачу про палиндромы решать, я правильно понимаю ты же её решил?
    → Ответить
    • 16 лет назад, скрыть # ^ |
      ← 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)) получилась.
      → Ответить
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        я так быстро сообразить не смог, целый час ковырял её, и только под конец написал и фенвика, и кучу, уже даже тестить начал, но...

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

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