codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2134.md (25114B)


      1 Source: https://codeforces.com/blog/entry/145832
      2 
      3 Unfortunately, the round turns out to be very unbalanced :( I'm deeply sorry about this issue.
      4 
      5 I hope you still enjoy the problems.
      6 
      7 **Rate the contest! (definitely not copied from past contests)**
      8 
      9 **Quality**
     10 
     11 * Excellent contest
     12 * Good contest
     13 * Average contest
     14 * Bad contest
     15 * Horrible contest
     16 
     17 **Difficulty**
     18 
     19 * Trivial contest
     20 * Easy contest
     21 * Average contest
     22 * Hard contest
     23 * Impossible contest
     24 
     25 [2134A - Painting With Two Colors](/contest/2134/problem/A "Codeforces Round 1045 (Div. 2)")
     26 
     27 **Hint 1**
     28 
     29 Check the parity of numbers $a$, $b$, and $n$.
     30 
     31 **Solution**
     32 
     33 Let us first consider the $b$ blue cells. Since all $b$ cells appear in the final painting, for the coloring to be symmetric, they must be placed at the middle of the grid. Consequently, $b$ and $n$ must have the same parity.
     34 
     35 Next, we examine two possible cases:
     36 
     37 * If $b \geq a$, then the blue cells can fully cover all red cells. In this situation, the value of $a$ does not affect the final coloring.
     38 * If $b \lt a$, then the red cells are not completely covered by the blue ones. Therefore, the red cells must also be placed in the middle of the grid, which means $a$ and $n$ must have the same parity as well.
     39 
     40 Thus, by checking these conditions, we can determine whether a symmetric coloring exists. This requires only $\mathcal{O}(1)$ time.
     41 
     42 **Code (C++)**
     43 
     44 ```
     45 #include <iostream>
     46 using namespace std;
     47 
     48 int main() {
     49   ios::sync_with_stdio(false);
     50   cin.tie(0);
     51   int t;
     52   cin >> t;
     53   while (t--) {
     54     int n, a, b;
     55     cin >> n >> a >> b;
     56     if (a <= b) {
     57       cout << ((n % 2) == (b % 2) ? "YES\n" : "NO\n");
     58     } else {
     59       cout << ((n % 2) == (b % 2) && (n % 2) == (a % 2) ? "YES\n" : "NO\n");
     60     }
     61   }
     62 }
     63 ```
     64 
     65 **Code (Python)**
     66 
     67 ```
     68 t = int(input())
     69 for _ in range(t):
     70     n, a, b = map(int, input().split())
     71     if a <= b:
     72         if n % 2 == b % 2:
     73             print('YES')
     74         else:
     75             print('NO')
     76     else:
     77         if n % 2 == a % 2 and n % 2 == b % 2:
     78             print('YES')
     79         else:
     80             print('NO')
     81 ```
     82 
     83 **Rate the problem!**
     84 
     85 **Quality**
     86 
     87 * Excellent problem
     88 * Good problem
     89 * Average problem
     90 * Bad problem
     91 * Horrible problem
     92 
     93 **Difficulty**
     94 
     95 * Trivial problem
     96 * Easy problem
     97 * Average problem
     98 * Hard problem
     99 * Impossible problem
    100 
    101 [2134B - Add 0 or K](/contest/2134/problem/B "Codeforces Round 1045 (Div. 2)")
    102 
    103 There are (at least) two solutions to the problem. Vote for your solution!
    104 
    105 **How did you solve the problem?**
    106 
    107 * $a_i \gets a_i + k \cdot (a_i \bmod (k+1))$
    108 * Find a small prime number $p$ and make all elements divisible by $p$
    109 * Others
    110 
    111 **Hint 1**
    112 
    113 Find an integer $g \gt 1$ and integers $c_1, c_2, \ldots, c_n$ such that each $a_i + k \cdot c_i$ is divisible by $g$.
    114 
    115 **Hint 2**
    116 
    117 Decide the value of $g$ only based on $k$. There may be more than one possible choices.
    118 
    119 **Solution**
    120 
    121 The problem is equivalent to finding an array of $n$ non-negative integers $c_1, c_2, \ldots, c_n$ such that $0 \le c_i \le k$ for $1 \le i \le n$ and
    122 
    123 $\gcd(a_1 + k \cdot c_1, a_2 + k \cdot c_2, \ldots, a_n + k \cdot c_n) \gt 1$
    124 
    125 The idea is as follows. If we can find an integer $g \gt 1$ and integers $c_1, c_2, \ldots, c_n$ such that each $a_i + k \cdot c_i$ is divisible by $g$ (for $1 \le i \le n$), then the GCD condition is satisfied.
    126 
    127 There are (at least) two ways to construct such a solution. The simplest solution is to take $g = k+1$ and define $c_i = a_i \bmod (k+1)$. This works because
    128 
    129 $a_i + k \cdot c_i \equiv c_i + k \cdot c_i \equiv (k+1) \cdot c_i \equiv 0 \pmod{k+1}$
    130 
    131 Hence every term is divisible by $k+1$.
    132 
    133 Alternatively, you can also find the smallest integer $x$ such that $\gcd(x,k) = 1$, and set $g = x$. Note that $g \leq 29$, since $k \leq 10^9$ and the product of all prime numbers from $2$ to $29$ already exceeds $10^9$.
    134 
    135 Then, for each $a_i$, we can add $k$ to it until it becomes divisible by $g$. In fact, the value of $c_i$ can be determined explicitly (though it is not required) as
    136 
    137 $a_i + k \cdot c_i \equiv 0 \pmod{g} \quad \implies \quad c_i \equiv (-a_i \cdot k^{-1}) \pmod{g}$
    138 
    139 where $k^{-1}$ is the modular inverse of $k$ modulo $g$.
    140 
    141 Thus, in either method, we can always construct a valid array so that the GCD of the resulting numbers is greater than $1$.
    142 
    143 **Code for solution 1 (C++)**
    144 
    145 ```
    146 #include <iostream>
    147 #include <vector>
    148 using namespace std;
    149 
    150 int main() {
    151   ios::sync_with_stdio(false);
    152   cin.tie(0);
    153   int t;
    154   cin >> t;
    155   while (t--) {
    156     int n, k;
    157     cin >> n >> k;
    158     vector<long long> a(n);
    159     for (auto &i : a) {
    160       cin >> i;
    161       i += (i % (k + 1)) * k;
    162     }
    163     for (auto i : a)
    164       cout << i << ' ';
    165     cout << '\n';
    166   }
    167 }
    168 ```
    169 
    170 **Code for solution 1 (Python)**
    171 
    172 ```
    173 t = int(input())
    174 for _ in range(t):
    175     n, k = map(int, input().split())
    176     a = list(map(int, input().split()))
    177     for i in range(n):
    178         a[i] += (a[i] % (k + 1)) * k
    179     print(*a)
    180 ```
    181 
    182 **Code for solution 2 (C++)**
    183 
    184 ```
    185 #include <iostream>
    186 #include <numeric>
    187 #include <vector>
    188 using namespace std;
    189 
    190 int main() {
    191   ios::sync_with_stdio(false);
    192   cin.tie(0);
    193   int t;
    194   cin >> t;
    195   while (t--) {
    196     int n, k;
    197     cin >> n >> k;
    198     vector<long long> a(n);
    199     for (auto &i : a) {
    200       cin >> i;
    201     }
    202 
    203     for (int g = 2;; g++) {
    204       if (gcd(g, k) != 1)
    205         continue;
    206       for (auto &i : a) {
    207         while (i % g != 0)
    208           i += k;
    209       }
    210       for (auto i : a)
    211         cout << i << ' ';
    212       cout << '\n';
    213       break;
    214     }
    215   }
    216 }
    217 ```
    218 
    219 **Code for solution 2 (Python)**
    220 
    221 ```
    222 import math
    223 t = int(input())
    224 for _ in range(t):
    225     n, k = map(int, input().split())
    226     a = list(map(int, input().split()))
    227     for g in range(2, k + 2):
    228         if math.gcd(g, k) > 1:
    229             continue 
    230         ok = True
    231         b = list(a)
    232         for i in range(n):
    233             if b[i] % g == 0:
    234                 continue
    235             for j in range(1, k + 1):
    236                 b[i] += k
    237                 if b[i] % g == 0:
    238                     break
    239             if b[i] % g != 0:
    240                 ok = False
    241         if ok:
    242             print(*b)
    243             break
    244 ```
    245 
    246 **Rate the problem!**
    247 
    248 **Quality**
    249 
    250 * Excellent problem
    251 * Good problem
    252 * Average problem
    253 * Bad problem
    254 * Horrible problem
    255 
    256 **Difficulty**
    257 
    258 * Trivial problem
    259 * Easy problem
    260 * Average problem
    261 * Hard problem
    262 * Impossible problem
    263 
    264 [2134C - Even Larger](/contest/2134/problem/C "Codeforces Round 1045 (Div. 2)")
    265 
    266 **Hint 1**
    267 
    268 Only subarrays with length equal to $2$ or $3$ are useful.
    269 
    270 **Hint 2**
    271 
    272 Propose a greedy algorithm to decide which element to perform an operation.
    273 
    274 **Solution**
    275 
    276 For convenience, if $n$ is even, we append $a_{n+1}=0$ to the end of the array. Note that $a_{n+1}$ cannot be modified.
    277 
    278 The first key observation is the following:
    279 
    280 **Observation.** If all subarrays $[a_l, a_{l+1}, \ldots, a_r]$ with the following properties satisfy the condition, then all subarrays satisfy the condition:
    281 
    282 * $r = l + 2$,
    283 * $l$ and $r$ are both odd.
    284 
    285 **Proof.** Consider such subarrays where both $l$ and $r$ are odd:
    286 
    287 $\begin{array}{rcl} \displaystyle \sum_{\substack{l \leq i \leq r \\ i \ \text{even}}} a_i &\geq& \displaystyle \sum_{\substack{l \leq i \leq r \\ i \ \text{even}}} \bigl(a_{i-1} + a_{i+1}\bigr) \\[1.2em]  
    288   
    289 &=& a_l \;+\; \displaystyle \left( \sum_{\substack{l+2 \leq i \leq r-2 \\ i \ \text{odd}}} 2a_i \right) \;+\; a_r \\[1.2em]  
    290   
    291 &\geq& a_l \;+\; \displaystyle \left( \sum_{\substack{l+2 \leq i \leq r-2 \\ i \ \text{odd}}} a_i \right) \;+\; a_r \\[1.2em]  
    292   
    293 &=& \displaystyle \sum_{\substack{l \leq i \leq r \\ i \ \text{odd}}} a_i \end{array}$
    294 
    295 The second inequality holds because all numbers are non-negative.
    296 
    297 Thus, checking only these subarrays is sufficient: all other subarrays will automatically satisfy the condition because they involve fewer elements at odd positions. $\square$
    298 
    299 We will call these subarrays **important** in the following discussion.
    300 
    301 Now we find the minimum number of operations. Instead of directly minimizing the number of operations, we can think in terms of constructing the final array $b$ after the operations. Our goal is to maximize the sum of the elements in $b$.
    302 
    303 Initially, we set $b_i = 0$ for all $i$. Notice that it is never beneficial to reduce values at even indices. Therefore, we can safely set $b_i = a_i$ for every even $i$.
    304 
    305 The task is then to determine the values of $b_i$ at odd indices. It turns out that the following greedy algorithm works:
    306 
    307 * Repeatedly pick the smallest odd index $i$ such that $b_i \lt a_i$, and increasing $b_i$ by $1$ does not violate the condition for any important subarray. Then increment $b_i$ by $1$.
    308 
    309 This greedy algorithm ensures that we maximize the sum of $b$ while preserving validity. It can be simulated in $\mathcal{O}(n)$ time.
    310 
    311 **Code (C++)**
    312 
    313 ```
    314 #include <algorithm>
    315 #include <iostream>
    316 #include <vector>
    317 using namespace std;
    318 
    319 int main() {
    320   ios::sync_with_stdio(false);
    321   cin.tie(0);
    322   int t;
    323   cin >> t;
    324   while (t--) {
    325     int n;
    326     cin >> n;
    327     vector<int> a(n);
    328     for (auto &i : a)
    329       cin >> i;
    330 
    331     vector<int> b(n + 1);
    332     long long ans = 0;
    333     for (int i = 0; i < n; i += 2) {
    334       int mn = a[i];
    335       if (i >= 2)
    336         mn = min(mn, a[i - 1] - b[i - 2]);
    337       if (i + 1 < n)
    338         mn = min(mn, a[i + 1]);
    339       b[i] = mn;
    340       ans += (a[i] - b[i]);
    341     }
    342 
    343     cout << ans << '\n';
    344   }
    345 }
    346 ```
    347 
    348 **Code (Python)**
    349 
    350 ```
    351 t = int(input())
    352 for _ in range(t):
    353     n = int(input())
    354     a = list(map(int, input().split()))
    355     b = [0] * (n + 1)
    356     ans = 0
    357     for i in range(0, n, 2):
    358         mn = a[i]
    359         if i >= 2:
    360             mn = min(mn, a[i - 1] - b[i - 2])
    361         if i + 1 < n:
    362             mn = min(mn, a[i + 1])
    363         b[i] = mn
    364         ans += (a[i] - b[i])
    365     print(ans)
    366 ```
    367 
    368 **Rate the problem!**
    369 
    370 **Quality**
    371 
    372 * Excellent problem
    373 * Good problem
    374 * Average problem
    375 * Bad problem
    376 * Horrible problem
    377 
    378 **Difficulty**
    379 
    380 * Trivial problem
    381 * Easy problem
    382 * Average problem
    383 * Hard problem
    384 * Impossible problem
    385 
    386 [2134D - Sliding Tree](/contest/2134/problem/D "Codeforces Round 1045 (Div. 2)")
    387 
    388 **Hint 1**
    389 
    390 Consider the diameter of the tree. What do you discover?
    391 
    392 **Hint 2**
    393 
    394 Each sliding operation increases the diameter of the tree by at most $1$.
    395 
    396 **Hint 3**
    397 
    398 Now about the construction. How to perform an operation at each step that increases the diameter by exactly $1$?
    399 
    400 **Solution**
    401 
    402 We begin with the following observation:
    403 
    404 **Observation.** Each sliding operation increases the diameter of the tree by at most $1$.
    405 
    406 **Proof.** Consider an operation $(a,b,c)$, any pair of indices $(u,v)$, and the unique path $p$ between $u$ and $v$. If $p$ does not pass through $b$, or if $b$ is an endpoint of $p$, then the length of $p$ increases by at most $1$ before and after the operation. Otherwise, let $i_1$ and $i_2$ denote the two neighbors of $b$ on the path $p$. Then:
    407 
    408 * If $i_1 = a$ and $i_2 = c$ (or vice versa), the length of $p$ does not change.
    409 * If $i_1 = a$ and $i_2 \neq c$ (or vice versa), the length of $p$ increases by $1$.
    410 * If $i_1 \neq a$ and $i_2 = c$ (or vice versa), the length of $p$ decreases by $1$.
    411 * In all other cases, the length of $p$ does not change.
    412 
    413 Thus, for any path in the tree, its length can increase by at most $1$. Consequently, the diameter of the tree increases by at most $1$ after a single operation. $\square$
    414 
    415 Let $l$ denote the diameter of the input tree. To transform it into a path graph (whose diameter is $n-1$), it is clear that at least $(n-1) - l$ operations are required.
    416 
    417 The remaining question is whether it is always possible to perform an operation at each step that increases the diameter by exactly $1$. This turns out to be true. To see this, take any diameter of the tree and root the tree at one of its endpoints. In each operation, select an edge adjacent to the diameter. Suppose this edge is $(u,v)$, where $u$ lies on the diameter and $v$ does not. Then perform the operation with $a$ as the parent of $u$ (in the rooted tree), $b = u$, and $c = v$. One can verify that this increases the diameter by $1$.
    418 
    419 From the above construction, we conclude not only that the minimum number of operations is $(n-1)-l$, but also that we can explicitly construct a sequence of operations that transforms the given tree into a path graph with this minimum number of moves.
    420 
    421 Finally, finding the first sliding operation can be done in $\mathcal{O}(n)$ time.
    422 
    423 **Code (C++)**
    424 
    425 ```
    426 #include <algorithm>
    427 #include <functional>
    428 #include <iostream>
    429 #include <vector>
    430 using namespace std;
    431 
    432 int main() {
    433   ios::sync_with_stdio(false);
    434   cin.tie(0);
    435   int t;
    436   cin >> t;
    437   while (t--) {
    438     int n;
    439     cin >> n;
    440     vector<vector<int>> G(n);
    441     for (int i = 0; i < n - 1; i++) {
    442       int u, v;
    443       cin >> u >> v;
    444       u--, v--;
    445       G[u].push_back(v);
    446       G[v].push_back(u);
    447     }
    448 
    449     vector<int> dist(n), p(n);
    450     function<void(int, int)> dfs = [&](int now, int par) {
    451       p[now] = par;
    452       for (int i : G[now]) {
    453         if (i != par) {
    454           dist[i] = dist[now] + 1;
    455           dfs(i, now);
    456         }
    457       }
    458     };
    459 
    460     dist[0] = 0;
    461     dfs(0, -1);
    462     int x = max_element(dist.begin(), dist.end()) - dist.begin();
    463     dist[x] = 0;
    464     dfs(x, -1);
    465     int y = max_element(dist.begin(), dist.end()) - dist.begin();
    466 
    467     if (dist[y] == n - 1) {
    468       cout << -1 << '\n';
    469     } else {
    470       vector<int> on_diameter(n);
    471       int now = y;
    472       while (now != -1) {
    473         on_diameter[now] = 1;
    474         now = p[now];
    475       }
    476       int a = -1, b = -1, c = -1;
    477       for (int u = 0; u < n; u++) {
    478         for (int v : G[u]) {
    479           if (on_diameter[u] && !on_diameter[v]) {
    480             a = p[u], b = u, c = v;
    481             break;
    482           }
    483         }
    484         if (a != -1)
    485           break;
    486       }
    487       cout << a + 1 << ' ' << b + 1 << ' ' << c + 1 << '\n';
    488     }
    489   }
    490 }
    491 ```
    492 
    493 **Rate the problem!**
    494 
    495 **Quality**
    496 
    497 * Excellent problem
    498 * Good problem
    499 * Average problem
    500 * Bad problem
    501 * Horrible problem
    502 
    503 **Difficulty**
    504 
    505 * Trivial problem
    506 * Easy problem
    507 * Average problem
    508 * Hard problem
    509 * Impossible problem
    510 
    511 [2134E - Power Boxes](/contest/2134/problem/E "Codeforces Round 1045 (Div. 2)")
    512 
    513 **Hint 1**
    514 
    515 An intuitive starting point may be to perform a throw query on every coordinate $i$. For which $i$ we can decide the value of $a_i$ immediately?
    516 
    517 **Hint 2**
    518 
    519 For those incides whose $a_i$ is unknown, try to perform some swap queries on them to get the values of $a_i$ for them.
    520 
    521 **Hint 3**
    522 
    523 No two unknown indices are adjacent.
    524 
    525 **Solution**
    526 
    527 An intuitive starting point is to perform a throw query on every coordinate $i$ ($1 \le i \le n$). Let $d_i$ denote the total number of jumps the ball makes when starting from coordinate $i$. For convenience, define $d_{n+1} = d_{n+2} = 0$.
    528 
    529 Notice that for $1 \le i \le n$, if $d_{i+1} \neq d_{i+2}$, then we can immediately determine $a_i$: if $d_i = d_{i+1} + 1$, then $a_i = 1$; otherwise $a_i = 2$.
    530 
    531 The difficult part of the problem is when $d_{i+1} = d_{i+2}$. We call an index $i$ \textbf{unknown} if $d_{i+1} = d_{i+2}$. In such cases, we can deduce $d_i$ without issuing a query, thus saving it for later use. The following observation is crucial:
    532 
    533 **Observation.** No two unknown indices are adjacent.
    534 
    535 **Proof.** If $i$ is unknown, then $d_i = d_{i+1} + 1$, hence $d_i \neq d_{i+1}$. Therefore, $i-1$ cannot be unknown. $\square$
    536 
    537 To exploit this fact, we adopt the following strategy: After computing all $d_i$, for each unknown index $i$ (in increasing order), we swap the boxes at positions $i$ and $i+1$, and then perform a throw query at coordinate $i+1$. Since index $i+1$ is not unknown, this reveals $a_i$. The special case is $i = n$: here, we swap boxes $n-1$ and $n$, then perform a throw query on coordinate $n-1$ to obtain $a_n$.
    538 
    539 To sum up:
    540 
    541 * For $i$ from $n$ down to $1$: perform a throw query on coordinate $i$. If $d_{i+1} = d_{i+2}$, skip the query for $i$ and mark $i$ as unknown (but still compute $d_i$). Otherwise, determine both $a_i$ and $d_i$.
    542 * For each $i$ from $1$ to $n-1$: if $i$ is unknown, swap box $i$ with box $i+1$ and perform a throw query at coordinate $i+1$. This reveals $a_i$.
    543 * Finally, swap $n-1$ and $n$, and perform a throw query on coordinate $n-1$ to determine $a_n$.
    544 
    545 For every unknown index we use $2$ queries, and for each known index we use $1$. Since no two unknown indices are adjacent, there are at most $\lceil \frac{n}{2} \rceil$ unknown indices. Hence, the total number of queries is at most $\left\lceil \frac{3n}{2} \right\rceil$.
    546 
    547 **Code (C++)**
    548 
    549 ```
    550 #include <iostream>
    551 #include <vector>
    552 using namespace std;
    553 
    554 int main() {
    555   ios::sync_with_stdio(false);
    556   cin.tie(0);
    557   int t;
    558   cin >> t;
    559   while (t--) {
    560     int n;
    561     cin >> n;
    562 
    563     vector<int> a(n);
    564     auto swap = [&](int x) {
    565       cout << "swap " << x + 1 << endl;
    566     };
    567     auto throw_ball = [&](int x) {
    568       cout << "throw " << x + 1 << endl;
    569       int ret;
    570       cin >> ret;
    571       return ret;
    572     };
    573     auto answer = [&]() {
    574       cout << "!";
    575       for (auto i : a)
    576         cout << ' ' << i;
    577       cout << endl;
    578     };
    579 
    580     vector<int> jumps(n + 2);
    581     for (int i = n - 1; i >= 0; i--) {
    582       if (jumps[i + 1] == jumps[i + 2]) {
    583         jumps[i] = jumps[i + 1] + 1;
    584       } else {
    585         jumps[i] = throw_ball(i);
    586         if (jumps[i] == jumps[i + 1] + 1)
    587           a[i] = 1;
    588         else
    589           a[i] = 2;
    590       }
    591     }
    592     for (int i = 0; i + 1 < n; i++) {
    593       if (a[i] == 0) {
    594         swap(i);
    595         int jumps_i = throw_ball(i + 1);
    596         if (jumps_i == jumps[i + 2] + 1)
    597           a[i] = 1;
    598         else
    599           a[i] = 2;
    600       }
    601     }
    602     swap(n - 2);
    603     int jumps_last = throw_ball(n - 2);
    604     if (jumps_last == 2)
    605       a[n - 1] = 1;
    606     else
    607       a[n - 1] = 2;
    608     answer();
    609   }
    610 }
    611 ```
    612 
    613 **Rate the problem!**
    614 
    615 **Quality**
    616 
    617 * Excellent problem
    618 * Good problem
    619 * Average problem
    620 * Bad problem
    621 * Horrible problem
    622 
    623 **Difficulty**
    624 
    625 * Trivial problem
    626 * Easy problem
    627 * Average problem
    628 * Hard problem
    629 * Impossible problem
    630 
    631 [2134F - Permutation Oddness](/contest/2134/problem/F "Codeforces Round 1045 (Div. 2)")
    632 
    633 Thanks to [Misuki](/profile/Misuki "Grandmaster Misuki") for coming up with a better solution! My original solution has a much larger constant.
    634 
    635 **Hint 1**
    636 
    637 Consider two groups of numbers; one is ${0, 2}$ and another is ${1, 3}$. What do you discover?
    638 
    639 **Hint 2**
    640 
    641 Consider the segments formed by ${0, 2}$ (same for ${1, 3}$). For each $i$ and $j$, find the number of ways to arrange them into $i$ segments so that the total number of adjacent pairs inside all segments contribute oddness $j$.
    642 
    643 **Hint 3**
    644 
    645 Enumerate all binary strings consisting of $c_0$ zeros and $c_2$ twos. Then split these strings into several substrings.
    646 
    647 **Hint 4**
    648 
    649 Brute force over the number of runs of the binary string. Find the contribution to the count.
    650 
    651 **Solution**
    652 
    653 Consider any rearrangement $b$. We color all elements $b_i$ with value $0$ or $2$ as red, and those with value $1$ or $3$ as blue. Then the array can be viewed as alternating red and blue segments.
    654 
    655 We observe the following:
    656 
    657 * Adjacent pairs within a red segment contribute $0$ or $2$ to the oddness. The same holds for blue segments.
    658 * Adjacent pairs between red and blue segments contribute exactly $1$ to the oddness.
    659 * The number of red and blue segments differs by at most $1$.
    660 
    661 Hence, if we can calculate the following:
    662 
    663 * $r_{i,j}$: number of ways to arrange $c_0$ zeros and $c_2$ twos into $i$ segments, so that the total number of adjacent pairs inside all segments contribute oddness $j$.
    664 * Similarly define $b_{i,j}$ for the blue digits ($1$ and $3$)
    665 
    666 Then the final answer can be computed in $\mathcal{O}(n^3)$ by performing convolutions between the arrays pairs $(r_i, b_i), (r_{i+1}, b_i), (r_i, b_{i+1})$.
    667 
    668 Now about computing $r_{i,j}$. This reduces to counting tuples of $i$ binary strings formed from $c_0$ zeros and $c_2$ twos, such that the total number of alternating adjacent pairs inside them equals $j$.
    669 
    670 The idea is as follows. First, enumerate all binary strings consisting of $c_0$ zeros and $c_2$ twos. Then split these strings into several substrings.
    671 
    672 Suppose a binary string has $l$ runs. Let $l_1 = \left\lceil \frac l 2 \right\rceil$ be the number of runs of $0$, and $l_2 = l - l_1$ the number of runs of $2$ (or vice versa). The number of such binary strings is
    673 
    674 $\displaystyle \binom{c_0 - 1}{l_1 - 1} \cdot \binom{c_2 - 1}{l_2 - 1}$
    675 
    676 In such strings, there are $l-1$ adjacent pairs with different numbers, and $c_0 + c_2 - l$ adjacent pairs with the same numbers.
    677 
    678 Now split the string into several substrings. Assume we choose $k_1$ positions among the $l-1$ differing adjacencies, and $k_2$ positions among the $c_0 + c_2 - l$ equal adjacencies. The number of ways to do this is
    679 
    680 $\displaystyle \binom{l - 1}{k_1} \cdot \binom{c_0 + c_2 - l}{k_2}$
    681 
    682 This partition produces $k_1 + k_2 + 1$ substrings, each contributing oddness $2 \cdot (l - 1 - k_1)$.  
    683 Thus, the contribution to $r_{k_1 + k_2 + 1, \, 2 \cdot (l - 1 - k_1)}$ is
    684 
    685 $\displaystyle \binom{c_0 - 1}{l_1 - 1} \cdot \binom{c_2 - 1}{l_2 - 1} \cdot \binom{l - 1}{k_1} \cdot \binom{c_0 + c_2 - l}{k_2}$
    686 
    687 Enumerating all possible tuples $(l, k_1, k_2)$ suffices to compute all $r_{i,j}$. This computation takes $\mathcal{O}(n^3)$ time.
    688 
    689 By the same process, we can compute $b_{i,j}$ in $\mathcal{O}(n^3)$. Finally, convolving the results yields the number of distinct permutations for each oddness value. The entire algorithm runs in $\mathcal{O}(n^3)$ time.
    690 
    691 **Code (C++)**
    692 
    693 ```
    694 #include <iostream>
    695 #include <vector>
    696 using namespace std;
    697 
    698 constexpr int MAXN = 800;
    699 
    700 // Modified from https://github.com/ToxicPie/NaCl
    701 template <typename T> struct M {
    702   constexpr static T MOD = 1'000'000'007;
    703   T v;
    704   M(T x = 0) {
    705     v = (-MOD <= x && x < MOD) ? x : x % MOD;
    706     if (v < 0)
    707       v += MOD;
    708   }
    709   explicit operator T() const { return v; }
    710   bool operator==(const M &b) const { return v == b.v; }
    711   bool operator!=(const M &b) const { return v != b.v; }
    712   M operator-() { return M(-v); }
    713   M operator+(M b) { return M(v + b.v); }
    714   M operator-(M b) { return M(v - b.v); }
    715   M operator*(M b) { return M((long long)v * b.v % MOD); }
    716   M operator/(M b) { return *this * (b ^ (MOD - 2)); }
    717   friend M operator^(M a, int b) {
    718     M ans(1);
    719     for (; b; b >>= 1, a *= a)
    720       if (b & 1)
    721         ans *= a;
    722     return ans;
    723   }
    724   friend M &operator+=(M &a, M b) { return a = a + b; }
    725   friend M &operator-=(M &a, M b) { return a = a - b; }
    726   friend M &operator*=(M &a, M b) { return a = a * b; }
    727   friend M &operator/=(M &a, M b) { return a = a / b; }
    728 };
    729 using Mod = M<int>;
    730 
    731 int main() {
    732   ios::sync_with_stdio(false);
    733   cin.tie(0);
    734   vector<vector<Mod>> binom_(MAXN + 1, vector(MAXN + 1, Mod(0)));
    735   for (int i = 0; i <= MAXN; i++)
    736     for (int j = 0; j <= i; j++) {
    737       if (j == 0 || j == i)
    738         binom_[i][j] = 1;
    739       else
    740         binom_[i][j] = binom_[i - 1][j] + binom_[i - 1][j - 1];
    741     }
    742   auto binom = [&](int x, int y) {
    743     if (x >= y && y >= 0 && x >= 0)
    744       return binom_[x][y];
    745     else
    746       return Mod(0);
    747   };
    748 
    749   int t;
    750   cin >> t;
    751   while (t--) {
    752     vector<int> cnt(4);
    753     for (auto &i : cnt)
    754       cin >> i;
    755     int n = cnt[0] + cnt[1] + cnt[2] + cnt[3];
    756 
    757     vector<vector<Mod>> r(n + 1, vector(n + 1, Mod(0))),
    758         b(n + 1, vector(n + 1, Mod(0)));
    759 
    760     auto fill_table = [&](int x, int y, vector<vector<Mod>> &table) {
    761       for (int i = 2; i <= x + y; i++) {
    762         vector<pair<int, int>> segments;
    763         if (i & 1)
    764           segments = {{i / 2, i - i / 2}, {i - i / 2, i / 2}};
    765         else
    766           segments = {{i / 2, i / 2}, {i / 2, i / 2}};
    767         for (auto [l1, l2] : segments) {
    768           if (x < l1 || y < l2)
    769             continue;
    770           auto mul = binom(x - 1, l1 - 1) * binom(y - 1, l2 - 1);
    771           int different = i - 1, same = (x + y) - 1 - different;
    772           for (int j = 0; j <= different; j++)
    773             for (int k = 0; k <= same; k++) {
    774               auto mul2 = binom(different, j) * binom(same, k);
    775               int c = different - j;
    776               table[j + k + 1][c] += mul * mul2;
    777             }
    778         }
    779       }
    780     };
    781 
    782     fill_table(cnt[0], cnt[2], r);
    783     fill_table(cnt[1], cnt[3], b);
    784 
    785     vector<Mod> ans(2 * (n - 1) + 1);
    786     for (int i = 1; i <= (n + 1) / 2; i++)
    787       for (int j = 0; j <= n; j++)
    788         for (int k = 0; k <= n; k++) {
    789           int oddness = (j + k) * 2 + (i * 2 - 1);
    790           if (oddness >= 0 && oddness <= 2 * (n - 1))
    791             ans[oddness] += r[i][j] * b[i][k] * 2;
    792         }
    793     for (int i = 1; i <= (n + 1) / 2 && i + 1 <= n; i++)
    794       for (int j = 0; j <= n; j++)
    795         for (int k = 0; k <= n; k++) {
    796           int oddness = (j + k) * 2 + i * 2;
    797           if (oddness >= 0 && oddness <= 2 * (n - 1)) {
    798             ans[oddness] += r[i][j] * b[i + 1][k];
    799             ans[oddness] += r[i + 1][j] * b[i][k];
    800           }
    801         }
    802 
    803     for (int i = 0; i <= 2 * (n - 1); i++)
    804       cout << ans[i].v << " \n"[i == 2 * (n - 1)];
    805   }
    806 }
    807 ```
    808 
    809 **Rate the problem!**
    810 
    811 **Quality**
    812 
    813 * Excellent problem
    814 * Good problem
    815 * Average problem
    816 * Bad problem
    817 * Horrible problem
    818 
    819 **Difficulty**
    820 
    821 * Trivial problem
    822 * Easy problem
    823 * Average problem
    824 * Hard problem
    825 * Impossible problem