Достаточно применять операции только к двум точкам.

Докажем, что максимальная площадь достигается, если мы сдвинем одну из точек на $$$\lfloor \frac{n}{2} \rfloor$$$ шагов вверх, а другую на $$$\lceil \frac{n}{2} \rceil$$$ шагов вправо. Для этого рассмотрим прямоугольник, описывающий получившийся треугольник после всех сдвигов точек; пусть его стороны равны соответственно $$$a$$$ и $$$b$$$. Покажем, что его максимальная площадь равна как раз $$$\frac{ab}{2}$$$. Поскольку треугольник $$$ABC$$$ вписан в наш прямоугольник, хотя бы одна его вершина должна совпасть с вершиной прямоугольника. Без ограничения общности будем считать, что это вершина $$$A$$$. Если обозначить прилежащие к ней углы за $$$\alpha$$$ и $$$\beta$$$, можно показать, что наибольшая площадь будет достигнута, когда значение $$$\text{tg}\,\alpha \cdot \text{tg}\,\beta$$$ минимально, то есть равно $$$0$$$ при $$$0 \le \alpha + \beta \lt \frac{\pi}{2}$$$.

Это как раз означает, что наибольшая площадь будет достигаться, когда хотя бы две вершины треугольника будут совпадать с вершинами рассматриваемого прямоугольника, что уже будет гарантировать нам площадь, равную половине площади прямоугольника. Последним шагом заметим, что единственным ограничением на $$$a$$$ и $$$b$$$ для нас является их сумма $$$a + b \le n$$$, а значит, нам выгодно сделать $$$a + b = n$$$ с произведением $$$ab \le \lfloor \frac{n}{2} \rfloor \lceil \frac{n}{2} \rceil$$$.

def INT(): return int(input())
def MAP(): return map(int, (input().split()))
def MAT(n): return [list(map(int, (input().split()))) for _ in range(n)]
for _ in range(INT()):
    n=INT()
    print((n>>1)*((n+1)>>1))

Обычно в задачах со степенями двойки в том или ином виде возникает идея жадной оптимизации.

Заметим, что все рассуждения из простой версии применимы и к сложной, только теперь мы должны придумать, как достичь минимальной абсолютной разности между суммой сдвигов по обеим осям. В общем виде для произвольных сдвигов эта задача является $$$\text{NP}$$$-трудной, но поскольку мы рассматриваем степени двойки, ее можно решить жадно: заведем два счетчика, равных $$$0$$$, и будем идти по отсортированному массиву степеней в обратном порядке, увеличивая счетчик с меньшей суммой на текущую степень. Идейно это работает, поскольку у малых степеней выше степень свободы при минимизации абсолютной разности. С более строгими рассуждениями вы можете ознакомиться ниже.

def INT(): return int(input())
def MAP(): return map(int, (input().split()))
def MAT(n): return [list(map(int, (input().split()))) for _ in range(n)]
for _ in range(INT()):
    n=INT()
    a=sorted(MAP(),reverse=True)
    rs0,rs1=0,0
    for el in a:
        if rs0<=rs1:rs0+=1<<el
        else:rs1+=1<<el
    print(rs0*rs1)

Подумайте, какие донаты являются весьма приятными независимо от своего положения.

Такими донатами будут все донаты, равные $$$\max(a)$$$, то есть если максимумов больше $$$k$$$, ответ заведомо равен $$$\text{NO}$$$. Но что если максимум встречается в массиве не более $$$k$$$ раз?

Заметим, что любой донат размера $$$\max(a)$$$ заведомо является весьма приятным, поскольку он, очевидно, будет не меньше среднего значения любого подмножества элементов массива. Значит, если максимум встречается в массиве более $$$k$$$ раз, ответ равен $$$\text{NO}$$$. В противном случае отсортируем массив $$$a$$$ по неубыванию и разрежем его на два массива $$$b$$$ и $$$c$$$ длины $$$n - k$$$ и $$$k$$$ соответственно. Теперь выпишем сначала элементы $$$c$$$ в прямом, а затем элементы $$$b$$$ в обратном порядке.

Покажем, что полученный массив удовлетворяет требуемому условию. Поскольку элементы $$$c$$$ идут по неубыванию, каждый из них не меньше всех предыдущих, а значит, и не меньше их среднего арифметического, поэтому все первые $$$k$$$ донатов точно окажутся весьма приятными. Теперь рассмотрим первый элемент второй части $$$b_1$$$. Среднее значение предшествующего ему префикса будет строго больше $$$b_1$$$, так как все элементы $$$c$$$ не меньше него, при этом сам $$$b_1$$$ меньше максимума, содержащегося в $$$c$$$. Все последующие донаты $$$b_2, b_3, \dots$$$ также не будут весьма приятными, поскольку элементы $$$b$$$ идут по невозрастанию и среднее арифметическое префикса каждый раз будет оставаться строго больше очередного рассматриваемого элемента.

Асимптотика решения $$$O(n \log n)$$$ на сортировку.

