1393A - Rainbow Dash, Fluttershy and Chess Coloring

Idea: AlFlen

**Tutorial**

Tutorial is loading...

**Solution (74TrAkToR)**

```
#include<bits/stdc++.h>
using namespace std;
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t, n;
cin >> t;
while (t--) {
cin >> n;
cout << n / 2 + 1 << '\n';
}
return 0;
}
```

1393B - Applejack and Storages

Idea: 74TrAkToR

**Tutorial**

Tutorial is loading...

**Solution (74TrAkToR)**

```
#include<bits/stdc++.h>
using namespace std;
int const MAXN = 1e5 + 5;
int cnt[MAXN];
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q, x, cnt2 = 0, cnt4 = 0;
char type;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> x;
cnt2 -= cnt[x] / 2;
cnt4 -= cnt[x] / 4;
cnt[x]++;
cnt2 += cnt[x] / 2;
cnt4 += cnt[x] / 4;
}
cin >> q;
for (int i = 1; i <= q; ++i) {
cin >> type >> x;
cnt2 -= cnt[x] / 2;
cnt4 -= cnt[x] / 4;
if (type == '+') cnt[x]++;
else cnt[x]--;
cnt2 += cnt[x] / 2;
cnt4 += cnt[x] / 4;
if (cnt4 >= 1 && cnt2 >= 4) cout << "YES" << '\n';
else cout << "NO" << '\n';
}
return 0;
}
```

1393C - Pinkie Pie Eats Patty-cakes

Idea: 74TrAkToR и lapochka_queen

**Tutorial**

Tutorial is loading...

**Solution (AlFlen)**

```
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100009;
int cnt[MAXN];
vector<int> a;
int n;
bool check(int x) {
for (int i = 1; i <= n; i ++) cnt[i] = 0;
for (int i = 0; i < n; i ++) cnt[a[i]]++;
set<pair<int, int>, greater<pair<int, int>>> ss; //use greater comparator to sort set in descending order
for (int i = 1; i <= n; i ++) {
if (cnt[i] > 0) ss.insert({cnt[i], i});
}
vector<int> b;
for (int i = 0; i < n; i ++) {
if (i >= x && cnt[b[i - x]]) {
ss.insert({cnt[b[i - x]], b[i - x]});
}
if (ss.empty()) return 0;
b.push_back(ss.begin()->second);
ss.erase(ss.begin());
cnt[b.back()]--;
}
return 1;
}
signed main() {
ios :: sync_with_stdio(0);
cin.tie(0);
int ttt;
cin >> ttt;
while (ttt--) {
cin >> n;
a.resize(n);
for (int i = 0; i < n; i ++) {
cin >> a[i];
}
int l = 0, r = n;
while (r - l > 1) {
int m = (r + l) / 2;
if (check(m)) {
l = m;
}
else {
r = m;
}
}
cout << l - 1 << "\n";
}
return 0;
}
```

Idea: 74TrAkToR

**Tutorial**

Tutorial is loading...

