Editorial of Educational Codeforces Round 12

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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).

665D - Simple Subset

The problem was suggested by Zi Song Yeoh zscoder.

Consider the subset A that is the answer to the problem. Let a, b, c be the arbitrary three elements from A and let no more than one of them is equal to 1. By the pigeonhole principle two of three elements from a, b, c have the same parity. So we have two integers with even sum and only one of them is equal to 1, so their sum is also greater than 2. So the subset A is not simple. In this way A consists of only two numbers greater than one (with a prime sum) or consists of some number of ones and also maybe other value x, so that x + 1 is a prime.

We can simply process the first case in O(n²) time. The second case can be processed in linear time. Also we should choose the best answer from that two.

To check the value of order 2·10⁶ for primality in O(1) time we can use the simple or the linear Eratosthenes sieve.

C++ solution

const int N = 1010, X = 2100300;

int n, a[N];

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

int szp, p[X];
int mind[X];

void prepare() {
	fore(i, 2, X) {
		if (!mind[i]) {
			p[szp++] = i;
			mind[i] = i;
		}
		for (int j = 0; j < szp && p[j] <= mind[i] && i * p[j] < X; j++)
			mind[i * p[j]] = p[j];
	}
}

void printAns(int cnt1, int a = -1, int b = -1) {
	vector<int> ans;
	forn(i, cnt1) ans.pb(1);
	if (a != -1) ans.pb(a);
	if (b != -1) ans.pb(b);
	assert(!ans.empty());
	random_shuffle(all(ans));

	cout << sz(ans) << endl;
	forn(i, sz(ans)) {
		if (i) putchar(' ');
		printf("%d", ans[i]);
	}
	puts("");
}

void solve() {
	int cnt1 = (int) count(a, a + n, 1);

	function<bool(int)> isPrime = [](int p) { return mind[p] == p; };

	if (cnt1 > 0)
		forn(i, n)
			if (a[i] != 1 && isPrime(a[i] + 1)) {
				printAns(cnt1, a[i]);
				return;
			}

	if (cnt1 > 1) {
		printAns(cnt1);
		return;
	}

	forn(i, n)
		forn(j, i)
			if (isPrime(a[i] + a[j])) {
				printAns(0, a[i], a[j]);
				return;
			}

	printAns(0, a[0]);
}

Complexity: O(n² + X), where X is the maximal value in a.

665E - Beautiful Subarrays

The problem was suggested by Zi Song Yeoh zscoder.

The sign $\text{[math]}$ is used for the binary operation for bitwise exclusive or.

Let s_i be the xor of the first i elements on the prefix of a. Then the interval (i, j] is beautiful if $\text{[math]}$ . Let's iterate over j from 1 to n and consider the values s_j as the binary strings. On each iteration we should increase the answer by the value z_j — the number of numbers s_i (i < j) so $\text{[math]}$ . To do that we can use the trie data structure. Let's store in the trie all the values s_i for i < j. Besides the structure of the trie we should also store in each vertex the number of leaves in the subtree of that vertex (it can be easily done during adding of each binary string). To calculate the value z_j let's go down by the trie from the root. Let's accumulate the value cur equals to the xor of the prefix of the value s_j with the already passed in the trie path. Let the current bit in s_j be equal to b and i be the depth of the current vertex in the trie. If the number cur + 2ⁱ ≥ k then we can increase z_j by the number of leaves in vertex $\text{[math]}$ , because all the leaves in the subtree of tha vertex correspond to the values s_i that for sure gives $\text{[math]}$ . After that we should go down in the subtree b. Otherwise if cur + 2ⁱ < k then we should simply go down to the subtree $\text{[math]}$ and recalculate the value cur = cur + 2ⁱ.

C++ solution

const int N = 1200300, LOGN = 30, V = N * LOGN;

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;
}

int tsz;
int nt[V][2];
int cnt[V];

void clear() {
	forn(i, V) {
		nt[i][0] = nt[i][1] = -1;
		cnt[i] = 0;
	}
	tsz = 1;
}

void add(int x) {
	int v = 0;
	cnt[v]++;

	nfor(i, LOGN) {
		int b = (x >> i) & 1;
		if (nt[v][b] == -1) {
			assert(tsz < V);
			nt[v][b] = tsz++;
		}
		v = nt[v][b];
		cnt[v]++;
	}
}


