CF2013D Minimize the Difference Solution

Introduction

The saddest part is that I figured it out just $$$5$$$ minutes after the contest ended. To commemorate this unfortunate story, I've decided to write a detailed solution (after all, this problem was quite challenging for me QvQ).

Problem Summary

Given a sequence, you can perform operations on two adjacent numbers $$$a_i$$$ and $$$a_{i+1}$$$ to decrease $$$a_i$$$ by $$$1$$$ and increase $$$a_{i+1}$$$ by $$$1$$$, with unlimited operations. Your task is to minimize the difference between the maximum value $$$M$$$ and the minimum value $$$m$$$ of the sequence after performing the operations.

Thought Process

It is clear that operations allow any $$$a_i$$$ and $$$a_j$$$ (with $$$i < j$$$) to decrease $$$d$$$ from $$$a_i$$$ and increase $$$d$$$ to $$$a_j$$$. Each $$$a_i$$$ can only affect elements with indices greater than $$$i$$$.

Since each element cannot influence the elements before it, we can consider adding elements in reverse order. Here, we define the queue with the first added element as the start, where $$$a$$$ is the new element, $$$b_1$$$ is the last element, and $$$b_2$$$ is the first element in the queue.

Now, when the queue satisfies the condition of minimal $$$M - m$$$, we consider how to handle the new element $$$a$$$:

1. If $$$a \leq m$$$, no operation can be performed since queue elements cannot change $$$a$$$, and $$$M$$$ cannot be minimized further. Thus, $$$a$$$ should directly enter the queue.
2. If $$$a > m$$$, then $$$a$$$ can increase $$$m$$$. After each adjustment to $$$m$$$, we can keep increasing $$$m$$$ while ensuring $$$a \geq m$$$ (i.e., reducing $$$a$$$ by $$$1$$$ and increasing $$$m$$$ by $$$1$$$).

It is evident that adding $$$a$$$ as described still maintains the condition that $$$M - m$$$ is minimized. The correctness of case $$$1$$$ is clear. For case $$$2$$$, if $$$a < m$$$ at the end, it means the minimum value has been reduced, which is clearly not an optimal solution. If each operation does not increase $$$m$$$ by $$$1$$$, then the answer cannot improve.

Thus, we only need to maintain a sequence where we can find the minimum value each time and ensure that a > m, so we can change it to a non-minimum element (i.e., change it to the second smallest).

We can consider using a monotonic queue. Each time we take the smallest element $$$m_0$$$ from the back and average it with $$$a$$$ to obtain $$$m'$$$. If $$$m'$$$ is greater than the last element in the queue, it indicates that the last element can still be increased. However, each $$$a$$$ may potentially remove all preceding elements, leading to a time complexity of $$$O(n^2)$$$, which is clearly insufficient.

Upon careful analysis, we find that after each operation, many identical elements emerge. Additionally, $$$a$$$ combined with smaller preceding elements will yield at most two distinct values (or one if divisible). Therefore, we can store elements as pairs $$$(a, i)$$$, where $$$a$$$ represents the value and $$$i$$$ counts the occurrences of that value. It is evident that the queue can contain at most $$$n$$$ elements (since averaging $$$a$$$ with preceding elements will at least merge one element and at most produce two). Moreover, each element in the queue can be dequeued at most once (which only occurs when averaging with $$$a$$$), leading to a time complexity of $$$O(n)$$$.

Code

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

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;

template <typename T> void read(T &x) {
	char ch = getchar();
	int sgn = 1; x = 0;
	while (!isdigit(ch)) {
		if (ch == '-') sgn = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	x *= sgn;
}

const int MAXN = 2e5 + 10;

ll a[MAXN];

int main() {
	int t; read(t);
	while (t--) {
		int n; read(n);
		for (int i = 1; i <= n; ++i) {
			read(a[i]);
		}
		deque<pair<ll, int> > que; que.clear();
		que.push_back({a[n], 1});
		for (int i = n - 1; i >= 1; --i) {
			que.push_back({a[i], 1});
			pair<ll, int> bk = que.back();
			que.pop_back();
			ll remain = 0;
			bool flag = 0;
			while (bk.first >= que.back().first) {
				flag = 1;
				ll sum = bk.first * bk.second + que.back().first * que.back().second - remain;
				ll newFirst = (ll)ceil(1.0 * sum / (bk.second + que.back().second));
				ll newSecond = bk.second + que.back().second;
				remain = ((bk.second + que.back().second) - (sum % (bk.second + que.back().second))) % (bk.second + que.back().second);
				que.pop_back();
				que.push_back({newFirst, newSecond});
				bk = que.back();
				que.pop_back();
				if (que.empty()) break;
			}
			que.push_back(bk);
			if (remain) {
				pair<ll, int> bk2 = que.back();
				que.pop_back();
				if (bk2.second - remain) que.push_back({bk2.first, bk2.second - remain});
				if (remain) que.push_back({bk2.first - 1, remain});
			}
		}
		printf("%lld\n", que.front().first - que.back().first);
	}
	return 0;
}