**Solution (74TrAkToR)**

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const maxn = 2005;
char a[maxn][maxn];
int cnt_up[maxn][maxn], cnt_down[maxn][maxn], L[maxn], R[maxn];
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) cin >> a[i][j];
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (i != 1 && a[i][j] == a[i - 1][j]) cnt_up[i][j] = cnt_up[i - 1][j] + 1;
else cnt_up[i][j] = 0;
}
}
for (int i = n; i >= 1; --i) {
for (int j = 1; j <= m; ++j) {
if (i != n && a[i][j] == a[i + 1][j]) cnt_down[i][j] = cnt_down[i + 1][j] + 1;
else cnt_down[i][j] = 0;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int go = j;
while (go <= m && a[i][j] == a[i][go]) go++;
go--;
for (int pos = j; pos <= go; ++pos) {
if (pos == j) L[pos] = pos;
else {
L[pos] = max(L[pos - 1], pos - min(cnt_up[i][pos], cnt_down[i][pos]));
}
}
j = go;
}
for (int j = m; j >= 1; --j) {
int go = j;
while (go >= 1 && a[i][j] == a[i][go]) go--;
go++;
for (int pos = j; pos >= go; --pos) {
if (pos == j) R[pos] = pos;
else {
R[pos] = min(R[pos + 1], pos + min(cnt_up[i][pos], cnt_down[i][pos]));
}
}
j = go;
}
for (int j = 1; j <= m; ++j) {
ans += (ll)min(j - L[j] + 1, R[j] - j + 1);
}
}
cout << ans << '\n';
return 0;
}
```

1393E2 - Twilight and Ancient Scroll (harder version)

Idea: AlFlen

**Tutorial**

Tutorial is loading...

**Solution (74TrAkToR)**

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int const maxn = 1e5 + 5, maxc = 1e6 + 5;
ll mod[2], P[2], p[2][maxc], rev_P[2];
vector < ll > h[2][maxn];
vector < int > sorted[maxn];
string s[maxn];
int nxt[maxc];
int a[maxc], dp[2][maxc], inf = 1e9 + 7;
int MOD = 1e9 + 7;
ll st(ll x, int y, int ok) {
if (y == 0) return 1;
if (y % 2 == 0) {
ll d = st(x, y / 2, ok);
return d * d % mod[ok];
}
return x * st(x, y - 1, ok) % mod[ok];
}
inline char get_c(int i, int x, int numb) {
if (numb < x) return s[i][numb];
if (numb + 1 < (int)s[i].size()) return s[i][numb + 1];
return ' ';
}
inline ll get_hash(int t, int i, int x, int len) {
if (len < x) return h[t][i][len];
return (h[t][i][x] + (h[t][i][len + 1] - h[t][i][x + 1] + mod[t]) * rev_P[t]) % mod[t];
}
inline pair < ll, ll > get_h(int i, int x, int len) {
return {get_hash(0, i, x, len), get_hash(1, i, x, len)};
}
inline int check(int i, int x, int j, int y) {
int len1 = (int)s[i].size(), len2 = (int)s[j].size();
if (x != len1) len1--;
if (y != len2) len2--;
int lef = 0, righ = min(len1, len2) + 1;
while (righ - lef > 1) {
int mid = (righ + lef) / 2;
if (get_h(i, x, mid) == get_h(j, y, mid)) lef = mid;
else righ = mid;
}
return get_c(i, x, lef) >= get_c(j, y, lef);
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mod[0] = 1e9 + 7, mod[1] = 1e9 + 9, P[0] = 29, P[1] = 31, rev_P[0] = st(P[0], mod[0] - 2, 0), rev_P[1] = st(P[1], mod[1] - 2, 1);
p[0][0] = 1, p[1][0] = 1;
for (int i = 1; i < maxc; ++i) {
for (int j = 0; j <= 1; ++j) p[j][i] = p[j][i - 1] * P[j] % mod[j];
}
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
for (int j = 0; j <= 1; ++j) {
h[j][i].push_back(0);
for (int pos = 0; pos < (int)s[i].size(); ++pos) {
h[j][i].push_back((h[j][i][pos] + p[j][pos] * (s[i][pos] - 'a' + 1)) % mod[j]);
}
}
nxt[(int)s[i].size() - 1] = (int)s[i].size() - 1;
for (int pos = (int)s[i].size() - 2; pos >= 0; --pos) {
if (s[i][pos] != s[i][pos + 1]) nxt[pos] = pos + 1;
else nxt[pos] = nxt[pos + 1];
}
int l = 0, r = (int)s[i].size() - 1;
for (int j = 0; j < (int)s[i].size(); ++j) {
if (s[i][nxt[j]] <= s[i][j]) a[l++] = j;
else a[r--] = j;
}
for (int j = 0; j < (int)s[i].size(); ++j) {
sorted[i].push_back(a[j]);
if (a[j] == (int)s[i].size() - 1) sorted[i].push_back((int)s[i].size());
}
}
for (int i = 0; i <= (int)s[1].size(); ++i) {
dp[0][i] = 1;
}
for (int i = 2; i <= n; ++i) {
int oks = (i - 1) % 2, ptr = 0, sum = 0, cur = -1;
for (auto key : sorted[i]) {
cur++;
while (ptr < (int)sorted[i - 1].size() && check(i, key, i - 1, sorted[i - 1][ptr])) {
sum += dp[(1^oks)][ptr];
if (sum >= MOD) sum -= MOD;
ptr++;
}
dp[oks][cur] = sum;
}
}
int ans = 0;
for (int i = 0; i <= (int)s[n].size(); ++i) {
ans += dp[(n - 1) % 2][i];
if (ans >= MOD) ans -= MOD;
}
cout << ans << '\n';
return 0;
}
```

