SnarkNews TCM/SE #1 - Codeforces

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

Автор Egor, 14 лет назад, По-русски

Олег собирается запустить серию "СРМов" с новыми правилами подсчета штрафа.

Первый из них состоится 20 июля в 20:00 MSD

UPD: Олег просил всех интересующихся запостить правильные по вашему мнению коэффициенты - дробь n/m и V - стоимость задачи в закрытую

snarknews

Egor
14 лет назад
42

Комментарии (42)

Написать комментарий?

ballon

14 лет назад, # |

А как зарегистрироватся на контест?

→ Ответить

Egor	14 лет назад, # ^ \| +3 Видимо, надо либо иметь логин на SN, либо написать Олегу (адрес сейчас уже не помню, к сожалению) → Ответить

maslowmw

14 лет назад, # ^ |

Учавстовать может любой, кто зарегистрирован в системе?

→ Ответить

Egor	14 лет назад, # ^ \| 0 афаик да → Ответить

vsb	14 лет назад, # \| 0 А куда постить коэффициенты? Если сюда, то вот мое мнение: n/m = 1/10, V = 5 → Ответить

Egor	14 лет назад, # ^ \| 0 То есть задача втемную = 5 задач в светлую? о_О n/m = 1/10 не дает практически ничего - например, при такх n и m не отыгрываются 7 минут в третьем раунде между мной и Билецким - хотя я сдал стандартный набор, а он - самую сложную задачу → Ответить

vsb	14 лет назад, # ^ \| +3 там же "сданная "втёмную" задача стоит 1+1/V" То есть, 5 втемную = 6 в открытую. n/m, ну я же не говорю что они должны быть именно такими. Просто это мой голос, я так понимаю, что эта тема именно для сбора голосов и создана :) → Ответить

Egor	14 лет назад, # ^ \| 0 Туплю :) → Ответить

AndreySiunov

14 лет назад, # ^ |

Зато Petr вышел на второе место :)

→ Ответить

slycelote

14 лет назад, # |

Не очень понял формулу. Подставил туда n=m=1, судя по результатам продолжительность_контеста в секундах == 300 ??

→ Ответить

Egor	14 лет назад, # ^ \| 0 Это штраф в секундах тоже. У Олега весь штраф считается в секундах и только в самом конце округляется до минут → Ответить

slycelote

14 лет назад, # ^ |

Мне все-таки кажется, что есть бага: продолжительность контеста везде, кроме 3-го раунда, считается 300 минут.

→ Ответить

Egor	14 лет назад, # ^ \| 0 Это вполне возможно → Ответить

goo.gl_SsAhv

14 лет назад, # |

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

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

→ Ответить

Egor	14 лет назад, # ^ \| 0 Все вопросы к ~~Яндексу~~ Снарку → Ответить

Gassa

14 лет назад, # ^ |

Теперь там есть ссылка: http://158.250.33.215/~ejudge/team.cgi?contest_id=585. Время старта перенесено на 20:07.

→ Ответить

Arkadiy

14 лет назад, # |

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

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

→ Ответить

Egor	14 лет назад, # ^ \| 0 (21:25:49) Snark: похоже на investigation по C → Ответить

fetetriste

14 лет назад, # ^ |

Как падает-то? WA или TL?

→ Ответить

AlexSkidanov

14 лет назад, # ^ |

У меня по С TL8, решал считая полиномиальные хещи без модуля (доверяя переполнению), и проверяя на наличие с помощью хеш таблицы, в которой проверял чтобы совпадал полиномиальный хеш и первая буква.

→ Ответить

AlexSkidanov

14 лет назад, # ^ |

Гм... TL у меня потому что хеш таблицы не хватает, а если ее расширить, она не влазит в память :о
Присоединяюсь к вопросу - как решать С? :о)

→ Ответить

Arkadiy

14 лет назад, # ^ |

