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

SnarkNews TCM/SE #1
Автор Egor, 14 лет назад, По-русски
Олег собирается запустить серию "СРМов" с новыми правилами подсчета штрафа.
Первый из них состоится 20 июля в 20:00 MSD
UPD: Олег просил всех интересующихся запостить правильные по вашему мнению коэффициенты - дробь n/m и V - стоимость задачи в закрытую
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
А как зарегистрироватся на контест?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Видимо, надо либо иметь логин на SN, либо написать Олегу (адрес сейчас уже не помню, к сожалению)
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А куда постить коэффициенты?
Если сюда, то вот мое мнение: n/m = 1/10, V = 5
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    То есть задача втемную = 5 задач в светлую? о_О
    n/m = 1/10 не дает практически ничего - например, при такх n и m не отыгрываются 7 минут в третьем раунде между мной и Билецким - хотя я сдал стандартный набор, а он - самую сложную задачу
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      там же "сданная "втёмную" задача стоит 1+1/V"
      То есть, 5 втемную = 6 в открытую.

      n/m, ну я же не говорю что они должны быть именно такими. Просто это мой голос, я так понимаю, что эта тема именно для сбора голосов и создана :)
      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Зато Petr вышел на второе место :)
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не очень понял формулу. Подставил туда n=m=1, судя по результатам продолжительность_контеста в секундах == 300 ??
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это штраф в секундах тоже. У Олега весь штраф считается в секундах и только в самом конце округляется до минут
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Мне все-таки кажется, что есть бага: продолжительность контеста везде, кроме 3-го раунда, считается 300 минут.
      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А где ссылка на сам контест ?

нигде её там не нашёл, там про Yandex Open только.

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

Как решать задачу С? Мое решение за N^2 падает на 6 тесте.

