Блог пользователя anup.kalbalia

Invitation to the September Cook-off on CodeChef
Автор anup.kalbalia, 13 лет назад, По-английски

CodeChef invites you to participate in the September CookOff along with the ACM ICPC Amritapuri warm up contest at http://www.codechef.com/COOK14.

Time: 2130 hrs 18th September 2011 to 0000 hrs 19th September 2011 (Indian Standard Time - +5:30 GMT)
Details: http://www.codechef.com/COOK14/
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: David Stolp (aka pieguy)

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.

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

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

I have account on site, but I cant find button to register to contest. Where is it?

CodeChef userid == Account on site?

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Where are the problems?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
will be editorials?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Yes they will be put up on the site immediately after the contest. The editorials are up here: http://www.codechef.com/wiki/september-cookoff%C2%A0contest-problem-editorials

    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
С какой асимптотикой заходили решения в задаче про матожидание? Неужели это очередная задача, в которой надо пихать решение с правильной асимптотикой? Codechef славится таким говном.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    У меня так и не получилось запихнуть за 2^n * n (хотя на 30 макстестах у меня локально работало <2 секунд), поэтому пришлось предпросчитать все ответы для n=18 (к счастью, вероятности даны в процентах).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится -23 Проголосовать: не нравится
      Спасибо, Илья. Я так и знал.
      КГ/АМ. Пошли в жопу они со своими дебильными задачами. Я сначала тоже хотел предпосчитать все ответы для 18, но на моем ведре это бы заняло час.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        А может хватит валить все свои фейлы на авторов? Вроде и авторы разные, а причина постоянно одна.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится -18 Проголосовать: не нравится
          Ты решал этот контест? Ты решал предыдущие контесты на этом же сайте? Если нет, то не намерен обсуждать дальше эти вопросы с человеком, даже имя которого мне не известно.
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится
          да он вроде не так часто валит....
          → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А расскажи, как избавиться от параметра количества шагов. С вероятностью понятно как от этого избавиться, но здесь мат ожидание просят.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Что за количество шагов? Динамика просто d[mask] - матожидание ответа, если осталась такая маска; перебираем ход и берём минимум из ответов (при фиксированном ходе мы либо остаёмся на месте с какой-то вероятностью, либо попадаем в какую-то меньшую маску). Или в чём вопрос?

        А предпросчёт - просто для всех пар (L, R), L<=R, S = 100 - L - R, n = 18 считаем ответ. В source limit это влезает, а для 17 и так всё быстро работает, т.к. в кеш их процессора влезает.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я думал, что неправильно делаю, нашел ошибку, спасибо.
          → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    У меня (2^n) * n зашло после того как заметил, что в маске вида XXX100YYYY  пытаться использовать YYY не надо  - добавил break 

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Хм, у меня такая отсечка время работы локально не изменила, поэтому я даже не стал пробовать сабмитить. Наверное, у них кеш процессора <мегабайта, поэтому на их сервере она дала какой-то эффект.
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Такое чувство, что неправильно выставили TL.  В конце еще попытался пропихнуть такую фишку: если в маске оставшихся мишеней нету двух первых и последней, то она на самом деле равносильна такой же, сдвинутой на 1 влево. По времени стало укладываться, но почему-то WA...
    → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Там есть хороший хак, которые вполне возможно дает асимптотическую оптимизацию.

    Если в маске есть два нуля подряд, то можно разбить ее на две независимые и просто сложить ответы для них. Масок, где нет двух нулей подряд совсем мало. Fibonacci[20]=6765. То есть реально вычислятся будет только для них. Но почему-то у меня стало только в три раза быстрее работать после этого хака.

    Но может все это и неправильно, так как я так и не сдал.

    UPD. Странно, в раборе именно все так и описано. Почему-же тогда не прошло.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Правильно - я так сдал )  Хотя 6765 выглядит подозрительно мало
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Проверил, для 15123 запускается обычное вычисление и для 52764 вычисление с разбиением. Да, где-то я соврал.
        → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я делал похоже, но с тремя нулями и оставлял один из них в каждой из частей. Но такое давало ВА.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите, пожалуйста, как решать задачу Last Digit Sum.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Рассмотрим числа вида: X * 10 + d, где 0 <= d < 10, то D(X * 10 + d) = (D(X) + D(d)) % 10
    Если пробежаться по d от 0 до 10, то мы получим 10 разных остатков в каком-то порядке, тогда для X%10 == 0, можно посчитать сумму всех D для чисел от 0 до X - 1 за O(1) : (X / 10) * (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9), а если X % 10 != 0, то можно несколько значений просчитать в лоб.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Заметим, что для любого а на отрезке от [a*10; (a+1)*10-1] ответ всегда равен 45. После этого задача решается очень просто.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Выше есть два простых решения. Можно было еще написать динамику по длине числа, остатку и тому, превысили мы уже префикс или нет. И таким образом строить число, начиная с первой цифры. Такое решение, конечно, не самое простое, зато более универсальное.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, но и набажить в нем проще. Я неправильно посчитал максимальное значение суммы, которое может потребоваться и получил много бревен. Наибольшую сумму имеет число 288888888, и я еле как с пятой или шестой попытки смог посчитать количество восьмерок в нем.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        А зачем нам значение суммы? Нам достаточно помнить ее остаток от деления на 10.
        → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      так же делал, только не догадался добавить третий параметр, считал динамику для чисел длины <= len(x) - 1, где len(x) = "длина" нашего числа, а потом еще муздохался с остальной частью, от 10^(len(x) - 1) до x, в итоге не сдал(( теперь хоть буду знать как такого рода задачи решаются)

      кст, можно ваше решение увидеть?

      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно ещё сделать так:

    Препросчитаем для каждого отрезка длинной 100к ответ (локально, но впринципе в итоге можно и без этого). Дальше сделаем такую фишку. Для числе от 0 до 100к посчитаем сколько чисел x не больше данного имеют какой D(x) (т.е. для каждого числа храним 10 значений). Дальше будем делать следующим образом: введем функци F(x) - сумма всех  D чисел не превосходящих x. Тогда ответ F(b) - F(a - 1). Теперь научимся считать F(x).

    Разобьем наш интервал [0, x] на 2 части (до ближайшего числа кратного 100к). Часть до кратного 100к - посчитаем из препросчитаного (хотя как я сказал, это в итоге можно будет не делать скорее всего (вплане в ТЛ войти должно)). А потом разобьем оставшиеся числа на 2 части - остаток от деления на 100к и целая часть от деления на 100к. Заметим, что целая - часть у всех общая. А тогда сколько чисел имеют какой остаток можно легко посчитать пользуюся нашим препросчитанным массивом длинны 100к (ибо у числа D(x) = (D(целая часть) + D(остаток)) mod 10).

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

      У меня такой хак не прокатил :D

      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        В хаке основное это по что остаток отрезка длинной от 0 до 100к за О(1). Иначе он не катит. =)
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          У меня и это ТЛилось. Но потом я заглянул в результаты предподсчета и был немало обрадован.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Кстати да... Дальше верхняя часть тоже до 100к и её разложение можно использовать (вплане я использовал).

            Время испольнения - 0.05 сек. Возможно у вас что-то не так (могу дать код).

            → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Последние пол часа пихал за 2^n*n.. Неужели нельзя сдать так..
Если бы не это, вполне контест можно было бы назвать "нормальным".
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Не хочу показаться расистом, но у индусов какая-то страсть давать мультитест там, где он точно не нужен. Задача реально решается за 5 минут безыдейной динамикой и все, что требуется от участников - придумать, как запихать эту динамику в идиотски выставленный TL. И, судя по 6 секундам TL, авторы ничего лучше нам не предложат.
    → Ответить