Helgui's blog

By Helgui, history, 19 months ago, In English,

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, gritukan 8786
Seoul National University zigui, dotorya, cki86201 8569
University of Warsaw Radewoosh, Errichto, mareksom 8386
St. Petersburg ITMO University Belonogov, SpyCheese, izban 8303
Moscow Institute of Physics & Technology Golovanov399, Kostroma, I_hate_ACM 7909
KAIST ko_osaga, alex9801, HYEA 7709
University of Tokyo Hujiwara, hogloid, DEGwer 7656
University of New South Wales izrak, abyssmall, AntiForest 7635
Tsinghua University stilwell, kfdong, xllend3 7624
Fudan University SakurakoujiRuna, tun, t90tank 7604
St. Petersburg State University sinesight, Kaban-5, pavel.savchenkov 7555
Ural Federal University kb., Tinsane, Umqra 7404
University of Bucharest alex.velea, retrograd, AndreiNet 7401
Sharif University of Technology seyedparsa, DarkestLight, M.Mahdi 7191
Uzhgorod National University MrDindows, Melnyk, Rubanenko 7166
Saratov State University BledDest, adedalic, Ajosteen 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, RonnieOSullivan 6768
Ulsan National Institute of Science and Technology na2a, Tachyon29, nezametdinov 6718
Belarusian State University progmatic, Fedosik, vilcheuski 6707
University of Tartu oml1111, hoomas, k__mas 6707

Read more »

 
 
 
 
  • Vote: I like it
  • +219
  • Vote: I do not like it

By Helgui, history, 23 months ago, In Russian,

Привет, Codeforces!

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

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

Недавно наткнулся на задачу 803F - Взаимно простые подпоследовательности, в которой требуется найти число таких подпоследовательностей массива, что НОД всех чисел подпоследовательности равен 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), то мы получим приведенную ранее формулу для ответа на задачу. Покажем это, сведя наш случай к известному, для которого доказан аналогичный результат.

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +55
  • Vote: I do not like it

By Helgui, history, 23 months ago, In Russian,

Сегодня делал очередную задачку в полигоне и заметил такую странность: ссылки на все задачи, созданные ранее, имеют вид 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

Read more »

 
 
 
 
  • Vote: I like it
  • +20
  • Vote: I do not like it

By Helgui, history, 23 months ago, In Russian,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +64
  • Vote: I do not like it

By Helgui, history, 2 years ago, In Russian,

Недавно обнаружил, что деление с остатком на натуральное число в Python'е (в отличие от С++, например) реализовано в полном соответствии с математическим определением, т.е. остаток r от деления целого a на натуральное b находится в диапазоне [0;b). Таким образом, если вы решаете задачу, требующую вычислений по модулю, не нужно заботиться о приведении остатка к [0;b) — Python сделает это за вас! Логично, что неполное частное также согласовано с этим определением. Разумеется, это касается только встроенного int и не распространяется на int* и uint* из numpy.

Примеры

(-1) % 10 == 99 % 10 #-1 сравнима с 99 по модулю 10?
True
-1 // 10 # Выходит, что неполное частное должно быть равно -1?
-1
# Да, -1 = (-1)*10 + 9

Вполне ожидаемо, что есть те, кто знает об этом (31533923) и те, кто не знает (5623328, 5544803).

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By Helgui, 3 years ago, In Russian,

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • +78
  • Vote: I do not like it

By Helgui, 3 years ago, In Russian,

Привет, Codeforces!

Алгоритм Дейкстры поиска кратчайших путей от одной вершины до остальных, как правило, формулируется в терминах взвешенного графа: граф сопровождается функцией — длина (вес, стоимость) ребра. В свою очередь, длина d пути p = v1v2v3... vm выражается суммой длин составляющих его ребер, т.е. . Все мы знаем критерий применимости алгоритма Дейкстры — функция w не принимает отрицательных значений. Это свойство весовой функции наряду со свойствами суммы (коей является d(p)) используется в доказательстве корректности алгоритма Дейкстры.

Оказывается, этот критерий можно обобщить, значительно расширив круг допустимых функций d(p). В частности, функция d(p) не обязана быть агрегатором весов рёбер, следовательно, граф может не являться взвешенным с точки зрения классического определения. Об этой возможности я узнал из лекции Виталия Гольдштейна в харьковской Зимней Школе. Если верить Виталию, то для доказательства корректности алгоритма Дейкстры, достаточно двух свойств функции d(p):

Внимание, вопрос:

кто-нибудь знаком со статьями, монографиями или материалами (за исключением сборника Зимней Школы 2013), посвященными алгоритму Дейкстры с произвольными весовыми функциями?

Read more »

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

By Helgui, 5 years ago, In Russian,

Привет, Codeforces!

Как вы помните, всем участникам одного из прошедших NEERC, яндекс дарил 250 Гб на я.диске. Для этого надо было заполнить форму/отправить письмо (точно не помню) и, разумеется, я не прошел мимо халявы. Иметь 250 Гб на облаке было очень удобно, но сегодня я обнаружил, что объем диска был сокращен до 10 Гб в одностороннем порядке, без всякого уведомления. Рекомендую всем, кто участвовал в той акции, проверить текущий объем.

Кто-нибудь помнит точные условия акции, в частности, давал ли яндекс эти 250 Гб на определенное время? Или, возможно, яндекс оставлял за собой право в любой момент забрать неиспользуемое пространство?

Read more »

 
 
 
 
  • Vote: I like it
  • +102
  • Vote: I do not like it