Polygon automaticly updates test meta files and produces strange difference, as JSON these files are the same but inputSha1 is moved to suffix.

MODIFIED	testsets/tests/1.meta
MODIFIED	testsets/tests/11.meta
MODIFIED	testsets/tests/2.meta
MODIFIED	testsets/tests/3.meta
MODIFIED	testsets/tests/5.meta
MODIFIED	testsets/tests/6.meta
MODIFIED	testsets/tests/7.meta
MODIFIED	testsets/tests/8.meta
MODIFIED	testsets/tests/9.meta

This difference appears after any action and it prevents from commiting any changes and from building any packages. Building packages asks to commit uncommited changes before building. Commiting changes says Your changes have not been committed. Try to find and resolve conflicts

Is there any workaround?

MikeMirzayanov

Recently Polygon got enhanced with AI-based features and this is great. Those features can be very helpful at certain situations, but if you don't need them you can just ignore them.

But few days ago I've first encountered a new block on the right panel:

and this one gave me more anxiety than usual. Why this one invites me to review something that I've never requested from AI? Why this one has a separate block and a bold label that suggests some tips as if it is some kind of advertisement?

The review link contains useSuggestGrammaticalStatementFixesCache=true, so correction tips are actually grammatical fixes. This block seems to immediately appear on problems that have newly created statements and on problems that were not visited for years alike. Also grammatical fixes that are provided by this block and by Suggest grammatical fixes seem to be identical.

This grammatical fixes cache seems to be updated with every statement/tutorial update. I was not able to find a way to disable this behaviour.

How do I disable this behavoir? Why this feature is enabled by default? Why this feature has to have a cache in the first place?

I expect that CodeForces does not run own AI service and uses an external one.

Then there are multiple reasons why I would prefer to disable it:

1. Querying AI service is usually more expensive than running some server-side script. So why should I waste someone's API quota on some intermediate or insignificant versions of my texts that will not be used and I do not care about fixes for it?
2. Recently I've noticed occasions of significant delays in saving problem statement/tutorial. When it happens statement form is locked with Saving... label for more than $$$30$$$ seconds. But if you decide to interrupt this process and reload the page it will still save the statement. I have no idea whether this issue is connected to querying AI services, but if it will be possible to fix it by opting out of AI assistance I would be glad to do it.
3. Most importantly: data security. Some authors (including me) can have prepared and partially prepared problems in Polygon waiting to be revealed in the first time untouched for a few years. How can I be sure that prompts that contain unrevealed problem statement and tutorial are not saved on the other side of the AI service and will not be used as a part of a future learning dataset? I do not want to eventially find out that some AI knows about my problem in exact original wording that is directly tied to problem tutorial in it's learning dataset.

Please, correct me if I'm wrong and give some comments, Polygon developers and MikeMirzayanov

I would like to ask about certain features in problemsetting with CF and Polygon that I was not able to figure out how to use (or not even sure if they are supported at all). Probably some of them deserve feature requests.

SVG images in problem statements

Scalable Vector Graphics is a nice format to draw simple images and schemes that can be very lightweight and can be intergated directly into HTML page.

Now if you include SVG image with

\includegraphics[scale=1]{a.svg}

it will be substituted with PNG version of the image in HTML and will fail to build PDF with

LaTeX Error: Cannot determine size of graphic in a.svg (no BoundingBox).

What am I doing wrong?

Animated GIFs in problem statements

Providing animated example is a great way to explain processes that are described in the problem. Providing an external link to GIF feels somewhat inconvenient.

Now if you include animated GIF with

\includegraphics[scale=1]{s.gif}

it tries to substitute it with PNG image, but the link is broken and it renders missing image in HTML.

Is it possible to make it work?

Custom HTML / JS in problem statements

If problems statement is just an HTML page it can be cool to enhance it with static frontend JS-based application that can play animations or provide interactive examples for participants. Especially for education purposes.

Yes, an ability to include user-written JS script can be a serious security issue, but in some way you have trust the contest author anyway.

Ghosts in gym standings

Ghost participants of past competititon is a really cool feature. I'm planning to add some contests from different platform to the CF gym, and I would also like to export ghosts data for them. But how to configure ghosts for a mashup? What format does it use?

I've only found Export the judgment log to DAT-file section with Ghosts checkbox, but this is not the way to include it.

Different LaTeX or different examples for HTML and for PDF outputs

When problem statement is going to be used in both ways in HTML and in PDF, it is very annoying when you would like to make them a little different in layout. For example long lines in input/output examples are perfectly fine in HTML version, but will not fit into default PDF layout and it is good to provide custom input/output data for it, but only in PDF.