Here is my unofficial editorial for A-D:

https://codeforces.com/blog/entry/81216

And apparantly, it has more votes.

Here are editorials for A-D in video format if anyone prefers that over text (sorry, no E, I'm not good enough to solve it): https://www.youtube.com/watch?v=oBYxcIjfoGM. Solution timestamps are in the description.

hate people that think if the contest was hard for them then it is bad I think that it was a nice contest. Thanks to the authors and testers. maybe just E1-E2 problem was a little bit hard for div 2

Definitely. The problems were hard but interesting and I really enjoyed upsolving. Perhaps the editorial should have been uploaded earlier, but the contest itself was enjoyable.

Idk, a lot of people mainly got mad because reading the long problem statements was headache inducing.

Except that statements weren't that long

Long is relative, they were definitely longer than they needed to be.

Though the editorial is late,it's an interesting contest.

![ ]()

haha

If you can read Chinese,I'd to recommend my blog

I'd like more of these :D

That's nice.

Why the answer is 3 when the $$$n$$$ is 4.

I think the answer is 2.

Answer is (n/2 + 1) .

Where am I......is this atcoder?

something similar haha :)

Why do so many people dislike editorial? If this is due to a delay in editorial, then we are just waiting for a good translation into English to make it clearer for you. I think we need to support AlFlen, as she tried a lot for the round and now she can get upset. This is our 1st round. Next time, we will pay attention to all the mistakes made in this round and make the round even better!

I think the round was great and hope to have more rounds of you guys, thanks!!!

I think, the problems were really good and interesting. I think ,many of us definitely have learnt something while solving the problems. But also, the problem statements were too lengthy and the delay of publishing the english editorial have disappointed the contestants.

I hope this comment of mine makes you two feel better, since this is the only reason I'm writing the comment.

In my opinion, the round was amazing (maybe not amazing but quite nice). Unfortunately, I should agree that problem statements were a bit long. I believe you can shorten them in the next round(s).

I don't know whether the problem D was diverse or not but I loved the question. I brainstormed for quite long time and finally figured out one solution. It made me feel amazing and I learned a lot from the question.

I don't think the reason why people are downvoting the editorial is the delay. Delay is understandable as its reason is clearly stated. The contest announcement was downvoted as well after the contest, because the upvotes were way higher before the contest, if I remember correct. The downvotes might be from the same people. Honestly, this hatred makes no sense.

Please be aware of us: the people that loved both your contest and you two.

We wish you good luck on your next preparations! (And stay safe)

