Editorial of Educational Codeforces Round 14 - Codeforces

Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

→ Pay attention

Before contest
Codeforces Round 950 (Div. 3)
18:20:37
Register now »

→ Streams

Codeforces Round 950 Solution Discussion

By aryanc403

Before stream 20:35:35

View all →

→ Top rated

#	User	Rating
1	tourist	3757
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	maomao90	171
2	awoo	165
3	adamant	163
4	TheScrasse	159
5	maroonrk	155
6	nor	154
7	-is-this-fft-	152
8	Petr	147
9	orz	146
10	pajenegod	145

View all →

→ Find user

→ Recent actions

Detailed →

Edvard's blog

Editorial of Educational Codeforces Round 14

By Edvard, history, 8 years ago, translation, In English

In English

691A - Fashion in Berland

The problem was suggested and prepared by Arthur Jaworski KingArthur.

In this problem you should simply check the conditions from the problem statement.

С++ solution

const int N = 1010;

int n, a[N];

bool read() {
	if (!(cin >> n)) return false;
	forn(i, n) assert(cin >> a[i]);
	return true;
}

void solve() {
	int cnt = accumulate(a, a + n, 0);
	if (n == 1) puts(cnt == 1 ? "YES" : "NO");
	else puts(cnt == n - 1 ? "YES" : "NO");
}

Complexity: O(n).

691B - s-palindrome

The problem was suggested by Nikita Melnikov nickmeller.

In this problem you should simply find the symmetric letters by picture and also observe that the pairs

Unable to parse markup [type=CF_TEX]

and (p, q) is the symmteric reflections.

C++ solution

string s;

bool read() {
	return !!getline(cin, s);
}

string symmetric = "AHIMOoTUVvWwXxY";
map<char, char> opposite = {{'p', 'q'}, {'q', 'p'}, {'d', 'b'}, {'b', 'd'}};

void solve() {
	forn(i, sz(s)) {
		if (symmetric.find(s[i]) != string::npos) {
			if (s[sz(s) - 1 - i] != s[i]) {
				puts("NIE");
				return;
			}
		} else if (opposite.count(s[i])) {
			if ((sz(s) & 1) && i == (sz(s) >> 1)) {
				puts("NIE");
				return;
			}
			if (s[sz(s) - 1 - i] != opposite[s[i]]) {
				puts("NIE");
				return;
			}
		} else {
			puts("NIE");
			return;
		}
	}
	puts("TAK");
}

Complexity: O(n).

691C - Exponential notation

The problem was suggsted by user blowUpTheStonySilence.

This is an implementation problem. You should do exactly what is written in the problem statement. On my mind the simplest way is to find the position of the first not zero digit and the position of the dot. The difference between that positions is the value of b (if the value is positive you should also decrease it by one).

C++ solution

string s;

bool read() {
	return !!getline(cin, s);
}

void solve() {
	int pos = int(find_if(all(s), [](char c) { return c != '0' && c != '.'; }) - s.begin());;
	size_t dot_pos = s.find('.');
	if (dot_pos == string::npos) {
		dot_pos = s.size();
	} else {
		s.erase(dot_pos, 1);
	}

	int expv = (int) dot_pos - pos;
	if (expv > 0) expv--;
	forn(t, 2) {
		while (s.back() == '0') s.pop_back();
		reverse(all(s));
	}
	if (sz(s) > 1) s.insert(1, ".");
	if (expv == 0) printf("%s\n", s.c_str());
	else printf("%sE%d\n", s.c_str(), expv);
}

Complexity: O(n).

691D - Swaps in Permutation

The problem was suggested by Zi Song Yeoh zscoder.

Consider a graph with n vertices whose edges is the pairs from the input. It's possible to swap any two values with the positions in some connected component in that graph. So we can sort the values from any component in decreasing order. Easy to see that after sorting the values of each component we will get the lexicographically maximal permutation.

C++ solution

const int N = 1200300;

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

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

bool used[N];
vector<int> g[N];
vector<int> perm, pos;

void dfs(int v) {
	if (used[v]) return;
	used[v] = true;
	pos.pb(v);
	perm.pb(p[v]);

	for (auto to : g[v]) dfs(to);
}

int ans[N];

void solve() {
	forn(i, n) {
		g[i].clear();
		used[i] = false;
	}

	forn(i, m) {
		g[a[i].x].pb(a[i].y);
		g[a[i].y].pb(a[i].x);
	}

	int cnt = 0;
	forn(i, n)
		if (!used[i]) {
			cnt++;
			pos.clear();
			perm.clear();
			dfs(i);
			sort(all(pos));
			sort(all(perm), greater<int>());
			forn(j, sz(perm))
				ans[pos[j]] = perm[j];
		}

	forn(i, n) {
		if (i) putchar(' ');
		printf("%d", ans[i] + 1);
	}
	puts("");
}

Complexity: O(n + m).

691E - Xor-sequences

The problem was suggested by Zi Song Yeoh zscoder.

Let

Unable to parse markup [type=CF_TEX]

be the number of xor-sequences of length i with the last element equal to a_j. Let

Unable to parse markup [type=CF_TEX]

be equal to one if

Unable to parse markup [type=CF_TEX]

contains the number of ones in binary presentation that is multiple of three. Otherwise let

Unable to parse markup [type=CF_TEX]

be equal to zero. Consider a vectors

Unable to parse markup [type=CF_TEX]

,

Unable to parse markup [type=CF_TEX]

and a matrix

Unable to parse markup [type=CF_TEX]

. Easy to see that

Unable to parse markup [type=CF_TEX]

. So

Unable to parse markup [type=CF_TEX]

