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

Автор Helgui, история, 6 лет назад, По-английски

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

Team Members Rating(sum)
Peking University Syloviaely, SkyDec, shanquan2 9172
Moscow State University LHiC, V--o_o--V, vintage_Vlad_Makeev 8786
Seoul National University zigui, dotorya, molamola. 8569
University of Warsaw Radewoosh, Errichto, mareksom 8386
St. Petersburg ITMO University Belonogov, SpyCheese, izban 8303
Moscow Institute of Physics & Technology Golovanov399, Kostroma, -imc- 7909
KAIST ko_osaga, alex9801, Konijntje 7709
University of Tokyo Hujiwara, hogloid, DEGwer 7656
University of New South Wales JoeyWheeler, xxTastyHypeBeast666xx, AntiForest 7635
Tsinghua University Stilwell, KFDong, xllend3 7624
Fudan University SakurakoujiRuna, tun, t90tank 7604
St. Petersburg State University el_sanchez, Kaban-5, pavel.savchenkov 7555
Ural Federal University kb., Tinsane, sivukhin 7404
University of Bucharest alex.velea, bicsi, AndreiNet 7401
Sharif University of Technology SeyedParsa, Deemo, M.Mahdi 7191
Uzhgorod National University MrDindows, Melnyk, Rubanenko 7166
Saratov State University BledDest, adedalic, Roms 7120
Massachusetts Institute of Technology ksun48, desert97, cliu568 7072
Shanghai Jiao Tong University Akigeor, lbn187, Nisiyama_Suzune 7062
National Taiwan University eddy1021, paulwang, akaiNeko 7054
Sharif University of Technology Haghani, JeBeK, matrix 6965
Universidade de São Paulo yancouto, victorsenam, arthur.nascimento 6956
The Chinese University of Hong Kong nhho, hohomu, jasonyik 6948
National Research University Higher School of Economics iskhakovt, kraskevich, Kronecker 6881
Scuola Normale Superiore dario2994, Delfad0r, fram 6877
University of Electronic Science and Technology of China Orenji.Sora, LaPlus, femsub 6781
Indian Institute of Technology — Roorkee gvaibhav21, adkroxx, saharshluthra 6768
Ulsan National Institute of Science and Technology Na2a, bekzhan29, nezametdinov 6718
Belarusian State University 244mhq, Mediocrity, vilcheuski 6707
University of Tartu oml1111, SLLN, .I. 6707

Полный текст и комментарии »

  • Проголосовать: нравится
  • +219
  • Проголосовать: не нравится

Автор Helgui, история, 6 лет назад, По-русски

Привет, Codeforces!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +55
  • Проголосовать: не нравится

Автор Helgui, история, 6 лет назад, По-русски

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

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

bug

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

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

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

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

bug

Полный текст и комментарии »

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

Автор Helgui, история, 6 лет назад, По-русски

Привет, 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. Время работы этого решения почти не отличается от самописного бинпоиска.

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

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

class Range{...}

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

s(x, k - 1) + s(x, n - k) + x ≤ m

Оформим все аналогично предыдущей задаче и получим такое решение 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 в задачах на бинпоиск по ответу имеет смысл только при небольшом размере диапазона.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

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

Привет, 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, где  <  <  — двоичный сдвиг влево.

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +78
  • Проголосовать: не нравится