Вроде как стандартная динамика. Либо пришли из предыдущей клетки, либо копированием куска.Проверка на то, мог ли быть кусок с позиции j по текущую получен проверяю хешом. Более того, я перепробовал пару-тройку осонований. И проверял совпадение одновременно сразу по двум хещам. Но это все равно не помогает.

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    (21:25:49) Snark: похоже на investigation по C
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Как падает-то? WA или TL?
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня по С TL8, решал считая полиномиальные хещи без модуля (доверяя переполнению), и проверяя на наличие с помощью хеш таблицы, в которой проверял чтобы совпадал полиномиальный хеш и первая буква.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Гм... TL у меня потому что хеш таблицы не хватает, а если ее расширить, она не влазит в память :о
      Присоединяюсь к вопросу - как решать С? :о)
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ну счет преодоления ТЛ. Посчитав с переполнениями (доверяя модулую) массив хешей с 1 по i-ый мы автоматически умеем вычислять хеш с любого j по k (j<k). Ну то есть зачем нам хеш-таблица - не очень понимаю.

        for (i=1;i<n;i++)

        {

        for (j=i-1;j>=0;j--)
        {

        int len = i-j+1;

        if (j-ln>=0)
        {

         unsigned long long h1 = get_hash(j,len);

         unsigned long long h2 = get_hash(j-len,len);

        //get_hash возвращает хеш с позиции j длиной len за О(1).
        }

        }

        unsigned long long get_hash(int pos, int len)
        {
         if (pos==0)
          return h[len-1];
         else return h[pos+len-1] - h[pos-1]*deg[len];
        }


        }

        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          По условию мы можем дописать в конец любой кусок текста, а не только кусок с конца, правильно? То есть в каждый момент времени мне надо за О(1) встречался ли данный кусок текста уже в подстроке [0:i].
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Вопрос снят :) Я почему-то считал что только с конца выделять можно...Упс)
            → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Вот мой код. Функция zFunction считает z фунцкию начиная с позиции оффсет (однако в массив z  пишет с 0):
        int n = s.length;
        int[] z = new int[n];
        int[] p = new int[n];
        zFunction(s, z, 0);
        for (int i = 1; i < n; i++) {
        p[i] = 0;
        z[i] = Math.min(z[i], i);
        }
        List<String> ans = new ArrayList<String>();
        ans.add("T");
        int pos = 1;
        int[] zz = new int[n];
        for (int i = 1; i < n; i++) {
        zFunction(s, zz, i);
        for (int j = i + 1; j < n; j++) {
        int cur = Math.min(zz[j - i], j - i);
        if (cur > z[j]) {
        z[j] = cur;
        p[j] = i;
        }
        }
        if (pos == i) {
        if (z[i] == 0) {
        ans.add("T");
        pos++;
        } else {
        ans.add("C " + (p[i] + 1) + " " + (p[i] + z[i]));
        pos += z[i];
        }
        }
        }
        out.println(ans.size());
        for (String ss : ans)
        out.println(ss);
        out.close();

        → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Удивительно, мне рассказали решение за O(n^2) с использованием КМП, я написал для начала решение, но вместо умного КМП использовал обычный string::find, и общая сложность должна была быть чуть ли ни O(n^4). Послал и получил ОК. не могу понять, почему так... 
    Кто может придумать контрпример или объяснить какая сложность этого решения?
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что все-таки мне не нравится в этих правилах, что 1*3 < 1.5*2 :о)
Получается что сдав одну в закрытую и три в открытую (и имея 4.5) я буду ниже тех, кто сдал три в открытую (4.5 as well). Думаю надо делать одну закрытую = 1.45 от открытой или типа того. То есть V=2.2(2) допустим.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А нахрена в открытую сдавать?
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Потому что у меня шанс сдать в чистую меньше чем 66%, а значит я ожидаемо получу больше баллов сдав в открытую.
      Так как моя цель занять наиболее высокое местов среднем случае а не в лучшем (то есть высокий шанс на топ10 доминирует над низким шансом на топ3), мне выгоднее сдавать в открытую.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        >у меня шанс сдать в чистую меньше чем 66%

        да ладно... на ТК ведь явно больше процент. просто немного потестить
        перед сдачей надо...
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, на ТЦ сдается лучше. Но на ТЦ во-первых три задачи а не шесть, и нет такой спешки, во-вторых там всегда обычно есть более менее случайный тест, который показывает, что решение не совсем левое :о)
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Спешки и тут нет, не спеши да и все :) Это чисто вопрос поведения участника... Нужно спокойно решать, потестить немного и слать в закрытую.
            → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Снарк говорит, что на следующем контесте будет тестироваться V = 5
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну с V=5 я даже A+B буду посылать в открытую :о)
      Шесть задач обычно не сдается, а при сданных пяти падение одной в принципе сводит на нет весь смысл от отправки в закрытую :о) Потому что получится 4.8, а при отправке в закрытую было бы 5.

      Anyway, посмотрим :о) В принципе формат в любом случае лучше, чем ACM+, и вообще любой формат, где задача после контеста может упасть, интереснее (потому что интрига до конца), поэтому развитие в эту сторону (TCM и альфараунды здесь) я считаю правильным :о)

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        * при отправке в открытую было бы пять
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        С другой стороны, тот, кто сдаст А+Б в открытую будет иметь над тобой преимущество независимо от времени (при одинаковом количестве задач)
        → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
WA 6. Проверка за O(1). TL тут вроде неоткуда взяться. Убил почти весь контест, пытясь шаманить с основаниями. Но больше фана я получил по Е :)  Думаю переключусь. Написал Е. И получил тоже ВА 6 ) Но там я понимаю где набагал, не успел залатать просто.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ахаха, деревья эти второй день подряд никто не хочет писать
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

а как решать Е ?
я решал так : res=0; for(i=1;i<=n;i++)if(i==1 || x[i]>x[i-1])res++; где res-ответ....ВА 6...:(
никак не могу понять почему ВА )))

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Ну вот ровно так не проходит для теста 1 - у тебя выдаст 0
    Если же res инициализируется 1, то не проходит для теста 3 4 1 2 - у тебя выдаст 3, а они могут за 2 рассеться
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
да, действительно неверно....!) спасибо за тесты :)
→ Ответить