def INT(): return int(input())
def MAP(): return map(int, (input().split()))
def MAT(n): return [list(map(int, (input().split()))) for _ in range(n)]
for _ in range(INT()):
    n,k=MAP()
    a=sorted(MAP())
    if a.count(a[-1])>k:
        print('nO')
        continue
    b=a[:n-k]
    c=a[n-k:]
    b=reversed(b)
    print('yEs')
    print(*c,*b)

$$$\gcd(a, x) = 1 \iff \gcd(a, a + x) = 1$$$

На самом деле нам хватит не более $$$n$$$ операций.

Постулат Бертрана

Заметим, что, если массив состоит только из простых чисел, он не является омерзительным, поскольку для любой пары элементов их $$$\gcd$$$ будет равен либо $$$1$$$, либо им самим.

Давайте попробуем заменить каждый из элементов $$$a_i$$$ на наименьшее простое $$$p \gt a_i$$$. Очевидно, что мы не израсходуем лимит операций, поскольку раз $$$\gcd(a_i, p) = 1$$$, то и $$$\gcd(a[i], p - a[i]) = 1$$$, то есть на одну замену мы потратим ровно $$$1$$$ операцию.

Таким образом, единственным оставшимся ограничением для нас является сумма элементов полученного массива $$$b$$$. Однако из постулата Бертрана следует, что для любого положительного $$$n$$$ отрезок $$$[n + 1, 2n]$$$ содержит хотя бы одно простое число, а значит, после замены сумма всех элементов массива $$$b$$$ не превысит $$$\sum (2 \cdot a_i) = 2 \cdot \sum a_i$$$, что нам и нужно.

Для вычисления ближайшего простого достаточно предподсчитать решето Эратосфена и сделать на нем один обратный проход либо искать бинпоиском по отсортированному массиву простых чисел, что, в зависимости от выбранного подхода, без учета предподсчета, даст асимптотику либо $$$O(n)$$$, либо $$$O(n \log n)$$$.

def INT(): return int(input())
def MAP(): return map(int, (input().split()))
def MAT(n): return [list(map(int, (input().split()))) for _ in range(n)]
MAX_A=100_000
prime=[1]*(MAX_A+100)
prime[0]=0
prime[1]=0
for i in range(2,int(MAX_A**0.5)+10):
    if prime[i]:
        for j in range(i*i,MAX_A+100,i):
            prime[j]=0
next_prime=[0]*(MAX_A+100)
p=-1
for i in range(len(prime)-1,0,-1):
    next_prime[i]=p
    if prime[i]:
        p=i
for _ in range(INT()):
    n=INT()
    a=list(MAP())
    b=[next_prime[el] for el in a]
    print(*b)

Решите задачу C1.

Подумайте, в каких случаях нам точно хватит не более 2 операций.

анартреБ талутсоП

Для начала разберем и тут же забудем про тривиальные случаи с $$$\mathrm{dist}(a, b) \lt 2$$$.

Теперь заметим, что, если отрезок $$$[a, b]$$$ содержит хотя бы одно простое, нам потребуется ровно $$$2$$$ операции. Чтобы увидеть это, рассмотрим в качестве промежуточного числа наибольшее среди этих простых $$$p$$$. Число $$$b$$$ не может делить $$$p$$$, поскольку мы знаем, что оно строго его больше (иначе бы мы смогли попасть из $$$a$$$ в $$$b$$$ за один шаг), но при этом, если бы оно было равно хотя бы $$$2p$$$, по постулату Бертрана в отрезке $$$[p+1, b]$$$ нашлось бы простое $$$q$$$, большее $$$p$$$, что невозможно, так как мы выбрали максимальное среди всех простых на отрезке. Значит, поскольку $$$p$$$ взаимнопросто и с $$$a$$$, и с $$$b$$$, мы можем перейти сначала в него, а затем сразу в $$$b$$$.

Осталось покрыть все случаи, когда $$$\gcd(a, b) \gt 1$$$ и отрезок $$$[a, b]$$$ не содержит простых. Поскольку $$$a \le 10^5$$$, мы можем сделать это, просто перебрав все такие пары, отсортированные по возрастанию длины, и построив на них тривиальную динамику. Это зайдет по времени, поскольку среднее расстояние между простыми числами, не превышающими $$$n$$$, равно примерно $$$\log(n)$$$, и сами простые распределены достаточно равномерно, поэтому общая асимптотика предподсчета будет примерно $$$O(m \log^2 m)$$$, где $$$m \le 10^5$$$.

Таким образом, мы получаем решение, похожее на решение $$$\mathrm{C1}$$$: разбираем за $$$O(1)$$$ тривиальные случаи, затем с помощью решета Эратосфена проверяем, верно ли, что наибольшее простое, меньшее $$$b$$$, больше $$$a$$$. Если больше, то строим ответ в $$$2$$$ операции, иначе берем его из нашего дп.

