It is sufficient to apply operations to only two points.

Let us prove that the maximum area is achieved if we shift one of the points by $$$\lfloor \frac{n}{2} \rfloor$$$ steps up, and the other by $$$\lceil \frac{n}{2} \rceil$$$ steps to the right. To do this, consider the bounding rectangle of the resulting triangle after all point shifts; let its side lengths be $$$a$$$ and $$$b$$$, respectively. We will show that its maximum area is precisely $$$\frac{ab}{2}$$$. Since triangle $$$ABC$$$ is inscribed in our rectangle, at least one of its vertices must coincide with a vertex of the rectangle. Without loss of generality, let this be vertex $$$A$$$. If we denote the angles adjacent to it by $$$\alpha$$$ and $$$\beta$$$, it can be shown that the maximum area is achieved when the value $$$\tan \alpha \cdot \tan \beta$$$ is minimized, which means it is equal to $$$0$$$ for $$$0 \le \alpha + \beta \lt \frac{\pi}{2}$$$.

This precisely implies that the maximum area is achieved when at least two vertices of the triangle coincide with the vertices of the bounding rectangle, which already guarantees us an area equal to half the area of the rectangle. As the final step, note that the only constraint on $$$a$$$ and $$$b$$$ is their sum $$$a + b \le n$$$, which means it is optimal to set $$$a + b = n$$$ with the product $$$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))

Usually, in problems involving powers of two, the idea of greedy optimization arises in one form or another.

Notice that all arguments from the easy version apply to the hard version as well, except now we must determine how to achieve the minimum absolute difference between the sum of shifts along both axes. In general, for arbitrary shifts, this problem is $$$\text{NP}$$$-hard, but since we are considering powers of two, it can be solved greedily: initialize two counters equal to $$$0$$$, and iterate over the sorted array of powers in reverse order, adding the current power to the counter with the smaller sum. Conceptually, this works because smaller powers have more degrees of freedom when minimizing the absolute difference. You can read the more rigorous justification below.

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)

Think about which donations are very pleasant regardless of their position.

Such donations will be all donations equal to $$$\max(a)$$$, which means that if there are more than $$$k$$$ maximums, the answer is definitely $$$\text{NO}$$$. But what if the maximum appears in the array at most $$$k$$$ times?

Notice that any donation of size $$$\max(a)$$$ is definitely very pleasant, since it will obviously be no less than the average value of any subset of the array elements. Thus, if the maximum occurs in the array more than $$$k$$$ times, the answer is $$$\text{NO}$$$. Otherwise, sort the array $$$a$$$ in non-decreasing order and split it into two arrays $$$b$$$ and $$$c$$$ of length $$$n - k$$$ and $$$k$$$, respectively. Now write out the elements of $$$c$$$ in forward order, and then the elements of $$$b$$$ in reverse order.

Let us show that the resulting array satisfies the required condition. Since the elements of $$$c$$$ are in non-decreasing order, each of them is not less than all preceding ones, and therefore not less than their arithmetic mean; thus, all of the first $$$k$$$ donations will definitely be very pleasant. Now consider the first element of the second part, $$$b_1$$$. The average value of the prefix preceding it will be strictly greater than $$$b_1$$$, since all elements of $$$c$$$ are not less than it, while $$$b_1$$$ itself is strictly smaller than the maximum contained in $$$c$$$. All subsequent donations $$$b_2, b_3, \dots$$$ will also not be very pleasant, because the elements of $$$b$$$ are in non-increasing order and the arithmetic mean of the prefix will strictly exceed the next considered element each time.

The complexity of the solution is $$$O(n \log n)$$$ for sorting.

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$$$

In fact, no more than $$$n$$$ operations will be sufficient for us.

Bertrand's postulate

Notice that if an array consists only of prime numbers, it is not disgusting, since for any pair of elements their $$$\gcd$$$ will be either $$$1$$$ or equal to themselves.

Let us try to replace each element $$$a_i$$$ with the smallest prime $$$p \gt a_i$$$. Obviously, we will not exceed the operation limit, because since $$$\gcd(a_i, p) = 1$$$, we also have $$$\gcd(a[i], p - a[i]) = 1$$$, which means we spend exactly $$$1$$$ operation per replacement.

Thus, the only remaining constraint for us is the sum of the elements of the resulting array $$$b$$$. However, Bertrand's postulate implies that for any positive integer $$$n$$$, the interval $$$[n + 1, 2n]$$$ contains at least one prime number, meaning that after the replacement, the sum of all elements of array $$$b$$$ will not exceed $$$\sum (2 \cdot a_i) = 2 \cdot \sum a_i$$$, which is what we need.

To compute the nearest prime, it is sufficient to precompute the Sieve of Eratosthenes and make a single backward pass over it, or use binary search over the sorted array of prime numbers, which, depending on the chosen approach and excluding precomputation, will yield a complexity of either $$$O(n)$$$ or $$$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)

Solve problem C1.

Think about which cases definitely require at most 2 operations.

etalutsoP s'dnartreB

To begin with, let us analyze and immediately forget about the trivial cases with $$$\mathrm{dist}(a, b) \lt 2$$$.

Now notice that if the interval $$$[a, b]$$$ contains at least one prime, we will need exactly $$$2$$$ operations. To see this, consider the largest among these primes, $$$p$$$, as an intermediate number. The number $$$b$$$ cannot be divisible by $$$p$$$, since we know that it is strictly greater than it (otherwise we would have been able to reach $$$b$$$ from $$$a$$$ in one step); at the same time, if it were at least $$$2p$$$, then by Bertrand's postulate the interval $$$[p+1, b]$$$ would contain a prime $$$q$$$ strictly greater than $$$p$$$, which is impossible because we picked the maximum among all primes in the interval. Hence, since $$$p$$$ is coprime to both $$$a$$$ and $$$b$$$, we can transition first into it, and then directly into $$$b$$$.