Ну счет преодоления ТЛ. Посчитав с переполнениями (доверяя модулую) массив хешей с 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];
}

}

→ Ответить

AlexSkidanov

14 лет назад, # ^ |

По условию мы можем дописать в конец любой кусок текста, а не только кусок с конца, правильно? То есть в каждый момент времени мне надо за О(1) встречался ли данный кусок текста уже в подстроке [0:i].

→ Ответить

Arkadiy

14 лет назад, # ^ |

Вопрос снят :) Я почему-то считал что только с конца выделять можно...Упс)

→ Ответить

Egor

14 лет назад, # ^ |

Вот мой код. Функция 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();

→ Ответить

vsb

14 лет назад, # ^ |

Удивительно, мне рассказали решение за O(n^2) с использованием КМП, я написал для начала решение, но вместо умного КМП использовал обычный string::find, и общая сложность должна была быть чуть ли ни O(n^4). Послал и получил ОК. не могу понять, почему так...

Кто может придумать контрпример или объяснить какая сложность этого решения?

http://vsb.pastebin.com/4htD77VG

→ Ответить

AlexSkidanov

14 лет назад, # |

Что все-таки мне не нравится в этих правилах, что 1*3 < 1.5*2 :о)
Получается что сдав одну в закрытую и три в открытую (и имея 4.5) я буду ниже тех, кто сдал три в открытую (4.5 as well). Думаю надо делать одну закрытую = 1.45 от открытой или типа того. То есть V=2.2(2) допустим.

→ Ответить

it4.kp

14 лет назад, # ^ |

А нахрена в открытую сдавать?

→ Ответить

AlexSkidanov

14 лет назад, # ^ |

Потому что у меня шанс сдать в чистую меньше чем 66%, а значит я ожидаемо получу больше баллов сдав в открытую.
Так как моя цель занять наиболее высокое местов среднем случае а не в лучшем (то есть высокий шанс на топ10 доминирует над низким шансом на топ3), мне выгоднее сдавать в открытую.

→ Ответить

it4.kp

14 лет назад, # ^ |

>у меня шанс сдать в чистую меньше чем 66%

да ладно... на ТК ведь явно больше процент. просто немного потестить
перед сдачей надо...

→ Ответить

AlexSkidanov

14 лет назад, # ^ |

Да, на ТЦ сдается лучше. Но на ТЦ во-первых три задачи а не шесть, и нет такой спешки, во-вторых там ~~всегда~~ обычно есть более менее случайный тест, который показывает, что решение не совсем левое :о)

→ Ответить

it4.kp

14 лет назад, # ^ |

Спешки и тут нет, не спеши да и все :) Это чисто вопрос поведения участника... Нужно спокойно решать, потестить немного и слать в закрытую.

→ Ответить

Egor	14 лет назад, # ^ \| +5 Снарк говорит, что на следующем контесте будет тестироваться V = 5 → Ответить

AlexSkidanov

14 лет назад, # ^ |

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

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

→ Ответить

AlexSkidanov

14 лет назад, # ^ |

* при отправке в открытую было бы пять

→ Ответить

Egor	14 лет назад, # ^ \| 0 С другой стороны, тот, кто сдаст А+Б в открытую будет иметь над тобой преимущество независимо от времени (при одинаковом количестве задач) → Ответить

Egor	14 лет назад, # ^ \| +1 в закрытую, конечно → Ответить

Arkadiy

14 лет назад, # |

WA 6. Проверка за O(1). TL тут вроде неоткуда взяться. Убил почти весь контест, пытясь шаманить с основаниями. Но больше фана я получил по Е :) Думаю переключусь. Написал Е. И получил тоже ВА 6 ) Но там я понимаю где набагал, не успел залатать просто.

→ Ответить

fetetriste

14 лет назад, # |

Ахаха, деревья эти второй день подряд никто не хочет писать

→ Ответить

ballon

14 лет назад, # |

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

→ Ответить

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