Ну или вы можете просто угадать, что $$$\mathrm{dist}(a, b) \le 2$$$ при $$$b - a \ge \text{small const}$$$, но это неинтересно. На самом деле эта задача в общем виде является открытой проблемой, и, судя по всему, $$$\mathrm{dist}(a, b)$$$ никогда не превышает $$$3$$$. Если у вас появится содержательное доказательство обратного, можете поделиться им в комментариях.

def INT(): return int(input())
def MAP(): return map(int, (input().split()))
def MAT(n): return [list(map(int, (input().split()))) for _ in range(n)]
from collections import defaultdict
from bisect import bisect_left
from math import gcd
 
MAXN=100021
sieve=[1]*(MAXN+1)
 
for p in range(2,int(MAXN**0.5)+2):
    if sieve[p]:
        sieve[p*p::p]=[0]*len(sieve[p*p::p])
        
np=[-1]*MAXN
loc=100019
for i in range(MAXN):
    if sieve[i]:loc=i
    np[i]=loc
 
primes=[i for i in range(2,MAXN+1) if sieve[i]]
pp=[]
 
for p1,p2 in zip(primes,primes[1:]):
    for x in range(p1+1,p2-1):
        for y in range(x+1,p2):
            pp.append((x,y))
 
pp.sort(key=lambda p:p[1]-p[0])
 
dp0=defaultdict(dict)
dp=defaultdict(dict)
 
for x,y in pp:
    if gcd(x,y)==1:
        dp0[x][y],dp[x][y]=1,y
        continue
    best=100
    ne=-1
    for z in range(x+1,y):
        dist=dp0[x][z]+dp0[z][y]
        if dist<best:
            best,ne=dist,dp[x][z]
            if dist==2:
                break
    dp0[x][y],dp[x][y]=best,ne
 
def path(x,y):
    rs=[]
    cur=x
    while cur!=y:
        cur=dp[cur][y]
        rs.append(cur)
    return rs
 
for _ in range(INT()):
    x,y=MAP()
    if x==y:
        print(0)
        print()
        continue
    if gcd(x,y)==1:
        print(1)
        print(y-x)
        continue
    p=np[min(y,MAXN-1)]
    if gcd(p,y)>1:p=np[p-1]
    if x<p:
        print(2)
        print(p-x,y-p)
    else:
        rs=[x]+path(x,y)
        print(len(rs)-1)
        for i in range(len(rs)-1):
            print(rs[i+1]-rs[i],end=' ')
        print()

Придумайте, как передать $$$n - 2$$$ бита.

Кажется полезным попробовать изучить, как применяемая ПАБ операция влияет на графы с простой структурой.

В ожидаемом решении переданный граф почти всегда является деревом.

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

Отсюда сразу же появляется следующая идея решения: построим двудольный граф, в котором вершина $$$i$$$ будет кодировать бит $$$s_{i - 1}$$$ в зависимости от того, получит ли она тот же цвет в двудольной раскраске, что и вершина $$$1$$$. В качестве двудольного графа проще всего использовать дерево.

Однако у нас остается один случай, когда строка состоит только из единиц, ведь в таком случае мы должны построить связный двудольный граф, в котором все вершины должны быть покрашены в один цвет, что, очевидно, невозможно. Чтобы закодировать его, передадим ПАБ любой граф, не являющийся двудольным, например, нам подойдет дерево, в котором мы замкнули цикл $$$1$$$—$$$2$$$—$$$3$$$. Остается доказать, что ПАБ не сможет сделать такой граф двудольным за любое число операций.

Докажите, что $$$n-1$$$ бит является точной верхней границей количества информации, которую может передать ЛКП.

def INT(): return int(input())
def MAP(): return map(int, (input().split()))
def MAT(n): return [list(map(int, (input().split()))) for _ in range(n)]
def dfs(g):
    l=[1]
    vis=[0]*(n+1)
    dd=[1]*(n+1)
    d=1
    while l:
        cur=l.pop()
        if vis[cur]:d-=1
        else:
            vis[cur]=1
            dd[cur]=d%2
            d+=1
            l.append(cur)
            for nei in g[cur]:
                if not vis[nei]:
                    l.append(nei)
    return dd[2:]
ty=input()
for _ in range(INT()):
    if ty=='first':
        n=INT()
        s=input()
        if '0' not in s:
            print(n)
            for i in range(n-1):
                print(1,2+i)
            print(2,3)
            continue
        print(n-1)
        lst=s.index('0')+2
        for i in range(2,n+1):
            if s[i-2]=='0':
                print(1,i)
            else:print(lst,i)
    if ty=='second':
        n,m=MAP()
        g=[[] for i in range(n+1)]
        for i in range(m):
            u,v=MAP()
            g[u].append(v)
            g[v].append(u)
        if m==n:
            print('1'*(n-1))
            continue
        print(*dfs(g),sep='')

Граф $$$G$$$ не обязательно связен.

Какое максимальное количество уникальных отдельных компонент могут связывать секретные ребра?

[ SYS_MSG: ANALYSIS PROTOCOL INITIATED ]

