Разбор Codeforces Round #527 (Div. 3)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		int n, k;
		cin >> n >> k;
		for (int j = 0; j < n; ++j) {
			cout << char('a' + j % k);
		}
		cout << endl;
	}
	
	return 0;
}

1092B - Формирование команд

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	sort(a.begin(), a.end());
	int res = 0;
	for (int i = 0; i < n; i += 2) {
		res += a[i + 1] - a[i];
	}
	
	cout << res << endl;
	
	return 0;
}

1092C - Префиксы и суффиксы

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

int n;
vector<string> v;

string res;

bool check(const string &pref, const string &suf) {
	string s = pref + suf.substr(n - 2);
	multiset<string> vv, sPref, sSuf;
	for (int i = 0; i < n - 1; ++i) {
		sPref.insert(s.substr(0, n - i - 1));
		vv.insert(s.substr(0, n - i - 1));
		sSuf.insert(s.substr(i + 1));
		vv.insert(s.substr(i + 1));
	}
	if (vv == multiset<string>(v.begin(), v.end())) {
		for (int i = 0; i < 2 * n - 2; ++i) {
			if (sPref.count(v[i])) {
				res += 'P';
				sPref.erase(sPref.find(v[i]));
			} else if (sSuf.count(v[i])) {
				res += 'S';
				sSuf.erase(sSuf.find(v[i]));
			} else {
				assert(false);
			}
		}
		return true;
	}
	return false;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n;
	v = vector<string>(2 * n - 2);
	vector<string> big;
	for (int i = 0; i < 2 * n - 2; ++i) {
		cin >> v[i];
		if (int(v[i].size()) == n - 1) {
			big.push_back(v[i]);
		}
	}
	
	if (check(big[0], big[1])) {
		cout << res << endl;
	} else {
		check(big[1], big[0]);
		cout << res << endl;
	}
	
	return 0;
}

1092D1 - Великая Вовина Стена (Версия 1)

Разбор

Решение 1

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n){
		scanf("%d", &a[i]);
		a[i] &= 1;
	}
	
	vector<int> st;
	forn(i, n){
		if (!st.empty() && a[i] == st.back())
			st.pop_back();
		else
			st.push_back(a[i]);
	}
	
	puts(st.size() <= 1 ? "YES" : "NO");
	return 0;
}

Решение 2

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n){
		scanf("%d", &a[i]);
		a[i] &= 1;
	}
	
	set<pair<int, int>> seg, even;
	forn(i, n){
		int j = i;
		while (j + 1 < n && a[j + 1] == a[i]) ++j;
		seg.insert({i, j});
		if ((j - i + 1) % 2 == 0)
			even.insert({i, j});
		i = j;
	}
	
	while (seg.size() > 1 && !even.empty()){
		auto cur = *even.begin();
		even.erase(cur);
		seg.erase(cur);
		auto it = seg.lower_bound(cur);
		if (it != seg.end()){
			cur.second = it->second;
			if ((it->second - it->first + 1) % 2 == 0)
				even.erase(*it);
			seg.erase(it);
		}
		it = seg.lower_bound(cur);
		if (it != seg.begin()){
			--it;
			cur.first = it->first;
			if ((it->second - it->first + 1) % 2 == 0)
				even.erase(*it);
			seg.erase(it);
		}
		seg.insert(cur);
		if ((cur.second - cur.first + 1) % 2 == 0)
			even.insert(cur);
	}
	
	puts(seg.size() == 1 ? "YES" : "NO");
	return 0;
}

1092D2 - Великая Вовина Стена (Версия 2)

Разбор

Решение

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 1000 * 1000 + 13;

