Editorial of Educational Codeforces Round 12

#	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	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

665A - Buses Between Cities

The problem was suggested by Sergey Erlikh unprost.

Consider the time interval when Simion will be on the road strictly between cities (x₁, y₁) (x₁ = 60h + m, y₁ = x₁ + t_a). Let's iterate over the oncoming buses. Let (x₂, y₂) be the time interval when the oncoming bus will be strictly between two cities. If the intersection of that intervals (x = max(x₁, x₂), y = min(y₁, y₂)) is not empty than Simion will count that bus.

С++ solution

int a, ta;
int b, tb;
int h, m;

bool read() {
	if (!(cin >> a >> ta)) return false;
	assert(cin >> b >> tb);
	assert(scanf("%d:%d", &h, &m) == 2);
	return true;
}

void solve() {
	int x1 = h * 60 + m;
	int y1 = x1 + ta;

	int ans = 0;
	for (int x2 = 5 * 60 + 0; x2 < 24 * 60; x2 += b) {
		int y2 = x2 + tb;
		int x = max(x1, x2), y = min(y1, y2);
		if (x < y)
			ans++;
	}
	cout << ans << endl;
}

Complexity: O(1).

665B - Shopping

The problem was suggested by Ayush Anand JeanValjean01.

In this problem you should simply do what was written in the problem statement. There are no tricks.

C++ solution

const int N = 111;

int n, m, k;
int p[N];
int a[N][N];

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

void solve() {
	int ans = 0;
	forn(i, n)
		forn(j, m) {
			int pos = int(find(p, p + k, a[i][j]) - p);
			ans += pos + 1;
			nfor(l, pos) p[l + 1] = p[l];
			p[0] = a[i][j];
		}
	cout << ans << endl;
}

Complexity: O(nmk).

665C - Simple Strings

The problem was suggested by Zi Song Yeoh zscoder.

There are two ways to solve this problem: greedy approach and dynamic programming.

The first apprroach: Considerr some segment of consecutive equal characters. Let k be the length of that segment. Easy to see that we should change at least $\text{[math]}$ characters in the segment to remove all the pairs of equal consecutive letters. On the other hand we can simply change the second, the fourth etc. symbols to letter that is not equal to the letters before and after the segment.

Greedy approach on C++

const int N = 200200;

int n;
char s[N];

bool read() {
	if (!gets(s)) return false;
	n = int(strlen(s));
	return true;
}

void solve() {
	for (int i = 0, j = 0; i < n; i = j) {
		while (j < n && s[j] == s[i]) j++;
		char c = 'a';
		while (c == s[i] || (i > 0 && c == s[i - 1]) || (j < n && c == s[j]))
			c++;
		fore(k, i, j)
			if ((i + k) & 1)
				s[k] = c;
	}
	puts(s);
}

The second approach: Let z_ka be the minimal number of changes so that the prefix of length k has no equal consecutive letters and the symbol s'_k equals to a. Let's iterate over the letter on the position k + 1 and if it is not equal to a make transition. The cost of the transition is equal to 0 if we put the same letter as in the original string s on the position k + 1. Otherwise the cost is equal to 1.

DP solution on C++

const int N = 1200300, A = 27;

int n;
char s[N];

bool read() {
	if (!gets(s)) return false;
	n = int(strlen(s));
	return true;
}

int z[N][A];
int p[N][A];
char ans[N];

void solve() {
	memset(z, 63, sizeof(z));

	z[0][A - 1] = 0;
	forn(i, n) {
		int c = int(s[i] - 'a');
		forn(j, A) {
			int dv = z[i][j];
			if (dv > INF / 2) continue;
			forn(nj, A - 1) {
				if (nj == j) continue;
				int ct = nj != c;
				if (z[i + 1][nj] > dv + ct) {
					z[i + 1][nj] = dv + ct;
					p[i + 1][nj] = j;
				}
			}
		}
	}

	int idx = int(min_element(z[n], z[n] + A) - z[n]);

	for (int i = n, j = idx; i > 0; j = p[i][j], i--)
		ans[i - 1] = char('a' + j);
	ans[n] = 0;

	cerr << z[n][idx] << endl;
	puts(ans);
}