Для начала заметим, что оба загаданных ребра обязаны соединять одну и ту же пару компонент связности графа $$$G$$$. Действительно, зафиксируем двудольную раскраску каждой компоненты. Добавление ребра между двумя разными компонентами всегда сохраняет двудольность, поскольку мы можем инвертировать раскраску одной из них. При этом каждое добавленное ребро задает требование к относительной инверсии раскрасок двух компонент. Если бы загаданные ребра соединяли разные пары компонент, то мы могли бы независимо выполнить все эти требования, и граф остался бы двудольным. Не соединять компоненты ребра также не могут, поскольку в таком случае они обязаны были бы соединять вершины разных цветов, и граф $$$G'$$$ также остался бы двудольным, а значит, оба ребра соединяют одну и ту же пару компонент.

Теперь пронумеруем вершины, последовательно обходя компоненты связности, а внутри каждой компоненты используя $$$\text{BFS}$$$. Важное свойство такой нумерации заключается в том, что любой префикс вершин внутри одной компоненты образует связный граф: у каждой вершины, кроме первой, уже присутствует ее родитель в $$$\text{BFS}$$$.

Первым бинарным поиском найдем вершину $$$u$$$, являющуюся концом одного из загаданных ребер. Для этого будем спрашивать, является ли двудольным подграф, состоящий из первых $$$k$$$ вершин. Он будет двудольным до тех пор, пока в него не попадут все концы обоих загаданных ребер, после чего в нем появится нечетный цикл, поэтому для ее поиска мы можем использовать бинарный поиск, потратив не более $$$\log 2000 = 11$$$ запросов.

Перенумеруем вершины еще раз, поставив первой компоненту, содержащую $$$u$$$, и запустив $$$\text{BFS}$$$ уже из нее, после чего аналогичным бинарным поиском найдем одну из вершин $$$v$$$ во второй компоненте, также являющуюся концом одного из загаданных ребер.

Теперь проверим запросом второго типа, является ли ребро $$$u$$$—$$$v$$$ одним из загаданных. Если да, то мы уже победили. В противном случае воспользуемся тем, что $$$u$$$ и $$$v$$$ не могут быть концами одного и того же ребра, а значит загаданные ребра не имеют общих концов, и в каждой из двух компонент есть ровно по два конца загаданных ребер. Один из них в каждой компоненте мы уже нашли.

Осталось найти второй конец в одной из компонент. Для этого выберем одну из двух компонент, перенумеруем ее вершины с помощью $$$\text{BFS}$$$ из ее найденной вершины и снова запустим бинарный поиск. На этот раз в каждом запросе будем рассматривать префикс выбранной компоненты вместе со всеми вершинами другой компоненты.

Последний бинарный поиск может быть оптимизирован до не более чем $$$10$$$ запросов, если для него мы выберем меньшую из двух компонент. Таким образом в худшем случае нам потребуется всего $$$11 + 11 + 1 + 10 = 33$$$ запроса.

> TASK COMPLETED. TERMINATING PROCESS.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi = pair<int, int>;

bool query(vector<int>& v) {
    if (v.empty()) return true;

    cout << "? 1 " << v.size();
    for (auto i : v) cout << ' ' << i;
    cout << endl;

    int x;
    cin >> x;

    if (x == -1) exit(0);

    return x;
}

int bs(vector<int>& v, vector<int>& include) {
    int lo = 0;
    int hi = v.size();

    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;

        vector<int> ask = include;
        for (int i = 0; i < mid; i++) {
            ask.push_back(v[i]);
        }

        if (query(ask)) lo = mid;
        else hi = mid;
    }

    return v[lo];
}

void solve(void) {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> comp(n + 1);
    vector<vector<int>> component;
    vector<int> dfs_order;

    {
        vector<bool> vis(n + 1);

        auto dfs = [&](auto&& self, int i) -> void {
            if (vis[i]) return;

            component.back().push_back(i);
            vis[i] = true;
            comp[i] = component.size();

            dfs_order.push_back(i);

            for (auto u : adj[i]) {
                self(self, u);
            }
        };

        for (int i = 1; i <= n; i++) {
            if (vis[i]) continue;

            component.emplace_back();
            dfs(dfs, i);
        }
    }

    vector<int> lol;
    int a = bs(dfs_order, lol);

    vector<int> out;

    for (auto i : dfs_order) {
        if (comp[i] != comp[a]) {
            out.push_back(i);
        }
    }

    vector<int> in;

    {
        vector<bool> vis(n + 1);

        auto dfs = [&](auto&& self, int i) -> void {
            if (vis[i]) return;

            vis[i] = true;
            in.push_back(i);

            for (auto u : adj[i]) {
                self(self, u);
            }
        };

        dfs(dfs, a);
    }

    int b = bs(in, out);
    int c = bs(out, in);

    cout << "? 2 " << a << ' ' << c << endl;

    int r;
    cin >> r;

    if (r) cout << "! " << a << ' ' << c << endl;
    else cout << "! " << b << ' ' << c << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) solve();

    return 0;
}

Посмотрите на процесс изменений элементов множества как на последовательность операций с декой.

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

Для эффективного пересчета статистик деки вы можете использовать какую-то известную структуру данных.