int n;
int a[N];

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d", &a[i]);
	vector<int> st;
	
	int mx = *max_element(a, a + n);
	
	forn(i, n){
		if (a[i] == mx) continue;
		
		int j = i - 1;
		while (j + 1 < n && a[j + 1] != mx){
			++j;
			if (!st.empty() && st.back() == a[j]){
				st.pop_back();
			}
			else if (st.empty() || st.back() > a[j]){
				st.push_back(a[j]);
			}
			else{
				puts("NO");
				return 0;
			}
		}
		
		if (!st.empty()){
			puts("NO");
			return 0;
		}
		
		i = j;
	}
	
	puts("YES");
	return 0;
}

1092E - Лес минимального диаметра

Разбор

Решение

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;
const int INF = 1000000000;

int n, m;
vector<int> g[N];

int bfs(int x, int dist[N]){
	queue<int> q;
	q.push(x);
	dist[x] = 0;
	int lst = -1;
	while (!q.empty()){
		int v = q.front();
		q.pop();
		lst = v;
		for (auto u : g[v]) if (dist[u] > dist[v] + 1){
			dist[u] = dist[v] + 1;
			q.push(u);
		}
	}
	return lst;
}

int distx[N], disty[N];
bool used[N];
vector<int> cur;

void dfs(int v){
	used[v] = true;
	cur.push_back(v);
	for (auto u : g[v]) if (!used[u])
		dfs(u);
}

