Today is the rarest data in the calendar, hooray!

Btw, does everyone know which years are leap?

Подскажите, есть ли на какой-то платформе задачи прошедшего региона, чтобы можно было виртуально написать? Знаю, что задачи уже есть на acmp, но там нет частичных баллов, а хотелось бы с ними.

Problem statement: You are given an integer $$$N$$$ and the task is to output an integer sequence $$$a_1, \ldots, a_m$$$, such that $$$1 \leq a_i \leq N$$$ and $$$a_i + a_j \neq a_k + a_l$$$ for $$$i \neq j, k \neq l, (i,\ j) \neq (k,\ l)$$$ (i. e. all $$$\frac{m(m-1)}{2} $$$ pairwise sums should be different). The goal is to maximize $$$m$$$ — the length of resulting sequence.

This problem comes from RUCODE recent competition, it had a requirement for answer $$$m \geq \frac{\sqrt{N}}{2}$$$. Also there was a requirement for $$$a_i \neq a_j,\ i \neq j$$$, but in reality in makes almost no sense since if $$$m \geq 3$$$ and if $$$a_i == a_j$$$ for some $$$i \neq j$$$, than $$$a_k + a_i == a_k + a_j$$$ for any $$$k \neq i,\ k \neq j$$$. Since case $$$m < 3$$$ is obvious, we will further assume that all numbers in a sequence are different.

The solution to this problem comes from the fact that...

So, if we take largest prime $$$p$$$ that $$$2p ^ 2 + (p ^ 2 + 1) \bmod (2p) <= N$$$, we will get a sequence with $$$m \approx \sqrt{\frac{N}{2}} = \frac{\sqrt{N}}{\sqrt{2}} = lb_1(N)$$$, which is enough to solve the original problem.

Now there some interesting questions:

1. Can we get some upper bound for $$$m$$$?

2. How can we compute the longest possible (an optimal) sequence for some small $$$N$$$?

Here are my humble answers:

1). Since $$$a_i + a_j < 2N$$$, then by Dirichlet's principle we get $$$\frac{m(m-1)}{2} < 2N \Rightarrow m^2 < 4N \Rightarrow m < 2\sqrt{N}$$$. So our construction is $$$ub_1 = 2\sqrt{2} \approx 2.82$$$ times shorter than this upper bound.

2). I wrote a recursive bruteforce, it can find the optimal answer for $$$N = 64$$$ in about $$$10$$$ seconds.

#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;

int mx, n;
__uint128_t best;

void go(__uint128_t nums, __uint128_t sums, int last = 0, int dep = 0) {
    if (dep > mx) best = nums, mx = dep;
    for (int i = last + 1; i <= n; ++i) {
        if ((sums & (nums << i)) == 0) {
            go(nums | (__uint128_t)(1) << i, sums | (nums << i), i, dep + 1);
        }
    }
}

void solve(int N) {
    best = mx = 0, n = N;
    go(0, 0);
    for (int i = 0; i < 128; ++i) {
        if (best >> i & 1) cout << i << ' ';
    } 
    cout << '\n';
}

int main() {
    solve(64);
}

These questions brings us to some more challenging problems:

1. Can we improve aforementioned lower bound construction? Or write some code, which will build longer sequence with some bruteforce and pruning?

2. Can we improve above the algorithm for finding the optimal sequence? Maybe get some polynomial solution (or prove that it lies somewhere in NP class)?

3. Can we improve upper bound for $$$m$$$?

Really wanna find some answers on these questions, appreciate any of your thoughts!

UPD1: thanks to nor, we now have an upper bound $$$m < (1 + \varepsilon) \sqrt{N} = ub_2(N)$$$, which brings us to the $$$\underset{N \to \infty}{\lim}\dfrac{ub_2(N)}{lb_1(N)} = \sqrt{2} \approx 1.41$$$ which is a massive improvement! Proof can be found here. Turns out that this problem was researched even before the era of computers!

Вдохновлённый постом Gleefre, предлагаю добавить на Codeforces поддержку языка YoptaScript — первого в мире скриптового языка программирования для гопников и реальных пацанов. Больше информации о языке вы сможете найти на официальном сайте.

YoptaScript — очень мощный язык, который может работать со скоростью JavaScript и даже более выразительный, чем Python (ИМХО). Я думаю, что его действительно стоит добавить в качестве поддерживаемого языка, потому что это очень зрелый язык с очень богатым набором функций.

Вот реализация сортировки с помощью кучи в YoptaScript: https://pastebin.com/k5b8WVJB (и я буду рад создать пиар по желанию).

Лучшей реализацией YoptaScript с открытым исходным кодом, является YoptaScript, который можно установить здесь.

YoptaScript можно так же подключить для вашего проекта с помощью пакетного менеджера npm: npm install -g yopta

Или введите npm install -g yopta чтобы установить йопту глобально.

На моём компьютере, heapSort бенчмарк укладывается в [293..346] ms со средним временем 301.69 ms.

Задача 1А — Театральная площадь может быть решена, например, так:

гыы lines внатуре readline().поделитьЯгу(" ") нахуй
гыы x внатуре Очканавт.чирикГони(lines[0] / lines[2]) нахуй
гыы y внатуре Очканавт.чирикГони(lines[1] / lines[2]) нахуй
наПечать(x * y) нахуй

There not so many div.1 rounds at all in the last months. Thanks to such users as little_angel, zxyoi, these rare rounds becomes unrated.

Thousands of contestants are angry of you. GYUS, YOU ARE SUCH A SLUTS.

Given $$$a_1, \ldots, a_n$$$, $$$0 \leq a_i < 2^{k}$$$. We want to find $$$1 \leq i_1 < i_2 < \ldots < i_T \leq n$$$, s. t. $$$a_{i_1} \oplus \ldots \oplus a_{i_T} = 0,\ T \geq 1$$$. This is well known problem, which can be solved in $$$O(k^2)$$$ with Gaussian Elimination technique ($$$O\left(\frac{nk^2}{w} + \frac{k^3}{w}\right)$$$ to be more precise).

But what if we want to minimize $$$T$$$ (still assuming $$$T \geq 1$$$)? I only came up with smth like $$$O^*(n^k)$$$ by trying to bruteforce all subsets with size $$$\leq k$$$ and checking whether or not we can get xor sum $$$0$$$ from this subset.

Can we do better, maybe some $$$O(polylog(n,\ k))$$$? Would appreciate any help, thanks.