### SuprDewd's blog

By SuprDewd, history, 6 weeks ago,

NWERC 2020 was finally held this last weekend after a few month delay due to the pandemic. The format was a little different this time around, with each contestant participating from home (i.e. three computers per team) and having full read access to the internet during the contest.

We wanted to let you know that this Saturday at 12:00 GMT we will be hosting an open version of the contest on Kattis: https://open.kattis.com/contests/nwerc2020open

The problemset, solution slides, testdata and judges' solutions are already available on our website, but we ask that you please refrain from looking at them until the open contest is over. Good luck, and we hope you enjoy the problems!

• +35

 » 6 weeks ago, # |   0 This coincides with the div 1 codeforces round :(
•  » » 6 weeks ago, # ^ |   0 That's unfortunate :( I don't think we can change the time now, sadly.
 » 5 weeks ago, # |   +8 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)$. code#include #include // Common file #include // Including tree_order_statistics_node_update #include using namespace std; using namespace __gnu_pbds; using ll = long long; using ordered_set = tree, rb_tree_tag, tree_order_statistics_node_update>; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector 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'; } 
 » 5 weeks ago, # |   +21 The problems are available for upsolving on Kattis, but by popular demand we have also uploaded the contest to the Codeforces gym.