So fast editorial！

Thanks for the fast editorial ;)

for D

a bxx ba => abxxba , which is a palindrome and it requires concatenating 3 strings

isn't this a counter example for the proof

In D1 you didn't need to have a constraint on sum of $$$n$$$, because $$$dp_k[n][m] = dp_1[n][m] \cdot k$$$ and everything can be precalculated in $$$O(maxn^2)$$$

Could anybody prove why I was able to cheese D:143658044? I simply handled trivial cases separately and then ran a nested loop with early exits and it somehow passed

I have implemented div 2 c in this link but it is giving me a memory limit exceeding error. Can any one pls suggest where I have implemented it wrong.

.

Another solution for problem D1C(D2E): Try to take the XOR of the red cells in the picture, then what happened?

code: 143676971

My solution for D2C is slightly different

If MEX of the entire array is mex and mex is small then we should remove as many equal mexes as possible. This way we guarantee that next mex will be even smaller

On the other hand if mex is large, then we already remove a significant number of elements

This way removing part becomes cheap because the total number of iterations when we actually remove becomes small

The complexity seems to be O(n * sqrt(n))

Thank you for this nice Mihai round ! I hope to see more Mihai rounds in the future !!

For C we can prove that any initial arrangements of row 1, yields a valid unique solution that can be constructed greedily. This is done by choosing row 2 in such a way it makes row 1 valid, and its obvious to see there is just one solution for that.

Let us assume there exists some solution. If we swap some element in row 1, $$$(1,x)$$$ you can notice it will change elements $$$(2,x+1)$$$ and $$$(2, x - 1)$$$, which will similarly change $$$(3, x - 2)$$$, $$$(3, x)$$$, $$$(3, x+2)$$$. By $$$\frac{n}{2}$$$ rows it will just swap $$$(\frac{n}{2}, 2x)$$$ or $$$(\frac{n}{2}, 2x + 1)$$$ for all $$$x$$$. This will make no difference in the last row, as it symmetrically loops after that. All other rows are taken care of in propogation.

I have another solution to C :

There's a typo in the editorial of Problem D2. $$$DP[i][i] = i$$$ should be replaced by $$$DP[i][i] = k \cdot i$$$

Cc: SlavicG magnus.hegdahl

I've found an alternative solution to Div2 C — Meximum Array that is quite elegant, if I may say so myself.

Let's keep track of current MEX value, which is initially zero, and look at each array element from left to right. We can store already seen array elements in a hash table, std::set or an array of size $$$2 * 10^5$$$ and update MEX value in $$$O(n)$$$ time. Notice that MEX can only change it's value when it's equal to current array element — and also that it can only grow. If we could somehow predict the future and know that we won't ever encounter an element equal to MEX, then we could conclude that current value of MEX is global maximum for entire array, add it to answer and reset MEX-tracking machinery (set current MEX value to zero and forget all seen elements). But we can do exactly that, we can predict the future in $$$O(1)$$$ time if we spend $$$O(n)$$$ time in preparation — for that we need to store count of not-yet seen elements for each element value in a hash map or an array and later update (decrement) it when going over each element from left to right.

Final complexity depends on what data structure we use for storing seen and unseen elements. I've got TLE with std::vector of size $$$2*10^5$$$ and using std::fill to reset it because of large hidden constant, but a solution with std::unordered_map was accepted.

Here is my code: https://mirror.codeforces.com/contest/1629/submission/143691434

Peculiar Movie Preferences Video Solution.

Don't forget to like and subscribe!!

https://www.youtube.com/watch?v=xBkDyMHVTJ0

If anyone's wondering, here's the genfunc sol for D2...

So, for Div. 1 D1, we can determine that the solution is

Let $$$A_n(x) = \sum\limits_{i=0}^{n} D[n][i] x^i$$$, then the recurrence above rewrites as

This rewrites explicitly as

Thus the final answer is