Решение скоро будет опубликовано.

#include <bits/stdc++.h>
using namespace std;

template <typename T>
T mod_inv_in_range(T a, T m) {
    T x = a, y = m;
    T vx = 1, vy = 0;

    while (x) {
        T k = y / x;
        y %= x;
        vy -= k * vx;

        swap(x, y);
        swap(vx, vy);
    }

    return vy < 0 ? m + vy : vy;
}

template <int MOD_>
struct modnum {
    static constexpr int MOD = MOD_;

private:
    int v;

public:
    modnum() : v(0) {}

    modnum(int64_t v_) : v(int(v_ % MOD)) {
        if (v < 0) v += MOD;
    }

    explicit operator int() const {
        return v;
    }

    friend ostream& operator<<(ostream& out, const modnum& n) {
        return out << int(n);
    }

    friend istream& operator>>(istream& in, modnum& n) {
        int64_t v_;
        in >> v_;
        n = modnum(v_);
        return in;
    }

    friend bool operator==(const modnum& a, const modnum& b) {
        return a.v == b.v;
    }

    friend bool operator!=(const modnum& a, const modnum& b) {
        return a.v != b.v;
    }

    modnum inv() const {
        modnum res;
        res.v = mod_inv_in_range(v, MOD);
        return res;
    }

    friend modnum inv(const modnum& m) {
        return m.inv();
    }

    modnum neg() const {
        modnum res;
        res.v = v ? MOD - v : 0;
        return res;
    }

    friend modnum neg(const modnum& m) {
        return m.neg();
    }

    modnum operator-() const {
        return neg();
    }

    modnum operator+() const {
        return modnum(*this);
    }

    modnum& operator++() {
        v++;
        if (v == MOD) v = 0;
        return *this;
    }

    modnum& operator--() {
        if (v == 0) v = MOD;
        v--;
        return *this;
    }

    modnum& operator+=(const modnum& o) {
        v -= MOD - o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }

    modnum& operator-=(const modnum& o) {
        v -= o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }

    modnum& operator*=(const modnum& o) {
        v = int(int64_t(v) * int64_t(o.v) % MOD);
        return *this;
    }

    modnum& operator/=(const modnum& o) {
        return *this *= o.inv();
    }

    friend modnum operator++(modnum& a, int) {
        modnum r = a;
        ++a;
        return r;
    }

    friend modnum operator--(modnum& a, int) {
        modnum r = a;
        --a;
        return r;
    }

    friend modnum operator+(const modnum& a, const modnum& b) {
        return modnum(a) += b;
    }

    friend modnum operator-(const modnum& a, const modnum& b) {
        return modnum(a) -= b;
    }

    friend modnum operator*(const modnum& a, const modnum& b) {
        return modnum(a) *= b;
    }

    friend modnum operator/(const modnum& a, const modnum& b) {
        return modnum(a) /= b;
    }
};

const int MOD = 1e9 + 7;
using mint = modnum<MOD>;

pair<mint, mint> merge(
    const pair<mint, mint>& a,
    const pair<mint, mint>& b
) {
    return make_pair(
        a.second * b.second - (a.second - a.first) * (b.second - b.first),
        a.second * b.second
    );
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, m;
        string input;
        cin >> m >> input;

        mint correction = 0, ways = 1;

        for (int i = m - 1; i >= 0; i--) {
            correction += ways;
            if (input[i] == '0') ways *= 2;
        }

        rotate(input.begin(), input.begin() + 1, input.end());
        n = count(input.begin(), input.end(), '1');

        deque<pair<mint, mint>> a(m, make_pair(1, 2));

        for (int x = 0; x < m; x++) {
            if (input[x] == '1') {
                a[(x + 1) % m] = make_pair(1, 1);
            }
        }

        mint curprod = 1, curterm = 0, prody = 1;

        for (auto& [x, y] : a) {
            curprod *= x;
            curterm = curterm * y + curprod;
            prody *= y;
        }

        mint ans = 0;

        for (int i = 0; i < m; i++) {
            ans += curterm;

            if (i == m - 1) break;

            curprod /= a[0].first;
            curterm /= a[0].first;

            a[0] = merge(a.back(), a[0]);

            curprod *= a[0].first;
            curterm *= a[0].first;
            curterm -= curprod;

            curterm /= a.back().second;
            curprod /= a.back().first;

            a.pop_back();

            curterm += prody - curprod;
            curterm *= a.back().first / a.back().second;

            pair<mint, mint> tmp = a.back();
            a.pop_back();
            a.push_front(tmp);
        }

        cout << ans - correction << '\n';
    }

    return 0;
}

What happens when $$$k$$$ is even? What happens when $$$k$$$ is odd?

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    a = list(map(lambda x: int(x) % 2, input().split()))
    b = list(map(lambda x: int(x) % 2, input().split()))
 
    if k % 2 == 0:
        print("YES" if a.count(0) <= b.count(0) else "NO")
    else:
        print("YES" if b.count(0) <= a.count(0) else "NO")

What must all strings whose answer is ``NO'' look like?

