Sprint: you choose when to start and then you have 120 minutes to solve 6 algorithmic problems.
Marathon: you have all the time until the end of the competition to solve one optimization problem.

What about Yandex Cup 2021 algorithm finalists? Did they get t-shirts?

If you go back to the website now and log in, you will be able to click a button to confirm your attendance for the final round. After doing so, you get a button that brings you to the competition page which has the time and duration listed. Hope this helps!

Greedy :)

Problem A. Max and the erudite competition

For solving this problem you should think as a coach. You can start from something simple.

My C++ solution

Alternate approach cause I kept messing up my greedy lol:

1 2 2 3 3 3 3 4 4 4
1 1 2 2 3 3 3 3 4 4

#include <bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;


#include <bits/extc++.h> 
using namespace __gnu_pbds;

template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll>   pl;
typedef pair<ld, ld>   pd;
typedef vector<int> vi;
typedef vector<ll>  vl;
typedef vector<ld>  vd;
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PRECISION std::cout << std::fixed << std::setprecision(20);
#define DBPRECISION std::cout << std::fixed << std::setprecision(4);
#define iter(x) (x).begin(), (x).end()
#define umap unordered_map
#define uset unordered_set
#define _f first
#define _s second
const char nl   = '\n';
const int  INF  = (1 << 30) - 1;
const ll   LINF = 1e18;
const ld   PI   = 3.14159265358979323846L;
const ld   E    = 2.71828182845904523536L;
const ld   eps  = 1e-7;
#define dbx(x) cout << x << endl;
#define dbn(x) cout << x << nl;
#define dba(x) cout << x << " ";

const int N = 2e5 + 5;
int a[N], b[N];
bool validate(int n, int k){ // False if we must have more losses than 'k'
    for(int i = k; i < n; i++){
        if(a[i] < b[i - k]) return false;
    }
    return true;
}
int main(){
    FASTIO
    PRECISION
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    sort(a, a + n);
    sort(b, b + n);

    int lo = 0, hi = n;
    while(lo < hi){
        int mid = (lo + hi) / 2;
        if(validate(n, mid)){
            hi = mid;
        }else{
            lo = mid + 1;
        }
    }

    // lo = min # of losses here

    umap<int, int> drawct;
    int cur = -lo + (n - lo);
    for(int i = lo; i < n; ){
        int t = i;
        int x = 0;
        while(i < n && a[i] == a[t] && b[i - lo] == a[t]){ // How many draws involve element 'a[i]'
            i++;
            x++;
        }
        if(!x) i++;
        cur -= x;
	// For additional losses [1...x], we'll create a new win
        while(x){
            drawct[x]++;
            x--;
        }
    }
    int ans = cur;
    for(int i = 1; i <= n; i++){
        lo++;
    	if(lo == n) break;
        cur -= 2; // -2 for the new loss; the new loss always comes from a previous win
        cur += drawct[i];
        ans = max(ans, cur);
    }
    cout << ans << nl;
}   

C: Fix N mod 3 (let's call it r) and binary search on N. For each prime factor of A, calculate how many times p^a is a factor of N!!! for each a >= 1 and add them up to get the total exponent of p in N!!!.

This can be done by counting the number of solutions to p^a | (3k + r). If p is 3, then we need r = 0 and k is a multiple of p^(a-1). If p is not 3, then the solutions will be k = p^a * anything + i, where i is whichever of (-r)/3, (-r + p^a) / 3, or (-r + 2p^a) / 3 is an integer.

Like previous years we are preparing online room to discuss Yandex Cup. We will return with it in some days.

Upsolve or look at problems one can here: https://contest.yandex.com/contest/42710/problems/

Upsolving is opened here. Letters for problems are shifted by 6 problems from the qualification round.

CHT / LiChao tree.

I will assume that $$$n = q$$$, expected complexity is $$$O(n\sqrt{n})$$$, but TL wasn't strict.

Let's replace $$$r$$$ by $$$\frac{r}{k}$$$ and name value that we need to calculate as $$$F(r, d)$$$.

It's easy to calculate $$$F(r, d)$$$ from $$$F(r - 1, d)$$$, main trick is that we are able to calculate $$$F(r, d)$$$ from $$$F(r, d - 1), \ldots, F(r, d - k + 1)$$$.

Do to this, let's notice that:

$$$\binom{x}{d}=\sum^{i=k}_{i=0} \binom{x - k}{d - i}\binom{k}{i}$$$

It's basically Vandermonde's identity.

Let's sum both parts for $$$x$$$ divisible by $$$k$$$ and not greater than $$$(r + 1) \cdot k$$$, we will get:

$$$\binom{(r + 1)\cdot k}{d} = \sum^{i=k}_{i=1} F(r, d - i)\binom{k}{i}$$$

(I moved part with $$$i = 0$$$, because evething except $$$\binom{(r + 1)\cdot k}{d}$$$ will cancel out).

From here, we can find $$$F(r, d - 1)$$$, if we know $$$F(r, d - 2), \ldots, F(r, d - k)$$$.

Let's go back to original problem.

We will also assume that $$$k \le \sqrt{n}$$$, otherwise we can calculate answer for each query in $$$O(\frac{n}{k})$$$ with total complexity $$$O(\frac{n^2}{k})$$$.

To solve the problem, let's fix some value of $$$B$$$ and calculate all values of the form $$$F(i \cdot B, x)$$$ for $$$x \le n$$$.

To do this, let's calculate $$$F(i \cdot B, x)$$$ for $$$x < k - 1$$$, we can easily do it in $$$O(\frac{n}{k} \cdot k) = O(n)$$$ for all $$$i$$$.

Then, for each $$$i$$$ we can find the remaining values in $$$O(nk)$$$(recovering $$$F(i\cdot B, d)$$$ from $$$F(i \cdot B, d - 1), \ldots F(i \cdot B, d - k + 1)$$$), so in total this part takes:

$$$O(nk \cdot \frac{n}{kB}) = O(\frac{n^2}{B})$$$.

Then, if we have the query $$$r, d$$$, let's just find largest $$$i$$$ such that $$$i \cdot B \le r$$$ and calculate answer from $$$F(i \cdot B, d)$$$ in $$$O(B)$$$. So, total complexity for queries will be $$$O(nB)$$$. Choosing $$$B = \sqrt{n}$$$ gives the desired complexity.

another passed solution that runs in time complexity $$$\mathcal{O}(n \sqrt{q \log n / k})$$$, where $$$n = \max(r)$$$. also took a bit of constant optimization on it.

let $$$T$$$ be the block size, and $$$F_u(x) = \sum_{i = 1}^{u T}(1 + x)^{i k}$$$. After preparing the first $$$n$$$ factorials and their inverse, we iterate for each $$$u = 0, 1, \ldots, \lfloor n / k / T \rfloor$$$ and process queries with $$$u k T \leq r < (u + 1) k T$$$ using $$$[x^d] F_u(x)$$$ and at most $$$T$$$ extra binomial coefficients, so the total complexity will be $$$\mathcal{O}(n + n^2 \log n / k / T + q T)$$$, which has a minimal value when $$$T = n \sqrt{\log n / k / q}$$$.