int calc(int x) {
	int v = 0;
	int ans = 0;

	auto getCnt = [](int v) { return v == -1 ? 0 : cnt[v]; };

	int cur = 0;
	nfor(i, LOGN) {
		if (v == -1) break;
		int b = (x >> i) & 1;
		if ((cur | (1 << i)) >= k) {
			ans += getCnt(nt[v][b ^ 1]);
			v = nt[v][b];
		} else {
			v = nt[v][b ^ 1];
			cur |= (1 << i);
		}
	}
	if (cur >= k) ans += getCnt(v);
	return ans;
}

void solve() {
	clear();

	add(0);

	li ans = 0;
	int s = 0;
	forn(i, n) {
		s ^= a[i];
		li cur = calc(s);
		ans += cur;
		add(s);
	}
	cout << ans << endl;
}

Comlpexity by the time and the memory: O(nlogX), where X is the maximal xor on the prefixes.

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]}$ .

Comments (39)

Show archived | Write comment?

Edvard

9 years ago, # |

Auto comment: topic has been updated by Edvard (previous revision, new revision, compare).

→ Reply

adkroxx

← Rev. 2 →

+21

This problem is also an easier version of This Problem !

fofao_funk

9 years ago, # ^ |

That's why you were able to solve it?

Yeah!

Cool. :)

Endagorion told me that there are something very similar at Project Euler. Also the problem to count semiprimes was last year at MIPT camp (the editorial from there). Anyway I think it's very good problem for Educational Round.

Funny:

peterwuyihong

3 years ago, # ^ |

A bit harder maybe, but all the same.

Al.Cash

+11

Can you explain your solution or provide some link to the theory behind it? It looks much simpler than author's.

+23

Let S(v,m) be the count of integers in the range 2..v that remain after sieving with all primes smaller or equal than m. That is S(v,m) is the count of integers up to v that are either prime or the product of primes larger than m.

S(v, p) is equal to S(v, p-1) if p is not prime or v is smaller than p². Otherwise (p prime, p²<=v) S(v,p) can be computed from S(v,p-1) by finding the count of integers that are removed while sieving with p. An integer is removed in this step if it is the product of p with another integer that has no divisor smaller than p. This can be expressed as

S(v,p)= S(v,p−1)− ( S(v/p, p−1)− S(p−1,p−1) ).

During computation of S(N,p) it is sufficient to compute S(v,p) for all positive integers v that are representable as floor(N/k) for some integer k and all p ≤ v^1/2.

NOTE: Pi(N) = S(N,N). When you call S(N,N) it will need to compute S(N/k,N/k) in its lower substate. Hence you can have all required values of Pi(N/k).

In my code DSUM(N,P) do the job of calculating S(N,P).

I used two arrays H[] and L[] for storing the values of S(N/k,p) in H[k] for k<=N^1/2 and for k>=N^1/2 I stored the values of S(N/k,p) in L[N/k].

For computation I started with p=2 and changed the values of all the state which is going to be affected by this particular prime. Continue doing this for all prime till N^1/2 and at the end for k<=N^1/2, H[k] will contain the values of Pi(N/k) and L[k] will contain the values of Pi(k).

PS: My complexity is O(N^3/4).

Idea: This Post!

Arg_007

8 years ago, # ^ |

Can I get your code please ???

sagitta

Can you explain why the time complexity of your solution is O(N^3 / 4)

(I find it difficult to calculate it)

jiaqiyang

Let $\text{[math]}$ .

Notice that v could only be i or $\text{[math]}$ , where 1 ≤ i ≤ m, and for each S(v, v) we would enumerate $\text{[math]}$ values to calculate it. So the time complexity of the above algorithm is

The former part is always smaller than the latter, so we could only analysis the complexity of the latter part, which would be same order as

and it's $O(n^{3/4})$ .

By the way, if you preprocess the π(m) for m ≤ n^2 / 3, you could find that the integral becomes

and it's $O(n^{2/3})$ . :)

← Rev. 3 →

I got AC there with the simple modification of the solution described in editorial:

k0st1a

+13

The editorial for this problem is a little modification of the materials from the lecture of Mikhail Tikhomirov...

Is it possible to find these materials?

likecs

I think he means to refer to this http://www.ams.org/mcom/1996-65-213/S0025-5718-96-00674-6/S0025-5718-96-00674-6.pdf

spharish

In problem F, how the recurrence dp(n, j) = dp(n, j + 1) + dp(⌊ n / pj⌋, j) is being derived?

friend

Here's what i think:

dp(n,j) counts all positive integers k with the properties:

1 ≤ k ≤ n
k = r₁^a₁r₂^a₂...r_v^a_v, where r₁, r₂, ... , r_v primes ≥ p_j.

Now we can split this set into 2 disjoint subsets:

all numbers from 1 to n inclusive whose prime factors are ALL bigger than p_j. This subset has exactly dp(n,j+1) elements.
all numbers from 1 to n inclusive that don't satisfy the previous property. Those are numbers in [1,n] that contain at least once p_j as a factor and all of their other factors are at least p_j as well. If k₂ is such a number then it takes the form:

k₂ = p_j^ar₁^a₁r₂^a₂... r_v^a_v = p_j * k₃,

where p_j is the j-th prime number and r₁, r₂, ..., r_v are all primes bigger than or equal to p_j.

k₃ is a number obviously in the range [1...⌊ n / p_j⌋] with every factor in its PPF (Prime Power Factorization) being at least p_j.There are dp(⌊ n / p_j⌋,j) such numbers,so the recursion is correct.

Protap_Ghose

In problem D, "Let's define a subset of the array a as a tuple that can be obtained from a by removing some (possibly all) elements of it ". Is there exists any case where (possibly all) all elements will be removed,i can`t fix it..

RikkaTakanashi

No.

SarvagyaAgarwal

What is the best approach for B if the constraints were higher (10^5 instead of 100 ) ?

the_art_of_war

I have only one idea to optimise it to O(n*k*log(m)) using segment tree.

bluefi

using penwick tree , we can solve O(n*m*log(k+n*m))

first we set the value Position[i] = position

a1 , a2 ,a3 ,.... an

Position[a1]= n*m+1, Position[a2]= n*m+2,... Position[ak] = n*m+k

and make variable pos = n*m;

and initialize penwick tree using Position[i] .

if we find item X, then add penwick_query(Position[x]) to return value.

and decrease_penwick(Position[x],-1) , Position[x]= pos--, penwick_increase(Position[x],1);

above action's time complexity is O(log(n*m+k) ).

-9

do you mean fenwick tree?

bluemmb

also you can write an O(n*m*log(k)) solution with ordered set.

http://codeforces.net/contest/665/submission/19748159

In problem F, can someone explain the two-step process of evaluating the DP States better?

prudvinit

Can someone explain me the condition cur+2^i >=k in problem E?

fifiman

A question regarding problem E. When I was solving the problem, instead of writing int b = (x >> i) & 1;, I wrote int b = x & (1 << i). This change gave me AC (i was in the same bounds as in the c++ solution).

What's the difference?

-Morass-

+10

Good day to you :)

It returns different value:

int b = (x >> i) & 1; Returns 1, if ith bit is 1

int b = x & (1 << i); Returns 2^i, if ith bit is 1

Hard to say, what happened next (for futher investigation, more code would be needed)

Hope it helped a bit ~ Good Luck :)

armyKid

can anyone plz explain D in detail !

unable to grab it!

thnxxxx

TouchMe

1.If there's multiple ones in original set, we should choose them, because 1+1=2, 2 is a prime number.

2.Now consider what are the extra elements we should insert into the answer. I donate the answer is {1,1,....,1,A,B,C,....}, look at the {1,A,B}, there are three elements, each of them must be odd or even, so there must be two element have the same parity, so add them together will get a even number larger than 2, that is definitely not a prime number.

3.So you see, if we exclude all the ones in the answer, the answer size must less or equal to 2.

NikaraBika

ans(Problem E) == (n * (n + 1) / 2) — ans(http://www.spoj.com/problems/SUBXOR/)

Hey guys, I use the DFS to solve problem D. I'm confused why my code passed test 11 only used 78ms where n equals to 1000, but get a TLE at test 12? here's my solution:code

Thanks

duckladydinh

For E: Can someone please explain why we have to flip the bit b in function get()?

Thank you.

Zearot

8 years ago, # |

Can someone explain what is RSQ structure? It is mensioned in problem F. Had no idea what it is. Thanks.

cmzuluagam

Could somebody explain me in problem E, why do we have to go down to the subtree (b xor 1) when (cur + 2^i) < k ?

vivukhue

6 years ago, # |

In problem E , L can equal to R . So I think we should check each elements of the array if it >= k

haimeo1201

6 years ago, # ^ |

mạnh

nitrogens

5 years ago, # |

Now we can simply solve the problem F with min_25 sieve in $$$O(\frac{n^{\frac{3}{4}}}{\log n} + \sqrt n)$$$ !!

I sincerely agree with you. :)

And notice that you need to calculate $$$\pi(\lfloor\frac n x\rfloor)$$$, choose Meissel-Lehmer and combine with min-25 can you reach a more efficient solution.

Edvard's blog

665A - Buses Between Cities

665B - Shopping

665C - Simple Strings

665D - Simple Subset

665E - Beautiful Subarrays

665F - Four Divisors