import sys
 
for _ in range(int(input())):
    n = int(input())
    print("?", 1, n)
    sys.stdout.flush()
    ct = int(input())
    if ct == 0:
        print("! NO")
        continue
    print("?", 1, ct)
    sys.stdout.flush()
    x = int(input())
    if x == ct:
        print("! NO")
    else:
        print("! YES")

Where is it useful to "cut" the array to decrease the gap value?

Consider separately the cases where the gap value is unique, occurs twice, and occurs three or more times.

#include <bits/stdc++.h>
using namespace std;
 
template <class T, T (*f)(T, T), T (*unit)()> struct Seg {
	vector<T> s; int n;
	Seg(int n = 0, T def = unit()) : s(2*n, def), n(n) {}
	void update(int pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(int b, int e) { // query [b, e)
		T ra = unit(), rb = unit();
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = f(ra, s[b++]);
			if (e % 2) rb = f(s[--e], rb);
		}
		return f(ra, rb);
	}
 
	T get(int x) { return s[x+n]; }
};
 
using T = int;
T f(T a, T b) { return max(a, b); }
T unit() { return 0; }
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
 
        Seg<T, f, unit> rmq(n - 1);
        vector<int> mx;
        int val = -1;
        for (int i = 0; i < n - 1; i++) {
            rmq.update(i, abs(a[i + 1] - a[i]));
            if (abs(a[i + 1] - a[i]) > val)
                mx = {i}, val = abs(a[i + 1] - a[i]);
            else if (abs(a[i + 1] - a[i]) == val)
                mx.push_back(i);
        }
 
        if (mx.size() >= 3) {
            cout << val << "\n";
            continue;
        }
 
        auto calc = [&](int i, int j) {
            int v2 = 2 * rmq.query(i, j);
            if (i > 0) v2 = max({v2, rmq.query(0, i - 1), abs(a[i - 1] - 2 * a[j])});
            if (j < n - 1) v2 = max({v2, rmq.query(j + 1, n - 1), abs(a[j + 1] - 2 * a[i])});
            return v2;
        };
 
        if (mx.size() == 2) {
            int i = mx[0], j = mx[1];
            cout << min(val, calc(i + 1, j)) << "\n";
            continue;
        }
 
        int i = mx[0];
        for (int j = 0; j <= i; j++) {
            val = min(val, calc(j, i));
        }
        for (int j = i + 1; j < n; j++) {
            val = min(val, calc(i + 1, j));
        }
 
        cout << val << "\n";
    }
}

Suppose that $$$|S|\ge 2$$$. Can you say anything about the minimum number of unstable elements in it?

Consider DP.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
 
const ll MOD = 998244353;
 
mt19937 rng(time(0));
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		vector<int> a(n);
		rep(i,0,n) cin >> a[i];
 
		vector<bool> s;
		s.push_back(true);
		for (int i = 1; i < n; i++) {
			if (a[i] == a[i - 1] + 1) {
				s.push_back(1);
			} else if (a[i] == a[i - 1] + 2) {
				s.push_back(0); s.push_back(1);
			} else {
				s.push_back(0); s.push_back(0); s.push_back(1);
			}
		}
		s.push_back(0);
 
		int m = sz(s);
		assert(m < 3 * n);
		ll ans = (1ll * (n + 1) * n / 2) % MOD; // n + (n C 2)
		vector<ll> dp1(m + 1, 1); // ((1110)|(110))*
		vector<ll> dp2(m + 1, 0); // 10((1110)|(110))*
		for (int i = 1; i < m; i++) {
			if (s[i - 1]) dp2[i + 1] = 1;
			if (i >= 2 && s[i - 1] && s[i - 2]) {
				dp1[i + 1] += dp1[i - 2];
				dp2[i + 1] += dp2[i - 2];
			}
			if (i >= 3 && s[i - 1] && s[i - 2] && s[i - 3]) {
				dp1[i + 1] += dp1[i - 3];
				dp2[i + 1] += dp2[i - 3];
			}
			dp1[i + 1] %= MOD;
			dp2[i + 1] %= MOD;
			ans += dp1[i + 1] - 1 + dp2[i + 1];
		}
		for (int i = 1; i < m; i++) {
			if (s[i - 1]) { // can end in 10
				ans += dp1[i - 1] + dp2[i - 1];
			}
		}
		s.push_back(0); s.push_back(0);
		// we've overcounted 2 * 10, 110, 101 substrings
		for (int i = 0; i < m; i++) {
			if (s[i]) ans -= 2;
			if (s[i] && s[i + 1]) ans -= 1;
			if (s[i] && s[i + 2]) ans -= 1;
		}
 
		cout << ((ans + MOD) % MOD) << "\n";
 
	}
 
}

What should the array look like after applying your operations? (Equivalently, what operations should you apply?)