Also PDF and HTML statements are rendered differently and some LaTeX can work in one of them, but break the other one.

What is happening with CodeForces and Polygon now?

Both sites every other time give A timeout occurred Error code 524 or load the page for $$$30+$$$ seconds.

Polygon almost all the time has Invokers waiting: 0. Problem statements cannot be previewed in HTML, nor in PDF. Validator tests are permanently in queue. Packages fail to build with the message Can't compile source file '<filename>': Can't receive answer from compilation service.

This started for me about $$$2$$$ hours ago.

Время от времени мне нравится заниматься теорикрафтингом и писать всякие калькуляторы для игр и моих решений в них.

Но в этот раз построение теорий зашло в вычислительную сторону вещей намного глубже чем обычно. Поэтому я решил также опубликовать свои результаты и тут.

Математика и статистика в выборе чемпионов в League of Legends ARAM

Это статья про когнитивные искажения при случайном выборе чемпионов и про модель, которая используется для оценки вероятностей определенных событий в серии сыгранных игр. Используемая модель — это ДП по количество сыгранных игр и вектору текущего распределения чемпионов, которое использует гипергеометрическое распределение для рассчета переходов. Сама модель написана на JS в странице браузера для облегчения ее кастомизации для всех.

Я был бы рад увидеть критику и предложения, особенно по математической и реализационной части (смотрите "Подход и детали модели").

Number system conversion algorithm is well-known and taught in almost every basic programming course. To get $$$y_b = x_{10}$$$ (number $$$y$$$ written in base $$$b$$$ equal to number $$$x$$$ base $$$10$$$) we have to iteratively chop the lowest digit in base $$$b$$$ from number $$$x$$$ using division and remainder operators:

def naive_conversion(x, base):
    y = ""
    while x > 0:
        y = str(x % base) + y
        x //= base

    return y

This works in $$$\mathcal{O}(\log x)$$$ for all $$$x$$$ that fit into machine word $$$(\log x < w)$$$. However this becomes inacceptably slow when we consider numbers of length $$$n$$$ that is large enough and we cannot use $$$\mathcal{O}(1)$$$ division. Let's define $$$n$$$ as length of converted number $$$x$$$ in some number system $$$(w \ll \log x = n)$$$. Still, base of number systems $$$b$$$ and all digits in it can be stored in usual integer. So we can implement conversion above in $$$\mathcal{O}(n^2)$$$ with some efficient implementation of big-number-by-small-number division.

This operation is commonly required when you are trying to print big integers in base $$$10$$$ that are stored by big integer library in binary notation. To overcome this some competitive programming libraries use base $$$10^9$$$ to print numbers in base $$$10$$$ digit-by-digit without complicated conversion. But this is just a trick for common number presentation. But how to generally approach this problem and be able to quickly convert big integers to any number system?

We are given big integer $$$x_b$$$ and another number system base $$$c$$$. We have to find $$$y$$$ such that $$$y_c = x_b$$$. $$$f(x_b, c) = y_c$$$. Suppose $$$x_b$$$ has length $$$n$$$ and $$$y_c$$$ will have length $$$m$$$.

Best aproach that I can think of is divide and conquer. Main problem with abritrary bases is that many digits in $$$x$$$ can affect many digits in $$$y$$$. To overcome this we can choose $$$p \approx \frac{m}{2}$$$ and represent $$$x_b = L_b \cdot c^p + R_b$$$, where $$$R_b < c^p$$$. In such form we can see that $$$L$$$ part can only affect higher half of digits of $$$y$$$ and $$$R$$$ part can only affect lower half of digits. Now we can safely split our number into two, solve problem recursively obtaining $$$f(L_b, c) = L'_c$$$ and $$$f(R_b, c) = R'_c$$$ and finally concatenate parts $$$y_c = L'_c \cdot c^p + R'_c$$$.

To split $$$x_b$$$ into $$$L_b, R_b$$$ we can use division and remainder. Assuming that big integer divmod can be implemented in $$$\mathcal{O}(n \log n)$$$ whole recursive calculation of $$$f(x_b, c)$$$ can be done in $$$\mathcal{O}(n \log^2 n)$$$.

