As an addition to Teams going to ACM ICPC World Finals 2018 I suggest table below

Updated after Codeforces Round #474

Updated after Codeforces Round #475

Привет, Codeforces!

Кратко о том, что здесь происходит: сначала мы находим задачку, решаем её формулой включений-исключений, удивляемся возникшей функции Мёбиуса, узнаём об обобщённой формуле обращения Мёбиуса, выводим решение задачи напрямую с помощью неё, а заодно решаем более общую задачу. Если это кажется Вам интересным, то продолжим.

//Вместо картинки
#include <A>
#include <B>
#include <C>
#exclude <AB>
#exclude <AC>
#exclude <BC>
#include <ABC>

Недавно наткнулся на задачу 803F - Coprime Subsequences, в которой требуется найти число таких подпоследовательностей массива, что НОД всех чисел подпоследовательности равен 1. Задача несложная и решается на основе следующих соображений:

1. Число непустых подпоследовательностей массива из k элементов равно 2^k - 1
2. Задачу можно переформулировать так: необходимо отыскать количество подпоследовательностей, для которых не найдется простого числа, делящего все элементы
3. Пусть P — множество простых чисел до 10⁵, а d(x) — число подпоследовательностей, каждый элемент которых кратен x. Если m(x) — число элементов массива, кратных x, то в соответствии с п. 1 имеем d(x) = 2^m(x) - 1
4. Если взаимнопростые p и q делят x, то p·q также делит x.

Скомбинировав вышесказанное и применив принцип включений-исключений получаем, что

считая, что произведение пустого множества равно 1. Итак, мы получили сумму из 2^|P| слагаемых, но большая часть из них не вносит вклада в ответ, т.к. соответствующее произведение превышает 10⁵. Можно непосредственно нагенерить нужные произведения, а можно просто пройтись по [1;10⁵], отбрасывая числа, не являющиеся произведениями простых (например, это можно проверить за логарифм, посчитав наименьший простой делитель в решете). Я воспользовался 2-м вариантом, и у меня получилось такое решение: 33406195

Сдав задачу, я заглянул в разбор, а там

Я посмотрел в код. Посмотрел в разбор. И снова в код. Функция sign(x), возвращающая знак слагаемого, как раз и есть функция Мёбиуса:

int sign(int x) {
	//lp[x] - наименьший простой делитель, а quot[x] - это x / lp[x]
	int prev = -1;
	int sgn = 1;
	for(; x > 1; x = quot[x]) { 
		if (lp[x] == prev) return 0;
		prev = lp[x];
		sgn = -sgn;
	}  
	return sgn;
}

Почему во включениях-исключениях всплыла функция Мёбиуса? Совпадение? Не думаю.

И тут я пошёл читать про функцию Мёбиуса. Я узнал про формулу обращения Мёбиуса, про обобщённую функцию Мёбиуса для частично упорядоченных множеств (под спойлером). Оказалось, что для обобщённой функции Мёбиуса также справедлива формула обращения, и формула включений-исключений является её частным случаем.

Обобщенный Мёбиус (кому лень идти на википедию)

Для множества A c отношением частичного порядка функция Мёбиуса определяется так

Для μ_A(a, b) справедлива формула обращения:

Заметив, что формула ответа напоминает обращение Мёбиуса, я попробовал вывести решение напрямую с помощью него и вот, что получилось.

Рассмотрим множество A = [1;10⁵] c отношением кратности (именно кратности, а не делимости) в качестве отношения порядка, т.е. (строгий вариант ). Например, , а . Пусть g(x) — число подпоследовательностей, НОД которых равен x. Обозначенная ранее величина d(x) выражается суммой g(y) по всем y кратным x, т.е.

Пусть μ_A(x, y) — функция Мёбиуса для A, тогда, применяя обобщенную формулу обращения Мёбиуса, получаем

Тогда ответ на задачу равен

Если показать, что μ_A(x, 1) = μ(x), то мы получим приведенную ранее формулу для ответа на задачу. Покажем это, сведя наш случай к известному, для которого доказан аналогичный результат.

Доказательство

Рассмотрим порядок "делимость" на множестве A = [1;10⁵], обозначив функцию Мёбиуса для него μ'_A(x, y). В работе From Posets to Derangements: An Exploration of the Mobius Inversion Formula показано (стр. 20-22), что μ'_A(1, x) = μ(x). Докажем, что μ_A(x, 1) = μ'_A(1, x).

По определению в случае x = 1 имеем μ_A(1, 1) = μ'_A(1, 1) = 1, а при x > 1

Утверждение 1: для всякого x > 1 верно

