У меня одного в дорешке ВТОРОГО тура KPI-Open-2014 пропала кнопка "submit"? Если же всё совсем плохо -- знает кто-нибудь, куда можно послать задачу второго тура H "Шеренга"?

Спасибо.

Всем привет!

Взялся тут выучить декартово дерево, встал вопрос реализации. Кто как пишет? Емакс читал, но реализация оттуда не понравилась -- не очень люблю на олимпиадах использовать указатели. Да и рекурсия это не очень круто, наверное.

В общем, обладателей хорошей быстрой простой красивой реализации всяких разных декартовых деревьев и операций на них -- прошу поделиться мастерством.

Большое спасибо.

Хочется каких-то вариаций тренировки и развлечения ради. Horrible решал. Заранее спасибо.

Привет.

На емаксе лежит вот такая реализация алгоритма поиска мостов:

void dfs (int v, int p = -1) {
	used[v] = true;
	tin[v] = fup[v] = timer++;
	for (size_t i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (to == p)  continue;
		if (used[to])
			fup[v] = min (fup[v], tin[to]);
		else {
			dfs (to, v);
			fup[v] = min (fup[v], fup[to]);
			if (fup[to] > tin[v])
				IS_BRIDGE(v,to);
		}
	}
}

Вопрос: а что если, когда попытаемся пройти по обратному ребру, в строчке 8 мы обновим fup[v] следующим образом:

fup[v] = min (fup[v], fup[to])    ?

Вроде интуитивно понятно, что все смежные вершины to могли еще быть не посещены поиском в глубину и fup[to] будет не готов, но всё же. Какой тест завалит реализацию с таким единственным изменением? Пробовал погонять на своих тестах -- вроде отрабатывает.

Спасибо.

Собственно, вот ссылка на задачу: http://acm.timus.ru/problem.aspx?space=1&num=1579

Решал жадно -- для каждой шубы найдем первую подходящую и возьмем её.

Придумывается как-то интуитивно, но хотелось бы понять, почему оно работает.

Спасибо.

Hi everyone!

A while ago I've decided to learn Aho-Corasick algorithm and found the following problem at spoj.com:

• Input to the program consists of a series of lines. The first line contains the string M (no more than 100000 characters long). The next line contains an integer N (<1000) the number of query strings. Each of the next N lines contain a string S (each of which is no more than 2000 characters long). Output should consist of N lines each with a character 'Y'/'N' indicating whether the string S is a substring of String M or not.

I've implemented Aho-Corasick algo and received CRASH. I think, it's a normal situation for such input size.

Now I'd like to know, is this problem solvable using Aho-Corasick or only suffix tree fits in given constraints?

Thanks.

Здравствуй, Codeforces, есть одна задача.

Есть изначально пустой словарь. Надо уметь обрабатывать два типа запросов:

1. Добавить новую строку в словарь.
2. Для некоторой входной строки проверить, встречается ли в ней какое-нибудь из словаря в качестве подстроки.

В общем-то, всё. Разумеется, желательно делать такие дела оптимально по времени и памяти. Как с таким справляться? Пока в голову не приходит ничего кроме "каждый раз, когда приходит новая строка, давайте сломаем старый автомат и с нуля построим новый". Средний по вдумчивости гуглинг ничего не дал.

Заранее спасибо за помощь.

Всем привет!

Дана строка длины 10^5, нужно найти такую её подстроку, которая повторяется подряд максимальное количество раз (и если таких несколько -- выбрать самую длинную/короткую/лексикографически_какую_нибудь).

Например тест bacacacb должен дать ответ ac.

Как решать такое? Спасибо.

Здравствуйте!

Пытался сегодня научиться писать алгоритм построения выпуклой оболочки, но что-то пошло не так :( Можете, пожалуйста, помочь найти баг в http://ideone.com/IXFfS9 ?

Вроде всё выглядит просто, но продолжаю получать упертый ВА4 в задаче А http://codeforces.com/gym/100173

Даже не могу придумать тест, который завалит моё решение.

Заранее спасибо за помощь!

May somebody recommend some? Thanks.