Codeforces 100971.J - История изменений

Ctrlalt: Отмена правки 2034, сделанной участником Ctrlalt (обс.)

2016-06-08T20:50:52Z

Отмена правки 2034, сделанной участником Ctrlalt (обс.)

← Предыдущая версия		Версия от 20:50, 8 июня 2016
Строка 1:		Строка 1:
	== Ссылка на задачу ==		== Ссылка на задачу ==
	* [http://codeforces.com/gym/100971/problem/M Codeforces #100971.M — ~~Разбиение~~ на ~~хорошие строки~~]		* [http://codeforces.com/gym/100971/problem/J Codeforces #100971.J — Роботы на складе]

	== Комментарии ==		== Комментарии ==
	~~Пусть d[i] — минимальное количество хороших строк, на которые можно разбить префикс s[0]..s[i]~~.		По условию задачи граф связен.

	Если ~~s[0]..s[i] содержит ровно k различных букв~~, то ~~d[i] = 1~~.		Если в графе есть хотя бы одна вершина, степень которой больше 2, то в такой вершине роботы могут при необходимости разойтись, поменяв свой порядок, поэтому ответ YES.

	Иначе ~~найдём такое минимальное l <= i и максимальное r <= i~~, ~~что s[l]..s[i] и s[r]..s[i] содержат k различных букв. Тогда d[i] = 1 + min(d[l - 1]..d[r - 1]).~~		Иначе если граф не содержит вершин со степенью больше 2, то он представляет собой цикл или путь. Если граф — цикл, то ответ YES, иначе ответ NO.

	~~Поиск минимума на отрезке можно выполнять деревом отрезков за O(logn)~~.

	~~Подсчёт количества различных букв на отрезке можно осуществлять:~~
	* 26 бинарными поисками за O(26 &~~times~~; ~~logn);~~
	* деревом отрезков отсортированных массивов за O(log^2(n));
	* деревом отрезков битовых масок за O(log^2(n)) (лишний логарифм на подсчёт числа единиц в результирующей маске);
	* разреженной таблицей битовых масок за O(logn).

	~~Определение l и r можно осуществлять:~~
	* бинарным поиском за O(logn);
	* двумя указателями за O(1*).

	~~Принимаются решения с итоговой асимптотикой не хуже O(n \times; log^2(n))~~.

	[[Category: Сборник задач: Codeforces]]		[[Category: Сборник задач: Codeforces]]
	[[Category: Задачи: ~~Динамическое программирование — один параметр]]~~		[[Category: Задачи: Циклы в графе]]
	~~[[Category: Задачи: Дерево отрезков]]~~
	~~[[Category: Задачи: Sparse Table]]~~
	~~[[Category: Задачи: Бинарный поиск]]~~
	~~[[Category: Задачи: Два указателя~~]]

Ctrlalt в 20:48, 8 июня 2016

2016-06-08T20:48:15Z

← Предыдущая версия		Версия от 20:48, 8 июня 2016
Строка 1:		Строка 1:
	== Ссылка на задачу ==		== Ссылка на задачу ==
	* [http://codeforces.com/gym/100971/problem/J Codeforces #100971.J — ~~Роботы~~ на ~~складе~~]		* [http://codeforces.com/gym/100971/problem/M Codeforces #100971.M — Разбиение на хорошие строки]

	== Комментарии ==		== Комментарии ==
	~~По условию задачи граф связен~~.		Пусть d[i] — минимальное количество хороших строк, на которые можно разбить префикс s[0]..s[i].

	Если ~~в графе есть хотя бы одна вершина, степень которой больше 2~~, то ~~в такой вершине роботы могут при необходимости разойтись, поменяв свой порядок, поэтому ответ YES~~.		Если s[0]..s[i] содержит ровно k различных букв, то d[i] = 1.

	Иначе ~~если граф не содержит вершин со степенью больше 2~~, ~~то он представляет собой цикл или путь~~. ~~Если граф~~ &~~mdash~~; ~~цикл, то ответ YES, иначе ответ NO~~.		Иначе найдём такое минимальное l <= i и максимальное r <= i, что s[l]..s[i] и s[r]..s[i] содержат k различных букв. Тогда d[i] = 1 + min(d[l - 1]..d[r - 1]).

			Поиск минимума на отрезке можно выполнять деревом отрезков за O(logn).

			Подсчёт количества различных букв на отрезке можно осуществлять:
			* 26 бинарными поисками за O(26 × logn);
			* деревом отрезков отсортированных массивов за O(log^2(n));
			* деревом отрезков битовых масок за O(log^2(n)) (лишний логарифм на подсчёт числа единиц в результирующей маске);
			* разреженной таблицей битовых масок за O(logn).

			Определение l и r можно осуществлять:
			* бинарным поиском за O(logn);
			* двумя указателями за O(1*).

			Принимаются решения с итоговой асимптотикой не хуже O(n \times; log^2(n)).

	[[Category: Сборник задач: Codeforces]]		[[Category: Сборник задач: Codeforces]]
	[[Category: Задачи: ~~Циклы в графе~~]]		[[Category: Задачи: Динамическое программирование — один параметр]]
			[[Category: Задачи: Дерево отрезков]]
			[[Category: Задачи: Sparse Table]]
			[[Category: Задачи: Бинарный поиск]]
			[[Category: Задачи: Два указателя]]

Ctrlalt: Новая страница: «== Ссылка на задачу == * [http://codeforces.com/gym/100971/problem/J Codeforces #100971.J — Роботы на складе] == Коммент…»

2016-06-08T15:05:11Z

Новая страница: «== Ссылка на задачу == * [http://codeforces.com/gym/100971/problem/J Codeforces #100971.J — Роботы на складе] == Коммент…»

Новая страница

== Ссылка на задачу ==
* [http://codeforces.com/gym/100971/problem/J Codeforces #100971.J — Роботы на складе]

== Комментарии ==
По условию задачи граф связен.

Если в графе есть хотя бы одна вершина, степень которой больше 2, то в такой вершине роботы могут при необходимости разойтись, поменяв свой порядок, поэтому ответ YES.

Иначе если граф не содержит вершин со степенью больше 2, то он представляет собой цикл или путь. Если граф — цикл, то ответ YES, иначе ответ NO.

[[Category: Сборник задач: Codeforces]]
[[Category: Задачи: Циклы в графе]]