Consider casing on the second largest element.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	while (t--) {
		int n; ll L; cin >> n >> L;
		vector<ll> a(n);
		rep(i,0,n) cin >> a[i];
		sort(all(a));
		if (L == 1) {
			cout << accumulate(all(a), 0ll) - a[n - 1] << "\n";
			continue;
		}
		if (a[n - 1] * a[n - 2] < L) {
			cout << "0\n";
			continue;
		}
		ll x = a[n - 1];
		ll y = 1;
		while ((y + 1) * (y + 1) < L) ++y;
		int start = n - 2;
		ll curr = 0;
 
		auto mx = [&](ll z) {
			if (z == 0) return 0ll;
			return max(0ll, x - (L - 1) / z);
		};
 
		while (start >= 0 && a[start] >= y) {
			curr += (a[start] - y);
			--start;
		}
		ll ans = curr + mx(y);
		--y;
		for (; y >= 0; --y) {
			curr += (n - 2 - start);
			while (start >= 0 && a[start] >= y) --start;
			ans = min(ans, curr + mx(y));
		}
		cout << ans << "\n";
	}
}

The graph is quite huge. Do you need all of it?

Try to show that you only need to keep around $$$O(m + n)$$$ edges while preserving the shortest path.

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
 
mt19937 rng(time(0));
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	while (t--) {
		int n, m; cin >> n >> m;
		int w, x, y, z; cin >> w >> x >> y >> z; --w, --x, --y, --z;
		vector<array<int, 2>> edges(m);
		vector<array<int, 2>> v;
		rep(i,0,n) {
			v.push_back({w, i});
			v.push_back({y, i});
			v.push_back({i, i});
		}
 
		rep(i,0,m) {
			int a, b; cin >> a >> b; --a, --b;
			edges[i] = {a, b};
			v.push_back({a, b});
			v.push_back({b, a});
		}
 
		sort(all(v));
		v.resize(unique(all(v)) - v.begin());
 
		int N = sz(v);
 
		auto find = [&](int i, int j) -> int {
			return lower_bound(all(v), array{i, j}) - v.begin();
		};
 
		vector<vector<int>> h(N);
		for (auto [a, b] : edges) {
			int wa = find(w, a), wb = find(w, b),
			    ya = find(y, a), yb = find(y, b),
			    aa = find(a, a), ab = find(a, b),
			    ba = find(b, a), bb = find(b, b);
 
			for (auto [p1, p2] : vector{array{wa, wb}, {ya, yb}, {aa, ab}, {ba, bb}, {ab, ba}}) {
				h[p1].push_back(p2);
				h[p2].push_back(p1);
			}
		}
 
		vector<int> dist(N, -1);
		queue<pair<int, int>> q;
		q.emplace(find(w, x), 0);
		while (!q.empty()) {
			auto [vtx, d] = q.front();
			q.pop();
			if (dist[vtx] >= 0) continue;
			dist[vtx] = d;
			for (auto a : h[vtx]) {
				if (dist[a] < 0) q.emplace(a, d + 1);
			}
		}
 
		cout << dist[find(y, z)] << "\n";
	}
}

Can you upper bound the answer?

The answer is at most $$$2\cdot 25 - 1 = 49$$$. Can you use this fact to construct a solution running in time $$$O(n\cdot 2^{49})$$$?

Please refer to the previous hint first. Can you make your solution faster to $$$O(n\cdot \varphi^{49})$$$?

Consider Meet In The Middle.

#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define sq(a) ((a)*(a))
 
#define per(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rep(i,a,b) for (int i=a; i<b; i++)
 
#define FOR(i,a,b) for (int i=a; i<b; i++)
#define F0R(i,a) for (int i=0; i<a; i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= a; i--)
#define R0F(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << endl, 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << endl;
#define _ << " _ " <<
 
#define ll long long
 
template<class T> bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool ckmax(T&a, T&b) { bool B = a < b; a = max(a,b); return B; }
 
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ld,ld> pld;
typedef complex<ld> cd;
 
typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;
 
const ld PI = acos(-1.0);
const ld EPS = 1e-7;
const int MOD = 998244353;
 
const int MX = 25;
const int BIG = 100;
 
void solve() {
  int n; cin >> n;
  vector<int> a(n);
  rep(i, 0, n) {
    cin >> a[i];
  }
  
  if (*min_element(all(a)) == 0) {
      cout << "0" << "\n";
      return;
  }
 
  vector<pair<int, int>> seen;
 
  auto left = [&](auto && self, int i, int cost, int v) {
    int op = v ^ a[i];
    seen.push_back({op, cost});
 
    if (i == 0) return;
    if (cost + 1 <= MX) {
      self(self, i - 1, cost + 1, op);
    }
 
    if (cost + 2 <= MX) {
      self(self, i - 1, cost + 2, v);
    }
  };
 
  int best = BIG;
 
  auto right = [&](auto && self, int i, int cost, int v) {
    int op = v ^ a[i];
 
    auto it = upper_bound(all(seen), mp(op, -1));
    if (it != seen.end()) {
      auto [u, v] = *it;
      if (u == op) best = min(best, cost + v - 1);
    }
 
    if (i + 1 == n) return;
    if (cost + 1 <= MX) {
      self(self, i + 1, cost + 1, op);
    }
 
    if (cost + 2 <= MX) {
      self(self, i + 1, cost + 2, v);
    }
  };
 
  if (n > MX) {
    best = 2 * MX - 1;
  }
 
  rep(i, 0, n - 1) {
    seen.clear();
    seen.reserve(514228);
 
    left(left, i, 1, 0);
    assert (sz(seen) <= 514228);
    sort(all(seen));
 
    right(right, i + 1, 1, 0);
  }
 
  if (best == BIG) best = -1;
  cout << best << endl;
}
 