It remains to cover all cases where $$$\gcd(a, b) \gt 1$$$ and the interval $$$[a, b]$$$ does not contain primes. Since $$$a \le 10^5$$$, we can do this simply by iterating over all such pairs sorted by ascending length, and computing a trivial dynamic programming on them. This will pass within the time limit, since the average distance between prime numbers not exceeding $$$n$$$ is approximately $$$\log(n)$$$, and primes themselves are distributed rather uniformly, so the total precomputation complexity will be approximately $$$O(m \log^2 m)$$$, where $$$m \le 10^5$$$.

Thus, we obtain a solution similar to the solution of $$$\mathrm{C1}$$$: handle trivial cases in $$$O(1)$$$, then using the Sieve of Eratosthenes, check whether the largest prime strictly less than $$$b$$$ is greater than $$$a$$$. If it is greater, we construct the answer in $$$2$$$ operations, otherwise we retrieve it from our DP.

Or you can simply guess that $$$\mathrm{dist}(a, b) \le 2$$$ for $$$b - a \ge \text{small const}$$$, but that is uninteresting. In fact, this problem in its general formulation is an open problem, and it appears that $$$\mathrm{dist}(a, b)$$$ never exceeds $$$3$$$. If you discover a substantive proof to the contrary, feel free to share it in the comments.

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()

Figure out how to transmit $$$n - 2$$$ bits.

It seems useful to try studying how the operation applied by PAB affects graphs with a simple structure.

In the intended solution, the transmitted graph is almost always a tree.

Looking closely, it is easy to notice that if the graph transmitted by LCB is bipartite, PUB cannot affect the sets of monochromatic vertices in the bipartite coloring with its operations, because any simple path it chooses always connects vertices of different colors, meaning that any edge added by it will not violate the initial partition into parts, while preserving the connectivity of the graph.

From here, the following solution idea immediately arises: construct a bipartite graph in which vertex $$$i$$$ encodes the bit $$$s_{i - 1}$$$ depending on whether it receives the same color in the $$$2$$$-coloring as vertex $$$1$$$. It is simplest to use a tree as the bipartite graph.

However, we are left with one case where the string consists solely of ones, because in this case we would have to construct a connected bipartite graph in which all vertices must be colored the same color, which is obviously impossible. To encode it, transmit to PUB any graph that is not bipartite; for example, a tree in which we closed a cycle $$$1$$$—$$$2$$$—$$$3$$$ will suit us. It remains to prove that PUB cannot make such a graph bipartite in any number of operations.

Prove that $$$n−1$$$ bits is a tight upper bound on the amount of information that an LCB can transmit.

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='')

The graph $$$G$$$ is not necessarily connected.

What is the maximum number of unique individual components that the secret edges can connect?

[ SYS_MSG: ANALYSIS PROTOCOL INITIATED ]

First, notice that both hidden edges must connect the same pair of connected components of graph $$$G$$$. Indeed, fix a bipartite coloring for each component. Adding an edge between two different components always preserves bipartiteness, because we can invert the coloring of one of them. In doing so, each added edge imposes a requirement on the relative inversion of the colorings of the two components. If the hidden edges connected different pairs of components, we could satisfy all these requirements independently, and the graph would remain bipartite. The edges also cannot connect vertices within the same component, because in that case they would have to connect vertices of different colors, and the graph $$$G'$$$ would also remain bipartite; hence, both edges connect the same pair of components.

Now let us number the vertices by sequentially traversing the connected components, and inside each component using $$$\text{BFS}$$$. An important property of such a numbering is that any prefix of vertices inside a single component forms a connected graph: every vertex, except the first, already has its parent in the $$$\text{BFS}$$$.

Using the first binary search, we find a vertex $$$u$$$ which is an endpoint of one of the hidden edges. To do this, we query whether the subgraph consisting of the first $$$k$$$ vertices is bipartite. It will remain bipartite until all endpoints of both hidden edges fall into it, after which an odd cycle will appear in it, so we can use binary search to locate it, spending at most $$$\log 2000 = 11$$$ queries.

Renumber the vertices once more, placing the component containing $$$u$$$ first and launching $$$\text{BFS}$$$ from it, after which, using an analogous binary search, we find one of the vertices $$$v$$$ in the second component, which is also an endpoint of one of the hidden edges.

Now, using a query of the second type, check whether the edge $$$u$$$—$$$v$$$ is one of the hidden edges. If yes, we have already won. Otherwise, use the fact that $$$u$$$ and $$$v$$$ cannot be the endpoints of the same edge, which means the hidden edges do not share common endpoints, and in each of the two components there are exactly two endpoints of the hidden edges. We have already found one of them in each component.

It remains to find the second endpoint in one of the components. For this purpose, choose one of the two components, renumber its vertices using $$$\text{BFS}$$$ from its identified vertex, and run binary search once again. This time, in each query we will consider a prefix of the chosen component along with all vertices of the other component.

The last binary search can be optimized to at most $$$10$$$ queries if we choose the smaller of the two components for it. Thus, in the worst case, we will need only $$$11 + 11 + 1 + 10 = 33$$$ queries.

> 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;
}

Look at the process of changing the elements of the set as a sequence of operations with a deque.

To model the process, maintain a deque of initial length $$$n$$$, in whose $$$i$$$-th cell the average probability across all supersets that the set contains element $$$i$$$ at the current step will be stored.

To efficiently recalculate the statistics of the deque, you can use some well-known data structure.

The solution will be published soon.

#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;
}