I created video editorial for E. Coloring a Red Black Tree.

nevermind i am just dumb, i fucking solved it lexicographically instead of "integer order"

the correct solution with AC is

for i in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    if len(set(a)) == n:
        ax = sorted(list(map(int,a)))[::-1]
        for i in range(n):
            ax[i] = str(ax[i])
        print(' '.join(ax))
    else:
        print('-1')

[deleted]

Here you go:

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 5005;
 
unsigned char dp1[MAXN][MAXN];
unsigned char dp2[MAXN][MAXN];
 
unsigned char base_cell(int i, int j, int n) {
    return (i + j <= n - 1) && ((i - j) % 3 != 0);
}
 
void cook(int n) {
    for (int i = 0; i < n; ++i) {
        memset(dp1[i], 0, n * sizeof(dp1[i][0]));
        memset(dp2[i], 0, n * sizeof(dp2[i][0]));
    }
 
    for (int i = 0; i < n; ++i) {
        int j = n - 1 - i;
        if (base_cell(i, j, n)) continue;
 
        if (i < n / 2) {
            if (i > 0) dp1[i - 1][j] ^= 1;
        } else {
            if (j > 0) dp2[i][j - 1] ^= 1;
        }
    }
 
    for (int i = n - 1; i >= 1; --i) {
        for (int j = 0; j < n; ++j) {
            if (!dp1[i][j]) continue;
            dp1[i - 1][j] ^= 1;
            if (j + 1 < n) dp1[i - 1][j + 1] ^= 1;
        }
    }
 
    for (int j = n - 1; j >= 1; --j) {
        for (int i = 0; i < n; ++i) {
            if (!dp2[i][j]) continue;
            dp2[i][j - 1] ^= 1;
            if (i + 1 < n) dp2[i + 1][j - 1] ^= 1;
        }
    }
 
    string row;
 
    for (int i = n - 1; i >= 0; --i) {
        row.clear();
        for (int j = n - 1; j >= 0; --j) {
            unsigned char val = base_cell(i, j, n);
 
            if (i + j == n - 1 && !val) val = 1;
 
            val ^= dp1[i][j] ^ dp2[i][j];
 
            row.push_back(char('0' + val));
            row.push_back(' ');
        }
        row.push_back('\n');
        cout << row;
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        cook(n);
    }
    return 0;
}

Me too bro

Assuming you understand the elements of the solution (you should pick some order to go through the nodes in, and then for each keep picking it until it turns red), here:

Consider you have two neighboring nodes $$$u$$$ and $$$v$$$ that are used one after the other in the order with red neighbor ratios $$$\frac{a}{b}$$$ and $$$\frac{c}{d}$$$ respectively (at the time that they're used). Then, the expected value here is $$$\frac{b}{a} + \frac{d}{c + 1}$$$. If you swapped their order, the expected value here is $$$\frac{d}{c} + \frac{b}{a + 1}$$$. So, it's beneficial to swap if $$$\frac{d}{c(c+1)}$$$ is bigger than $$$\frac{b}{a(a+1)}$$$.

Note that this is a comparator based on the nodes themselves! So, at any given step, if the node with the minimum value of $$$\frac{b}{a(a+1)}$$$ is at some later point in the projected order, you can keep bubbling it up earlier and never lose (note that if two nodes didn't neighbor, swapping them in the order doesn't matter).

Maybe not the most formal but yeah roughly this exchange argument is the reason.

UPD: I found out why it works

For any black node $$$u$$$ with degree $$$\deg(u)$$$ and $$$cnt(u)$$$ red neighbors, the probability of selecting a red neighbor in one operation is $$$\frac{cnt(u)}{\deg(u)}$$$.

$$$\therefore$$$ the expected number of operations to color node $$$u$$$ red is:

Suppose you have two adjacent black nodes, $$$u$$$ and $$$v$$$. If you color one, it becomes a red neighbor to the other, increasing the other's $$$cnt$$$ by $$$1$$$ and reducing its expected cost.

Let's compare the total expected cost of the two possible color orderings:

To minimize the expected operations, we must order $$$cost(u,v)$$$ and $$$cost(v,u)$$$ (exchange argument):

Rearranging:

Some more rearranging and simplifying:

Use this as a heap (priority queue) comparator

Surprisingly appeared in his dreams!!

He might have used any generator or something similar with intended logic, ran it locally and got the values. What else can be the reason? And everyone has their own coding style. We can see people become LGMs with different approaches, not something one should focus on.

It is not "hardcoding", he seems to be using the same fractal as the official solution. (We run the visualizer)

haha i was wondering the same

what happened to u today bro, why didnt u solve the contest after B??

what was your approach can you elaborate a bit?

Done, thanks!

For any answer to exist, it must satisfy the following 2 conditions :
1. A valid $$$n \cdot m$$$ matrix should exist.
2. It must be possible to arrange these p (segments) & q (L-shapes), to cover all edges of the $$$n \cdot m$$$ matrix.

For condition-1, for a $$$n \cdot m$$$ matrix to exists, then its total edges must be equal to $$$p + 2 \cdot q$$$.

Now let,
$$$E_h$$$ = Total horizontal edges of $$$n \cdot m$$$ matrix
$$$E_v$$$ = Total vertical edges of $$$n \cdot m$$$ matrix

Then,

Here, it can be proven that :

Now let n <= m (for ease of understanding), then we can iterate over all n in sqrt(p + 2 ⋅ q) time. Then for FIXED p, q and n we can easily find m as,

Hence, we get our possible (n x m) candidate dimension for given p and q.

Now, how to check if this dimension is correct or not? For that lets analyze the edge difference of the matrix :

If the difference is non-zero, then it can only be obtained by using straight segments only.
Cause using a L-shape increases both horizontal and vertical edge count by +1, no matter what orientation of it was used. But using a straight segment affects only one type of edge, either horizontal or vertical i.e. this difference gap could only be achieved by using straight segments only.

So, from here we get our necessity condition :

Let,
$P_h$ = Total horizontal edges using only straight segment
$$$P_v$$$ = Total vertical edges using only straight segment

Also, since the difference is caused only by straight segments only, we get,

Also,

Adding these two equations we get,

This means p and |m-n| MUST have the same parity.

So, the remaining p's must be even numbered. Hence, these remaining segments come in pairs (1 horizontal + 1 vertical) and can be used as L-shape. See the editorials explicit construction for its sufficiency.

Hope this helps :)

I looked at it like this:
1. You can always construct an $$$ m * m$$$ grid with $$$2*m*(m+1)$$$ $$$ L-shapes$$$ perfectly.(You first make the diagonal, then set all the pieces in the upper and lower triangle facing inward.)
2. Now WLOG if you increase one side to $$$m+1$$$, then you can place all the new pieces such that only 1 line segment is missing, if you only try to increase 1 side of the grid. Then you can generalise this for any $$$m $$$ and $$$ n$$$.

with fast factorization p,q 1e18 is doable with the original constraints

thank you

same idea

in the third line for the condition check , ig it should be q <= min(n,m)+m*n, as the number of horizontal or vertical edges provided by L-shape cannot exceed the ones in the grid.

you are not starting on the first element , you are starting before the first element. AND

you can either stay or move right or left so you can just wait.

I think my solution is faster, although I am not 100% sure.

https://codeforces.me/contest/2219/submission/371142745

TETOOOOOOOOOOOOOOOOOOOOO