I'll hope to learn more when the editorial comes out, though as among lot of people,I didn't like sentence framing a little as it got confusing.(Little Understandable if I guess it isn't your first language either) But would look forward to your next round . Def it'll get more support with few corrections. I'm trying to get better at dp and 4th was a good exercise. Thanks. :)

its because pupils and newbies have no brains

You kind of missed the deadline. People complained about the problemstatements and then had to wait for the tutorial. Downvotes is what you get if you upset people.

Downvotes is not a quality measurement, it is a measurement of emotions.

Unofficial Editorial for A in

English, complete beginner friendly:ExplainationIf the language of problems were formal and short than this round would have been great. BTW Thanks for the editorials.

Can Anyone explain me the

"DFS and similar"way of solving Problem D?The way I did it is mostly dp but use bfs to calculate.

Let $$$dp[i][j]$$$ be the number of possible desired square that centered at $$$(i,j)$$$. It’s obvious that $$$dp[i][j] = min(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1])+ 1$$$ as long as those four around is the same alphabet with the center. To calculate this, I simply find all square which $$$dp[i][j] = 1$$$ (which is easy to find) and use BFS from those square to calculate dp for all squares.

Come on guys, the editorial is admittedly pretty late (and still incomplete) but that's not really a reason to downvote the blog to hell. I'm sure the authors are working hard to get it out. Although, I am still curious to why translating is taking a long time.

If it has to do with problem quality, I don't even know where to start. People can find something bad in everything.

We entrusted the translation to more experienced people and now we are waiting for it to be ready

Can Some One Plz Help Figure, What Could Have Been The Problem With Rectangular Field In The First Question

EDIT: Now, they have updated the English version.

It's so real:D

Finally here!

What will be the O(n) solution of C problem

I'm not sure if the O(n) really existed. Personally I don't think O(n) exist in this one, except assuming Radix Sort is O(n) (which tbh, hell, why would you write radix anyway when you have std::sort that still pass the test)

But for O(nlogn) there're some slight ideas I can give to you.

First, you hash the amount of each type (2,2,1,3,1,4,4,2,4,5,6) will be A[1] = 2, A[2] = 3, A[3] = 1, A[4] = 3,...) (O(n))

Then sort it (2,3,1,3,1,1) --> (1,1,1,2,3,3) O(nlogn)

Max is 3. Amount of max(AmountMax) is 2.

The idea of the calculation is that you put the type that has the maximum amount (in this case, 2 and 4) alternately first.

--> 2,4,__,2,4,__,2,4 :: Distance from this will be Max-1.

Then, you put the rest( in this case, 1,3,5,6) in the space between these 2,4 sets to increase the distance. Distance from this will be (Amount of non-max number (or 1+1+1+2=5) divided by amount of space (which is Max-1))

So, the distance can be calculated in O(n).

In case you want to see the real code, I have one in my submission. It's pretty hard to read though. If you have some questions, you can ask.

well i guess i have easier code to understand: 89231819

yeah that's much better.

You don’t need radix sort to make this algorithm run in O(n). The problem already said that $$$a_i <=n$$$ so simply run through the hash array, find the maximum, and run again to find the number of maximum. (It could also be done in one loop.)

check this

https://codeforces.com/contest/1393/submission/95337238

Can anyone explain the Binary Search solution to the C Problem ? Please explain how to perform the check whether a given minimum found by Binary Search is valid or not?

Please explain here

yeah, there are lot of video editorials available as well, go through youtube if you don't find em.

So I came across the binary search solution in this contest only. You are using the binary search to guess the largest number possible which can accomodate all numbers.

Think like this, the largest difference between numbers is going to be n. (when all numbers are different). and it's gonna be 0 when all numbers are same.

So what i do is i try with mid. (n-0)/2. If i can create a possible permutation in which all like numbers are atleast at a gap of n/2. then I'll search in between range of n/2 and n. and so on.(Basic logic of binary search).

If n/2 fails then obviously I try with a shorter number. This helps coz. If i try iteratively it'll be

`O(n)`

but with this I can make it`O(log(n))`

.How we check the possible arrangement is like scheduling of numbers.

Take a map and store all frequencies of each number.So you have some key value pair.

Where first value corresponts to key i.e number and value is it's frequency.

Now I store this in reverse order in set . the frequency being the pair.first and number being pair.second. How this helps is to keep a sorted order with

`greater`