def fastbase(x, b, order=-1):
    if order == -1:
        order = 1
        while b**(order+1) <= x:
            order *= 2

    if order == 0:
        return str(x)

    sep = b ** order

    hi, lo = divmod(x, sep)

    return fastbase(hi, b, order//2) + fastbase(lo, b, order//2)

In this implementation $$$m$$$ is naively estimated as lowest possible power of two, but then extra leading zeroes must be stripped.

We made some benchmarking in Kotlin and in Python. This algorithm appears to be somewhat competitive with built-in algorithms in Kotlin, however in Python3 this works even faster.

import time, sys

times = [time.time()]


def benchmark_check(*msg):
    times.append(time.time())
    print(*msg, end=" ")
    print("in", times[-1] - times[-2])


def fastbase(x, b, order=-1):
    if order == -1:
        order = 1
        while b**(order+1) <= x:
            order *= 2

    if order == 0:
        return str(x)

    sep = b ** order

    hi, lo = divmod(x, sep)

    return fastbase(hi, b, order//2) + fastbase(lo, b, order//2)


print("Number system conversion test. Python version:", sys.version)

s = 250*1000

n = 1
for i in range(1, s+1):
    n *= i

benchmark_check("Built", s, "factorial")

n10f = fastbase(n, 10).lstrip('0')
benchmark_check("D&C fast conversion to base 10")

n10 = str(n)
benchmark_check("Default conversion to base 10")

n10format = "{0:d}".format(n)
benchmark_check("Format conversion to base 10")

bin2 = bin(n)
benchmark_check("Bin conversion to base 2")

n2 = "{0:b}".format(n)
benchmark_check("Format conversion to base 2")

n8 = "{0:o}".format(n)
benchmark_check("Format conversion to base 8")

n16 = "{0:x}".format(n)
benchmark_check("Format conversion to base 16")

Number system conversion test. Python version: 3.9.7 (tags/v3.9.7:1016ef3, Aug 30 2021, 20:19:38) [MSC v.1929 64 bit (AMD64)]
Built 250000 factorial in 15.586419582366943
D&C fast conversion to base 10 in 15.642351150512695
Default conversion to base 10 in 21.88812279701233
Format conversion to base 10 in 21.88341784477234
Bin conversion to base 2 in 0.006005048751831055
Format conversion to base 2 in 0.006005525588989258
Format conversion to base 8 in 0.0030024051666259766
Format conversion to base 16 in 0.0020012855529785156

Blazing fast conversions to binary formats (and powers of binary) show that numbers are stored in binary.

Are there any well-knows algorithms? What algorithms are used in standard libraries? Are there any better solutions?

Recently I was preparing some problems in Polygon. One of the problems required custom checker. I've implemented and set up my checker and it turned out that it gives verdict FL for all checker tests. I have tried alternating checker implementations, replacing it completely with standard wcmp.cpp code and simplifying logic into single line

quitf(_ok, "ok");

but none of that helped. Only thing that I managed to achieve is to get exit code 13131313 for roughly half of checker tests.

After messing around for a few hours I finally noticed red "Show warnings" label. (I'm not sure if this label was there when I first encountered this problem roughly a week ago.) Turns out there is that critical warning:

Turns out that I was unlucky choosing problem name set-diff-patch-notes and moving it into checker name. After renaming source file it worked just fine.

But how does this work? Are there any other bad substrings? Why there is a weird limitations for checker file names?

A friend of mine suggested that it has something to do with version control system used in Polygon. But if that's the case why any other source files (solutions, validators) have no problems with patch substring?

[This article is also available in English]

Привет, CodeForces.

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

Я познакомился с матроидами на Зимних Петрозаводских Сборах 2019. Там была задача, которая очевидно не решалась обычными способами, известными мне тогда. Разбор этой задачи состоял буквально из трех слов “just matroid intersection”. Тогда мне потребовалось больше двух дней дорешивания чтоб найти всю необходимую информацию и детали и написать решение, которое получает Accepted. И намного больше времени мне потребовалось чтобы понять почему это действительно работает и как именно это работает. (Я до сих пор сомневаюсь в некоторых деталях.)

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

Это было даже не близко к тому, чтобы быть понятным для меня тогда. (Возможно я просто недостаточно математик для этого, пока что.) Но все же, я уверен что существует способ сделать его более понятным, очевидным и детализированным.

Я уверен, в спортивном программировании есть много людей, которые бы тоже хотели познакомиться с матроидами. И поэтому я решил рассмотреть эту тему с самого начала фокусируясь больше на объяснениях, логических шагах и предоставлении большего числа примеров. Это и есть цель этой статьи и вам не обязательно знать что-либо о матроидах для прочтения.

Привет, CodeForces.

Недавно решил поближе познакомиться с такой структурой данных как дерево Фенвика или binary indexed tree.

В данной статье я буду рассматривать дерево Фенвика для суммы, но все написанное легко обобщается на случай любой ассоциативной, коммутативной и обратимой операции.

vector<int> fenwick;

void init_empty(int size_) {
    fenwick.assign(size_, 0);
}

int sum(int r) {
    int res = 0;

    while (r >= 0) {
        res += fenwick[r];
        r = (r & (r+1)) - 1;
    }

    return res;
}

int sum(int l, int r) {
    return sum(r) - sum(l-1);
}

void inc(int i, int delta) {
    while (i < fenwick.size()) {
        fenwick[i] += delta;
        i |= i+1;
    }
}

Прочитав статьи о нем на e-maxx.ru и neerc.ifmo.ru и спросив друзей меня заинтересовал один момент. Обе статьи (и друзья) для инициализации этого дерева на заданном массиве предлагают создавать дерево Фенвика следующим образом:

1. Деревом Фенвика для массива нулей будет массив нулей, возьмем его за основу,
2. Далее запросами к дереву заменим все элементы исходного массива нулей на нужные нам и мы получим дерево Фенвика для нашего массива.

void init_vector_classic (vector<int> a) {
    init_empty(a.size());

    for (int i = 0; i < a.size(); i++) inc(i, a[i]);
}

Это работает за O(N * logN) от длинны исходного массива.

Можем ли мы делать это быстрее? Определенно можем!

По определению дерева Фенвика каждый его элемент представляет собой сумму на непрерывном отрезке исходного массива. Ввиду того, что запросы на изменение массива в процессе его инициализации отсутствуют, мы можем использовать частичные суммы для определения элементов дерева Фенвика. Это потребует препроцессинга O(N), но позволит определять элементы дерева за O(1). Таким образом асимптотика улучшится до O(N) + O(1) * O(N) = O(N).

void init_vector_linear_prefix (vector<int> a) {
    init_empty(a.size());

    vector<int> prefix_sum;
    prefix_sum.assign(a.size(), 0);
    prefix_sum[0] = a[0];
    for (int i = 1; i < a.size(); i++) prefix_sum[i] = prefix_sum[i-1] + a[i];

    for (int i = 0; i < a.size(); i++) {
        int lower_i = (i & (i+1)) - 1;
        fenwick[i] = prefix_sum[i] - (lower_i >= 0 ? prefix_sum[lower_i] : 0);
    }
}

Но в такой реализации мы получаем дополнительные O(N) памяти на хранение массива.

Можем ли мы этого избежать? Можем!

Заметим, что для инициализации fenwick[i] нам могут потребоваться только такие элементы prefix_sum[j], где j ≤ i. Это дает нам возможность использовать только один массив и, начиная с конца, постепенно переводить его из префиксных сумм в дерево Фенвика.

void init_vector_linear (vector<int> a) {
    init_empty(a.size());

    fenwick[0] = a[0];
    for (int i = 1; i < a.size(); i++) fenwick[i] = fenwick[i-1] + a[i];

    for (int i = a.size()-1; i > 0; i--) {
        int lower_i = (i & (i+1)) - 1;
        if (lower_i >= 0) fenwick[i] -= fenwick[lower_i];
    }
}

Таким образом мы можем улучшить время инициализации дерева Фенвика до O(N) используя O(1) дополнительной памяти.

Конечно, в большинстве задач кол-во запросов к дереву Фенвика примерно соизмеримо с его размером, потому улучшение времени его инициализации не улучшит итоговую асимптотику решения. Однако такая оптимизация дает возможность уменьшить константу той части вашего решения, которая работает с деревом (или деревьями) Фенвика, путем добавления совсем небольшого объема кода.

Что вы думаете по этому поводу и как вы инициализируете свои деревья Фенвика?

UPD: Существует другой подход к этой задаче, который позволяет добиться еще меньшего объема кода! Спасибо, Jakube за комментарий об этом и sdnr1 за написание блога об этом.

Привет, CodeForces.

Сегодня хотел попробовать написать интерактивную задачу 753B - Интерактивные быки и коровы (простая версия) на Ruby. Но на все варианты решения (23586661, 23586795, 23586863, 23611181) вердиктом было "Решение «зависло» на тесте 1".

Так же подозрительно, что для этой задачи (и для ее усложненной версии) нет Accepted посылок на Ruby.

Это баг CF или я что-то делаю не так?

UPD: Разобрался с вопросом: причиной была моя невнимательность при изучении примеров и, как следствие, некорректность решения. Верный вариант решения — 23649752.