No, SEERC 2020 was expected to be in Fall 2020. However, it was moved to Spring 2021.

It is similar to the World Finals. World Finals 2020 will not be in 2020.

My solution to C:

Make a triangle ABC, and a path of nodes 0..n with 0=A. Now connect each one of 1..n with one of A, B or C. The number of ways to color a prefix with color equal to A,B,C is in the form (x,y,0), and it transitions to (0,x,x+y) or (y,0,x+y), and 14 steps is enough to reach some (x,y,0) with x+y=k for all k <= 500.

A can be solved by analyzing the DP as a convex hull: for each prefix, what's the maximum value such that the last stack has depth $$$d$$$? We need to support the following 2 operations: take $$$f(x) \to f'(x) = max(f(x-1), f(x), f(x+1))$$$ (with the special case that $$$f'(-1) = -\infty$$$) and $$$f(x) \to f'(x) = f(x) + a_i x$$$. Both of these preserve the fact that the function is concave.

We can maintain the function as a set of segments with $$$\Delta x = 1$$$, sorted in decreasing order by $$$\Delta y$$$; the first operation is inserting 2 segments of slope 0, and then deleting the steepest segment for $$$f'(-1)$$$, and the second operation can be handled with a lazy increment to the slope. If we use a priority queue, this code is extremely short:

#include <bits/stdc++.h>

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int N; cin >> N;

	int64_t cur_slope = 0;
	priority_queue<int64_t> pq;
	int64_t ans = 0;

	pq.push(-cur_slope);
	pq.push(-cur_slope);
	ans += pq.top() + cur_slope; pq.pop();

	while (N--) {
		int a; cin >> a;
		cur_slope += a;

		pq.push(-cur_slope);
		pq.push(-cur_slope);
		ans += pq.top() + cur_slope; pq.pop();
	}
	cout << ans << '\n';

	return 0;
}

Funnily enough, I wrote essentially the exact same code in 2015 for a USACO Camp problem (haybales, Day 3). The problem was as follows:

Given an array of integers, find the minimum number of operations to make it non-increasing, where each operation can increment or decrement one value.

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

typedef long long ll;

int main() {
    int N; cin >> N;

    priority_queue<ll> s;
    ll y = 0;

    for(int i = 0; i < N; i++) {
        ll v; cin >> v;

        y += v;

        s.push(-v);
        s.push(-v);

        y += s.top();
        s.pop();

    }

    cout << y << '\n';
    return 0;
}

In fact, the answer to SEERC A is exactly the answer to haybales on the $$$N+1$$$ prefix sums of the costs. Does anyone have an intuitive/combinatorial explanation? Is it LP duality or something?

G: Just walk along the outside of the region following right-hand-rule. You just need to be able to efficiently jump to the next left-turn along your current segment (if it exists), which you can get by preprocessing the perpendicular segments in a persistent data structure. This is efficient because the size of the boundary of the region is linear. The editorial mentions an upper bound of $$$O(n \alpha(n))$$$ segments on the outside, but I believe I have a tighter bound: each right-turn (convex vertex) must correspond to the end of the segment so there are at most $$$O(n)$$$ right-turns. Furthermore, we make exactly 4 more right turns than left turns, so the total number of turns/segments we use must be $$$O(n)$$$ as well.

I'm not sure about other solutions, but one observation we made (and didn't use) is that the problem guarantees the number of 0's is at most 9, so that directly gives you an upper bound of approximately $$$d/3$$$ without having to consider the other cases.

Probably I have the idea.

Based on the conclusion we got before, to get the answer we can just divide the numbers in two part by the number of '1' bits.

Consider how we answer all the queries completely included in the range $$$[l,r]$$$. Let $$$\textit{mid}=\lfloor(l+r)/2\rfloor$$$ and recursively solve the queries that completely included in $$$[l, mid]$$$ or $$$[mid+1,r]$$$, then the remaining queries we divide them into two parts. For the left part we record $$$b$$$ information at each position, and for the right part we process left to right by the right point of queries and keep the $$$b$$$ information during scanning. Because we record each position $$$O(\log n)$$$ times and each time we cost $$$O(b)$$$ time, so total complexity is $$$O(nb\log n)$$$.

Actually if we want to reach the better time complexity, all we need is just one more thing. Notice that "record $$$b$$$ information at each position" is no need, because we just wonder the left points of the queries. So record the position we need instead of all of them. Now we get the $$$O(n\log n+(q+n)\cdot b)$$$ solution.

My Code Here