Complexity: O(n).

665F - Four Divisors

The editorial for this problem is a little modification of the materials from the lecture of Mikhail Tikhomirov Endagorion of the autumn of 2015 in Moscow Institute of Physics and Technology. Thanks a lot to Endagorion for that materials.

Easy to see that only the numbers of the form p·q and p³ (for different prime p, q) have exactly four positive divisors.

We can easily count the numbers of the form p³ in $\text{[math]}$ , where n is the number from the problem statement.

Now let p < q and π(k) be the number of primes from 1 to k. Let's iterate over all the values p. Easy to see that $\text{[math]}$ . So for fixed p we should increase the answer by the value $\text{[math]}$ .

So the task is ot to find $\text{[math]}$ — the number of primes not exceeding $\text{[math]}$ , for all p.

Denote p_j the j-th prime number. Denote dp_n, j the number of k such that 1 ≤ k ≤ n, and all prime divisors of k are at least p_j (note that 1 is counted in all dp_n, j, since the set of its prime divisors is empty). dp_n, j satisfy a simple recurrence:

dp_n, 1 = n (since p₁ = 2)
dp_n, j = dp_{n, j + 1} + dp_{⌊ n / p_j⌋, j}, hence dp_{n, j + 1} = dp_n, j - dp_{⌊ n / p_j⌋, j}

Let p_k be the smallest prime greater than $\text{[math]}$ . Then π(n) = dp_n, k + k - 1 (by definition, the first summand accounts for all the primes not less than k).

If we evaluate the recurrence dp_n, k straightforwardly, all the reachable states will be of the form dp_{⌊ n / i⌋, j}. We can also note that if p_j and p_k are both greater than $\text{[math]}$ , then dp_n, j + j = dp_n, k + k. Thus, for each ⌊ n / i⌋ it makes sense to keep only $\text{[math]}$ values of dp_{⌊ n / i⌋, j}.

Instead of evaluating all DP states straightforwardly, we perform a two-step process:

Choose K.
Run recursive evaluation of dp_n, k. If we want to compute a state with n < K, memorize the query ``count the numbers not exceeding n with all prime divisors at least k''.
Answer all the queries off-line: compute the sieve for numbers up to K, then sort all numbers by the smallest prime divisor. Now all queries can be answered using RSQ structure. Store all the answers globally.
Run recurisive evaluation of dp_n, k yet again. If we want to compute a state with n < K, then we must have preprocessed a query for this state, so take it from the global set of answers.

The performance of this approach relies heavily on Q — the number of queries we have to preprocess.

Statement. $\text{[math]}$ .

Proof:

Each state we have to preprocess is obtained by following a dp_{⌊ n / p_j⌋, j} transition from some greater state. It follows that Q doesn't exceed the total number of states for n > K.

$\text{[math]}$

The preprocessing of Q queries can be done in $\text{[math]}$ , and it is the heaviest part of the computation. Choosing optimal $\text{[math]}$ , we obtain the complexity $\text{[math]}$ .

C++ solution

li n;

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

const int K = 10 * 1000 * 1000;
const int N = K;
const int P = 700100;
const int Q = 25 * 1000 * 1000;

int szp, p[P];
int mind[N];

void prepare() {
	szp = 0;
	forn(i, N) mind[i] = -1;
	fore(i, 2, N) {
		if (mind[i] == -1) {
			assert(szp < P);
			mind[i] = szp;
			p[szp++] = i;
		}
		for (int j = 0; j < szp && j <= mind[i] && i * p[j] < N; j++)
			mind[i * p[j]] = j;
	}
}

inline int getk(li n) {
	int lf = 0, rg = szp - 1;
	while (lf != rg) {
		int md = (lf + rg) >> 1;
		if (p[md] * 1ll * p[md] > n) rg = md;
		else lf = md + 1;
	}
	assert(p[lf] * 1ll * p[lf] > n);
	return lf;
}

int t[K];
void inc(int i, int val) {
	for ( ; i < K; i |= i + 1)
		t[i] += val;
}
int sum(int i) {
	int ans = 0;
	for ( ; i >= 0; i = (i & (i + 1)) - 1)
		ans += t[i];
	return ans;
}

