Codeforces Round #812 (Div. 2) Editorial
Difference between en68 and en69, changed 158 character(s)


<spoiler summary="Before the round starts">↵
Great efforts have been put over last year. We want to say thanks to everybody who helped us to make this round as it is. Cannot wait to see you guys on the next one!↵

<spoiler summary="Testers' predictions">↵
<table>↵
  <tr style ="background-color:#D3D3D3">↵
    <th>Tester</th>↵
    <th>A</th>↵
    <th>B</th>↵
    <th>C</th>↵
    <th>D</th>↵
    <th>E</th>↵
    <th>F</th>↵
  </tr>↵
  <tr>↵
    <td>[user:tfg,2022-08-06]</td>↵
    <td>800</td>↵
    <td>1100</td>↵
    <td>1500</td>↵
    <td>1600</td>↵
    <td>1900</td>↵
    <td>2400</td>↵
  </tr>↵
  <tr>↵
    <td>[user:neko_nyaaaaaaaaaaaaaaaaa,2022-08-06]</td>↵
    <td>800</td>↵
    <td>1100</td>↵
    <td>1700</td>↵
    <td>1900</td>↵
    <td>2100</td>↵
    <td>2600</td>↵
  </tr>↵
  <tr>↵
    <td>[user:BucketPotato,2022-08-06]</td>↵
    <td>800</td>↵
    <td>1000</td>↵
    <td>1400</td>↵
    <td>1800</td>↵
    <td>2400</td>↵
    <td>-</td>↵
  </tr>↵
  <tr>↵
    <td>[user:LetterC67,2022-08-06]</td>↵
    <td>800</td>↵
    <td>1200</td>↵
    <td>1400</td>↵
    <td>1600</td>↵
    <td>2100</td>↵
    <td>-</td>↵
  </tr>↵
  <tr>↵
    <td>[user:_FireGhost_,2022-08-06]</td>↵
    <td>800</td>↵
    <td>1100</td>↵
    <td>1500</td>↵
    <td>1900</td>↵
    <td>2000</td>↵
    <td>2400</td>↵
  </tr>↵
  <tr>↵
    <td>[user:fextivity,2022-08-06]</td>↵
    <td>800</td>↵
    <td>1000</td>↵
    <td>1400</td>↵
    <td>1700</td>↵
    <td>2000</td>↵
    <td>2400</td>↵
  </tr>↵
  <tr>↵
    <td>[user:generic_placeholder_name,2022-08-06]</td>↵
    <td>800</td>↵
    <td>1100</td>↵
    <td>1600</td>↵
    <td>1900</td>↵
    <td>2200</td>↵
    <td>-</td>↵
  </tr>↵
</table>↵
</spoiler>↵


<spoiler summary="Some comments from testers and authors">↵

<spoiler summary="From BucketPotato">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005266180480712845/unknown.png)↵
</spoiler>↵


<spoiler summary="From tfg">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005259978401132614/unknown.png)↵
</spoiler>↵


<spoiler summary="Shower thoughts from vangtrangtan">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005260683446845531/unknown.png)↵
</spoiler>↵


<spoiler summary="From Fireghost">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005265905795747850/unknown.png)↵
</spoiler>↵


<spoiler summary="Also from Fireghost">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005261172280397888/unknown.png)↵
</spoiler>↵


<spoiler summary="From thenymphsofdelphi">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005261535624581141/unknown.png)↵
</spoiler>↵


<spoiler summary="From antontrygubO_o">↵
![ ](https://cdn.discordapp.com/attachments/984834520865988618/1005671932810764388/unknown-20.png)↵
</spoiler>↵


<spoiler summary="Huge help from Vladithur when polishing our statements">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005262548305707008/unknown.png)↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005262912648122368/unknown.png?width=1086&height=682)↵
</spoiler>↵


<spoiler summary="From hydroshiba">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005261760686735491/unknown.png)↵
</spoiler>↵


<spoiler summary="From thanhchauns2">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005264486120312852/unknown.png)↵
</spoiler>↵


<spoiler summary="From me">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005265647627939950/unknown.png)↵
</spoiler>↵


