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

CodeChef August Cook-off 2011
Автор LGM, 13 лет назад, По-английски

Here are some details of this CodeChef Cook-Off:

Date : Sunday, 21st August, 2011
Time : 9:30pm to 12:00 am (Indian Standard Time)
Problems : 5 problems
Problem Setter : Anil Kishore and Harsha S
Contest Link : http://www.codechef.com/COOK13/

Good Luck to All!

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
hope a good contest!
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I don't understand. How can it be 9:30 pm to 12:00 am? What is 12:00 am? There is no time "12:00 am" in pm/am format.

To Russian users:
Правильно ли я понимаю, что это сегодня 20:00 - 22:30 по Москве?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
If I want to participate first time, i must just register on site and wait beginning of contest?!
Or i must register to contest also, like i topcoder and codeforces?!
and difficulty of problems are like in codeforces or more difficult?!
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hope it won't again be a math hell like previous :-|
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как делать Angree Chef для K<SQRT(N) ?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А причём там sqrt? Просто считаем для каждой позиции i индекс j = f(i), такой, что ai = aj и чисел, равных ai, между ними ровно k. А потом обрабатываем запросы офлайн (сортируя по правому концу), считая ответ деревом интервалов  (в каждый момент tree[i] = количество уже пройденных j, таких, что f(j) = i, тогда ответ на запрос с левым концом l - сумма tree[l] + tree[l + 1] + ...).

    Upd. Конечно же, если пройдено j, j', такие, что aj = aj', то в дереве интервалов считаем только самый последний.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо.
      Просто сразу в голову залезло корневое решение, и + еще для больших К работает, то вот я подумал, что существует и для маленьких тоже.
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Корневое решение: Будем обходить отрезки в особом порядке и будем поддерживать для каждого номера деревни сколько таких на текущем отрезке, а также ответ для текущего отрезка . Понятно как все это дело обновлять при переходе от одного отрезка (x1,y1) до другого (x2,y2) за O(|x1-x2|+|y1-y2}). Отрезок (x,y) можно считать точкой (x,y) на поле NxN и нужно так обойти эти точки чтоб суммарное расстояние было O(N^1.5). Для этого разобъем поле NxN на поле из квадратов sqrt(N) x sqrt(N). И обходить точки будем сперва перебираем кадраты sqrt(N) x sqrt(N) (построчно) и в каждом обходим точки которые попали в соотв квадрат (в любом порядке).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Прикольное решение. Интересно , а есть все-таки что-то, что разбивает К на две группы.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Насколько я знаю, за попадание в десятку можно получить футболку. Хотелось бы узнать так ли это, и если так, то что необходимо для этого сделать после занятия требуемого места.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

не туда
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто-нибудь пытался использовать BufferedReader в решениях на Java? В моем случае программы валились с исключением, при ловле - WA.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня когда-то были проблемы на этом сайте с ридером. Оказалось, его нельзя закрывать.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А кто нибудь сдавал задачу про строку через хэши (а то у меня TL)?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, с огромным трудом сдал. Сначала решение локально работало где-то 0.650с на рандомном тесте. После нескольких улучшений довел до 0.550с. Прошло. Вообще факт ТЛ весьма забавный - решение линейное, константа вроде бы не очень большая.

    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, у меня с первого раза зашло, вообще никаких проблем не было. Там же в худшем случае всего 500000 сложений/умножений int64, которые в отличие от взятий по модулю быстрые.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      У меня тоже взятий по модулю не было, но почему то все время TL я даже пробовал запоминать какие сдвиги уже проверяли.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Эм, "какие сдвиги уже проверяли"? Видимо, мы с тобой по-разному делали. Я с самого начала посчитал все сдвиги, равные самой строке (сдвигая по одному символу), а потом уже безо всяких хешей считал ответ.
        → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я делал хеш на unsigned int и просто 2*n сдвигов проверял. Без проблем прошло. Зато ТЛ по треугольнику с решением O(500^3) для 5 секунд как то странно с такой сложностью ТЛ ловить
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Так там еще и группы тестов есть. Вроде-бы такое и не должно заходить.
          ПС. у них не очень быстрые компы, то что у меня вкладывалось в половину ТЛа, у них валилось.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            ну да, просто не додумался до квадратного решения нормального :) заметил про диагональ, придумал дп за куб и прикинул, что где то 500КК сложность в 5 сек обычно проходит :) видимо, на codechief лучше так не думать :)
            → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите пожалуйста, как решать задачу про треугольник, по которому ходят двое людей.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Все что выше диагонали с финишем доступно только первому человеку, все что ниже - только второму. При этом если один из них попадет на диагональ, дальше ему придется идти только по ней => нет смысла на диагональ приходить обоим. Рассматриваем два случая, кто будет на диагонали (возможно никого), для каждого из них - простое ДП.
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Решение в лоб.
    Для начала заметим, что по диагонали x + y = n - 1, при оптимальных путях, должен ходить только один (кроме финальной точки). Тогда для каждого из случаев: только первый может ходить по диагонали, только второй может ходить по диагонали - посчитаем динамически ответ для каждого по отдельности, сложим; в конце вычтем учтенное дважды нижнее левое поле. Найдем из двух вариантов максимальный.


    Интересно послушать решения поумнее.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Заметим что никто из игроков не может пересечь диагональ i + j = n + 1. Поэтому двигается игрок так - сперва идет строго выше диагонали i + j = n + 1, а по этой диагонали до финиша. Для каждой клетки на диагонали посчитаем сколько стоит до нее дойти так, что это первая 'диагональная' клетка на пути до нее. Для обоих игроков это можно посчитать за O(n^2) стандартной динамикой. Дальше перебираем когда впервые зашел на диагональ первый игрок и когда второй - всего O(n^2) вариантов и ответ для каждого варианта считаем за O(1).
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не обязательно перебирать все O(n^2) вариантов, когда кто зайдет на диагональ. Достаточно O(n) вариантов - "когда первый зайдет" или "когда второй зайдет". А тот, кто не заходит всегда будет финишировать в соседней по стороне клетке с финишем.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну да, но в таком решении надо было чуть больше подумать), а сложность и так O(n^2).
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Проходило ли по задаче про треугольник такое решение? Написал его за полчаса до конца на Java и получил Runtime. Только сейчас узнал, что из-за неправильного обращения с Reader-ом. Оптимайзил, чтобы влезть в Memory Limit.

Решение. Найдем ответ для первого чувака, восстановим оптимальный путь из (n, 0) в (0, 0) и пометим те клетки, которые есть в этом пути, нулями. Дальше такой же динамикой найдем ответ для второго чувака, прибавим к первому и выведем.

Правильно ли это?
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Должно пройти, если посчитать то же самое еще раз, только поменяв очередность - сначала для второго, обнулить посещенные, посчитать для первого.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Судя по времени, прошло дальше, но все равно Wrong Answer.
      http://pastie.org/2407953

      Попробую написать решение, которое обсуждали выше.
      → Ответить