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

Автор nikalosaberidze, 12 лет назад, По-английски

Tomorrow is Code Jam's first round. Code Jam. I hope that will be good problems and two hours and thirty minutes will be enough to solve problems :))) Goodluck everybody :)))

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

»
12 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Is number of the participants too much?

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

я делаю ап и напоминаю тем кто забыл (как и я), что раунд состоится сегодня (27.04) в 5.00 по москве

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

    ты только что поделил мои шансы на футболку на два =(

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

      Футболки разыгрываются в Round 2

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Туда тоже пройти нужно

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +27 Проголосовать: не нравится

          Туда вроде легко

          не пройду, будете здесь надо мной смеяться

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What is the solution for C-large?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B-large жадиной решается? если да, то какой?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Пусть next[i] — номер первого элемента справа, который больше a[i], CUR — текущая энергия, тогда нам выгодно чтобы в момент, когда мы придем в next[i] там было Е энергии. То есть сейчас нам нужно потратить такой Х энергии, что R*(i-next[i])+CUR-X=E.

    Будет хорошо, если это по-человечески кто-то докажет :)

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

      Мне кажется, тот путь, которым можно прийти к решению и есть доказательство?

      Логично, что если мы вкладываем энергию в максимальный элемент v[i], то это больше любого другого варианта увеличивает сумму. Тогда если для текущего элемента M есть нерассмотренный элемент R с большей величиной v[R], то энергию выгоднее вложить в него. Значит выгодно сохранить энергию для него, а в текущий вложить столько энергии, сколько пропадет сколько пропадет впустую при переходе в R с нулевым вкладом энергии во все промежуточные элементы M + 1..R - 1. Энергию выгодно вкладывать в текущий элемент, а в не в какой-нибудь из элементов M + 1..R - 1, потому что R — первый элемент, больший чем M, значит все промежуточные элементы меньше M.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Я решал (не успел сдать) чуть другой жадиной (квадратичной в худшем случае)

    Заведем функцию solve(int l, int r, startEnergy, finishEnergy), тогда нам надо найти solve(0,n,e,0). Найдем в массиве максимум(пусть индекс i), максимизируем то, с чего начинаем, минимизируем то, чем закнчиваем. start = min(e, startE + (i -l) * R), finish = max(0, finishEnergy + (r - i) * R). Запускаем на двух отрезках, слева и справа то же самое с соответствующими границами start/end.

    Код думаю понятнее объяснения

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to approach B large.I wasn't getting any intuition from the problem description.Trying out few test cases did gave some pointers but that was not enough to solve it in time.

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

    Suppose we had v1, ..., vn and we were standing at the beginning, that is v1.

    If v2 > v1, then spending more than R in v1 would be wrong right? And at least we should spend R (remember R ≤ E), because we will recover it anyway before getting to v2. This happens because we would rather (greedily) spend energy in v2 than in v1, and spend the "excess" (due to the fact that energy never exceeds E) in v1.

    Now, suppose v2 < v1, but v3 > v1, then again, spending more than 2R = (3 - 1)R would be wrong, so we spend 2R (actually min{2R, remainingenergy}, because we can recover the full E by the time we get to v3) in v1, and move on to v2.

    Try to complete the idea ;P

»
12 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Кто-нибудь знает какие есть хитрые баги в B-large? У меня она упала на контесте, но сейчас тот же самый код зашел в дорешивании. Решение — стандартное жадное.