Editorial of Educational Codeforces Round 11

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	170
2	Um_nik	162
3	atcoder_official	161
4	maomao90	160
5	djm03178	158
5	-is-this-fft-	158
7	Dominater069	156
8	adamant	154
9	luogu_official	153
10	awoo	152

660C - Hard Process

The problem was suggested by Mohammad Amin Raeisi Smaug.

Let's call the segment [l, r] good if it contains no more than k zeroes. Note if segment [l, r] is good than the segment [l + 1, r] is also good. So we can use the method of two pointers: the first pointer is l and the second is r. Let's iterate over l from the left to the right and move r while we can (to do that we should simply maintain the number of zeroes in the current segment).

C++ solution

const int N = 1200300;

int n, k;
int a[N];

bool read() {
	if (!(cin >> n >> k)) return false;
	forn(i, n) assert(scanf("%d", &a[i]) == 1);
	return true;
}

void solve() {
	int ansl = 0, ansr = 0;
	int j = 0, cnt = 0;
	forn(i, n) {
		if (j < i) {
			j = i;
			cnt = 0;
		}

		while (j < n) {
			int ncnt = cnt + !a[j];
			if (ncnt > k) break;
			cnt += !a[j];
			j++;
		}
		
		if (j - i > ansr - ansl)
			ansl = i, ansr = j;

		if (cnt > 0) cnt -= !a[i];
	}

	cout << ansr - ansl << endl;
	fore(i, ansl, ansr) a[i] = 1;
	forn(i, n) {
		if (i) putchar(' ');
		printf("%d", a[i]);
	}
	puts("");
}

Complexity: O(n).

660D - Number of Parallelograms

The problem was suggested by Sadegh Mahdavi smahdavi4.

It's known that the diagonals of a parallelogram split each other in the middle. Let's iterate over the pairs of points a, b and consider the middle of the segment $\text{[math]}$ : $\text{[math]}$ . Let's calculate the value cnt_c for each middle. cnt_c is the number of segments a, b with the middle c. Easy to see that the answer is $\text{[math]}$ .

C++ solution

const int N = 2020;

int n;
int x[N], y[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n)
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	return true;
}

inline li C2(li n) { return n * (n - 1) / 2; }

void solve() {
	map<pti, int> cnt;

	forn(i, n)
		forn(j, i) {
			int cx = x[i] + x[j];
			int cy = y[i] + y[j];
			cnt[{cx, cy}]++;
		}

	li ans = 0;
	for (const auto& p : cnt)
		ans += C2(p.y);
	cout << ans << endl;
}

Complexity: O(n²logn).

660E - Different Subsets For All Tuples

The problem was suggested by Lewin Gan Lewin.

Let's consider some subsequence with the length k > 0 (the empty subsequences we will count separately by adding the valye mⁿ at the end) and count the number of sequences that contains it. We should do that accurately to not count the same sequence multiple times. Let x₁, x₂, ..., x_k be the fixed subsequence. In the original sequence before the element x₁ can be some other elements, but none of them can be equal to x₁ (because we want to count the subsequence exactly one time). So we have m - 1 variants for each of the elements before x₁. Similarly between elements x₁ and x₂ can be other elements and we have m - 1 choices for each of them. And so on. After the element x_k can be some elements (suppose there are j such elements) with no additional constraints (so we have m choices for each of them). We fixed the number of elements at the end j, so we should distribute n - k - j numbers between numbers before x₁, between x₁ and x₂, \ldots, between x_k - 1 and x_k. Easy to see that we have $\text{[math]}$ choices to do that (it's simply binomial coefficient with allowed repititions). The number of sequences x₁, x₂, ..., x_k equals to m^k. So the answer is $\text{[math]}$ . Easy to transform the last sum to the sum $\text{[math]}$ . Note the last inner sum can be calculating using the formula for parallel summing: $\text{[math]}$ . So the answer equals to $\text{[math]}$ . Also we can get the closed formula for the last sum to get logarithmic solution, but it is not required in the problem.