int main() {
	scanf("%d%d", &n, &m);
	forn(i, m){
		int v, u;
		scanf("%d%d", &v, &u);
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	
	forn(i, n) distx[i] = disty[i] = INF;
	
	vector<pair<int, int>> comps;
	forn(i, n) if (!used[i]){
		cur.clear();
		dfs(i);
		int x = bfs(i, distx);
		int y = bfs(x, disty);
		for (auto v : cur) distx[v] = INF;
		bfs(y, distx);
		int d = disty[y], center;
		for (auto v : cur) if (distx[v] == d / 2 && disty[v] == d - d / 2)
			center = v;
		comps.push_back({d, center});
	}
	
	vector<pair<int, int>> ans;
	nth_element(comp.begin(), comp.end() - 1, comp.end());
	forn(i, int(comps.size()) - 1){
		g[comps[i].second].push_back(comps.back().second);
		g[comps.back().second].push_back(comps[i].second);
		ans.push_back({comps[i].second, comps.back().second});
	}
	
	forn(i, n) distx[i] = disty[i] = INF;
	int y = bfs(bfs(comps.back().second, distx), disty);
	
	printf("%d\n", disty[y]);
	for (auto it : ans)
		printf("%d %d\n", it.first + 1, it.second + 1);
	return 0;
}

1092F - Дерево максимальной стоимости

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

long long res, ans;

vector<int> a;
vector<long long> sum;
vector<vector<int>> g;

void dfs(int v, int p = -1, int h = 0) {
	res += h * 1ll * a[v];
	sum[v] = a[v];
	
	for (auto to : g[v]) {
		if (to == p) {
			continue;
		}
		dfs(to, v, h + 1);
		sum[v] += sum[to];
	}
}

void go(int v, int p = -1) {
	ans = max(ans, res);
	
	for (auto to : g[v]) {
		if (to == p) {
			continue;
		}
		
		res -= sum[to];
		sum[v] -= sum[to];
		res += sum[v];
		sum[to] += sum[v];
		
		go(to, v);
		
		sum[to] -= sum[v];
		res -= sum[v];
		sum[v] += sum[to];
		res += sum[to];
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	a = vector<int>(n);
	sum = vector<long long>(n);
	g = vector<vector<int>>(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	dfs(0);
	go(0);
	
	cout << ans << endl;
	
	return 0;
}

==================

int status[210]; //status[i] = whether i-th string is unused(0), marked as prefix(1), or suffix(2) for (int i = 0; i < 2*n-2; ++i) status[i] = 0; bool ok = true; string pref = "", suff = ""; //check whether all prefixes of *s* can be found from the input for (int i = 0; i < n; ++i) { pref += s[i]; bool found = false; for (int j = 0; j < 2*n-2; ++j) { if (status[j] == 0 && pref == affixes[j]) { status[j] = 1; //number for prefix (see above) found = true; break; } } if (found == false) { ok = false; break; } } //similar code for suffixes //... if (ok) { //success, iterate over *status*, if status[i]=1, print 'P', otherwise print 'S' }

cmp = find_all_reachable_from(1); for( i = 1 ; i <= n ; i++ ){ if( i is not in cmp ){ cmp1 = find_all_reachable_from(i) v1 = center_in( cmp ); v2 = center_in( cmp2 ); // add edge in v1 and v2 g[v1].push_back(v2); g[v2].push_back(v1); for( v in cmp2 ){ cmp.push_back(v); } } }

Комментарии (46)

Показать архивные | Написать комментарий?

M_H_H_7

5 лет назад, # |

-14

my solution on E was same with editorial but i got WA on test 8

→ Ответить

awoo

5 лет назад, # ^ |

You are searching for the wrong vertex. I'm really bad at all these graph definitions, is it centroid?) Imagine the following tree:

tree

You'll consider vertex 6 center but 4 is the real center.

Yes you're right,thank you

Brankonymous

← Rev. 2 →

deleted

nikesh04

← Rev. 3 →

My logic was almost same as the editorial. Can you look at it and explain what is wrong in it if possible. My solution is also failing in test case 8.

Solution Link is : Solution Link

Hmm, as far as I can understand, you consider the center the vertex with distance of half the diameter from one of its ends. That is wrong.

Diameter is 4, you can say that vertex 6 is center.

I'm not sure if there is a simpler way but I usually search for vertex with distances (diam / 2) from one end of the diameter and (diam — diam / 2) from the other end.

Thanks for helping. I got my submission acccepted :).

My code for finding centre was kinda tedious. Can you provide your code to find centre of connected tree?

Editorial has my code in it. It's basically bfs from x, from y and a loop over the vertices of the current component.

shahidul_brur

Here I have written my approach to solve problem F: [Editorial] Another Solution to Problem F(1092F) from Codeforces Round #527 (Div. 3)

the_hyp0cr1t3

4 года назад, # ^ |

Nice

OneLastTime

Kindly, would you link this to the official contest?

limabeans

how do we solve C but with bigger constraints?

How much bigger are we talking about? One can easily do O(input size) (like O(n²)) replacing multiset with trie but that's about it.

Draevich

if i'm not mistaking we can use hashes to compare string parts faster. It is one of the optimization for this task

saketh

+21

D1 is interesting! I believe the same idea extends if you are able to place horizontal blocks with size 1 × H and vertical blocks with size V × 1 (in this problem H = V = 2). Any contiguous section of H columns with the same height modulo V can be greedily deleted from consideration. It is possible to make all columns have the same height iff after making all such deletions all remaining columns (if any) have the same height.

tatya_bichu

for problem C: Store all given strings and their positions. Let's two strings of length n - 1 be A and B in given strings. Assume A to be largest prefix then search for A.substr(0, i) for 0 < = i < n - 1. If all such strings are present then A can be a prefix and check for B as suffix in similar manner. If this goes wrong check for B as a prefix and A for suffix. Is it a correct Approach?

But that's exactly the editorial?

I got WA at test 17

Oh, that's an interesting case. Let the test be string "abb". Imagine getting it wrong — prefix "bb " and suffix "ab". Each substring exist and the amount is correct. However, they can't make a full string.

Got it! Thank you.

gjaiswal108

I also have used the same approach,even I am getting correct answer for your test "abb", getting prefix="ab" and suffix ="bb". Still I am getting wrong answer on test case 17. Can you explain it why? awoo

you_paison

Can anyone tell what is the intuition behind the logic of D1 problem i.e how to approach and think as keeping them as odd and even and then deleting all even length segments then deciding if size <=1 then "YES" else "NO". Thanks in advance.

It's just an experience thing, I believe. Vova first told me D2 and I immediately was like "what if that is correct bracket sequences". It just felt alike. Details for implementation came pretty minor after it.

As for D1, turning the numbers to their parities is the most intuitive thing. You kinda trying to check what if there were just a single way to put bricks. And then come up with a strat to do this. The stack is harder but having some similar problems solved already helps find this approach here. The ending step is just common sense. I mean, obviously, either all the segments got destroyed, or all but the one of odd length left. Easier tests for this case (like 1 2 2) can help to understand.

alessandrosolbiati

3 lines implementation in python2.x of A solution

for _ in xrange(int(raw_input())):
    n, k = map(int, raw_input().split())
    print ''.join([chr(ord('a') + i%k) for i in xrange(n)])

find more here

noob77777

+13

I have a alternative solution to problem D1.

Clearly, by using vertical blocks we can change any given input to a binary representation. We simply use a[i] = a[i] % 2 . Now clearly a solution only exists when we can transform this representation to all '0's or all '1's

I claim that we can reach every possible valid state that has a solution by adding 3 i.e binary '11' to a set of all '0's. Example if we have only 4 columns we have possible states of '0000', '0011', '1001','0110', '1111' , '1100'. So, clearly if solution exists the binary representation should be divisible by 3 or '11'. Note that this is only valid when an all '0's solution exists. We also have to check another case for all '1's solution by using a[i] = (a[i] + 1) % 2 repeating the process.

So we simply check if your binary representation is divisible by 3 in one of the 2 cases or not. For that we check if absolute value of the difference between the sum of digits in odd places and even places in our binary representaion is divisible by 3 or not, i.e. abs(sum_odd_places - sum_even_places) % 3 == 0.

Overall Complexity is O(n) .

Solution Code : Python |Submission|

arvindf232

2 года назад, # ^ |

Your solution is incorrect. The following case

6
2 1 2 1 2 1

gives "YES" in your code, but official solution gives NO. In fact, answer should clearly be NO, You cannot add any horizontal brick at any moment. Divisible by 3 is a necessary condition, but not sufficient.

ArepitaDePernil

I was trying to solve problem E using centroids (not centroid decomposition) my idea is to find centroids for each connected component add an edge between 2 connected components and then find a new centroid on this new tree, and so on until there is only one centroid left, then I calculate maximum possible dist as maximum_height + 2nd maximum_height, I really do not know why but it gives me wrong answer on test case #8 because my answer is: 22 9 60

21 9 100

since I do not have access to the test cases anyone has some advice into what could be happening? I think the idea should work since the centroid is the node that is in the "middle" of each tree.

Actually centroid decomposition isn't working here. Because, even if it's the "center", that doesn't mean that its the node that have average shortest path to all other nodes.

Thanks for the reply now I know the difference between centroid and center

Cyber_Wizard

please someone explain how we can solve d2 question

I solved it using stack, the idea is that you need to always pair 2 elements in order to say that you can place a brick wall of size N which has to be divisible by 2 (this due to the 2x1 thing). The solution is something like this:

Given P as the array of elements, and S the stack we have the following:

if P[i] == S.top() we have a size 2 or divisible by 2 N , so we pop the top of S
if S.empty() || P[i]!=S.top() , we have a new possible wall to take into account we push the element into S IF P[i]<S.top() , why is that? just check this example:
4
1 2 2 1

As you can see there is no way to connect the 1's because the 2's can only increase so answer is NO

At the end of the algorithm you should have either a size 0 or size 1 stack, if you have a size 2 or more then you couldn't connect 2 or more elements so answer is NO

A size 0 represents that you have a solution so answer is YES
A size 1 represents that you may have a solution, on this case:
3
5 6 6

you can see you are left with 1 element but the answer is NO, that is because the element that should remain is always the maximum height possible , because if not there is no way to pair it with the other N-1 elements that form a single wall.

So if S.top()!=max_h then NO, else YES

That's pretty much it.

Predestination

please explain me the logic of D1 I am not able to understand.

Since you have a 2x1 block that you can either place horizontally or vertically, you then can assure this things:

You can always increase the height of any element of the array by 2 even if it is by itself
You can only increase the height by 1 if there are 2 elements connecting that create a segment , but as the size of blocks is 2 then it must be of even size

Having that in mind then you can use the parity instead of the elements itself, lets take an example where the array is called P:

1 2 2 3

As you can see on the case above you can increase P[1] because it pairs with P[2], but then you have an issue how can you pair P[0] with P[3]? well you increase 1 by 2 and it is 3, ok now a little thing, in math there are this rules:

even + even = even
odd + even = odd
odd + odd = even
even + odd = odd

So if you assume that you can reach any increasing odd number from an odd number, and any increasing even number from an even number, then you can pair 1 and 3 for example or 2 and 10, then what matters is the parity

If you look above I explained how to solve problem D2 , here is the same deal the difference is that arrays are like this:

0 0 1 1

The only change to the algorithm is that you do not need to check if P[i]<S.top() due to the vertical choice

VLADO

Can someone please tell me where my mistake is in problem E? I am doing exactly what the editorial says, but I'm using DFS instead of BFS to find the diameter and center, so maybe that's why it's wrong? Link — 47346955

Reckt

dfs2 function won't return the center of the diameter in all cases (I'm too lazy to write a test for that) anyways, I've fixed dfs2 and it just worked fine. here it is

Thank you so much for helping me, I really appreciate it.

devansh1497

Can someone please explain the logic for C problem in more detail?

You have two strings with length n-1. Let them be a1,a2,a3,...,an-1 and b1,b2,b3,...bn-1. Then the final string is either a1,a2,...,an-1,bn-1 (if first string is prefix and second is suffix), or b1,b2,...,bn-1,an-1 (if second string is prefix and first is suffix). So, we can try both combinations. Let this combined string be s. Now how do we verify that s is correct? We should check all prefixes and suffixes of it, and if s is correct, we should be able to find that prefix or suffix in the other given strings from the input (remember that in the input we have all the prefixes and suffixes of every length).

The constraints are small enough that you can use brute force.

For example, here is how you would check if all prefixes are good (you should do this with all suffixes right after). s is the string we want to verify is correct. All strings from the input are stored in an array affixes.

ankeet

For problem F, I think it would be more clear if you were to write the code for "undoing" the re-root operation as the "re-root" operation, but with v and to reversed:

		res -= sum[to];
		sum[v] -= sum[to];
		res += sum[v];
		sum[to] += sum[v];
		
		go(to, v);
		
		res -= sum[v];
		sum[to] -= sum[v];
		res += sum[to];
		sum[v] += sum[to];

osho_garg

What will this block do in the Problem C solution ?

else { assert(false); }

akSingh

Whenever there is a false statement within an assert block the program displays a Run time error and terminates . Since it is written in the problem statement that there is always a solution therefore the control will never be transferred to this block of code unless there exists no string and if that is the case then an error will be produced indicating to the user that there is some problem with the test data and not his logic. However run time error may arise due to other reasons too (obviously).

SamuelLim

Hi, I am not sure if there is a problem with Problem C test case 14. My code produced an answer which is totally opposite to the required answer, but somehow I can't find out what's wrong. Can anyone help?

This is my submission: https://codeforces.com/contest/1092/submission/54026479

Lezendary_sandwich

@PikMike in problem F. You could easily see that sum[v] is nothing but total sum — sum[v] i.e. sum[1]-sum[v]; res=res+sum[1]-2*sum[v] then to reverse re root; use res-=sum[1]-2*sum[v]

valdaarhun

4 года назад, # |

Hi. Could someone please explain the diagnostics message that i am getting in testcase 17 for problem 1092C? I am not able to understand why my code is giving a runtime error. Here's my submission 78355872

Never mind. I got it. It doesn't work with a testcase like "abb" as mentioned in one of the comments above by pikmike.

sagsango

someone please help me in this problem: My approach for adding edge :

Блог пользователя vovuh