. Let's use the associative property of matrix multiplication: at first let's calculate

Unable to parse markup [type=CF_TEX]

with binary matrix exponentiation and then multiply it to the vector

Unable to parse markup [type=CF_TEX]

.

C++ solution

const int N = 101;

int n;
li k;
li a[N];

bool read() {
	if (!(cin >> n >> k)) return false;
	forn(i, n) assert(cin >> a[i]);
	return true;
}

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

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

int count(li x) {
	int ans = 0;
	while (x) {
		ans++;
		x &= x - 1;
	}
	return ans;
}

void mul(int a[N][N], int b[N][N], int n) {
	static int c[N][N];
	forn(i, n)
		forn(j, n) {
			c[i][j] = 0;
			forn(k, n) inc(c[i][j], mul(a[i][k], b[k][j]));
		}
	forn(i, n) forn(j, n) a[i][j] = c[i][j];
}

void bin_pow(int a[N][N], li b, int n) {
	static int ans[N][N];
	forn(i, n) forn(j, n) ans[i][j] = i == j;

	while (b) {
		if (b & 1) mul(ans, a, n);
		mul(a, a, n);
		b >>= 1;
	}

	forn(i, n) forn(j, n) a[i][j] = ans[i][j];
}

void solve() {
	static int a[N][N];
	memset(a, 0, sizeof(a));
	forn(i, n) {
		forn(j, n)
			a[i][j] = count(::a[i] ^ ::a[j]) % 3 == 0;
		a[i][n] = 1;
	}

	//forn(i, n + 1) clog << mp(a[i], n + 1) << endl;

	bin_pow(a, k, n + 1);

	int ans = 0;
	forn(i, n + 1) inc(ans, a[i][n]);
	cout << ans << endl;
}

Complexity:

Unable to parse markup [type=CF_TEX]

.

691F - Couple Cover

The problem was suggested by Michael Kirsche mkirsche.

Let's count the number of pairs with multiple less than p. To get the number of not less pairs we should sumply subtract from

Unable to parse markup [type=CF_TEX]

the number of less pairs. Let cnt_i be the number of values in a equal to i and z_j be the number of pairs from a with the multiple equal to j. To calculate the values from z we can use something like Eratosthenes sieve: let's iterate over the first multiplier a and the multiple of it

Unable to parse markup [type=CF_TEX]

and increment

Unable to parse markup [type=CF_TEX]

by the value

Unable to parse markup [type=CF_TEX]

. After calculating the array z we should calculate the array of its partial sums and find the number of less pairs in O(1) time.

C++ solution

const int N = 3100300;

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

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

int cnt[N];
li z[N];

void solve() {
	memset(cnt, 0, sizeof(cnt));

	forn(i, n) cnt[a[i]]++;

	fore(a, 1, N) {
		if (!cnt[a]) continue;
		for (int b = a; b < N; b += a) {
			if (b / a != a) z[b] += li(cnt[a]) * cnt[b / a];
			else z[b] += li(cnt[a]) * (cnt[a] - 1);
		}
	}

	fore(i, 1, N) z[i] += z[i - 1];

	forn(i, m) {
		li ans = li(n) * (n - 1) - z[p[i] - 1];
		printf("%lld\n", ans);
	}
}

Complexity:

Unable to parse markup [type=CF_TEX]

, where X is the maximal value in p.

Tutorial of Educational Codeforces Round 14

Tags

educational round 14, editorial

+47

Edvard
8 years ago
9

Comments

Comments (8)

Show archived | Write comment?

»

8 years ago, # |

← Rev. 2 →

Vote: I like it

0

Vote: I do not like it

For problem D,

Though not necessary , even has a larger complexity and even dsu can be used in a better way to lower complexity I always wanted to use some kind of heuristic in my code 19211367.

Got WA in contest due to some minor major mistake( A mistake that is so minor but changes everything you are doing :P ).

→ Reply

»

DigitalArtistKz

8 years ago, # |

Vote: I like it

0

Vote: I do not like it

In case someone faced the same issue. For problem E, my O(n3logk) solution in C# was getting TLE, so I parallelized matrix multiplication and got AC. 19309384

→ Reply

»

8 years ago, # |

Vote: I like it

0

Vote: I do not like it

Apologies all for what is probably a silly question.

The solution to 691D includes the line: const int N = 1200300; pti a[N];

I can't find any documentation for a pti datatype. I assume this is an abbreviation commonly used in codeforces solutions? If so can someone link me to an explanation of what this is? Or a solution where the abbreviation is defined.

→ Reply

»

»

8 years ago, # ^ |

Vote: I like it

0

Vote: I do not like it

I had never seen this abbreviation before, but looking through Edvard's submissions, for example, 19489538 you can see it means pair <int, int>.

→ Reply

»

7 years ago, # |

Vote: I like it

+3

Vote: I do not like it

I think that problem 691D - Swaps in Permutation have the same concept as problem 500B - New Year Permutation. I use dsu to solve both of these two problems.

Anyway, D is still very good problems I think so. Thanks zscoder.

→ Reply

»

6 years ago, # |

Vote: I like it

0

Vote: I do not like it

I think the complexity of problem D is wrong. did you mention the sorting complexity?

→ Reply

»

3 years ago, # |

Vote: I like it

0

Vote: I do not like it

why the answer for "mm" is NIE in problem B? isn't "mm" symmetric by the middle? or is it should be odd length string? from where can i infer that from the passage?

→ Reply

»

»

3 years ago, # ^ |

Vote: I like it

0

Vote: I do not like it

Right top corner of 'm' is round but left top corner of 'm' is not round. That's why "mm" is not symmetric.

→ Reply