where number with highest frequency is always at the top after every updation. ( I guess like max_priority_queue.PROCESS.

1) pick the number on top of set. and since I assumed the partition size to be let's say

`k`

with binary search I store it in a vector. and decrease the count from the set. and reinsert it after updation of frequency.2) The purpose of vector is , when the vector gets filled to size

`k`

. (this first element was used k-1 steps back in our sequence hence can be pushed again in our expected permutation and we continue the process.2.1) If frequency count of first element of vector becomes 0. We can no longer use it.

I hope this helps , go through internet and you'll find a better explaination than this, I guess.

Thanks for the reply. I got it accepted, if anyone wants the Binary Search approach : https://codeforces.com/contest/1393/submission/89486191

In B, condition should be

sum4 >= 1andnot sum4 <= 1.If anyone need detail explanation ( not a video tutorial ) for B & C

Can anyone explain me editorial of problem C?

when maximum occurrence 1 time

n = total array size

m = maximum occurrence number

result = ((n-1)/(m-1))-1

n = 8

1 1 4 6 4 6 4 7

m = 3 (cz 4 total 3 times)

so result = ((n-1)/(m-1))-1 = 2

when maximum occurrence more than 1 time

n = 7

1 1 2 2 4 4 7

m = 2

but 1 two time 2 two time 4 two time

so let i = 3

result = ((n-i)/(m-1))-1 = 3

Has anyone thought of a BFS solution for problem D? I did try to find a DP solution but could only think of BFS when I upsolved it the day after the contest.

Your question does not really make sense, but I suppose you could think of dp only. So I'll post the bfs sol here: Let's call rhombus lvl 1 just one square. Rhombus lvl 2 is the cross etc...Now you need to realize this : if you have a connected component consisting of the same letters the borders of this component are going to be the middles of rhombi lvl 1. So you label every square which is rhombus lvl 1 as rhombus lvl 1. (these are easy to recognize, they have a different letter right next to them. ) Every unlabeled square is rhombus lvl > 1. Now you can already see, that all squares that are unlabeled and next to a rhombus lvl 1 will be rhombi lvl 2. You label them as lvl 2 and continue for next lvls... This is what gives you the multisrc bfs solution. The lvl of a rhombus will be the distance to the nearest lvl 1 square.

code : https://codeforces.com/contest/1393/submission/89257765

Apparently that's what I thought! I wish I could get it within the contest though :( my code: https://codeforces.com/contest/1393/submission/89314195

3b1b style visualization of neal's clean code to problem B, originally posted on Announcement blog due to late editorial, linking here

Why does this contest have so many downvotes? The problems are quite interesting.

can anyone explain me the chess problem rule . how they are putting blocks one by one.

i am new ti competitive coding . kindly try to explain me in detail.

I'll try to explain it as clearly as i can. Now first imagine a big value of n. Now, we know that the first player will color the border most i.e. if you think it is of a grid then the 1st player will try to fill row(1), row(n), col(1), col(n). Lets call this as frame1. Now we know that the goal is to color the grid as a chess board so the first player will color alternatively. Now, when the second player will start coloring frame1 will be fully colored as well as some of the blocks in frame2 will also be filled. Now notice that frame2 is row2, row(n-1), col(2), col(n-1). The size of frame2 is 2 less than frame1. Now, when the first player again starts coloring the frame2 gets fully colored along with half of frame3 (which is 2 less than frame2).

Now, if you see a pattern that frame1 gets filled in 2 steps and consecutive frames in 1 step. So, the ans = number of frames + 1; number of frames = n/2 as for each frame n is decreased by 2.

Hope that helps!!

can someone explain problem c and also the role of the binary search

I don't think binary search is necessary.

Solution for O(n) time is easily achievable.

My Solution — https://codeforces.com/contest/1393/submission/89264631

Feel free to ask if didn't understand anything in my code.