C++ solution

int n, m;

bool read() {
	return !!(cin >> n >> m);
}

const int N = 1200300;

const int mod = 1000 * 1000 * 1000 + 7;

int gcd(int a, int b, int& x, int& y) {
	if (!a) {
		x = 0, y = 1;
		return b;
	}
	int xx, yy, g = gcd(b % a, a, xx, yy);
	x = yy - b / a * xx;
	y = xx;
	return g;
}

inline int inv(int a) {
	int x, y;
	assert(gcd(a, mod, x, y) == 1);
	x %= mod;
	return x < 0 ? x + mod : x;
}

inline int mul(int a, int b) { return int(a * 1ll * b % mod); }
inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }

inline void inc(int& a, int b) { a = add(a, b); }

int fact[N], ifact[N];

inline int C(int n, int k) {
	if (k < 0 || k > n) return 0;
	return mul(fact[n], mul(ifact[k], ifact[n - k]));
}

int pm[N], pm1[N];

void solve() {
	const int N = n + 1;

	fact[0] = 1; fore(i, 1, N) fact[i] = mul(fact[i - 1], i);
	forn(i, N) ifact[i] = inv(fact[i]);

	pm[0] = 1; fore(i, 1, N) pm[i] = mul(pm[i - 1], m);
	pm1[0] = 1; fore(i, 1, N) pm1[i] = mul(pm1[i - 1], sub(m, 1));

	int ans = pm[n];
	fore(s, 1, n + 1) {
		int cur = 1;
		cur = mul(cur, pm[s]);
		cur = mul(cur, pm1[n - s]);
		cur = mul(cur, C(n, s - 1));
		inc(ans, cur);
	}
	cout << ans << endl;
}

Complexity: O((n + m)log MOD), где MOD = 10⁹ + 7.

660F - Bear and Bowling 4

The problem was prepared by Kamil Debowski Errichto. The problem analysis is also prepared by him.

The key is to use divide and conquer. We need a recursive function f(left, right) that runs f(left, mid) and f(mid+1, right) (where mid = (left + right) / 2) and also considers all intervals going through mid. We will eventually need a convex hull of lines (linear functions) and let's see how to achieve it.

For variables L, R ( $\text{[math]}$ , $\text{[math]}$ ) we will try to write the score of interval [L, R] as a linear function. It would be good to get something close to a_L·x_R + b_L where a_L and b_L depend on L, and x_R depends on R only.

$\text{[math]}$

For each L we should find a linear function f_L(x) = a_L·x + b_L where a_L, b_L should fit the equation ( * ):

$\text{[math]}$

Now we have a set of linear functions representing all possible left endpoints L. For each right endpoint R we should find x_R and const_R to fit equation ( * ) again. With value of x_R we can iterate over functions f_L to find the one maximizing value of b_L + a_L·x_R. And (still for fixed R) we should add const_R to get the maximum possible score of interval ending in R.

Brute Force with functions

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax = 1e6 + 5;
ll ans;
ll t[nax];

struct Fun {
	ll a, b;
	ll getValue(ll x) { return a * x + b; }
};

void rec(int first, int last) {
	if(first == last) {
		ans = max(ans, t[first]);
		return;
	}
	int mid = (first + last) / 2;
	
	rec(first, mid); // the left half is [first, mid]
	rec(mid+1, last); // the right half is [mid+1, last]
	
	// we must consider all intervals starting in [first,mid] and ending in [mid+1, last]
	
	vector<Fun> functions;
	ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid]
	ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1)
	for(int i = mid; i >= first; --i) {
		sum_so_far += t[i];
		score_so_far += sum_so_far;
		functions.push_back(Fun{mid - i + 1, score_so_far});
	}
	
	sum_so_far = 0;
	score_so_far = 0;
	for(int i = mid+1; i <= last; ++i) {
		sum_so_far += t[i];
		score_so_far += t[i] * (i - mid);
		for(Fun & f : functions) {
			ll score = score_so_far + f.getValue(sum_so_far);
			ans = max(ans, score);
		}
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
	rec(1, n);
	printf("%lldn", ans);
	return 0;
}

