Today is the rarest data in the calendar, hooray!

Btw, does everyone know which years are leap?

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!

Inspired by the Gleefre's article, I suggest adding YoptaScript language support to Codeforces — the world's first scripting programming language for gopniks and real boys. More information about the language can be found on the official website.

YoptaScript — is a very powerful language that can run at speed of JavaScript and is even more expressive than python (IMHO). I think that it is really worth adding as supported language because it is a very mature language, which has a very reach set of features.

Here is an implementation of binary heap sort benchmark in YoptaScript: https://pastebin.com/k5b8WVJB (and I'll be glad to create a PR if wanted).

The best open source YoptaScript implementation is YoptaScript, which can be installed here.

YoptaScript can also be included for your project using the package manager npm: npm install -g yopta

Or type npm install -g yopta to install YoptaScript globally.

On my computer, heapSort benchmark results in a range of [293..346] ms with an average time o 301.69 ms.

The problem 1А — Театральная площадь can be solved like this:

гыы 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.