Unfortunately, it took me quite a while to derive everything and I could only solve it after the contest has ended :(

Regarding the editorial of Problem D2:

I think the reason why the $$$x$$$ value that maximises the expression $$$min(DP[i−1][j−1]+x,DP[i−1][j]−x)$$$ is always valid (namely, $$$0 \le x \le k$$$ is satisfied) should be mentioned in the analysis of the solution.

Cc: SlavicG magnus.hegdahl

pronblem B was hell for me because i am not really good at math problems otherwise everything was perfect thanks for this round

Did someone else not notice D2 having the "sum of N is bounded" restriction and sat on the solution for half of the contest? :|

I didn't solve E during contest, but I solved it after contest! Here's the solution:

Observation 1: We know that our final answer will just be the bitwise XOR of some elements of our grid. This is kind of hard to prove (I think), but it's intuitive enough.

Observation 2: We're choosing some subset of elements in our matrix and bitwise XORing all of those elements which we chose.

Observation 3: We can imagine this as a binary matrix, where 1 means that we chose that element and 0 means that we do not chose that element. We want to construct the matrix in such a way that each element has an odd number of neighbors which are 1. That way, we include everything in our bitwise XOR.

Observation 4: If we fix some row of our boolean matrix, the rest of the matrix is fixed.

Observation 5: If we fix the first row to contain only ones, we're done.

So the idea is to fill the first row with ones and then fill out the rest, which is fixed.

143706309

For Problem Div2 D, tags are showing twice.

Where does my solution for C go wrong? I didn't do anything with suffixes so that may have been an issue but I fail to see how $$$\text{MEX}(l,N)$$$ and $$$\text{MEX}(r,N)$$$ could be used to calculate $$$\text{MEX}(l,r)$$$ (following the notation of the editorial).

I am getting WA25 on My solution of D, Would some give me an example so I could understand, Thanks for helping in Advance

In Div 1A for test case -

1 3 1 1 1

Why is answer 0 0 0 wrong? According to the definition in problem statement 0 0 0 is larger than 0. We can obtain 0 0 0 by choosing k=1 3 times.

Upd: Nvm. Realized its correct answer. I did changed break to continue in my code before submitting..

In Div2 D, I don't think it's enough to pair at most 2 strings. Consider the following example z yxa xyz

I don't see how we can select 2 strings to form palindrome, but selecting all surely works. What am I missing ?? Help me!

z is a plindorome. I am stupid.Please ignore.

I'm confused about the test data of problem E (div. 2). What I understood from the problem statement is "each cell contains the xor sum of all its adjacent cells". Suppose we have a grid of $$$2\times2$$$ like this:

The xor sum of neighboring cells for each cell will be:

So the conditions $$$y_{1,1} = y_{2, 2}$$$ and $$$y_{1,2} = y_{2,1}$$$ should be satisfied for a valid $$$2\times 2$$$ grid.

But why the test contains test data like this?

What is a possible original grid for this test data? Am I missing something?

is there a DP-solution for problem D — div2 ?

For div 2E, you can visit each cell and include it in the xor if the neighbours haven't been marked. Initially all cells are unmarked. After including a cell mark all its neighbours, as they will be included in the xor.

Accepted solution

For problem E . It seems that many problem requiring finding a path to any node in the tree can be turned into find the path to the ending nodes of "diameter" of the tree (the diameter here can be the sum of length,max ...). And the ending nodes of diameter can be easily maintain by segment tree.

I first saw this trick here : https://mirror.codeforces.com/contest/1434/problem/D

Can anyone explain how come the number of odd numbers in the range [l,r] is given by (r-l+1)+(r/2+(l-1)/2)???

fun contest, thoroughly enjoyed the problems :D

Can anyone tell me what's the error in my implementation of problem D 143737471

I think the 1628C — XOR-сетка method seems a little troublesome, I have a very concise writing here

Starting from the second row, you only need to select those cells that have been selected an even number of times in the previous row for XOR

My solution for Div1D:

Let $$$f(n, m)$$$ be $$$2^{n - 1}$$$ times the answer for $$$k=1$$$, so that this value is always an integer.

Note that we have the recurrence relation $$$f(n, m)=f(n - 1, m) + f(n - 1, m - 1),$$$ as well as the known values $$$f(n, n) = n\cdot 2^{n - 1}.$$$

Let $$$F(n, m)$$$ be the same function as $$$f$$$ but extended by the recurrence relation to values where $$$m > n$$$ (so $$$F(n - 1, n)=F(n, n) - F(n - 1, n - 1)$$$). We can compute $$$F(0, m) = m.$$$

We can easily use these values as a basis for computing $$$F(n, m)$$$ as a sum, as the value $$$F(0, m')$$$ will contribute to this $$$\binom n{m - m'}$$$ times.

Then $$$F(n, m)$$$ is just $$$\sum_{i=1}^m i\binom n{m - i},$$$ from which we can easily compute the desired answer.

Code: 143689440

Hey in the question 1628A - Meximum Array , can anyone explain the correctness of second test case as per the problem statement :

I think the second test case should be like this

2 2 3 4 0 1 2 0 -> [2 2 3 4 ] = 5

0 1 2 0 -> [0 1 2] = 3

0 -> [0] = 1

so vector b becomes [5,3,1] and this is lexicographically greater than the given b -> [5,3,1]

Kindly clarify this.

Explained 1628D1 — Game on Sum (Easy Version) DP Concept much clearly up here:

DP Concept Video Explaination

Can anyone check my solution for Div2 D? I can't find what's wrong here. https://mirror.codeforces.com/contest/1629/submission/143764101

How to solve Div2C/Div1A in o(n) ?

There is a slightly easier solution for the Div1 C task. I noticed that if we suppose the table is chessboard, every cell would contain information only about the other color. So, we can calculate XOR of all the white and black cells separately. If left up cell is white, to calculate answer on the black cells, we simply need to go from the left up diagonal to the right down. To count every cells one time, we can use the previous diagonal and add cells as on the picture. (x is diagonal we want to count, 2 is diagonal we already know, 1 is for cells we need to take). Counting the answer for other diagonals is pretty similar.

Scheme: https://imgur.com/a/ut95K9y

My solution: https://mirror.codeforces.com/contest/1629/submission/143699683

Great Contest

For 2C.. What is the output for

6
0 1 2 0 1 2

I think the answer should be 4?

This is a much easier solution for Div1C, we can calculate the white cell in the same way.

I have a question about div2C (which is much harder than div2D btw). Let m be an array of MEX suffices. That is, m[i] is MEX of all elements from a[0] to a[i]. From this, how to calculate MEX of all elements from a[l] to a[r] for any l and r?

About the problem D1 (Div 1), what if $$$\frac{DP[i-1][j] - DP[i-1][j-1]}{2} > k$$$, in that case the optimal $$$x$$$ would be $$$x = k$$$, but the fact that we're working under $$$\mathbb{Z}_{10^9 + 7}$$$ makes impossible to identify this case. I would appreciate some explanation about this. I'm probably missing something.

How do we efficiently calculate the Mex for the Mex problem?

Regarding the Editorial's solution for Div2E, I have wondered why does this strategy always work, I mean why do the $$$n^{th}$$$ row cells always get used odd number of times by the time the $$$(n-1)^{th}$$$ row cells get used odd number of times. After some thinking I reached the following proof:

Assume a matrix $$$mat$$$ such that $$$mat[i][j]$$$ is $$$1$$$ if we XOR the result with $$$xor\_sum[i][j]$$$ and $$$0$$$ otherwise. We want to prove that using a valid (every cell in the original grid is included odd number of times) matrix $$$mat$$$ of size $$$n\times (n-1)$$$ ($$$n$$$ is even) where the first and last rows are all ones, and the first and last column values from top to bottom are $$$1, 0, 1, 0, ..., 1, 0, 1$$$, we can always build another valid matrix $$$mat2$$$ of size $$$(n+8)\times (n+7)$$$.

Define boundary cells of a matrix of size $$$n\times m$$$ to be the cells with row $$$1$$$ or $$$n$$$ or column $$$1$$$ or $$$m$$$. Using matrix $$$mat$$$ of size $$$n\times (n-1)$$$, let's add new boundary cells in $$$4$$$ steps to reach our desired matrix $$$mat2$$$:

1. The first boundary cells: All zeros, now the matrix size is $$$(n+2)\times (n+1)$$$.
2. The second boundary cells: The first and last rows are all zeros, and the first and last column values from top to bottom are $$$0, 1, 0, 1, ..., 0, 1, 0$$$, now the matrix size is $$$(n+4)\times (n+3)$$$.
3. The third boundary cells: All ones, now the matrix size is $$$(n+6)\times (n+5)$$$.
4. The fourth boundary cells: The first and last rows are all ones, and the first and last column values from top to bottom are $$$1, 0, 1, 0, ..., 1, 0, 1$$$, now the matrix size is finally $$$(n+8)\times (n+7)$$$.

Observe how all the new rows/columns are added in a way such that their respective original grid cells are used odd number of times. The base cases are for $$$n = 2, 4, 6, 8$$$, using these we can build the matrix of any other even positive $$$n$$$.

To obtain the $$$n\times n$$$ matrix, simple append a first row of all zeros, its cells will be always valid (as the row below it is all ones) and will not affect the validity of other cells.

Example for obtaining $$$mat2$$$ of size $$$12\times 11$$$ from $$$mat$$$ of size $$$4\times 3$$$:

$$$mat$$$:

$$$mat2$$$ ($$$mat$$$ is highlighted in yellow):

The binary tree, LCA stuff in the editorial of E are essentially proving this cool fact:

Let $$$f_T(x, y)$$$ be the maximum weight along the simple path from $$$x$$$ to $$$y$$$ in an edge-weighted tree $$$T$$$. Then, given any edge-weighted tree $$$T$$$, there exists a tree $$$T'$$$ such that $$$\forall x, y : f_T(x, y) = f_{T'}(x, y)$$$, and every vertex of $$$T'$$$ has degree $$$\leq 2$$$ (i.e. $$$T'$$$ is a line).