Now let's make it faster. After finding a set of linear functions f_L we should build a convex hull of them (note that they're already sorted by slope). To achieve it we need something to compare 3 functions and decide whether one of them is unnecessary because it's always below one of other two functions. Note that in standard convex hull of points you also need something similar (but for 3 points). Below you can find an almost-fast-enough solution with a useful function bool is_middle_needed(f1, f2, f3). You may check that numbers calculated there do fit in long long.

Almost fast enough

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax = 1e6 + 5;
ll ans;
ll t[nax];

struct Fun {
	ll a, b;
	ll getValue(ll x) { return a * x + b; }
};

bool is_middle_needed(const Fun & f1, const Fun & f2, const Fun & f3) {
	// we ask if for at least one 'x' there is f2(x) > max(f1(x), f3(x))
	assert(0 < f1.a && f1.a < f2.a && f2.a < f3.a);
	
	// where is the intersection of f1 and f2?
	// f1.a * x + f1.b = f2.a * x + f2.b
	// x * (f2.a - f1.a) = f1.b - f2.b
	// x = (f1.b - f2.b) / (f2.a - f1.a)
	ll p1 = f1.b - f2.b;
	ll q1 = f2.a - f1.a;
	// and the intersection of f1 and f3
	ll p2 = f1.b - f3.b;
	ll q2 = f3.a - f1.a;
	assert(q1 > 0 && q2 > 0);
	// return p1 / q1 < p2 / q2
	return p1 * q2 < q1 * p2;
}

void rec(int first, int last) {
	if(first == last) {
		ans = max(ans, t[first]);
		return;
	}
	int mid = (first + last) / 2;
	
	rec(first, mid); // the left half is [first, mid]
	rec(mid+1, last); // the right half is [mid+1, last]
	
	// we must consider all intervals starting in [first,mid] and ending in [mid+1, last]
	
	vector<Fun> functions;
	ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid]
	ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1)
	for(int i = mid; i >= first; --i) {
		sum_so_far += t[i];
		score_so_far += sum_so_far;
		Fun f = Fun{mid - i + 1, score_so_far};
		while(true) {
			int s = functions.size();
			if(s >= 2 && !is_middle_needed(functions[s-2], functions[s-1], f))
				functions.pop_back();
			else
				break;
		}
		functions.push_back(f);
	}
	
	sum_so_far = 0;
	score_so_far = 0;
	for(int i = mid+1; i <= last; ++i) {
		sum_so_far += t[i];
		score_so_far += t[i] * (i - mid);
		for(Fun & f : functions) {
			ll score = score_so_far + f.getValue(sum_so_far);
			ans = max(ans, score);
		}
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
	rec(1, n);
	printf("%lldn", ans);
	return 0;
}

Finally, one last thing is needed to make it faster than O(n²). We should use the fact that we have built a convex hull of functions (lines). For each R you should binary search optimal function. Alternatively, you can sort pairs (x_R, const_R) and then use the two pointers method — check the implementation in my solution below. It gives complexity $\text{[math]}$ because we sort by x_R inside of a recursive function. I think it's possible to get rid of this by sorting prefixes $\text{[math]}$ in advance because it's equivalent to sorting by x_R. And we should use the already known order when we run a recursive function for smaller intervals. So, I think $\text{[math]}$ is possible this way — anybody implemented it?

Intended solution with two pointers

// O(n log^2(n))
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nax = 1e6 + 5;
ll ans;
ll t[nax];

struct Fun {
	ll a, b;
	ll getValue(ll x) { return a * x + b; }
};

