F. Ограничения нас наводят на мысль о некоторой динамике по изломному профилю.

Да можно и по обычному профилю. Выходит O(n·2¹⁶·10) или O(n·2¹²·10)

Hi! Just a small note about problem D.

In the editorial you said to subtract cnt_ai  *  a_i, but then you are adding cnt_ai  *  a_i again in the last sum, so you could just omit those two terms.

I know it adds the same, but I think is more natural for the understanding to just don't include them.

Isn't the time complexity for E gonna be O(n * n * n * k) ?

n *n -> generating all the possible string 't'.

n *k -> checking it will all the strings s1, s2 ... sn

If this complexity is right, then won't the above solution give TLE ?

It would have been really nice, if the author would have attached a sample submission.

There's a simple observation that can make the E solution a lot faster and less likely to get TLE. When you are determining the indices where s_i ≠ t_i, if there are more than 4 such indices, then the answer is -1 (since s and t are too far from each other for there to exist a "base string"). Now you'll only have O(1) candidates for the "base string", and the rest of the approach is quite fast.

Another solution for F:

Use DP state (i, mask) to mean the minimum cost to make everything before column i dots, and the columns i through i + 3 having asterisks in the positions indicated by mask (which ranges from 0 to 2¹⁶ - 1). The transitions are to clear a square in the mask (1x1, 2x2, 3x3, or 4x4), or, if the bottom 4 bits of the mask are empty, to shift to column i + 1.

There are 1 + 4 + 9 + 16 = 30 transitions of the first type, and 0 or 1 transitions of the second type, so the total time is O(n·2¹⁶·31). Implemented in a top-down (recursive) fashion, this doesn't run in time (submission: 33204536). The worst case is with a 4x1000 matrix, all asterisks, which takes about 5 minutes on my machine.

To speed it up, we note that if the bottom 4 bits are empty, the shifting transition is always best: we don't need to check all the square-clearing options. Furthermore, unless we are at i = n - 4, it is always best to clear squares that border the left edge of the square under consideration. This reduces the possible transitions by about a factor of 2, but it also drastically reduces the number of states visited: in the maximum case described above, our recursion only visits 106371 states, and the submission (33204643) passes in 61ms.

Can someone explain the logic behind the solution of problem D please?

D can also be solved using a Fenwick tree. Go through the sequence of numbers from least to greatest, updating the tree from 0 to 1 as you go. For each new value, update all previous values more than 1 less than it in the Fenwick tree, then add val*query(0, ind-1) — val*query(ind+1, MAX_N-1) to the final answer. Then do the same thing again, but in reverse sorted order.

The answer for problem C is just the mode (the highest frequency among all numbers) of the array.

Can someone explain author's approach to the problem F in more detail? What is the bit mask representing, and how is he using it to form dp states?

very nice solution for problem G, thinking the min-cut way is much easier :-)

In problem D test 29's correct answer is -9999999990000000000. Isn't it exceeding 10^18 by it's absolute value?

903F - Clear The Matrix What does mask mean? I am visualizing it like this.
~~~~~ mask = 1

for i = 3 and j = 4

|*|.|.|

|.|.|.|

|.|.|.|

|.|.|.|

mask = 3

for i = 3 and j = 4

|*|*|.|

|.|.|.|

|.|.|.|

|.|.|.|

~~~~~
Is this correct.

In problem D how to calculate that the absolute value of the answer will be up to 10^19?

Can someone explain problem D please?

O(n·4·212).

Мои глаза...

4*2**12 — это константа.

Can someone explain the solution to F?

For problem, A is this logic is correct or not

if(x%7==0 || x%3==0) _ print("YES");_ else if((x%7)%3 == 0) _ print("YES")_ else _ print("NO")_

In problem E, rather than swapping s_i,diffpos with any other character of s_i , Can't I swap it with any other character at a position in array pos?

Can anyone explain why we need previous 12 cells in problem F? Why not any other number?? Thanks in advance.

Can somebody help me in question E. My solution getting TLE , i have use hash like abc---> a*p^2 + b*p+ c , and try to find the intersection of all swap of all string

my solution link

I have another approach to problem E, which differs from that described in the editorial. I haven't proved it's correctness, and I'm not even sure if it's correct, but it passes the given 70 tests and I stress-tested it against a few other tests. It would be interesting to see if someone could hack it.

It stems from the brute force solution: just recursively iterate over all possible strings and check if each string is valid. The issue with the recursive solution (the reason why it's slow) is that sometimes, we know that a prefix is invalid. It's invalid if it's not a prefix of a permutation of the original input (i.e. it contains more occurrences of a given character than it should). It's also invalid if it differs by more than 2 from other strings in the input. Just using these 2 ideas to prune generates a pretty good brute force when $$$k$$$ is large, since it's highly unlikely that a given string satisfies those two criteria.

So now the issue is dealing with small $$$k$$$ ($$$k \le 10$$$). We can store what the interesting points are (points at which a swap may have occured) and try randomly swapping interesting points.

It turns out, to my surprise, that this actually works.

TL;DR Please hack me :).

143162377

certainly Education Forces have weird taste of fun