And here is how to construct $$$T'$$$ in $$$O(n\log n)$$$:

/*
    given an edge list of the form {{w, x, y}, ...}
    where {w, x, y} means an edge from x to y with weight w,
    return a new edge list on the same vertices, such that:
    a) every vertex has degree <= 2 (i.e. the tree is a line)
    b) the maximum edge weight along the path from x to y in the
       new graph is the same as in the old graph, for any x and y.
*/
vector<array<int, 3>> make_linear(vector<array<int, 3>> e) {
    int n = e.size()+1;

    // u.rep(i) -> representative of set containing i
    // u.unite(x, y) -> unite sets containing x and y
    dsu u(n);

    // left and right endpoints of the line of vertices
    // corresponding to the set with representative i
    vector<int> l(n), r(n);
    for (int i = 0; i < n; i++)
        l[i] = r[i] = i;

    vector<array<int, 3>> line_e;

    sort(e.begin(), e.end());
    for (auto& [w, x, y] : e) {
        x = u.rep(x), y = u.rep(y);
        u.unite(x, y);
        int z = u.rep(x);
        line_e.push_back({w, r[x], l[y]});
        l[z] = l[x], r[z] = r[y];
    }

    return line_e;
}

To solve problem E, just do the tree replacement, and then it reduces to an easy problem on an array. :)