<spoiler summary="From errorgorn">↵
![ ](https://media.discordapp.net/attachments/845208765750181898/1005266730777595914/unknown.png?width=508&height=117)↵
</spoiler>↵

</spoiler>↵

</spoiler>↵

[1713A \- Traveling Salesman Problem](https://mirror.codeforces.com/contest/1713/problem/A)↵

<spoiler summary="Hint 1">↵
Do we actually need to go off the axis?↵
</spoiler>↵


<spoiler summary="Hint 2">↵
How to avoid visiting an axis more than once?↵
</spoiler>↵


<spoiler summary="Tutorial">↵

### <a href = "https://mirror.codeforces.com/contest/1713/problem/A">1713A \- Traveling Salesman Problem</a>↵

Suppose we only have boxes on the $Ox+$ axis, then the optimal strategy is going in the following way: $(0, 0), (x_{max}, 0), (0, 0)$. There is no way to do in less than $2 \cdot |x_{max}|$ moves.↵

What if we have boxes on two axis? Let's assume it is $Oy+$, suppose we have a strategy to go in the following way: $(0, 0), (x_{max}, 0),..., (0, y_{max}), (0, 0)$. In this case it is optimal to fill the three dots with $(0, 0)$, which is just solving each axis independently.↵

Therefore, the number of axis does not matters. For each axis that has at least one box, go from $(0, 0)$ to the farthest one, then come back to $(0, 0)$.↵

Time complexity: $O(n)$↵
</spoiler>↵


<spoiler summary="Solution">↵

~~~~~↵
def solve():↵
    n = int(input())↵
    minX, minY, maxX, maxY = 0, 0, 0, 0↵
    for i in range(n):↵
        x, y = list(map(int, input().split()))↵
        minX = min(x, minX)↵
        maxX = max(x, maxX)↵
        minY = min(y, minY)↵
        maxY = max(y, maxY)↵
    print(2 * (maxX + maxY - minX - minY))↵


test = int(input())↵
while test > 0:↵
    test -= 1↵
    solve()↵
~~~~~↵

</spoiler>↵

<spoiler summary="Feedback">↵
- Didn't solve [likes:1,A]↵
- Good problem [likes:2,A]↵
- Average problem [likes:3,A]↵
- Bad problem [likes:4,A]↵
</spoiler>↵

[1713B \- Optimal Reduction](https://mirror.codeforces.com/contest/1713/problem/B)↵

<spoiler summary="Hint 1">↵
How to calculate $f(a)$?↵
</spoiler>↵


<spoiler summary="Hint 2">↵
What if $a$ is intially sorted?↵
</spoiler>↵


<spoiler summary="Hint 3">↵
Consider $a$ has $3$ elements. What if $a_1 > a_2$ and $a_2 < a_3$?↵
</spoiler>↵

<spoiler summary="Tutorial">↵

### <a href = "https://mirror.codeforces.com/contest/1713/problem/B">1713B \- Optimal Reduction</a>↵

Let's define $max([l, r])$ the maximum integer over $a_l, a_{l+1}, \dots, a_r$. Note that $max([1, r])$ and $max([l, n])$ can be precalculated through prefix max and suffix max array.↵

Consider an indices triplet $(i, j, k)$ of the array ($1 \le i < j < k \le n$), and we want to make $a_i$, $a_j$ and $a_k$ all equal to $0$ in some operations. There are $2$ cases:↵

- $a_i > a_j$ and $a_j < a_k$: this cost $a_i + a_k - a_j$ operations.↵
- Other cases cost the same number of operations: $max(a_i, a_j, a_k)$.↵

In the other hand:↵

- $a_i + a_k - a_j = max(a_i, a_k) + min(a_i, a_k) - a_j = max(a_i, a_j, a_k) + min(a_i, a_k) - a_j$↵
- $min(a_i, a_k) - a_j > 0$. Therefore $max(a_i, a_j, a_k) + min(a_i, a_k) - a_j > max(a_i, a_j, a_k)$↵

So as we can see, the first case requires $max(a_i, a_j, a_k) + min(a_i, a_k) - a_j$ operations while the second case requires only $max(a_i, a_j, a_k)$ operations. So if the first case is satisfied for some triplet $(i, j, k)$, then the answer is not optimal.↵

As a result, we've found the construction of the optimal array. The answer is _NO_ if there exists an index $i$ ($2 \le i \le n - 1$) such that $max([1, i-1]) > a_i$ and $a_i < max([i+1, n])$. Otherwise, the answer is always _YES_.↵

<spoiler summary="How to prove the correctness?">↵

By constructing a permutation $p$ where the array $a$ is sorted, we can prove that $f(p) = p[n]$. The operations can be done by finding the left most element $p_l$ such that $p_l \neq 0$, then decrease all the elements $p_l, p_{l+1}, \dots, p_n$ by $1$.↵

This strategy costs exactly $p[n] = max([1, n])$ operations and it can obviously be showed that there is no other permutation of $a$ which costs less operations than when it is sorted. As a result, because we have proved for every permutation $p$ of $a$, $f(p) \ge max([1, n])$, the answer is always $YES$ if the condition $a_i > a_j$ and $a_j < a_k$ is not satisfied for all triplet $(i, j, k)$ ($1 \le i < j < k \le n$).↵
</spoiler>↵

Time complexity: $O(n)$↵

</spoiler>↵


<spoiler summary="Solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

const int N = 1e5 + 5;↵

int n, a[N], pref[N], suff[N];↵

int main() {↵
    int tc; cin >> tc;↵
    while (tc--) {↵
        cin >> n;↵
        for (int i = 1; i <= n; i++)↵
            cin >> a[i];↵

        pref[1] = a[1];↵
        for (int i = 2; i <= n; i++)↵
            pref[i] = max(pref[i-1], a[i]);↵

        suff[n] = a[n];↵
        for (int i = n - 1; i >= 1; i--)↵
            suff[i] = max(suff[i+1], a[i]);↵

        bool ok = true;↵
        for (int i = 2; i <= n - 1; i++) {↵
            if (pref[i-1] > a[i] && a[i] < suff[i+1]) {↵
                ok = false;↵
            }↵
        }↵

        cout << (ok ? "YES\n" : "NO\n");↵
    }↵
}↵
~~~~~↵

</spoiler>↵

<spoiler summary="Feedback">↵
- Didn't solve [likes:1,B]↵
- Good problem [likes:2,B]↵
- Average problem [likes:3,B]↵
- Bad problem [likes:4,B]↵
</spoiler>↵

[1713C \- Build Permutation](https://mirror.codeforces.com/contest/1713/problem/C)↵


<spoiler summary="Hint 1">↵
Is there any case that the answer doesn't exist?↵
</spoiler>↵

<spoiler summary="Hint 2">↵
**What if:** $n \le 5$↵
</spoiler>↵

<spoiler summary="Hint 3">↵
Construct the suffix instead of the prefix.↵
</spoiler>↵

<spoiler summary="Hint 4">↵
With any positive integer $x$, there is at least one square number in $[x, 2x]$. [Proof.](https://math.stackexchange.com/questions/1190737/proving-that-there-is-a-perfect-square-between-n-and-2n)↵
</spoiler>↵

<spoiler summary="Tutorial">↵

### <a href = "https://mirror.codeforces.com/contest/1713/problem/C">1713C \- Build Permutation</a>↵

First, let's prove that the answer always exists. Let's call the smallest square number that is not smaller than $k$ is $h$. Therefore $h \leq 2 \cdot k$, which means $h - k \leq k$. [Proof.](https://math.stackexchange.com/questions/1190737/proving-that-there-is-a-perfect-square-between-n-and-2n) ↵

So we can fill $p_i = h - i$ for $(h - k \leq i \leq k)$. Using this method we can recursively reduce $k$ to $h - k - 1$, then all the way down to $-1$.↵

We can prove that $h - k \geq 0$, as $h \geq k$.↵

Time complexity: $O(n)$↵
</spoiler>↵


<spoiler summary="Solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

const int N = 1e5 + 5;↵

int n, ans[N];↵

void recurse(int r) {↵
if (r < 0) return;↵
int s = sqrt(2*r); s *= s;↵
int l = s - r; recurse(l - 1);↵
for (; l <= r; l++, r--) {↵
ans[l] = r; ans[r] = l;↵
}↵
}↵

int main() {↵
int tc; cin >> tc;↵
while (tc--) {↵
cin >> n; recurse(n - 1);↵
for (int i = 0; i < n; i++)↵
cout << ans[i] << ' ';↵
cout << '\n';↵
}↵
}↵
~~~~~↵


</spoiler>↵



<spoiler summary="Feedback">↵
- Didn't solve [likes:1,C]↵
- Good problem [likes:2,C]↵
- Average problem [likes:3,C]↵
- Bad problem [likes:4,C]↵
</spoiler>↵

[1713D \- Tournament Coundown](https://mirror.codeforces.com/contest/1713/problem/D)↵


<spoiler summary="Hint 1">↵
We made sure that almost every $2^{n - 1}$ solutions cannot pass.↵
</spoiler>↵


<spoiler summary="Hint 2">↵
Did you use the $0$ query?↵
</spoiler>↵


<spoiler summary="Hint 3">↵
$\frac{2^{n + 1}}{3} = 2^n \cdot \frac{2}{3}$, what is the conclusion?↵
</spoiler>↵


<spoiler summary="Tutorial">↵

### <a href = "https://mirror.codeforces.com/contest/1713/problem/D">1713D \- Tournament Coundown</a>↵

There is a way to erase $3$ participants in every $2$ queries. Since there are $2^n - 1$ participants to be removed, the number of queries will be $\left \lceil (2^n - 1) \cdot \frac{2}{3} \right \rceil = \left \lfloor \frac{2^{n + 1}}{3} \right \rfloor$.↵
Suppose there are only $4$ participants. In the first query we will ask the judge to compare the $1^{st}$ and the $3^{rd}$ participants. There are three cases:↵

- The $1^{st}$ participant wins more game than the $3^{rd}$ one: the $2^{nd}$ and $3^{rd}$ cannot be the winner.↵

- The $3^{rd}$ participant wins more game than the $1^{st}$ one: the $1^{st}$ and $4^{th}$ cannot be the winner.↵

- The $1^{st}$ and $3^{rd}$ participants' numbers of winning games are equal: both the $1^{st}$ and $3^{rd}$ cannot be the winner.↵

Ask the remaining two participants, find the winner between them.↵

If there are more than $4$ participants, we can continuously divide the number by $4$ again and again, until there are at most $2$ participants left. Now we can get the winner in one final query.↵
</spoiler>↵


<spoiler summary="Solution">↵

~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

int ask(vector<int> &k)↵
{↵
cout << "? " << k[0] << ' ' << k[2] << endl;↵
int x;↵
cin >> x;↵
if (x == 1)↵
{↵
cout << "? " << k[0] << ' ' << k[3] << endl;↵
cin >> x;↵
if (x == 1) return k[0];↵
return k[3];↵
}↵
else if (x == 2)↵
{↵
cout << "? " << k[1] << ' ' << k[2] << endl;↵
cin >> x;↵
if (x == 1) return k[1];↵
return k[2];↵
}↵
else↵
{↵
cout << "? " << k[1] << ' ' << k[3] << endl;↵
cin >> x;↵
if (x == 1) return k[1];↵
return k[3];↵
}↵
}↵

void solve()↵
{↵
int n;↵
cin >> n;↵
vector<int> a, b;↵
for (int i = 1; i <= (1LL << n); i++)↵
{↵
a.push_back(i);↵
}↵
while (a.size() > 2)↵
{↵
while (!a.empty())↵
{↵
vector<int> k(4);↵
k[0] = a.back();↵
a.pop_back();↵
k[1] = a.back();↵
a.pop_back();↵
k[2] = a.back();↵
a.pop_back();↵
k[3] = a.back();↵
a.pop_back();↵
int win = ask(k);↵
b.push_back(win);↵
}↵
a = b;↵
b.clear();↵
}↵
if (a.size() == 2)↵
{↵
cout << "? " << a[0] << ' ' << a[1] << endl;↵
int x;↵
cin >> x;↵
if (x == 2) a[0] = a[1];↵
}↵
cout << "! " << a[0] << endl;↵
}↵

int main(int argc, char ** argv)↵
{↵
int tests;↵
cin >> tests;↵
while(tests--) solve();↵
}↵
~~~~~↵


</spoiler>↵



<spoiler summary="Feedback">↵
- Didn't solve [likes:1,D]↵
- Good problem [likes:2,D]↵
- Average problem [likes:3,D]↵
- Bad problem [likes:4,D]↵
</spoiler>↵

[1713E \- Cross Swapping](https://mirror.codeforces.com/contest/1713/problem/E)↵

<spoiler summary="Hint 1">↵
Think of the most to the least significant cell of the matrix.↵
</spoiler>↵

<spoiler summary="Hint 2">↵
How many positions in the matrix can a cell travel to after performing the operations?↵
</spoiler>↵

<spoiler summary="Hint 3">↵
And for each position that that cell can travel to, how many ways are there we can make it?↵
</spoiler>↵

<spoiler summary="Tutorial">↵

### <a href = "https://mirror.codeforces.com/contest/1713/problem/E">1713E \- Cross Swapping</a>↵

Let's take a look at what the lexicographically smallest matrix is. Let's call $(x, y)$ a cell that is in the intersection of row $x$ and column $y$ of the matrix, and the integer written on that cell is $A_{x, y}$. A cell $(x_p, y_p)$ of this matrix is called more significant than the another cell $(x_q, y_q)$ if and only if $x_p < x_q$, or $x_p = x_q$ and $y_p < y_q$. The problem asks us to find the smallest matrix so the best suitable way to solve this problem is to traverse through the most to the least significant cell of the matrix, then determine if the current cell can be minimized or not.↵

Suppose the current cell we are looking at is $(x, y)$. If $x = y$ then its position will not change after performing the operations. But if $x \neq y$, there are exactly $2$ operations that swap $(x, y)$ with another cell, that is $k = x$ and $k = y$. Both of these operations swap $(x, y)$ with the same cell $(y, x)$. So the only way we can minimize the value of $(x, y)$ is to try swapping it with $(y, x)$ (if $x < y$ and $A_{x, y} > A_{y, x}$) in some way.↵

As a result we have our constructive algorithm. Remind that for each operation $k = i$ of the matrix ($1 \le i \le n$), there are $2$ states: it is being performed and not being performed. Suppose we have traversed to the cell $(x, y)$. If $x \ge y$, ignore it. If $x < y$ then we try to make $A_{x, y} = min(A_{x, y}, A_{y, x})$ by deciding to swap or not to swap the cells. If $A_{x, y} > A_{y, x}$, try to swap $(x, y)$ with $(y, x)$ by making $2$ operations $k = x$ and $k = y$ having different states. And if $A_{x, y} < A_{y, x}$ then we should keep their positions unchanged by making $2$ operations $k = x$ and $k = y$ having the same state. Note that if $A_{x, y} = A_{y, x}$, we do nothing.↵

Let's implement this algorithm using a simple DSU where the $ith$ node represents the operation $k = i$. We define the value $par[u]$ in such a way that, suppose $p$ is the root of the $u$ node's component, $par[u] = p$ if $2$ operations $k = u$ and $k = p$ should have the same state, or $par[u] = -p$ if $2$ operations $k = u$ and $k = p$ should have different states. Define another function $join(i, j)$ to union $2$ nodes $i$ and $j$ to the same component. Note that $u$ and $-u$ are always in the same component and $par[-u] = -par[u]$. Thus, for the current cell $(x, y)$, we want to swap it with $(y, x)$ by calling $join(x, -y)$, or keep its position unchanged by calling $join(x, y)$.↵

After constructing the graphs, the last thing to do is to determine which operations should be performed. One way to do so is for each root of the components of the DSU, we perform the operation which this root represents for. Then for other nodes just check $par[i] > 0$ for the $ith$ node and if it is true, the $k = i$ operation should be performed. When we have the list of the operations that need to be performed, we can bruteforcely perform each operation from the list one by one and the final matrix will be the lexicographically smallest matrix.↵

Time complexity: $O(n^2)$ ↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

const int N = 2e3 + 5;↵

int n, a[N][N];↵

int par[N];↵
int getPar(int u) {↵
    if (u < 0) return -getPar(-u);↵
    if (u == par[u]) return u;↵
    return par[u] = getPar(par[u]);↵
}↵
void join(int u, int v) {↵
    u = getPar(u); v = getPar(v);↵
    if (abs(u) != abs(v)) {↵
        if (u > 0) par[u] = v;↵
        else par[-u] = -v;↵
    }↵
}↵

int main() {↵
    cin.tie(nullptr) -> sync_with_stdio(false);↵

    int tc; cin >> tc;↵
    while (tc--) {↵
        cin >> n;↵
        for (int i = 1; i <= n; i++)↵
            for (int j = 1; j <= n; j++) {↵
                cin >> a[i][j];↵
            }↵
    ↵
        iota(par + 1, par + n + 1, 1);↵
        // set par[i] == i for i in [1, n]↵

        for (int i = 1; i <= n; i++)↵
            for (int j = 1; j <= n; j++) {↵
                if (a[i][j] < a[j][i]) join(i, j);↵
                if (a[i][j] > a[j][i]) join(i, -j);↵
            }↵
    ↵
        for (int i = 1; i <= n; i++) {↵
            if (getPar(i) < 0) continue;↵
            // we only perform the operation↵
            // if and only if getPar(i) > 0↵
            for (int j = 1; j <= n; j++)↵
                swap(a[i][j], a[j][i]);↵
        }↵

        for (int i = 1; i <= n; i++) {↵
            for (int j = 1; j <= n; j++) {↵
                cout << a[i][j] << ' ';↵
            }↵
            cout << '\n';↵
        }↵
    }↵
}↵
~~~~~↵

</spoiler>↵



<spoiler summary="Feedback">↵

- Didn't solve [likes:1,E]↵
- Good problem [likes:2,E]↵
- Average problem [likes:3,E]↵
- Bad problem [likes:4,E]↵

</spoiler>↵

[1713F \- Lost Array](https://mirror.codeforces.com/contest/1713/problem/F)↵

<spoiler summary="Hint 0">↵

- Is there any case that the answer doesn't exist?↵
- If exist, are there multiple? ↵

</spoiler>↵

<spoiler summary="Hint 1">↵

- How many times does $a_i$ contribute to $b_{j, n}$?↵

<spoiler summary="Hint 1.1">↵
[Pascal's Triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle)↵
</spoiler>↵

$\rightarrow$ Calculate value that $a_i$ contribute to $b_{j, n}$.↵

<spoiler summary="Hint 1.2">↵
[Sierpiński triangle](https://en.wikipedia.org/wiki/Sierpi%C5%84ski_triangle)↵
</spoiler>↵

</spoiler>↵

<spoiler summary="Hint 2">↵

Consider the inverse problem: Given array $a$. Construct $b_{j, n}$ for all $j$. How can you solve this problem?↵

</spoiler>↵

<spoiler summary="Hint 3">↵

Consider easier problem: Let construct matrix $g$ of size $(2n + 1) \times (n + 1)$ same way as matrix $b$. Given $g_{i, n}$ $(1 \le i \le 2n)$, please reconstruct $a$. How can you solve this problem?↵

</spoiler>↵

<spoiler summary="Tutorial">↵

### <a href = "https://mirror.codeforces.com/contest/1713/problem/F">1713F \- Lost Array</a>↵

First, we can see that $a_i$ contribute $\binom{(n - i) + (j - 1)}{j - 1}$ times to $b_{j, n}$, which can calculate similar to [Pascal's Triangle](https://en.wikipedia.org/wiki/Pascal%27s_triangle). It's easy to see that the value that $a_i$ contribute to $b_{j, n}$ equal to $a_i$ when $\binom{(n - i) + (j - 1)}{j - 1}$ is odd, $0$ otherwise.↵

Let's solve the inverse problem: Given array $a$. Construct $b_{j, n}$ for all $j$. $(1 \le j \le n)$↵

By [Lucas Theorem](https://en.wikipedia.org/wiki/Lucas%27s_theorem), $\binom{(n - i) + (j - 1)}{j - 1}$ is odd when $(n - i)\ AND\ (j - 1) = 0$↵

$\rightarrow (n - i)$ is a submask of $\sim(j - 1)$ (with $\sim a$ is inverse mask of $a$).↵

Let define $m = 2^k$ with smallest $m$ satisfy $m \ge n$. Set $a'_i = a_i$ and $b'_j = b_{\sim(j - 1)} = b_{(m - 1) - (j - 1)}$ then $b'$ is the [Zeta transform](https://mirror.codeforces.com/blog/entry/45223) of $a'$.↵

So we could apply [Mobius transform](https://mirror.codeforces.com/blog/entry/72488) in $b'$ to get $a'$. Since the operation is xor, mobius transform is as same as zeta transform. But unlike the inverse problem, there are some differences. We don't know the value of $b'_i$ for $i$ in $[0, m - n)$.↵

Let $c$ be the sum over supermasks array of $b'$ (with $i$ is supermasks of $j$ when $i\ AND\ j = j)$, then set $c_k = 0$ for $k$ in $[m - n, m)$. After that, do another sum over supermasks on $c$ to get original value of $b'$. Now we can find $a'$ from $b'$ and $a$ from $a'$.↵

Complexity: $O(nlog_2(n))$↵

</spoiler>↵


<spoiler summary="Solution">↵

~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
using namespace std;↵
using namespace __gnu_pbds;↵

#define endl '\n'↵
#define fi first↵
#define se second↵
#define For(i, l, r) for (auto i = (l); i < (r); i++)↵
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)↵
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)↵
#define Fora(v, a) for (auto v: (a))↵
#define bend(a) (a).begin(), (a).end()↵
#define isz(a) ((signed)(a).size())↵

using ll = long long;↵
using ld = long double;↵
using pii = pair <int, int>;↵
using vi = vector <int>;↵
using vpii = vector <pii>;↵
using vvi = vector <vi>;↵

const int N = 1 << 19;↵

int n;↵
int a[N], b[N], ta[N], tb[N];↵
int c[N];↵

int m, lm, all1;↵

signed main(){↵
    cin >> n;↵
    ForE(i, 1, n){↵
        cin >> b[i];↵
    }↵

    m = 1 << __lg(n);↵
    if (m < n){↵
        m *= 2;↵
    }↵
    lm = __lg(m);↵
    all1 = m - 1;↵
    memset(ta, -1, sizeof(ta));↵
    memset(tb, -1, sizeof(tb));↵
    ForE(i, 1, n){↵
        tb[all1 ^ (i - 1)] = b[i];↵
        ta[n - i] = -2;↵
    }↵

    For(i, 0, m){↵
        c[all1 ^ i] = max(tb[i], 0);↵
    }↵
    For(bit, 0, lm){↵
        For(msk, 0, m){↵
            if (msk >> bit & 1){↵
                c[msk] ^= c[msk ^ (1 << bit)];↵
            }↵
        }↵
    }↵
    For(i, 0, m){↵
        if (tb[i] == -1){↵
            c[all1 ^ i] = 0;↵
        }↵
    }↵
    For(bit, 0, lm){↵
        For(msk, 0, m){↵
            if (msk >> bit & 1){↵
                c[msk] ^= c[msk ^ (1 << bit)];↵
            }↵
        }↵
    }↵
    For(i, 0, m){↵
        if (tb[i] == -1){↵
            tb[i] = c[all1 ^ i];↵
        }↵
    }↵

    For(i, 0, m){↵
        ta[i] = tb[i];↵
    }↵
    For(bit, 0, lm){↵
        For(msk, 0, m){↵
            if (msk >> bit & 1){↵
                ta[msk] ^= ta[msk ^ (1 << bit)];↵
            }↵
        }↵
    }↵
    ForE(i, 1, n){↵
        a[i] = ta[n - i];↵
    }↵
    ForE(i, 1, n){↵
        cout << a[i] << ' ';↵
    } cout << endl;↵
}↵

~~~~~↵

</spoiler>↵

<spoiler summary="Feedback">>↵

- Didn't solve [likes:1,F]↵
- Good problem [likes:2,F]↵
- Average problem [likes:3,F]↵
- Bad problem [likes:4,F]↵
</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en70 English GlowCheese 2022-08-08 11:16:58 2638 Tiny change: 'answer is \t{YES}\n\nTime c' -> 'answer is _YES_.\n\nTime c'
en69 English DeMen100ns 2022-08-07 07:10:27 158 Tiny change: '\n<spoiler s' -> '<spoiler s'
en68 English thanhchauns2 2022-08-07 05:58:39 2008
en67 English thanhchauns2 2022-08-07 05:56:47 1827
en66 English thanhchauns2 2022-08-07 04:14:45 25 Reverted to en64
en65 English thanhchauns2 2022-08-07 04:14:19 25
en64 English thanhchauns2 2022-08-07 04:01:17 117 Tiny change: '\n<spoiler s' -> '<spoiler s'
en63 English DeMen100ns 2022-08-06 21:56:20 1 Tiny change: '\n\n<spoiler' -> '\n<spoiler' (published)
en62 English DeMen100ns 2022-08-06 21:50:42 3335 Tiny change: '\n<spoiler s' -> '<spoiler s' (saved to drafts)
en61 English GlowCheese 2022-08-06 20:26:42 80
en60 English GlowCheese 2022-08-06 20:06:31 20
en59 English GlowCheese 2022-08-06 20:01:09 0 Tiny change: '\n\n<spoiler' -> '\n<spoiler' (published)
en58 English GlowCheese 2022-08-06 20:00:59 384 (saved to drafts)
en57 English thanhchauns2 2022-08-06 19:58:44 13
en56 English thanhchauns2 2022-08-06 19:44:37 8
en55 English thanhchauns2 2022-08-06 19:35:30 0 Tiny change: '\n\n<spoiler' -> '\n<spoiler' (published)
en54 English GlowCheese 2022-08-06 16:11:36 3
en53 English GlowCheese 2022-08-06 16:10:33 17
en52 English GlowCheese 2022-08-06 16:09:44 2
en51 English GlowCheese 2022-08-06 16:09:26 355
en50 English GlowCheese 2022-08-06 15:59:53 375
en49 English thanhchauns2 2022-08-06 15:06:30 716 Tiny change: 'two axis? Suppose the second axis is $Oy+$.' -> 'two axis? Let's assume it is $Oy+$.'
en48 English GlowCheese 2022-08-06 10:28:36 4
en47 English GlowCheese 2022-08-06 10:28:02 153
en46 English GlowCheese 2022-08-06 10:26:04 1459 Tiny change: '\n\n<spoiler' -> '\n<spoiler'
en45 English GlowCheese 2022-08-06 09:57:33 1963
en44 English thanhchauns2 2022-08-06 09:41:49 150
en43 English GlowCheese 2022-08-06 08:54:45 34 Tiny change: '\n<spoiler s' -> '<spoiler s'
en42 English GlowCheese 2022-08-06 08:52:57 21 Tiny change: '\n<spoiler s' -> '<spoiler s'
en41 English GlowCheese 2022-08-06 08:50:49 293
en40 English GlowCheese 2022-08-06 08:46:44 1094
en39 English thanhchauns2 2022-08-06 08:14:23 805 Tiny change: '\n<spoiler s' -> '<spoiler s'
en38 English thanhchauns2 2022-08-06 08:13:07 35
en37 English thanhchauns2 2022-08-06 08:08:24 212
en36 English thanhchauns2 2022-08-06 08:07:41 30 Tiny change: '\n\n<spoil' -> '[likes:1]\n\n<spoil'
en35 English thanhchauns2 2022-08-06 08:05:56 1 Tiny change: '\n\n<spoil' -> '(likes:3,option1)\n\n\n<spoil'
en34 English thanhchauns2 2022-08-06 07:47:17 3
en33 English thanhchauns2 2022-08-06 07:46:47 56 Tiny change: '\n<spoiler s' -> '<spoiler s'
en32 English GlowCheese 2022-08-06 07:42:11 912
en31 English thanhchauns2 2022-08-06 07:37:28 1231
en30 English thanhchauns2 2022-08-06 07:34:33 1291
en29 English thanhchauns2 2022-08-06 03:12:36 4858 Tiny change: 'nd-color:#808080">\n <t' -> 'nd-color:#D3D3D3">\n <t'
en28 English thanhchauns2 2022-08-06 01:59:29 2804 Tiny change: 'cale=en)\n \n<spoiler' -> 'cale=en)\n\ndấdas\n<spoiler'
en27 English GlowCheese 2022-08-06 00:04:36 3963 Tiny change: ' the most significant to the l' -> ' the most to the l'
en26 English DeMen100ns 2022-08-05 19:51:28 23 Tiny change: ' = 0$ or $\~(n - i)\' -> ' = 0$ or $ \~(n - i)\'
en25 English DeMen100ns 2022-08-05 19:46:22 1 Tiny change: ' = 0$ or $~(n - i)\ ' -> ' = 0$ or $\~(n - i)\ '
en24 English DeMen100ns 2022-08-05 19:36:08 18 Tiny change: 'of $b'_i$ $(n \le i < m)$.\n\n.' -> 'of $b'_i$ for $i$ in $[n, m)$.\n\n.'
en23 English DeMen100ns 2022-08-05 19:31:10 228 Tiny change: '$(n \le i \le m)$.\n\nS' -> '$(n \le i < m)$.\n\nS'
en22 English DeMen100ns 2022-08-05 18:27:38 232
en21 English DeMen100ns 2022-08-05 14:17:39 167 Tiny change: 'en $b$ is ([zeta transform]https://co' -> 'en $b$ is the [zeta transform](https://co'
en20 English DeMen100ns 2022-08-05 12:31:31 2542
en19 English thanhchauns2 2022-08-05 09:29:45 234
en18 English DeMen100ns 2022-08-05 08:07:25 4 Tiny change: 'umbẻtimes does $alpha_i$' -> 'umbẻtimes of $alpha_i$'
en17 English DeMen100ns 2022-08-05 08:06:52 280
en16 English thanhchauns2 2022-08-05 05:50:48 61
en15 English thanhchauns2 2022-08-04 22:47:28 1018 Tiny change: 'ce $k$ to smaller $h - k - ' -> 'ce $k$ to $h - k - '
en14 English thanhchauns2 2022-08-04 22:12:39 4
en13 English thanhchauns2 2022-08-04 22:12:13 355
en12 English DeMen100ns 2022-08-04 11:11:54 523
en11 English DeMen100ns 2022-08-04 10:04:36 289
en10 English DeMen100ns 2022-08-03 13:07:25 1400 Tiny change: 'ea: [user:thanhchauns2,2022-07-30]\n\n<spoi' -> 'ea: [user:DeMen100ns]\n\n<spoi'
en9 English thanhchauns2 2022-08-03 07:51:22 6
en8 English DeMen100ns 2022-08-03 07:40:24 315 Tiny change: '**What if: ** $n \le ' -> '**What if:** $n \le '
en7 English DeMen100ns 2022-08-03 07:17:53 1233
en6 English thanhchauns2 2022-08-02 20:50:44 31
en5 English thanhchauns2 2022-08-02 20:33:43 1129
en4 English thanhchauns2 2022-08-01 02:54:50 8 Tiny change: 'tinuously reduce the numb' -> 'tinuously divide the numb'
en3 English thanhchauns2 2022-07-30 15:01:43 16 Tiny change: 'number by 4 again and' -> 'number by $4$ again and'
en2 English thanhchauns2 2022-07-30 15:00:55 2915 Tiny change: 'a' -> 'a\n\n![ ](D - Tournament Countdown)'
en1 English DeMen100ns 2022-07-30 14:10:29 41 Initial revision (saved to drafts)