No editorial for E1? =(

Problem E1/E2 also has a O( L ) solution, but it is an implementation nightmare, and the constant overhead possibly makes it worse than the O( L*Log L ) solution. The idea is to consider the cases when deletions are from both the strings, and the first string deletion is to the left of second string deletion, when it is to the right of it, and finally when deletion happens in only either the first string or the second string — https://codeforces.com/contest/1393/submission/89457260

Your approach sounds interesting, and I'm yet to dive into your code, but perhaps we can kill off the third case by adding a 27th character, say

`%`

, to the end of each word.So, deleting nothing from the string == deleting the

`%`

.Storyforces

Can someone please explain the meaning of "It allows you to use the binary search on the answer" in 3rd question in the editorial.

For 1393 A , if n=7 my answer is coming out to be 5 . Can someone explain how is it 4?

I will explain you my logic for A. Let's say we know answer for i and we want to find for (i+2)x(i+2)(Adding two rows and two columns at all four sides of (ixi) matrix ). Now, if let's say person A is the last one to finish square ixi then the person A will also complete the squares he is supposed to complete in (i+2)x(i+2). And then person B will finish the (i+2)x(i+2) squares he is supposed to colour. Hence we can conclude that to colour (i+2)x(i+2) matrix we need only one more turn as compared to ixi matrix. So for a particular nxn matrix we can divide the case where n is odd or even. For odd n, for 1x1 we need 1 turn, for 3x3 we need 2 turn, so for odd n, the answer is number of odd numbers from 1 to n which is (n+1)/2. For even n,number of turns for n=2 is 2. For n=4 is 3. So number of even numbers from 2 to n is n/2. But since initially we need 2 turns for n=2, we need to add 1 to the result. So for even n, we need n/2+1 turns. So for your question of n=7, for 1x1 we need 1 turn, for 3x3 we need 2 turn, for 5x5 we need 3 turns and for 7x7 we would need 4 turns.

What does it mean by "We can use binary search and hash to compare strings in O(logL)" in the editorial of Problem E2?

First you need to calculate the prefix hashes for strings $$$s_1$$$ and $$$s_2$$$. Let these be $$$hash_1[1...n]$$$ and $$$hash_2[1...m]$$$ respectively ($$$|s_1| = n$$$ and $$$|s_2| = m$$$), where $$$hash_1[i]$$$ is the hash for string $$$s_1[1...i]$$$.

For a given $$$i$$$ that you're searching on, if $$$hash_1[i] = hash_2[i]$$$, then you know that $$$s_1[1...i] = s_2[1...i]$$$, so the different character would be in the right half. Otherwise, if $$$hash_1[i] \ne hash_2[i]$$$, then there must be some different character in $$$1...i$$$, so search the left half.

The specific hash method (rolling hash) used in this problem allows you to calculate the hash for any substring by making $$$(hash[j] - hash[i-1]) \div k^{i-1} = \text{(hash of }s[i...j]\text{)}$$$. This can be used to get the hash of $$$s[1...i-1, i+1...n]$$$.

Hey,

Can someone explain the data structures solution for the Problem B?

Sure maintain a set of all planks and their counts in a set ordered by the counts(decreasing). then simply check all the conditions ( for this you need only the first 3 plankcounts).Also, Deletion and updating in a set can be performed easily in O(logn) code-https://codeforces.com/gym/320771/submission/110894283

Can someone please explain to me why my solution for D fails, or just point out a (small enough) case that does not produce the expected output? 89490717

is this the first editorial that got downvoted ?

Also, I'm a noob and i can't figure out what does this part in editorial for B do. Can anyone plz explain ?

Here cnt2 and cnt4 stores the total number of pair of logs and total number of quadruplets of logs. And cnt(x) stores the number of logs of size x. Suppose cnt(x) is initially 7. Now it contributes 3 towards cnt2 (as it has 3 pair of logs) and 1 towards cnt4 (as it has 1 quadruple). Now after increasing the value of cnt(x) by 1 it becomes 8 which should contribute 4 towards cnt2 and 2 towards cnt4. So that's why we decrease the value of cnt2 and cnt4 before increasing cnt(x)

so its like we go back one step ?

Exactly!!

I hope its not too late...can someone please tell me what is wrong with this 89254760. I tried to solve the queries online... I kept the count of how many groups of 8, 6 ,4, 2 are there after each query... If i am missing some case please tell as i could not figure it out all this while.... Thanks in advance!!

E is a really nice problem ! Thanks,AlFlen and 74TrAkToR!

Could someone please explain the Problem E editorial in detail. I'm not able to understand the following

"Let's use dynamic programming dp[i][j] the number of ways to form the non-decreasing subsequence on the strings 1..i, s.t. the delete character in string i is j. This works in O(L3)" : How do we calculate dp[i][j] from smaller values of dp

"For each string, sort all strings obtained by deleting at most one character from this string. You can do it in O(L2.logL) for all strings." , Could someone please give an example of this

Q1: $$$dp[i][j] = sum(dp[i - 1][k], k = 0\rightarrow n \mid str[i - 1][k] \leq str[i][j])$$$, $$$str[i][j]$$$ represents the string generated by deleting the j-th (1-beginned index) character from string $$$i$$$. $$$str[i][0]$$$ represents string $$$i$$$ itself.

Q2: "For each string, sort all strings obtained by deleting at most one character from this string." Let's take

`'abcd'`

as one of "each string". Then "all strings obtained by deleting at most one character from this string" represents the list ['abcd', 'bcd', 'acd', 'abd', 'abc']. Then sort them, we get the list ['abc', 'abcd', 'abd', 'acd', 'bcd']. For each string of length $$$l$$$, it takes $$$O(l^2\log l)$$$ to do that, because the list is $$$(l+1)$$$ long, and each time of comparing costs $$$O(l)$$$, too. But does $$$O(l^2\log l)$$$ sums up at $$$O(L^2\log L)$$$? I don't really understand, too. Waiting for better answers.For the first question, how is it ensured in the dp that that the different strings are in non-decreasing order. If possible could you please give a short example ?

Consider all the possible strings for the first case (from here is called $$$sub$$$):

In the above example, $$$dp[3][4]$$$ would be the number of sequences of the form $$$[sub[1][i_1], sub[2][i_2], sub[3][4]] = [sub[1][i_1], sub[2][i_2], ataa]$$$.

To (naively) move from $$$i-1$$$ to $$$i$$$, for each $$$j$$$, count the number of modified strings in $$$sub[i-1]$$$ that are $$$\le sub[i][j]$$$. $$$dp[i][j] = \sum dp[i-1][k]$$$ for every string $$$sub[i-1][k]$$$.

You can generate each $$$sub[i]$$$ in $$$O(|s[i]|^2)$$$ time and sort in $$$O(|s[i]|^2 \log |s[i]|)$$$ time. This overall comes out to $$$O(L^2 \log L)$$$ worst case (one giant string of length $$$L$$$).

Oh, $$$a^2+b^2\leq(a+b)^2$$$, I forgot that! Thx! Now I'm sure it's an $$$O(L^2\log L)$$$ algotithm!

Very sad to see dislikes for this beautiful problemset. Dislikes maybe because of long english statements (i did not find statements long , many past rounds contain more than this english) , late editorial, hard E . Problems are so tricky. The problems are really beautiful I have learnt other methods to solve B,C,D. Thank you so much.

Actually, although I've never solved the E/F problem in any div2 contests(and I didn't solve the problem D in this contest too, shamed), I don't think the problem E1 & E2 is so hard that it should be blamed of and the contest editorial should get a -119 voting. Anyway, if you just want to solve it in your mind rather than coding it and get an AC in the 2h contest time, it's able to do that. I thought these problems after the contest and got my solution, it is close to the NlogN solution, although I didn't do the hash and I got a wrong complexibility. I believe I can't solve the problem in the contest, but it's because of my insufficient capability, not the problem itself. I'm not saying that I can solve this problem and making a show of myself expressing that "Hey, I can solve this problem, you can't!", but I just want to say that the problem is not unsolvable and the -119 voting is unbelievable. It's not a problem that the problem contributor don't want you to solve, and it tests your mind and your way of thinking rather than your knowledge of uncommon algorithms. Every problem of this contest is doing so, and that's really cool. I think E1&E2 is a good problem, and the Round #662 is a good contest, from the bottom of my heart. Thanks to the problem contributor. Thanks for your reading. Sorry for my poor English.