int32_t main() { FAST
  int t;
  cin >> t;
 
  while (t--) solve();
 
  return 0;
}

Recall how one wins in Nim. Next, note that this problem essentially reduces to solving each prefix quickly.

This is, under the hood, a matroid problem. For each new value, try to construct an "exchange" graph using the matroid basis exchange property to determine if it's possible to insert the element.

Please refer to the previous hint first. It gives an $$$O(n^3\log^2 n)$$$ time algorithm. To improve this, consider if you need the full graph or if you can "thin" it.

Make sure your XOR basis operations are of optimal complexity.

#include <bits/stdc++.h>
using namespace std;
 
constexpr int LOG = 14;
 
struct xor_basis {
	vector<int> inner;
	vector<int> base;
	vector<int> comb;
 
	xor_basis(): base(LOG), comb(LOG) {}
 
	int represent(int mask) {
		int c = 0;
		for (int i = 0; i < LOG; i++) {
			if (!(mask & (1 << i))) continue;
			if (!base[i]) return -1;
			mask ^= base[i], c ^= comb[i];
		}
		return c;
	}
 
	bool independent(int mask) {
		for (int i = 0; i < LOG; i++) {
			if (!(mask & (1 << i))) continue;
			if (!base[i]) return true;
			mask ^= base[i];
		}
		return false;
	}
 
	void swap(int out, int in) {
		int pos = find(inner.begin(), inner.end(), out) - inner.begin();
		int c = represent(in);
		inner[pos] = in;
		for (int i = 0; i < LOG; i++) if (comb[i] >> pos & 1) comb[i] ^= c ^ (1 << pos);
	}
 
	bool insert(int mask) {
		int sv = mask, c = 1 << inner.size();
		for (int i = 0; i < LOG; i++) {
			if (!(mask & (1 << i))) continue;
 
			if (!base[i]) {
				base[i] = mask, comb[i] = c, inner.push_back(sv);
				return true;
			}
			mask ^= base[i], c ^= comb[i];
		}
		return false;
	}
};
 
void solve() {
    int n; cin >> n;
	vector<int> a(n), s(n);
	for (int i = 0; i < n; i++) cin >> a[i];
 
	vector<xor_basis> bases;
	bases.emplace_back();
 
	auto add = [&](int idx) {
		for (int i = 0; i < bases.size(); i++) {
	        if (bases[i].independent(s[idx])) {
	            bases[i].insert(s[idx]); // special case
	            return;
	        }
	    }
 
		int N = 2*n + bases.size();
 
		vector<int> smap(N, -1);
		for (int i = 0; i < bases.size(); i++) for (auto x : bases[i].inner) smap[x - 1] = i;
		for (int i = 0; i < bases.size(); i++) smap[i + 2*n] = i;
 
		vector<int> par(N, -2);
		vector<int> q;
		q.push_back(s[idx] - 1); par[s[idx] - 1] = -1;
		int found = -1;
		for (int head = 0; head < q.size(); head++) {
			int vtx = q[head];
 
            int x = vtx + 1, next_idx = (smap[vtx] + 1) % bases.size();
 
            if (x == s[idx] || bases.size() > 1) {
                if (bases[next_idx].independent(x)) {
                    par[2 * n + next_idx] = vtx, found = 2 * n + next_idx;
                    break;
                }
				int z = bases[next_idx].represent(x);
				for (int p = 0; p < bases[next_idx].inner.size(); p++) {
					if (z >> p & 1) {
						int y = bases[next_idx].inner[p] - 1;
						if (par[y] == -2) par[y] = vtx, q.push_back(y);
					}
				}
            }
		}
 
		if (found < 0) { // easy case -- no path
			bases.emplace_back();
			bases.back().insert(s[idx]);
			return;
		} else {
			int p = par[found];
			assert(bases[smap[found]].insert(p + 1));
			while (p + 1 != s[idx]) {
				int prev = par[p];
				bases[smap[p]].swap(p + 1, prev + 1);
				p = prev;
			}
		}
	};
 
	auto print_sol = [&]() {
		cout << bases.size() << "\n";
		for (const auto& base : bases) {
			cout << base.inner.size();
			for (auto x : base.inner) {
				cout << " " << x;
			}
			cout << "\n";
		}
	};
 
	for (int i = 0; i < n; i++) {
		int k = (i == 0 ? 0 : bases.size());
		s[i] = a[i] ^ k;
		add(i);
	}
	print_sol();
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
    int t; cin >> t;
    while (t--) solve();
}