int szq;
pti q[Q];
int ans[Q];
vector<int> vs[P];

void process() {
	sort(q, q + szq, greater<pti> ());
	memset(t, 0, sizeof(t));

	forn(i, szp) vs[i].clear();
	fore(i, 2, K)
		vs[mind[i]].pb(i);

	inc(1, +1);

	int p = szp - 1;
	for (int i = 0, j = 0; i < szq; i = j) {
		while (p >= q[i].x) {
			for (auto v : vs[p])
				inc(v, +1);
			p--;
		}

		while (j < szq && q[j].x == q[i].x) {
			ans[j] = sum(q[j].y);
			j++;
		}
	}
}

map<pair<li, int>, li> z;

li solve(li n, int jj, bool fs) {
	if (!n) return 0;
	int j = min(jj, getk(n));
	if (!j) return n + j - jj;

	li ans = 0;
	if (n < K) {
		pti p(j, (int) n);
		if (fs) {
			assert(szq < Q);
			q[szq++] = p;
			ans = 0;
			return 0;
		} else {
			int idx = int(lower_bound(q, q + szq, p, greater<pti> ()) - q);
			assert(idx < szq && q[idx] == p);
			ans = ::ans[idx];
		}
	} else {
		if (!z.count(mp(n, j))) {
			ans = solve(n, j - 1, fs);
			ans -= solve(n / p[j - 1], j - 1, fs);
			z[mp(n, j)] = ans;
		} else {
			ans = z[mp(n, j)];
		}
	}

	ans += j - jj;

	return ans;
}

inline li pi(li n, bool fs) {
	int k = szp - 1;
	return solve(n, k, fs) + k - 1;
}

void solve() {
	szq = 0;
	z.clear();
	for (int j = 0; p[j] * 1ll * p[j] <= n; j++) {
		li nn = n / p[j];
		if (nn > p[j]) {
			pi(n / p[j], true);
		}
	}

	process();

	z.clear();
	li ans = 0;
	for (int j = 0; p[j] * 1ll * p[j] <= n; j++) {
		li nn = n / p[j];
		if (nn > p[j]) {
			ans += pi(n / p[j], false);
			ans -= j + 1;
		}
	}

	for (int i = 0; i < szp && p[i] * 1ll * p[i] * 1ll * p[i] <= n; i++)
		ans++;

	cout << ans << endl;
}

Complexity: $\text{[math]}$ .

Rev.	By	When	Δ	Comment
ru9	Edvard	2016-04-21 01:56:30	7297
en13	Edvard	2016-04-21 00:46:44	2897
en12	Edvard	2016-04-21 00:24:45	2294
en11	Edvard	2016-04-21 00:12:52	2378
en10	Edvard	2016-04-21 00:02:42	818
en9	Edvard	2016-04-21 00:00:58	1001
en8	Edvard	2016-04-20 23:03:30	65
ru8	Edvard	2016-04-20 23:03:12	112
ru7	Edvard	2016-04-20 22:56:00	68
en7	Edvard	2016-04-20 22:55:17	16
en6	Edvard	2016-04-20 22:54:41	13
ru6	Edvard	2016-04-20 20:48:13	6203
en5	Edvard	2016-04-20 20:20:15	9	Tiny change: 'the number of the fo' -> 'the numbers of the fo'
en4	Edvard	2016-04-20 20:14:31	2
en3	Edvard	2016-04-20 20:13:49	156
en2	Edvard	2016-04-20 20:00:29	8	(published)
en1	Edvard	2016-04-20 19:58:31	6278	Initial revision for English translation
ru5	Edvard	2016-04-20 19:38:18	133
ru4	Edvard	2016-04-20 19:36:17	2945
ru3	Edvard	2016-04-20 19:12:54	68
ru2	Edvard	2016-04-20 17:48:16	117
ru1	Edvard	2016-04-20 17:39:47	6525	Первая редакция (сохранено в черновиках)

665A - Buses Between Cities

665B - Shopping

665C - Simple Strings

665F - Four Divisors

History