This coincides with the div 1 codeforces round :(

We had a solution to B that is very different from the jury's solution.

We define the function $$$f(i, d)$$$, which is given by

• If $$$d \geq 0$$$, the number of operations we need to level everything, if positions $$$i, i+1, \dots, n$$$ are as normal, positions $$$i-1, \dots, i-d$$$ are $$$0$$$, and positions $$$i-d-1, i-d-2, \dots$$$ are $$$1$$$.
• If $$$d < 0$$$, the number of operations we need to level everything SUBTRACTED BY $$$|d|$$$, if positions $$$i, i+1, \dots, n$$$ are as normal, positions $$$i-2, i-3, \dots$$$ are $$$1$$$, and position $$$i-1$$$ is $$$1-d$$$.

The answer is given by $$$f(0, \infty)$$$, and $$$f(n, d) = 0$$$ for all $$$d$$$.

Now, if $$$a[i] = 0$$$, then $$$f(i, d) = f(i+1, d+1)$$$.

Otherwise,

• Let $$$0 < j_1 \leq \infty$$$ be the minimum value s.t. $$$f(i+1, j_1) < f(i+1, j_1 - 1)$$$ (this is the first amount where we want to push blocks past the left edge).
• Let $$$-\infty \leq j_2 <= 0$$$ be the maximum value s.t. $$$f(i+1, j_2) = f(i+1, j_2 - 1)$$$ (this is the first amount where we want to push the extra blocks past the right edge).

Then, $$$f(i, d) = f(i+1, d - (a[i] - 1)) + (a[i] - 1)$$$ + $$$a(i, d)$$$, where $$$a(i, d) = 0$$$ if $$$d \in [j_2 + (a[i] - 1), j_1 + (a[i] - 1) - 1]$$$, and $$$1$$$ otherwise.

These updates can be made in $$$\mathcal{O}(\log n)$$$, though our implementation was $$$\mathcal{O}(\log^2 n)$$$. Thus, total complexity is $$$\mathcal{O}(n \log n)$$$.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;

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

	int n;
	cin >> n;
	
	vector<ll> as(n);
	for (ll& a : as) cin >> a;

	ll base = 0, shift = 0;
	ordered_set dec_pos;
	for (int i = n-1; i >= 0; --i) {
		if (as[i] == 0) {
			shift += 1;
		} else if (as[i] >= 1) {
			base += as[i];
			
			auto it = dec_pos.upper_bound(shift);
			if (it != dec_pos.end()) {
				dec_pos.erase(it);
			}
			
			shift -= as[i] - 1;

			ll high = shift;
			ll low = shift - 1000000;
			while(low != high) {
				ll mid = (low + high);
				if (mid < 0) mid /= 2;
				else mid = (mid + 1) / 2;

				if ((ll)dec_pos.order_of_key(mid) > (ll)dec_pos.order_of_key(shift + 1) - (shift - mid + 1)) low = mid;
				else high = mid - 1;
			}
			dec_pos.insert(low);
		}
	}
	cout << base - (int)dec_pos.size() << '\n';

}

The problems are available for upsolving on Kattis, but by popular demand we have also uploaded the contest to the Codeforces gym.

In problem I, my teammate AsunderSquall used a weird algorithm and magically got accepted.

There is a simple $$$O(n^4)$$$ brute force method and it's too slow. But we add this line :

if (clock() * 1.0 / CLOCKS_PER_SEC > 6.9) { puts("impossible"); exit(0); }

It means if we can't find a vaild solution in TL, the program just gives up. Then we passed the test.

After the (VP)contest we guessed that if the solution exists, we can just make the first person start at $$$1$$$.

Can anyone proof this, or figure out it is fake and passed just because of weak test?