And apparantly, it has more votes.

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.

I'd like more of these :D

That's nice.

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.

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.

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

It's so real:D

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.

check this

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

Please explain here

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://mirror.codeforces.com/contest/1393/submission/89257765

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!!

I don't think binary search is necessary.

Solution for O(n) time is easily achievable.

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

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

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.

finally when deletion happens in only either the first string or the second string

So, deleting nothing from the string == deleting the %.

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

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://mirror.codeforces.com/gym/320771/submission/110894283

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)

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.

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

   1       2       3
1  bcd     aza     taka
2  acd     zza     aaka
3  abd     zaa     atak
4  abc     zaz     ataa
5  abcd    zaza    atka
6                  ataka

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

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

This works in $$$O(L^3)$$$.

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

For each string, sort all strings obtained by deleting at most one character from this string. You can do it in $$$O(L^2 * \log L)$$$ for all strings.

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