Good to have a rain after a drought

Good Luck coders ;)

I think Codeforces community doesn't like wishes and greets...

its rated for you

Educational Codeforces Round 62 [Rated for Div. 2], Isn't just the title enough to answer your question ?

There is no out of contest for Educational Rounds. They are for everyone. Just, it is rated for the division 2 participants.

WOW! MADE IT!!

everybody let us go!

What is the test case 2 for Problem B?

True. The statement for A ruined the contest for me.

Note that there are no odd palindrome substrings of length > 1 if and only if there are no palindrome substrings of length 3. Then, note that a substring is a palindrome of length 3 if and only if the first character equals the last character in the substring. Thus, you can decompose the array into odd and even index arrays, and the problem becomes how many ways to fill in the array such that no two consecutive elements are equal. Then, we notice that we can further decompose each array into arrays of the form "# -1 -1 -1 .... -1 -1 -1 #", where # is either nothing or a positive element. From here, figuring out the number of constructions is an old HackerRank problem, with a solution on GeeksForGeeks.

Note that "no palindrome of odd length=no palindrome of length three", then solve for odd/even indices of the array separately.

You can see my dp solution here 51717191

You have to find first '>' from left and '<' from end. From this points you can get delete rest of them.

After I finished the contest, I had some submissions on my account which I didn't do. It was almost same with my previous wrong submissions. So, I strongly think that my account was hacked. Now I changed the passwords :(

He should be banned

It seems it's okay to remove "It seems" in your comment. Other interpretations seem impossible.

https://mirror.codeforces.com/contest/1140/submission/51701961 https://mirror.codeforces.com/contest/1140/submission/51721098

He has also copied your submission.

Edit: seems it was after contest...

but how can one came to know dotorya password

https://atcoder.jp/contests/agc032/standings

If you are told the minimum beauty value of your elements, could you easily find out what the optimal elements to pick would be?

Store beauty and length in a vector of pairs. Sort by beauty in decreasing order. Now travel from index 0 to n-1. If index < k , then take sum of all lengths till index and multiply it by current beauty and keep max of the answer. Store the lengths in a min-heap or a priority queue with min on top. If index>=k then check where current length is greater than min length in heap or not. If it is greater than min length in heap, delete min from heap and add current length to heap and accordingly change the sum of k top lengths. Then take the required product and keep the max.

sort according to beauty in descending order . Then use priority queue to keep track for k-1 largest length songs .

Sort songs in decreasing beauty, and check for each of them what elements to pick such that length of k or less songs are biggest (and those elements have beauty greater or equal than picked song)

I actually thought D was probably one of the most nicely written problems in the set. Their definition of triangulation was a bit different than what I'm used to, but triangulation of a polygon is a very widely used thing that you should know.

In my opinion, none of the problem statements were badly written, they presented exactly what they wanted to. The matter of fact is that if somebody finds it difficult to understand the task, he marks it as badly written. Believe me, not only is solving a task a skill that comes from practice but understanding a task quickly also comes from practice and experience. So don't blame the statements. Sometimes statements are just complex and not "badly written". Just because you are taking time to analyse them and sort everything out in your head, doesn't mean they are badly written.

You can choose same character any number of times. But that doesn't imply the answer will either be 1 or 0.

don't trust how you understood the problem always read the Note that explain samples ... I did this mistake several times but now I will always read samples note

Maybe it's right.

Find solution for D: 1 minute

Think why solution for D is so easy: 9 minutes

weird how the examples show that's clearly not the case?

made the same mistake :(

The easiest way to maintain all components is to create a separate vertex for each x-coordinate and y-coordinate, and treat each point as an edge that connects its x-coordinate with its y-coordinate. Then the answer for each component is the product of the number of x-coordinates and the number of y-coordinates in that component.

I think it's the way to fill all -1 in the array so that there isnt any value of i such that a[i] = a[i+2]

We have to calculate the total number of ways to assign values (in range[1, k]) to the -1's in the array, such that no palindrome of odd length is present in the resulting array.

Ok thanks

We have to remove first, then apply operations

If the original string is like "<<>>", then although remove the most out "<" (or ">"), there is another inner "<>". so the correct answer is 2, not 1.

you need to check bold statement in the problem.

The edge i..(i+1) is a side of the triangle, in any triangulation. I.e: it would always be an edge. So the best way to connect it to 1 as the third node, and therefore create the minimum possible value.

The key idea is that vertices $$$i$$$ and $$$i+1$$$ will always share a triangle.

You are going to have to use all edges in the outer polygon in a triangulation, and for each edge you have to choose one additional label, and using 1 works. So the answer is simply

Actually not all solved it by trial and error. I proved it during contest time :)

Actually I tried all possible states xD 51705295