Доказательство: , следовательно,

Утверждение 2: для всяких x и верно

Доказательство

Если , то по определению . Заметим, что z кратно y и не равно ему, следовательно z > y. Получается, что значение μ_A(x, y) складывается только из значений μ_A(x, z), z > y, что даёт возможность применить мат. индукцию для доказательства.

Для удобства запишем выражение для μ_A(x, y) в другом виде:

Для наглядности обозначим, чему равно μ_A(x / y, 1) по определению:

Докажем утверждение индукцией по y в нисходящем порядке.

База: μ_A(x, x) = μ_A(1, 1) = 1. Переход: (y < x):

что и требовалось доказать.

Комбинируя утверждения 1 и 2 получаем, что для всякого x > 1 верно:

Теперь докажем основное утверждение тоже по индукции. База верна по определению. Выполним переход:

что и требовалось доказать.

В итоге получаем:

Таким образом, мы получили решение задачи, не прибегая к включениям-исключениям, а применив обобщенную формулу обращения Мёбиуса. В качестве бонуса имеем решение более общей задачи:

Сегодня делал очередную задачку в полигоне и заметил такую странность: ссылки на все задачи, созданные ранее, имеют вид https://polygon.codeforces.com/p/<user>/<problem>, а на созданную сегодня задачу https://polygon.codeforces.com/p<random>/<user>/<problem>, где <random> — случайный набор из 6 символов.

Вид ссылок меня мало волнует, но Codeforces не вытягивает задачи по этим ссылкам и замена /p<random>/ на /p/ не помогает (разумеется, у пользователя Codeforces на полигоне доступ к задаче есть). При попытке добавить задачу в мэшап получаю такое сообщение

Раньше на это не натыкался. Кстати, старые задачи, ссылки на которые имеют привычный вид, добавляются в мэшапы без проблем.

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

Проблема в полигоне или здесь?

UPD. Если попробовать добавить несуществующую задачу с полигона, но с ссылкой нужного формата, выдается другое сообщение, поэтому мне кажется, что формат с .../p/... просто захардкоден и другие варианты не распознаются как ссылки, ведущие на полигон.

Привет, Codeforces! Сегодня мы попробуем решить пару задач на целочисленный бинпоиск по ответу с помощью std::lower_bound и поймем, что это бессмысленно, но красиво (на самом деле нет).

Начнем с задачи 535C - Tavas and Karafs, которая решается двоичным поиском (например, 32799258). В этой задаче по заданным l, t, m, A, B нужно найти такое наибольшее , что

Как известно, std::lower_bound(first, last, v, pred) возвращает итератор, указывающий на первое значение a такое, что pred(a, v) == false, или last, если такого значения нет. Если в качестве предиката использовать s(x) - s(l - 1) ≤ t·m, то ответом на задачу будет значение, предшествующее lower_bound'у.

Приступим. Диапазоном для бинпоиска будет служить массив range такой, что range[i] = i. Заполнить такой массив поможет std::iota из <numeric>.

const int N = 1000000;
int range[N + 5];
//...
iota(range, range + N, 0);

lower_bound заточен под бинарные предикаты, но у нас унарный. Значит, второй аргумент и искомое значение (третий параметр lower_bound) будут фиктивными. Оформим предикат в виде лямбды и получим такую функцию

inline int solve(int l, int t, int m) {
    int r = (t - A) / B + 1;
    i64 lim = i64(t)*m;
    if (r < l)            
        return -1;
    if (sum(l, l) > lim)
        return -1;
    return *lower_bound(range + l, range + r + 1, 0, [lim, l](int item, int) -> bool {
    	return sum(l, item) <= lim; //sum(l, item) - это s(item) - s(l - 1) из описания
    }) - 1;
}

Возможно, обработка случаев с -1 не требуется, но я её оставил от предыдущего решения. Полный вариант — 32800781. Время работы этого решения почти не отличается от самописного бинпоиска.

В рассмотренной задаче мы явно использовали то, что диапазон бинпоиска небольшой, и его можно целиком хранить в массиве. Но что делать, если границы имеют порядок 10⁹ или даже 10¹⁸? В этом случае придется реализовать итератор для целочисленного диапазона, использующий O(1) памяти, который удовлетворяет интерфейсу RandomAccessIterator.

Например, так (много кода):

class Range {
public:
	typedef long long IntType;
	
