**Tutorial**

Tutorial is loading...

**Solution**

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

**Tutorial**

Tutorial is loading...

**Solution**

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

**Tutorial**

Tutorial is loading...

**Solution**

```
#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 - Great Vova Wall (Version 1)

**Tutorial**

Tutorial is loading...

**Solution 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;
}
```

**Solution 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 - Great Vova Wall (Version 2)

**Tutorial**

Tutorial is loading...

**Solution**

```
#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 - Minimal Diameter Forest

**Tutorial**

Tutorial is loading...

**Solution**

```
#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 - Tree with Maximum Cost

**Tutorial**

Tutorial is loading...

**Solution**

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

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

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

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

Yes you're right,thank you

deleted

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.

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

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

Nice

Kindly, would you link this to the official contest?

how do we solve C but with bigger constraints?

How much bigger are we talking about? One can easily do

O(inputsize) (likeO(n^{2})) replacing multiset with trie but that's about it.if i'm not mistaking we can use hashes to compare string parts faster. It is one of the optimization for this task

D1 is interesting! I believe the same idea extends if you are able to place horizontal blocks with size 1 ×

Hand vertical blocks with sizeV× 1 (in this problemH=V= 2). Any contiguous section ofHcolumns with the same height moduloVcan 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.for problem C: Store all given strings and their positions. Let's two strings of length

n- 1 beAandBin given strings. AssumeAto be largest prefix then search forA.substr(0,i) for 0 < =i<n- 1. If all such strings are present thenAcan be a prefix and check forBas suffix in similar manner. If this goes wrong check forBas a prefix andAfor 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.

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? PikMike

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.

Thanks a lot sir.

For Uniform String, I had just made an array alphabetically like if n=5 and k=3 so make it abcab here only 3 letters a b c are used. Thus making the easiest solution I think.

3 lines implementation in python2.x of A solution

find more here

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'sI 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|

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

vs

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

The first approach of D1 can be implemented using linked list. The complexity will be

O(n).Code here: Code

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.

Great explanation bro, thanks

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:

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

thank u so much bro ,this helps me a lot thank u

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

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.

D1: when 'n' is odd does the bracket analogy still hold?? or what does that even mean then? obviously valid bracket sequences must be of even length, so I am a little confused. Can anyone please clarify??

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 thatsis correct? We should check all prefixes and suffixes of it, and ifsis 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).

sis the string we want to verify is correct. All strings from the input are stored in an arrayaffixes.I was trying to solve Problem C but my answer is wrong for test 4, can anybody help??I have attached my solution Solution Link

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

vandtoreversed:What will this block do in the Problem C solution ?

else { assert(false); }

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

Thank you :)

I am not able to understand why i am getting WA on test 9 for question 1092D1. Link to my solution

What's wrong in my code for 1092C ? I got this error code on test case 9

`wrong answer The number of 'P's and 'S's should be one and one for length 1`

Found the reason?

For problem D1,

"Now imagine the following greedy solution. While you have some segment of the same parities of even length, fill it with horizontal bricks. This operation merges this segment with one to the left and to the right. If there is a single segment left then the answer is "YES". Otherwise it's "NO".

The proof is left to the readers"Can anyone help me with the proof of this algorithm?. I am stuck with the proving part.

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

@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]