it seems i have proved this solution. Suppose there isn't any diagonal from 1 in optimal triangulation. Then we can move this triangulation in clockwise and decrease the cost. So there is some diagonal from 1 to i. Let's consider triangulation of "1 to i" polygon. If there isn't any diagonal from 1 we can do how described above and so on. So, to minimaze the triangulation cost it needs that all diagonals starts in 1.

This comes in somewhat late, but I haven't seen a full proof in the comments yet.

Let the value of a segment be the product of its endpoint. Then clearly the value of a triange is greater than or equal to the value of any of its sides. Moreover, unless one of the vertices is $$$1$$$, the value of the triangle is greater than or equal to the sum of any two sides. This is because $$$abc - ab - ac$$$ factors as $$$a((b - 1)(c - 1) - 1)$$$ which is non-negative unless $$$b$$$ or $$$c$$$ is $$$1$$$.

Now note that every side of the polygon belongs to a triangle in the triangulation. If this triangle contains no other side then its value is at least the value of that side. If it does contain another side then the value of the triangle is greater than or equal to the sum of these two sides, unless one of the vertices is $$$1$$$. By adding up it follows that the sum of the values of all the triangles is at least the sum of the values of the sides, except for the two sides that include vertex $$$1$$$ (because they may be included in a triangle that has another side of the polygon).

Triangulation $$$(1, 2, 3), (1, 3, 4), (1, 4, 5), \dots, (1, n - 1, n)$$$ gives exactly that sum of values, so that's our answer. Also note that the exact labels on the vertices don't matter, all that is needed is that exactly one label is equal to $$$1$$$.

huh?

О я вижу вы гений

That's not really true. We just greatly underestimated contestants. Personally, I thought that majority will stuck in some sort of dp, so after some discussion we decided to leave a place to a straightforward solution. In the end community surprised me in the good way.

PS: linear is not a limit: OEIS/interpolation gives us closed formula and $$$O(1)$$$ solution.

Actually you can solve problem D in O(1) time complexity.

Let S = 2 * 3 + 3 * 4 + ... + (n-1) * n

3S = 2 * 3 * (4-1) + 3 * 4 * (5-2) + ... + (n-1) * n * (n+1-(n-2))

3S = 2 * 3 * 4-1 * 2 * 3 + 3 * 4 * 5-2 * 3 * 4 + ... + (n-1) * n * (n + 1)-(n-2) * (n-1) * n

3S = (n-1) * n * (n + 1)-6

S = ((n-1) * n * (n + 1)-6) / 3

P/s: I don't know how to use Latex :( So the signs and numbers may be ugly

Или, например, можно убрать вознаграждение за взлом пользователей, имеющих менее 5 контестов с хотя бы одной решенной задачей. Задача, как-минимум, усложняется и будет проще отлавливать неспортивное поведение.

Okay, the main intuition behind the answer can be said that, if the beauty is fixed, then you can easily find the answer, by taking the sum of all the largest k songs (sorted by length). Using this intuition, we iterate over through all the different beauties present in the array and dynamically maintain the sum of largest k elements, using a priority queue, and updating the sum while traversing. Here is the link to my code — https://mirror.codeforces.com/contest/1140/submission/51714832

Probably not since you would have (3*10^5)^2 states

this is also pointed out above, but for some strange reason all the comments are heavily downvotes.

It's not my account, and I think that my account was hacked. (Password leak or something) Now I changed my password, and hope it won't happen again.

I can't believe people are upvoting this. Why would dotorya make a fake account and then compete with both of them in the same contest submitting same solutions? I don't think a legendary grandmaster would be that stupid. It must be a hacker's account, should be banned soon.

Let's divide all edges into two types: edges of the first type connect vertices having different remainders modulo $$$2$$$, and edges of the second type connect vertices having same remainders.

First of all, let's solve an easier version of the problem: we have to minimize the number of edges of the second type in our path, and minimizing the length of the path has lower priority. Then we can build one tree where each vertex is a union of vertices $$$2x + 1$$$ and $$$2x + 2$$$ in the original graph, and use something like binary lifting or centroid decomposition on this tree. For example, if applying binary lifting, we may maintain an array $$$up[N][LOGN][2][2]$$$, where $$$up[v][k][f1][f2]$$$ is the length of the shortest path that starts in vertex $$$2v + f1$$$ of the original graph, goes $$$2^k$$$ steps up the tree, and ends in the vertex having remainder $$$f2$$$ modulo $$$2$$$ in the original graph.

Okay, but we can't use this approach in the problem from the contest, because sometimes it is better to traverse some additional edges of the second type, so we may choose cheaper edges of the first type. To handle this, let's preprocess all edges of the second type in such a way that cost of each such edge will be equal to the shortest path between its endpoints. This can be done with a Dijkstra-like algorithm.