Another problem that can be solved using this trick is 609E - Minimum spanning tree for each edge.

You have changed test case 1 of E in judging but the answer is still the same as the test case 1 given in the question, pls correct it so my answer gets accepted.

In Div1 D1 how do we go from this statement

$$$DP[i][j]=min(DP[i−1][j−1]+x,DP[i−1][j]−x)$$$ for x that maximizes this value.

To this statement

$$$DP[i][j]=(DP[i−1][j−1]+DP[i−1][j])/2$$$

Shouldn't it be

$$$DP[i][j] = DP[i-1][j-1] + min(k, (DP[i-1][j] - DP[i-1][j-1])/2)$$$

because of the constraint on x?

Why we are taking MEX of SUFFIX not that of PREFIX ? Please explain. Thanks.

I have the same idea on problem C, but I don't know how to find MEX on subsegment. Can you explain?

can anyone tell me why my solution for problem D is not working https://mirror.codeforces.com/contest/1629/submission/143927718

For Problem-E (Div.2),
Another logic would be to do ans = ans ^ grid[i][j] for all i and j within bounds (0 <= i, j < n) iff all neighbours of grid[i][j] are still unvisited (here grid refers to the grid which is given in input). In this way we guarantee that every element of Victor's actual grid is counted only once while taking xor.

This has been stress tested by harasees_singh for all even n from 2 to 1000.

Here is the link to my submission: 143698533

Can anyone help me with my submission of D of Div2.

problem-1628B - Peculiar Movie Preferences My submission-143689113 Thank you

Here's another solution for Div1E, which uses the following observation:

Let $$$A$$$ be any subset of vertices, $$$a_i$$$ be the $$$i$$$-th element of $$$A$$$, $$$f(x,y)$$$ be the maximum edge weight on the unique path from $$$x$$$ to $$$y$$$, and $$$p$$$ be any permutation of $$$[|A|]$$$.

Then the following holds:

That is, the maximum edge weight on any path from two elements of $$$A$$$ is the maximum of $$$f(a_i,a_{i+1})$$$ of any ordering of $$$a$$$.

Proof: It's sufficient to show that any edge which is on at least one path of a pair of vertices from $$$A$$$ will be on at least one of the paths $$$(a_i,a_{i+1})$$$. Let's take any such edge. Then the vertices of $$$A$$$ can be split into two subsets $$$A_1$$$ and $$$A_2$$$ based on which side of the edge they are on. It's easy to see that as long as neither of the two subsets is empty, any ordering of $$$a$$$ will contain two consecutive elements, such that one is from $$$A_1$$$ and the other is from $$$A_2$$$. $$$\square$$$

To solve the problem, first notice that if $$$B$$$ is the current set of vertices that are on, and $$$c$$$ is the query vertex, we are looking for $$$\max\limits_{x \in B \cup\{c\}}\max\limits_{y \in B \cup\{c\}}f(x,y)$$$.

Since any ordering works, let's simply take the ordering from the input. Then we can preprocess $$$f(i,i+1)$$$, make a segment tree keeping $$$f(x,y)$$$ of consecutive elements of $$$B$$$, and notice that any update requires the addition of at most two $$$f(x,y)$$$ calls that weren't already preprocessed. This gives an $$$\mathcal{O}(n \log n)$$$ solution. Code: 144633280.

Could anyone please explain why my O(n*logn*logn) for problem C is giving TLE?

My submission link: https://mirror.codeforces.com/contest/1629/submission/238484131