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

TopCoder SRM 622
Автор chrome, 10 лет назад, По-русски

Всем привет!

Завтра рано утром, в 05.00 MSK состоится Topcoder SRM 622.

Предлагаю после контеста обсудить здесь задачи.

GL & HF

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

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

Я один до сих пор чищу кеш Java перед каждым запуском арены? Это можно как-нибудь вылечить?

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

    Может быть и один, ибо я с такой проблемой в принципе не сталкивался. А что бывает если не почистить?

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

    Вот, у меня та же проблема.

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

    Создаем батник под названием arena.bat Пишем в нем: javaws http://www.topcoder.com/contest/arena/ContestAppletProd.jnlp

    Сохраняем и помещаем в папку Windows.

    Чтобы запустить нажимаем Win+R, пишем "arena", жмем Enter. И все больше проблем с ареной нет!

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

UPD: Уже все норм.

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

Интересно, увеличили ли стек для java.

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

Что-то сегодня в div2 маловато хаков было =(

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

    На мой вкус задачи были плохо подходящими для хаков — проходили довольно топорные решения, а там, где был потенциал для ошибок — авторы доброжелательно подбросили правильные тесты.

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

кто как решал 500?

написал дп: минимальное количество компонент на которые можно разбить поддерево вершины v так, чтобы макс высота от v была h. O(n * n * maxDist).

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

    Можно жадно взять минимум по компонентам, из всех таких — минимум по высоте, потому что в крайнем случае это все можно просто отрезать — ответ увеличится на 1 только

    → Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Увидел в своей комнате чувака, который по div2 250 написал решение с переполнением — искал первые 1000 чисел Фибоначчи. Естественно, я подумал, что это можно использовать. Вывел с таким же переполнением сгенеренные числа от 1 до 10^6. Там оказались только числа Фибоначчи и я чет приуныл :(

a[0] = a[1] = 1;
for (int i = 2; i <= 1000; ++i) {
    a[i] = a[i - 1] + a[i - 2];
    if (a[i] > 0 && a[i] < 1000000) cout << a[i] << " ";
}
→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Логично: шанс того, что "случайное" 64-битное число окажется в диапазоне от нуля до миллиона, равен 106 / 264, это мало.

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

      Но все-же 32-битное. Но я надеялся изо всех сил :)

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

        Да, тогда довольно точная оценка сверху на вероятность — 1000·106 / 232, это чуть меньше четверти. Действительно, тогда стоило проверить.

        → Ответить
»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Это правда, что я балда, и 900 так не решается, как я ее посубмитил? Если нет, почему все Java-кодеры не посубмитили это на 850? Вроде же BigInteger умеет делать xor, или я туплю?

P.S. Я бы и сам попробовал написать на Java. Но, к сожалению, когда я открыл задачу было 18 минут до конца. А Java-IDE у меня на ноуте не стоит, я подумал, что не успею поставить.

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

    Забыл приложить решение.

    vector<li> fs;
map<li, number> d;
number get(li rg){
    if(rg <= 0)
        return number();
    if(d.count(rg))
        return d[rg];
    number& ans = d[rg];

    int idx = sz(fs) - 1;
    while(fs[idx] > rg){
        idx--;
    }

    li F = fs[idx];
    ans = get(F - 1);

    if(((rg - F + 1) & 1) == 1)
        ans.change(idx);
    ans.xored(get(rg - F));
    return ans;
}

    Ответ — это (get(B).xored(get(A-1))).md(1e9 + 7).

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

      Да не, вроде решается. У нас один рекурсивный вызов всегда идёт вида Fk - 1, а для таких — сразу оба вида Fk - 1

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

        Да, я это понимаю. Но мой внутренний голос говорит: What's wrong with you, 900? Что-то не верится, что 900 так просто взялась и решилась, не думая.

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

          Возможно, авторы что-то другое имели ввиду. Иначе непонятно к чему ограничение 10^15.

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

      Именно так она и решается. Впрочем, у меня она упадет — map<INT,vi>, вместо map<ll,vi>. 5 утра бесследно не проходят...

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

        Не уверен, что упадет. Ты знаешь тест? Там же состояний около 100, какова вероятность, что они по модулю 2^32 будут одинаковы?

        → Ответить