	class iterator : public std::iterator<random_access_iterator_tag, 
		IntType, 
		IntType, 
		const IntType*, 
		IntType> {
	public:
		typedef iterator It;
		
		iterator(IntType pos)
			: pos(pos) {
		}

		//value access
		IntType operator[](IntType idx) {
			return (pos + idx);
		}

		IntType operator*() {
			return pos;
		}

		//arithmetics
		It& operator +=(IntType delta) {
			pos += delta;
			return (*this);
		}

		It& operator ++() {
			return (*this) += 1;
		}

		It operator ++(int) {
			++pos;
			return It(pos - 1);
		}

		It& operator -=(IntType delta) {
			pos -= delta;
			return (*this);
		}

		It& operator --() {
			return (*this) -= 1;
		}

		It operator --(int) {
			--pos;
			return It(pos + 1);
		}

		IntType operator -(const It& rhs) const {
			return pos - rhs.pos;
		}

		//relational
		bool operator ==(const It& rhs) const {
			return pos == rhs.pos;
		}

		bool operator != (const It& rhs) const {
			return pos != rhs.pos;
		}

		bool operator <(const It& rhs) const {
			return pos < rhs.pos;
		}

		bool operator <=(const It& rhs) const {
			return pos <= rhs.pos;
		}

		bool operator >(const It& rhs) const {
			return pos > rhs.pos;
		}

		bool operator >=(const It& rhs) const {
			return pos >= rhs.pos;
		}

	private:
		IntType pos;
	};

	Range(IntType a, IntType b)
		: a(a), b(b) {
	}

	Range()
		: Range(0, 1) {
	}
	
	iterator begin() const {
		return iterator(a);
	}

	iterator end() const {
		return iterator(b + 1);
	}

	IntType a, b;
};

Этот вариант опробуем на задаче 760B - Frodo and pillows (спасибо -Morass- за Problem Topics). В этой задаче по заданным n, m, k небходимо найти такое наибольшее , что

Оформим все аналогично предыдущей задаче и получим такое решение c использованием Range:

//...
typedef long long i64;

inline i64 pillows(i64 x, i64 y) {
	if (y > x -; 1) {
		return (x*(x - 1)) / 2 + y - (x - 1);
	}
	return ((2*x - y - 1)*y) / 2;
}

int main() {
	i64 n, m, k;
	cin >> n >> m >> k;
	Range range(1, m);
	cout << (*lower_bound(range.begin(), range.end(), 0, [n, m, k](long long x, int) -> bool {
		return pillows(x, k - 1) + pillows(x, n - k) + x <= m; 		
	}) - 1);
	return 0;
}

Полный вариант — 32802235.

Очевидно, что вариант с Range имеет смысл только тогда, когда есть возможность заинлайнить (с помощью JHelper и подобных инструментов) написанный ранее класс Range. Но в этом случае можно заинлайнить и написанный ранее шаблонизированный бинпоиск, получив исходник меньшего размера и более быстрое (хоть и незначительно) решение. Таким образом, практическое применение lower_bound в задачах на бинпоиск по ответу имеет смысл только при небольшом размере диапазона.

Привет, Codeforces!

Я не уверен, что эта тема не освещалась ранее, но поиск по блогам результатов не дал.

Сразу к делу

Взглянем на статью о дереве Фенвика в википедии: "Дерево Фенвика (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT)..."

Разве дерево Фенвика является двоичным? В общем случае — нет. На рисунке ниже дерево Фенвика изображено в виде... дерева! Дело в том, что в подавляющем большинстве материалов, авторы не пытаются указать, почему дерево Фенвика — дерево.

Почему недвоичное дерево назвали двоичным?

Все дело в неверном переводе составного прилагательного "Binary Indexed", одним из корректных переводов которого является "двоично-индексируемое". В ошибочном варианте перевода "Binary" и "Indexed" воспринимаются, как два самостоятельных прилагательных — "двоичное" и "индексированное".

А что такое двоично-индексируемое дерево?

Дерево, вершины которого пронумерованы числами так, что номера (индексы) вершин-сыновей вычисляются с помощью битовых операций над номером вершины-родителя. Помимо дерева Фенвика, яркими примерами двоично-индексированных деревьев служат двоичная куча (в классической реализации) и дерево отрезков, написанное на массиве. Кстати, эти примеры — не самые удачные, т.к. в них фигурируют двоичные двоично-индексирумые деревья, поэтому рассмотрим еще один пример. Имеется полное дерево степени 4, корень которого имеет индекс 0, а сыновья вершины x имеют индексы (x <  < 2) + 1, (x <  < 2) + 2, (x <  < 2) + 3, (x <  < 2) + 4, где  <  <  — двоичный сдвиг влево.

Надеюсь, этот пост будет полезен тем, кто еще не разобрался с деревом Фенвика. Спасибо за внимание!