Another Editorial for Problem D:

Let's enumerate on the bottom cell of a cloth. Define

`dp[i][j]`

as: the number of clothes that use the`cell[i][j]`

as it's bottom cell.`dp[i][j]`

are initially 1 for all $$$(i, j)$$$, now let's translate them. We can find that if`dp[i][j] == X`

, then each of`(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1] and dp[i - 2][j])`

should be at least $$$(X - 1)$$$, and all of these positions are filled with the same letter. So it comes:Finally, $$$ans = \sum_{i=1}^{n}\sum_{j=1}^{n}dp[i][j]$$$.

Great problem, and simple solution, thanks to Angavid. I told him a wrong dp solution (with a wrong complexibility), and he worked out this beautiful solution in 5 min.(He solved this problem in a totally different way(even not dp!) in the contest, and I don't understand it until now) Thanks to him. ydyyds!

For DIV2 D, a cell is the center cell of a pattern of size k if and only if the neighbouring cells are patterns of size k-1, I thought about this approach but couldn't formulate a solution in the specified complexity, did anyone follow the same?

UPDATE : Thanks to LUL____SEPLED1305 I understood, we have to figure out cells with value 1, all it's unvisited neighbours should have value 2, it can't be 1 because we already figured out those cells, it can't be 3 because it's neighbour is 1, we can use induction to extend this.

Submission : 89601502

nice contest

Do you think it's okay to cut off $$$O(n \log n)$$$ solutions to E2 with a decent constant? Because I don't think it is. There's no reason to put such a strict time limit there.

can anyone please explain why in problem 2,we need atleast 4 pairs for making rectangle,it should be 2 pairs since we only need 2 pairs to make rectangle,we already made a square when we have 4 planks of some length

1393 BPLEASE HELP ME IN THE SOLUTION ,NOT GETTING WHICH CASE IS NOT CONSIDER## include<bits/stdc++.h>

## define int long long

## define rep(i,a,n) for(int i=a;i<n;i++)

using namespace std; void func() { int n;cin>>n; int a[n],b[100002]={0}; rep(i,0,n) { cin>>a[i]; b[a[i]]++; }

int p2=0,p4=0,p6=0,p8=0; rep(i,0,n) { if(b[i]>=8)

p8++;

else if(b[i]>=6) p6++; else if(b[i]>=4) p4++; else if(b[i]>=2) p2++;

} int q;cin>>q; while(q--) { char c; int k; cin>>c>>k;

if(c=='+') { if(b[k]==7) { p6--; p8++; } if(b[k]==5) { p4--; p6++; } if(b[k]==3) { p2--; p4++; } if(b[k]==1) p2++; b[k]++;

} if(c=='-') { if(b[k]==8) { p8--; p6++; } if(b[k]==6) { p6--; p4++; } if(b[k]==4) { p4--; p2++; } if(b[k]==2) p2--; b[k]--; } if((p8>=1)||(p6>=2)||(p6==1&&p4>=1)||(p6==1&&p2>=1)||(p4>=2)||(p4>=1&&p2>=2)) cout<<"YES\n"; else cout<<"NO\n"; } } signed main() { func(); }

AlFlen I can't understand how check function is working in Problem C solution. Can you explain? How do we make sure that x will satisfy the constraints?