bool is_middle_needed(const Fun & f1, const Fun & f2, const Fun & f3) {
	// we ask if for at least one 'x' there is f2(x) > max(f1(x), f3(x))
	assert(0 < f1.a && f1.a < f2.a && f2.a < f3.a);
	
	// where is the intersection of f1 and f2?
	// f1.a * x + f1.b = f2.a * x + f2.b
	// x * (f2.a - f1.a) = f1.b - f2.b
	// x = (f1.b - f2.b) / (f2.a - f1.a)
	ll p1 = f1.b - f2.b;
	ll q1 = f2.a - f1.a;
	// and the intersection of f1 and f3
	ll p2 = f1.b - f3.b;
	ll q2 = f3.a - f1.a;
	assert(q1 > 0 && q2 > 0);
	// return p1 / q1 < p2 / q2
	return p1 * q2 < q1 * p2;
}

void rec(int first, int last) {
	if(first == last) {
		ans = max(ans, t[first]);
		return;
	}
	int mid = (first + last) / 2;
	
	rec(first, mid); // the left half is [first, mid]
	rec(mid+1, last); // the right half is [mid+1, last]
	
	// we must consider all intervals starting in [first,mid] and ending in [mid+1, last]
	
	vector<Fun> functions;
	ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid]
	ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1)
	for(int i = mid; i >= first; --i) {
		sum_so_far += t[i];
		score_so_far += sum_so_far;
		Fun f = Fun{mid - i + 1, score_so_far};
		while(true) {
			int s = functions.size();
			if(s >= 2 && !is_middle_needed(functions[s-2], functions[s-1], f))
				functions.pop_back();
			else
				break;
		}
		functions.push_back(f);
	}
	
	vector<pair<ll, ll>> points;
	sum_so_far = 0;
	score_so_far = 0;
	for(int i = mid+1; i <= last; ++i) {
		sum_so_far += t[i];
		score_so_far += t[i] * (i - mid);
		points.push_back({sum_so_far, score_so_far});
		/*for(Fun & f : functions) {
			ll score = score_so_far + f.getValue(sum_so_far);
			ans = max(ans, score);
		}*/
	}
	
	sort(points.begin(), points.end());
	int i = 0; // which function is the best
	for(pair<ll, ll> p : points) {
		sum_so_far = p.first;
		score_so_far = p.second;
		while(i + 1 < (int) functions.size()
			&& functions[i].getValue(sum_so_far) <= functions[i+1].getValue(sum_so_far))
				++i;
		ans = max(ans, score_so_far + functions[i].getValue(sum_so_far));
	}
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
	rec(1, n);
	printf("%lldn", ans);
	return 0;
}

Complexity: O(nlog²n).

Rev.	By	When	Δ	Comment
en7	Edvard	2016-04-10 18:47:25	66	Tiny change: ' we have $k-1$\nchoic' -> ' we have $m-1$\nchoic'
en6	Edvard	2016-04-09 22:13:28	3481
ru7	Edvard	2016-04-09 21:38:53	202
en5	Edvard	2016-04-09 21:36:44	1097
en4	Edvard	2016-04-09 21:31:11	1280
en3	Edvard	2016-04-09 21:28:04	856
en2	Edvard	2016-04-09 21:17:51	847
ru6	Edvard	2016-04-09 21:09:43	50	Мелкая правка: 'ость: $O(n+k)$.\n\n###' -> 'ость: $O(n)$.\n\n###'
ru5	Edvard	2016-04-09 21:07:54	56
ru4	Edvard	2016-04-09 02:22:21	3780	Мелкая правка: ' log^{2}{n})$.' -
ru3	Edvard	2016-04-09 01:05:26	3539	Мелкая правка: 'mits_{s=1} m^s (m-1)^(n-s) \sum_{k=0' -
en1	Edvard	2016-04-09 00:38:15	9069	Initial revision for English translation
ru2	Edvard	2016-04-09 00:33:39	1030	Мелкая правка: 'cnt_c-1)}2.\n\n 'cnt_c-1)}2$.\n\n
ru1	Edvard	2016-04-09 00:03:25	2956	Первая редакция (опубликовано)

660A - Co-prime Array

660B - Seating On Bus

660C - Hard Process

660D - Number of Parallelograms

660E - Different Subsets For All Tuples

660F - Bear and Bowling 4

History