solved.ac Grand Arena #3

## Solution 1

Let's decide on the two fruits that will be used. After that, we look for the longest continuous subsequence of those two fruits. This can be done by using the `split` method (if your language supports it) or by maintaining a `cnt` variable and traversing the list from the front. If the current element is one of the chosen types of fruits, add $1$ to `cnt` . Otherwise, reset `cnt` to $0$. Find the maximum possible `cnt` value.

Supposing there are $d = 9$ types of fruits, there are $\frac{d(d-1)}{2} = 36$ ways to choose two of them, and each of the choices $O(N)$ time. Total time complexity is $O(d^2N)$.

### Code (C++20)

```cpp
#include <iostream>
#include <ranges>
#include <vector>
using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S)
        cin >> s;
    int ans = 0;
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j < i; j++)
        {
            auto v = S | views::transform([&](int x)
                                          { return x == i || x == j; });
            for (auto w : views::split(v, false))
                ans = max(ans, (int)distance(w.begin(), w.end()));
        }
    cout << ans << endl;
}
```

### Code (Python)

```python
import re


def main():
    input()
    s=''.join(input().split())
    ans = 0
    for i in range(1, 10):
        for j in range(1, i):
            ans = max(ans, max(map(len, re.split(f'[^{i}{j}]', s))))
    print(ans)


if __name__ == "__main__":
    main()
```

### Code (Rust)

```rust
use std::io::*;
use std::iter::FromIterator;

fn main() {
    stdin().read_line(&mut String::new()).unwrap();
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let s = String::from_iter(s.chars().filter(|&x| !x.is_ascii_whitespace()));
    let mut ans = 0;
    for i in '1'..='9' {
        for j in '1'..i {
            ans = ans.max(
                s.split(|x| x != i && x != j)
                    .map(|x| x.len())
                    .max()
                    .unwrap_or_default(),
            );
        }
    }
    println!("{}", ans);
}
```

## Solution 2

Let's denote using $R_l$, the rightmost point of the longest continuous sequence of two or less types of fruits starting from $S_l$. That is, there are always two or less types of fruits in $S_l, S_{l+1}, \cdots, S_{R_l}$. Removing $S_l$ from the sequence, there are still two or less types of fruits in $S_{l+1}, \cdots, S_{R_l}$ so $R_{l+1}$ is always larger than or equal to $R_l$. Therefore, $R_l$ increases with $l.

Supposing $R_{l-1}$ was calculated, and since we know $R_l$ to be larger than or equal to $R_{l-1}$, we can use a naive solution using a loop from $r = R_{l-1}$ increasing $r$ by $1$ each iteration looking for the maximum $r$ such that there are two or less types of fruits in $S_{l}, \cdots, S_r$. Since $r$ increases by $N$ in the loop, the number of iterations does not exceed $O(N)$.

Now we just need to find the types of fruits in $S_l, \cdots, S_r$ fast. This can be done by maintaining a `cnt` array of length $10$ in which we store the count of each type of fruit in the current range $S_l, \cdots, S_r$,  and if we also store the number of types of fruits with more than $1$ fruit, this can be solved in $O(1)$ time. Total complexity is $O(N)$.

Variable `r` is used to maintain $R_l + 1$ in the below code.

### Code (C++)

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;
    vector<int> S(N);
    for (int &s : S)
        cin >> s;
    int ans = 0, r = 0, non_zero = 0;
    vector<int> cnt(10);
    for (int l = 0; l < N; l++)
    {
        while (r < N)
        {
            int nxt_non_zero = non_zero + (cnt[S[r]] == 0 ? 1 : 0);
            if (nxt_non_zero <= 2)
            {
                cnt[S[r]]++;
                r++;
                non_zero = nxt_non_zero;
            }
            else
                break;
        }
        ans = max(ans, r - l);
        cnt[S[l]]--;
        if (cnt[S[l]] == 0)
            non_zero--;
    }
    cout << ans << endl;
}
```

### Code (Python)

```python
def main():
    N = int(input())
    S = map(int, input().split())

    ans = r = non_zero = 0
    cnt = [0]*10

    for l in range(N):
        while r < N:
            nxt_non_zero = non_zero + (1 if cnt[S[r]] == 0 else 0)
            if nxt_non_zero <= 2:
                cnt[S[r]] += 1
                r += 1
                non_zero = nxt_non_zero
            else:
                break
        ans = max(ans, r - l)
        cnt[S[l]] -= 1
        if cnt[S[l]] == 0:
            non_zero -= 1

    print(ans)


if __name__ == "__main__":
    main()
```

### Code (Rust)

```rust
use std::io::*;

fn main() {
    let n = read_vec()[0];
    let s = read_vec();

    let mut ans = 0;
    let mut r = 0;
    let mut non_zero = 0;
    let mut cnt = [0; 10];

    for l in 0..n {
        while r < n {
            let nxt_non_zero = non_zero + if cnt[s[r] as usize] == 0 { 1 } else { 0 };
            if nxt_non_zero <= 2 {
                cnt[s[r]] += 1;
                r += 1;
                non_zero = nxt_non_zero;
            } else {
                break;
            }
        }
        ans = ans.max(r - l);
        cnt[s[l]] -= 1;
        if cnt[s[l]] == 0 {
            non_zero -= 1;
        }
    }

    println!("{}", ans);
}

fn read_vec() -> Vec<usize> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
```



## Solution

Let's denote the cost of the MST of $G$ as $\mathrm{mst}(G)$.

For an arbitrary graph $G$, increasing the weight of one of its edges by $1$ increases $\mathrm{mst}(G)$ by a maximum of $1$. This is because where $G'$ is the graph with the increased weight, the cost of the tree corresponding to the MST of $G$ increases by a maximum of $1$, and $\mathrm{mst}(G')$ is smaller than or equal to this value.

Now let's consider the following procedure. We increase the weight of the $i$-th edge by $1$ starting from $l_i$ until it becomes $r_i$. We repeat this process in order starting from the $1$-st edge to the $M$-th edge.

Where $t$ is the weight we have increased in total, we will call this graph  $G_t$, and we will denote the sum of $r_i - l_i$ as $X$. Throughout the above procedure, $\mathrm{mst}(G_t)$ monotonically increases across all integers between $\mathrm{mst}(G_0)$ and $\mathrm{mst}(G_X)$ inclusive.

Therefore, if $\mathrm{mst}(G_0) \le K \le \mathrm{mst}(G_X)$, we can find the point where $\mathrm{mst}(G_t) = K$ is first satisfied by running a binary search on values of $t$. $G_t$ can be constructed in $O(M)$ time, and the cost of the MST can be calculated in $O(M\log M)$ time, resulting in a total time complexity of $O(M \log M \log X)$ which is sufficient to solve this problem.

### Code (C++)

```cpp
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

struct DisjointSet
{
    vector<int> par;

    DisjointSet(int N) : par(N)
    {
        iota(par.begin(), par.end(), 0);
    }

    int find(int x)
    {
        if (par[x] == x)
            return x;
        return par[x] = find(par[x]);
    }

    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return false;
        par[y] = x;
        return true;
    }
};

struct Edge
{
    int u, v;
    long long c;
    bool operator<(const Edge &E) const { return c < E.c; }
};

long long mst(int N, const vector<tuple<int, int, long long, long long>> &G, long long t)
{
    // construct G_t
    vector<Edge> E;
    for (auto [u, v, l, r] : G)
    {
        long long c = min(t, r - l);
        E.push_back({u, v, l + c});
        t -= c;
    }
    sort(E.begin(), E.end());

    // find MST
    DisjointSet dsu(N + 1);
    long long sum = 0;
    for (auto [x, y, c] : E)
        if (dsu.merge(x, y))
            sum += c;
    return sum;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    long long K;
    cin >> N >> M >> K;

    vector<tuple<int, int, long long, long long>> G(M);
    long long X = 0;
    for (auto &[u, v, l, r] : G)
    {
        cin >> u >> v >> l >> r;
        X += r - l;
    }

    // binary search
    long long s = -1, e = X;
    while (s + 1 < e)
    {
        long long m = (s + e) / 2;
        if (mst(N, G, m) >= K)
            e = m;
        else
            s = m;
    }

    // print answer
    if (mst(N, G, e) == K)
    {
        cout << "YES\n";
        for (auto &[u, v, l, r] : G)
        {
            int c = min(e, r - l);
            cout << min(l + c, r) << '\n';
            e -= c;
        }
    }
    else
    {
        cout << "NO\n";
    }

    return 0;
}
```

### Code (Python)

```python
import sys

def input():
    return sys.stdin.readline().rstrip()

class DisjointSet:
    def __init__(self, N):
        self.par = [i for i in range(N + 1)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def merge(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        self.par[y] = x
        return True

def mst(N, G, t):
    # construct G_t
    E = []
    for u, v, l, r in G:
        c = min(t, r - l)
        E.append((u, v, l + c))
        t -= c
    E.sort(key=lambda x: x[2])

    # find MST
    dsu = DisjointSet(N)
    sum = 0
    for x, y, c in E:
        if dsu.merge(x, y):
            sum += c
    return sum

def main():
    N, M, K = [int(x) for x in input().split()]
    G = []
    for i in range(M):
        u, v, l, r = [int(x) for x in input().split()]
        G.append((u, v, l, r))

    X = sum(r - l for u, v, l, r in G)

    # binary search
    s, e = -1, X
    while s + 1 < e:
        m = (s + e) // 2
        if mst(N, G, m) >= K:
            e = m
        else:
            s = m

    # print answer
    if mst(N, G, e) == K:
        print("YES")
        for u, v, l, r in G:
            c = min(e, r - l)
            print(min(l + c, r))
            e -= c
    else:
        print("NO")

if __name__ == "__main__":
    main()
```

### Code (Rust)

```rust
use std::{cell::*, fmt::Debug, io::*, str::*};

struct DisjointSet {
    par: Vec<usize>,
}

impl DisjointSet {
    fn new(n: usize) -> DisjointSet {
        DisjointSet {
            par: (0..n).collect(),
        }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.par[x] == x {
            x
        } else {
            let parent = self.find(self.par[x]);
            self.par[x] = parent;
            parent
        }
    }

    fn merge(&mut self, x: usize, y: usize) -> bool {
        let x = self.find(x);
        let y = self.find(y);
        if x == y {
            false
        } else {
            self.par[y] = x;
            true
        }
    }
}

struct Edge {
    u: usize,
    v: usize,
    c: i64,
}

fn mst(n: usize, g: &Vec<(usize, usize, i64, i64)>, mut t: i64) -> i64 {
    // construct G_t
    let mut e = Vec::new();
    for &(u, v, l, r) in g {
        let c = t.min(r - l);
        e.push(Edge { u, v, c: l + c });
        t -= c;
    }
    e.sort_by_key(|k| k.c);

    // find MST
    let mut dsu = DisjointSet::new(n + 1);
    let mut sum = 0;
    for edge in e {
        if dsu.merge(edge.u, edge.v) {
            sum += edge.c;
        }
    }
    sum
}

fn main() {
    let (n, m, k) = {
        let v = read_vec();
        (v[0], v[1], v[2] as i64)
    };

    let mut g = vec![(0, 0, 0, 0); m];
    for (u, v, l, r) in &mut g {
        let edge = read_vec();
        *u = edge[0];
        *v = edge[1];
        *l = edge[2] as i64;
        *r = edge[3] as i64;
    }
    let x = g.iter().map(|&(_u, _v, l, r)| r - l).sum();

    // binary search
    let mut s = -1;
    let mut e = x;
    while s + 1 < e {
        let m = (s + e) / 2;
        if mst(n, &g, m) >= k {
            e = m;
        } else {
            s = m;
        }
    }

    // print answer
    if mst(n, &g, e) == k {
        println!("YES");
        let mut e = e;
        for (_u, _v, l, r) in g {
            let c = e.min(r - l);
            println!("{}", r.min(l + c));
            e -= c;
        }
    } else {
        println!("NO");
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```



## Solution

Finding the size of a set can be thought of as counting the number of elements in it. Thus, the given equation can be changed as follows.
$$
a_{k} = \sum_{\substack{\tau \subseteq \{1, \cdots, N\}\\|\tau|=k}}\sum_{s \in \mathcal{S}} \left[s \in \bigcap_{i \in \tau} S_{i}\right]_{\mathbf{1}}
$$

Here, $\mathcal{S}$ is the set of all elements which can be in the set, that is, $\mathcal{S} = \bigcup_{i} S_{i}$, and $[a \in A]_{\mathbf{1}}$ is a mathematical expression which evaluates to $1$ if $a$ is in set $A$, and $0$ if it isn't.

Now let's change the order of the sums and think of the expression **for each $s$** . For any $s$, if the intersection of $k$ sets is to include $s$, all $k$ sets must include $s$. If $c_{s}$ is the number of times $s$ is included in $S_{i}$, we need to choose $k$ sets from the $c_{s}$ sets which have $s$ as an element for all the chosen sets to include $s$. There are exactly $\binom{c_{s}}{k}$ cases of this.

We can summarize the above as follows.

$$
\begin{aligned}a_{k} &= \sum_{\substack{\tau \subseteq \{1, \cdots, N\}\\|\tau|=k}}\sum_{s \in \mathcal{S}} \left[s \in \bigcap_{i \in \tau} S_{i}\right]_{\mathbf{1}} \\&= \sum_{s \in \mathcal{S}} \sum_{\substack{\tau \subseteq \{1, \cdots, N\}\\|\tau|=k}}\left[s \in \bigcap_{i \in \tau} S_{i}\right]_{\mathbf{1}}\\&= \sum_{s \in \mathcal{S}}\binom{c_{s}}{k}.\end{aligned}
$$

Now, let's define the polynomial with $c_k, a_k$ as its coefficients. That is, $C(x) := \sum_{k=1}^{N} c_{k} x^{k};$ $A(x) := \sum_{k=1}^{N} a_{k} x^{k} = \sum_{k=1}^{N} \sum_{i=0}^{N} \left(c_{i} \cdot \binom{i}{k}\right)x^{k}$. We can solve this problem by finding the coefficient of $A(x)$. Changing the order of the sums,

 $$
\begin{aligned}A(x) &= \sum_{i=1}^{N} \left(c_{i}\sum_{k=1}^{N} \binom{i}{k}x^{k}\right) \\&= \sum_{i=1}^{N} \left(c_{i}(x + 1)^{i} - c_i \right)\\&= \sum_{i=1}^{N} c_{i}(x + 1)^{i} - \sum_{i=1}^N c_i \\&= C(x+1) + (\textrm{const})\end{aligned}
$$

. Thus, we can solve this problem by calculating the coefficient of $C(x+1)$ after finding $C(x)$. $C(x)$ can be found by sorting and sweeping once. Now, we just need to calculate  $C(x+1)$ with the given $C(x)$. This is called a taylor shift. Generally, if we define $f(x) = \sum_{k=0}^N \frac{F_k}{k!} x^k$, $f(x+c)$ can be calculated as follows.

$$
\begin{aligned} f(x+c) &= \sum_{k=0}^{N} \frac{F_k}{k!} (x+c)^k \\ &= \sum_{k=0}^{N} \sum_{i=0}^{k} \frac{F_k}{k!} \binom ki c^{k-i} x^i \\ &= \sum_{k=0}^{N} \sum_{i=0}^k F_k \frac{c^{k-i}}{(k-i)!} \frac{x^i}{i!} \\ &= \sum_{i=0}^{N} \sum_{k=i}^{N} F_k \frac{c^{k-i}}{(k-i)!} \frac{x^i}{i!} \\ &= \sum_{i=0}^{N} G_i \frac{x^i}{i!}\end{aligned}
$$

 Here, $G_i = \sum_{k=i}^{N} F_k \frac{c^{k-i}}{(k-i)!}$. $G$ can be found using array $F$ and using FFT to calculate $\frac{c^{k-i}}{(k-i)!}$. Thus, $f(x+c)$ can be calculated in $O(N \log N)$ time.
### Code (pending)

```
```



## Solution

Instead of solving the problem on $B_i$ coins of $A_i$ won, we can change the problem to that of using $1$ coin of $2^j A_i$ won by deciding on a suitable $j$ for $2 \log_2 B_i$ coins. Let's denote the new coins made from this procedure as $A^{(j)}_i$.

The problem of finding whether $x$ won can be made for $0 \le x \le \sum A^{(0)}_i$ using coins of $A^{(0)}_i$ won can be solved in $O(N \sum A_i /w)$ time using knapsack and `bitset`. After this, coins greater than or equal to $A^{(\ge1)}_i$ are all even, so if the parity of $x$ and $X$ are different, these coins cannot be used to make $X$ won. So we leave only numbers of the form $2k + (X \bmod 2)$ based on the parity of $X$. We repeat a similar process after reducing the coin weight, $X$, and the DP table in half. Since the length of the DP table never exceeds $4 \sum A_i$ throughout this process, the time complexity is $O(N \sum A_i \log X / w)$.

## Implementation

It is not simple to implement this solution. Here are some tips for implementation for each language.

### C++

The problem with the built-in `std::bitset<n>`  of C++ is that the size is fixed. For this problem, we need to be able to adjust the size `n` of `std::bitset<n>` as there are multiple testcases. Since the size `n ` of `bitset` needs to be decided in compile time, we will use a bitset of size $2^k$. We will use a template of the following format. If `len` is greater than or equal to the size $L$ of the bitset we need, `std::bitset<len>` is used. If is smaller, `2*len` is called as the parameter of the same solve function. The code is given below. Since `len` and `MAX` can be decided in compile time, ` std::min(2*len, MAX)` can also be decided in compile time.
```cpp
const int MAX = ...;
template<int len = 1>
... solve(int desired_length, ...) {
    if(desired_length > len) {
        return solve<std::min(2*len, MAX)>(desired_length, ...);
    }
    std::bitset<len> ...
    ...
}
```


### Python

Python's big integer can be used like a `bitset`. However, it may be difficult to leave only the parity of the bits in the big integer. For this, the number is first converted to a binary string of `0` and `1` . Then, after taking just the characters in odd or even indices, we convert the string back to a big integer. We can convert big integer `v` to a binary string `s` and the other way round quickly by the following method.

- Big integer $\rightarrow$ binary string: `s = f'{v:0b}'`
- Binary string $\rightarrow$ big integer: `v = eval('0b' + s)`

### Rust

Rust는 has no built-in `bitset`, so we must implement our own `bitset`. We group boolean in groups of $64$, and if we need to apply or operations, we need to manage the quotient and remainder of dividing the shift size by 64. 


### Code (C++)

```cpp
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M, K;
    cin >> N >> M >> K;
    vector<int> R(N);
    for (int &r : R)
        cin >> r;
    vector<vector<pair<int, int>>> G(N);
    for (int i = 0; i < M; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v;
        G[u].emplace_back(v, c);
        G[v].emplace_back(u, c);
    }
    vector<int> vis(N), history;
    function<bool(int)> dfs = [&](int u)
    {
        ++vis[u];
        history.push_back(u);
        if (vis[u] == 1)
        {
            // only can jump to matching color
            for (auto [v, c] : G[u])
                if (R[u] == c)
                {
                    if (vis[v] != 2)
                    {
                        bool ret = dfs(v);
                        history.push_back(u);
                        return ret;
                    }
                    else
                    {
                        history.push_back(v);
                        return dfs(u);
                    }
                }
            return false;
        }
        else
        {
            // visit everywhere
            for (auto [v, c] : G[u])
                if (vis[v] != 2)
                {
                    if (!dfs(v))
                        return false;
                    history.push_back(u);
                }
            return true;
        }
    };

    bool res = dfs(0);
    if (!res || ranges::any_of(vis, [](int x)
                               { return x != 2; }))
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n";
        cout << history.size() << '\n';
        ranges::reverse(history);
        for (int h : history)
            cout << h + 1 << ' ';
        cout << '\n';
    }

    return 0;
}
```

### Code (Python)

```python
def main():
    T = int(input())
    for i in range(T):
        N, X = map(int, input().split())
        CV = [tuple(map(int, input().split())) for _ in range(N)]
        CV_split = []
        while True:
            s = []
            for i in range(N):
                C, V = CV[i]
                if C != 0:
                    cnt = 2 if C % 2 == 0 else 1
                    CV[i] = ((C-cnt)/2, V)
                    s.extend([V]*cnt)
            if not s:
                break
            CV_split.append(s)

        d = 1
        logs = []

        for Vs in CV_split:
            logs.append((X % 2, d))
            for V in Vs:
                d |= d << V
            bs = f'0{d:0b}'
            d = eval('0b' + bs[(X+len(bs)+1) % 2::2])
            X //= 2
        if not (d & (1 << X)):
            print('NO')
            continue
        ans = {}
        for i in range(len(logs)-1, -1, -1):
            rem, bs = logs[i]
            cv = CV_split[i]
            X = 2*X + rem
            tbl = []
            for C in cv:
                tbl.append(bs)
                bs |= bs << C
            for j in range(len(cv)-1, -1, -1):
                C = cv[j]
                if X >= C and bool(tbl[j] & (1 << (X-C))):
                    X -= C
                    ans[C] = ans.get(C, 0) + (1 << i)

        assert X == 0
        print("YES")
        print(' '.join(map(str, (ans.get(v, 0) for _,  v in CV))))


if __name__ == '__main__':
    main()
```

### Code (Rust)

```rust
use core::fmt;
use std::{collections::HashMap, io::*};

fn main() {
    let t = read_vec()[0];
    for _ in 0..t {
        let (n, mut x) = {
            let v = read_vec();
            (v[0], v[1])
        };
        let mut cv = Vec::new();
        for _ in 0..n {
            let v = read_vec();
            cv.push((v[0], v[1]));
        }
        let mut cvsplit = Vec::new();
        loop {
            let mut splits = Vec::new();
            for (c, v) in &mut cv {
                if *c != 0 {
                    let cnt = if *c % 2 == 0 { 2 } else { 1 };
                    *c = (*c - cnt) / 2;
                    for _ in 0..cnt {
                        splits.push(*v);
                    }
                }
            }
            if splits.is_empty() {
                break;
            }
            cvsplit.push(splits);
        }
        let mut d = BitSet::new();
        d.set(0, true);
        let mut logs = Vec::new();

        for cv in &cvsplit {
            logs.push((x % 2, d.clone()));
            for v in cv {
                d.lshiftor(*v);
            }
            let mut e = BitSet::new();
            for i in (x % 2..d.len()).step_by(2) {
                if d.get(i) {
                    e.set(i / 2, true);
                }
            }
            x /= 2;
            d = e;
        }
        if !d.get(x) {
            println!("NO");
            continue;
        }
        let mut ans = HashMap::new();
        for i in (0..logs.len()).rev() {
            let (rem, bs) = &logs[i];
            let cv = &cvsplit[i];
            x = 2 * x + rem;
            let mut tbl = Vec::new();
            let mut cbs = bs.clone();
            for v in cv {
                tbl.push(cbs.clone());
                cbs.lshiftor(*v);
            }
            for j in (0..cv.len()).rev() {
                let v = cv[j];
                if x >= v && tbl[j].get(x - v) {
                    x -= v;
                    ans.insert(v, ans.get(&v).unwrap_or(&0usize) + (1usize << i));
                }
            }
        }
        assert!(x == 0);
        println!("YES");
        for (_, v) in cv {
            print!("{} ", ans.get(&v).unwrap_or(&0usize));
        }
        println!();
    }
}

#[derive(Clone)]
struct BitSet(Vec<u64>);

impl BitSet {
    fn new() -> BitSet {
        BitSet { 0: Vec::new() }
    }
    pub fn get(&self, idx: usize) -> bool {
        let upper = idx >> 6;
        let lower = idx & 63;
        if upper < self.0.len() {
            (self.0[upper] & (1u64 << lower)) != 0
        } else {
            false
        }
    }
    pub fn set(&mut self, idx: usize, val: bool) {
        let upper = idx >> 6;
        let lower = idx & 63;
        if upper >= self.0.len() {
            self.0.resize(upper + 1, 0);
        }
        if val {
            self.0[upper] |= 1u64 << lower;
        } else {
            self.0[upper] &= !(1u64 << lower);
        }
    }
    fn trunc(&mut self) {
        while self.0.last() == Some(&0u64) {
            self.0.pop();
        }
    }
    fn len(&self) -> usize {
        if self.0.is_empty() {
            return 0;
        }
        1 + (((self.0.len() - 1) << 6) | (self.0.last().unwrap().ilog2() as usize))
    }
    pub fn lshiftor(&mut self, sft: usize) {
        if self.0.is_empty() {
            return;
        }
        let upper = sft >> 6;
        let lower = sft & 63;
        let p_sz = self.0.len();
        if lower == 0 {
            self.0.resize(p_sz + upper, 0u64);
            for i in (0..p_sz).rev() {
                self.0[upper + i] |= self.0[i];
            }
        } else {
            self.0.resize(p_sz + upper + 1, 0u64);
            for i in (0..p_sz).rev() {
                self.0[upper + i + 1] |= self.0[i] >> (64 - lower);
                self.0[upper + i] |= self.0[i] << lower;
            }
            self.trunc();
        }
    }
}
impl fmt::Debug for BitSet {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "BitSet{{ ")?;
        for i in 0..self.len() {
            if self.get(i) {
                write!(f, "{} ", i)?;
            }
        }
        write!(f, "}}")
    }
}

fn read_vec() -> Vec<usize> {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
```



## Solution

Let's think of the buildings visited in reverse order of visit. This changes the operation of visiting $u \rightarrow v$ then re-coloring $v$ in color $p$ to that of coloring $v$ in color $p$ when visiting $v \rightarrow u$. However, if $v$ is already colored, nothing is done.

Thus, the problem is about finding an order of visit such that all buildings are visited with the additional condition that an edge of color $r_v$ must be used when visiting the building for the first time. Any edge can be used second time onwards.

Using this, we run a DFS such that each building is visited twice.

- If building $v$ is visited for the first time, use an edge of color $r_v$ to move from one building to another.
- If building $v$ is visited for the second time, visit adjacent buildings which were not yet visited twice.

Finally, print the answer in reverse order.

If there is no adjacent edge of color $r_v$ or all the buildings are not connected, the answer is `NO`. Otherwise, the above algorithm works properly so the answer is always  `YES`. Since each building is visited a maximum of two times (ignoring the return call of the dfs function), the total number of visits is less than or equal to $4N$.

### Code (C++)

```cpp
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, M, K;
    cin >> N >> M >> K;
    vector<int> R(N);
    for (int &r : R)
        cin >> r;
    vector<vector<pair<int, int>>> G(N);
    for (int i = 0; i < M; i++)
    {
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v;
        G[u].emplace_back(v, c);
        G[v].emplace_back(u, c);
    }
    vector<int> vis(N), history;
    function<bool(int)> dfs = [&](int u)
    {
        ++vis[u];
        history.push_back(u);
        if (vis[u] == 1)
        {
            // only can jump to matching color
            for (auto [v, c] : G[u])
                if (R[u] == c)
                {
                    if (vis[v] != 2)
                    {
                        bool ret = dfs(v);
                        history.push_back(u);
                        return ret;
                    }
                    else
                    {
                        history.push_back(v);
                        return dfs(u);
                    }
                }
            return false;
        }
        else
        {
            // visit everywhere
            for (auto [v, c] : G[u])
                if (vis[v] != 2)
                {
                    if (!dfs(v))
                        return false;
                    history.push_back(u);
                }
            return true;
        }
    };

    bool res = dfs(0);
    if (!res || ranges::any_of(vis, [](int x)
                               { return x != 2; }))
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n";
        cout << history.size() << '\n';
        ranges::reverse(history);
        for (int h : history)
            cout << h + 1 << ' ';
        cout << '\n';
    }

    return 0;
}
```

### Code (Python)

```python
import sys
sys.setrecursionlimit(1_000_000)


def input(): return sys.stdin.readline().rstrip()


def main():

    n, m, _ = map(int, input().split())
    g = [[] for _ in range(n)]
    r = list(map(int, input().split()))
    for _ in range(m):
        u, v, c = map(int, input().split())
        u -= 1
        v -= 1
        g[u].append((v, c))
        g[v].append((u, c))

    vis = [0] * n
    history = []

    def dfs(u):
        vis[u] += 1
        history.append(u)
        if vis[u] == 1:
            # only can jump to matching color
            for v, c in g[u]:
                if r[u] == c:
                    if vis[v] != 2:
                        ret = dfs(v)
                        history.append(u)
                        return ret
                    else:
                        # visit v, and return u.
                        history.append(v)
                        return dfs(u)
            return False
        else:
            # visit everywhere
            for v, _ in g[u]:
                if vis[v] != 2:
                    if not dfs(v):
                        return False
                    history.append(u)
            return True

    res = dfs(0)
    if not res or any(x != 2 for x in vis):
        print('NO')
    else:
        print('YES')
        print(len(history))
        print(' '.join(map(lambda x: str(x+1), history[::-1])))


if __name__ == '__main__':
    main()
```

### Code (Rust)

```rust
use std::{cell::*, fmt::Debug, io::*, str::*};

fn main() {
    let (n, m, _) = {
        let v = read_vec();
        (v[0], v[1], v[2])
    };
    let mut g = vec![Vec::new(); n];
    let r = read_vec();
    for _ in 0..m {
        let (u, v, c) = {
            let v = read_vec::<usize>();
            (v[0] - 1, v[1] - 1, v[2])
        };
        g[u].push((v, c));
        g[v].push((u, c));
    }

    struct Dfs<'a> {
        g: &'a Vec<Vec<(usize, usize)>>,
        r: &'a Vec<usize>,
        vis: Vec<usize>,
        history: Vec<usize>,
    }
    impl Dfs<'_> {
        fn dfs(&mut self, u: usize) -> bool {
            self.vis[u] += 1;
            self.history.push(u);
            match self.vis[u] {
                1 => {
                    // only can jump to matching color
                    for &(v, c) in &self.g[u] {
                        if self.r[u] == c {
                            if self.vis[v] != 2 {
                                let ret = self.dfs(v);
                                self.history.push(u);
                                return ret;
                            } else {
                                // visit v, and return u.
                                self.history.push(v);
                                return self.dfs(u);
                            }
                        }
                    }
                    false
                }
                2 => {
                    // visit everywhere
                    for &(v, _) in &self.g[u] {
                        if self.vis[v] != 2 {
                            if !self.dfs(v) {
                                return false;
                            }
                            self.history.push(u);
                        }
                    }
                    true
                }
                _ => panic!(),
            }
        }
    }

    let mut dfs = Dfs {
        g: &g,
        r: &r,
        vis: vec![0; n],
        history: Vec::new(),
    };
    let res = dfs.dfs(0);
    if !res || dfs.vis.iter().any(|&x| x != 2) {
        println!("NO");
    } else {
        println!("YES");
        println!("{}", dfs.history.len());
        for i in dfs.history.into_iter().rev() {
            print!("{} ", i + 1);
        }
        println!();
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
#[macro_export]
macro_rules! print {
    ($($t:tt)*) => {
        STDOUT.with(|cell| write!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```



## Solution

First let's consider the TSP Circuit instead of trail. That is, let's find the length of the shortest Circuit which visits all $v_1, v_2, \cdots, v_K$ then returns to the starting point irrespective or order of visit.

- If there is at least $1$ of $v_1, \cdots, v_K$ on both subtrees at the ends of edge $e$, that edge must be included at least twice in the TSP Circuit.
  - Supposing that $v_i$ and $v_j$ were at the ends of $e$의, you pass $e$ once while going through $v_i \rightarrow v_j$ and once while going through $v_j \rightarrow v_i$.
- There exists a TSP Circuit which passes only the edges which suit the above condition exactly twice.
  - Using $e$, we can use dfs to visit all the nodes starting from $v_1$.

Thus, the length of the TSP Circuit is the number of edges such that both subtrees at the ends of the edge $e$ contain at least $1$ of $v_1, \cdots, v_K$.

If the edge connecting $i$ and $\left\lfloor \frac i 2 \right \rfloor$ suits this condition, there needs to be at least $1$ and less than $K$ nodes from $v_1, \cdots, v_K$ in the subtree of $i$ with $1$ as its root. To determine this, we find the collection of numbers of the form $\left\lfloor \frac{i}{2^k} \right\rfloor$ which are ancestors of $i$, and look for the value which appears at least $1$ and less than $K$ times in the list. Using data structures such as a `HashMap` , this problem can be solved in $O(N \log \max v_i)$ time.

Now, let's think about the length of the TSP trail. In the TSP trail, we can ignore one whole path from one node to another in the above process dfs. Since we want this to be as long as possible, it is best to set it as the diameter of the tree. The diameter of the tree can be found by calling the distance function $2N-3$ times. Start from any node $v$, and find the furthest node $u$, and then find the furthest node $w$ from $u$. $u$ and $w$ form the diameter. The distance function can be implemented to run in $O(\log v_i)$ time, so the diameter can also be found in $O(N\log \max v_i)$ time. The length of the TSP trail is the length of the TSP Circuit we found minus the diameter of the tree.


### Code (C++20)

```cpp
#include <algorithm>
#include <cinttypes>
#include <iostream>
#include <vector>
using namespace std;

int dist(uint64_t u, uint64_t v)
{
    int d = 0;
    while (u != v)
    {
        d += 1;
        if (u < v)
            swap(u, v);
        u /= 2;
    }
    return d;
}

int solve(const vector<uint64_t> &V)
{
    uint64_t anchor = ranges::max(V, [&](uint64_t a, uint64_t b)
                                  { return dist(a, V[0]) < dist(b, V[0]); });
    uint64_t anchor2 = ranges::max(V, [&](uint64_t a, uint64_t b)
                                   { return dist(a, anchor) < dist(b, anchor); });
    int d = dist(anchor, anchor2);

    unordered_map<uint64_t, int> hm;
    for (uint64_t i : V)
        while (i != 1)
        {
            hm[i] = hm[i] + 1;
            i /= 2;
        }
    int e = 0;
    for (const auto &[key, value] : hm)
        if (value != (int)V.size())
            ++e;
    return 2 * e - d;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int N;
        cin >> N;
        vector<uint64_t> V(N);
        for (uint64_t &x : V)
            cin >> x;
        cout << solve(V) << '\n';
    }

    return 0;
}
```

### Code (Python)

```python
import sys


def input(): return sys.stdin.readline().rstrip()


def dist(u, v):
    d = 0
    while u != v:
        d += 1
        if u < v:
            u, v = v, u
        u //= 2
    return d


def solve(v):
    hm = {}
    for i in v:
        while i != 1:
            hm[i] = hm.get(i, 0) + 1
            i //= 2

    e = sum(1 for x in hm.values() if x != len(v))
    anchor = max(v, key=lambda x: dist(x, v[0]))
    d = max(dist(x, anchor) for x in v)

    return 2 * e - d


def main():
    t = int(input())
    for _ in range(t):
        input()
        print(solve(list(map(int, input().split()))))


if __name__ == "__main__":
    main()
```

### Code (Rust)

```rust
use std::{cell::*, collections::HashMap, fmt::Debug, io::*, mem::*, str::*};

fn dist(mut u: u64, mut v: u64) -> usize {
    let mut d = 0;
    while u != v {
        d += 1;
        if u < v {
            swap(&mut u, &mut v);
        }
        u /= 2;
    }
    d
}

fn solve(v: Vec<u64>) -> usize {
    let mut hm = HashMap::new();
    for mut i in v.iter().cloned() {
        while i != 1 {
            hm.insert(i, *hm.get(&i).unwrap_or(&0usize) + 1);
            i /= 2;
        }
    }
    let e = hm.values().filter(|&&x| x != v.len()).count();
    let anchor = *v.iter().max_by_key(|&&x| dist(x, v[0])).unwrap();
    let d = v.iter().map(|&x| dist(x, anchor)).max().unwrap();
    2 * e - d
}

fn main() {
    let t = *read_vec().first().unwrap();
    for _ in 0..t {
        read_vec::<u64>();
        println!("{}", solve(read_vec()));
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```



## Solution

To differentiate the $N$ people based on the number of emeralds they returned over $X$ days, there needs to be a day for an arbitrary pair of people in which the two returned different number of emeralds. That is, the pair of $(a_{1i}, a_{2i}, \cdots, a_{Xi})$ and $(a_{1j}, a_{2j}, \cdots, a_{Xj})$ must be different. However, $a_{1i} + a_{2i} + \cdots + a_{Xi} \leq K$, so we need to find the minimum $N$ such that the number of sequences whose sum is $K$ and length is $X$ does not exceed $N$.

This can be done as follows. Suppose we had the children line up $K$ emeralds in a row and place $X$ curtains between them. Then, we will ask them to return emeralds up to the next curtain each day. We do not consider emeralds placed after the last curtain. The number of ways to place the curtains is equal to the number of ways to line up the $X$ curtains and the $K$ emeralds which is equal to $$\frac{(K+X)!}{K!X!} = \binom{K+X}{K}$$. Thus, the value we want to find is the smallest $X$ such that $\binom{K+X}{K} \geq N$.

Since $\binom{K+X}{K}$ increases with $X$, we can probably perform a binary search. However, this is not yet sufficient to find $X$ fast enough for the problem. Let's try some optimizations.
- When $K = 1$, we are looking for the smallest $X$ such that $\binom{1+X}{1} = X + 1 \geq N$, so the answer is $X = N - 1$.
- When $K = 2$, we are looking for the smallest $X$ such that $\binom{2+X}{2} = \frac{(X+1)(X+2)}{2} \geq N$, we can solve the quadratic inequality to find $X$.
- If $K \geq 35$ and $X \geq 35$, $\binom{K+X}{K} \geq \binom{70}{35} \approx 112.19 \times 10^{18} \geq N$, so $X \leq 35$. Therefore, for at least one $\binom{K + X}{K} = \binom{K + X}{X}$ the bottom value is less than or equal to $35$, so we can precompute all binomial coefficients whose bottom value is less than or equal to $35$. If $K \geq 3$, we only need to precompute up to around $X \leq 2 \times 10^{6}$.
- If the time for this precomputation is still very tight within the constraints, the case for $K = 3$ can be solved by solving a cubic inequality. This way, we only need to precompute up to around $X \leq 10^{5}$.

The time complexity is $\mathcal{O}(N^{1/3} \log N)$ or $\mathcal{O}(N^{1/4} \log N)$ for precomputation, and $\mathcal{O}(\log N)$ for each query.
### Code (C++)

```cpp
#include <algorithm>
#include <cinttypes>
#include <cmath>
#include <iostream>
using namespace std;

const int64_t INF = 3e18;
const int MAX_K = 35, MAX_M_E = 1900000;
int64_t E_precalc[MAX_K + 1][MAX_M_E + 1];

int64_t E(int64_t k, int64_t m)
{
    if (k > m)
        swap(k, m);
    if (k == 0)
        return 1;
    if (k == 1)
        return min(m + 1, INF);
    if (k == 2)
        return m - 3 <= sqrtl(2.2 * INF) ? min((m + 2) * (m + 1) / 2, INF) : INF;
    if (k > MAX_K || m > MAX_M_E)
        return INF;
    return E_precalc[k][m];
}
void init()
{
    for (int i = 3; i <= MAX_K; ++i)
        for (int j = 0; j <= MAX_M_E; ++j)
        {
            E_precalc[i][j] = j <= 2 ? E(i, j) : E(i - 1, j) + E(i, j - 1);
            if (E_precalc[i][j] > INF)
                E_precalc[i][j] = INF;
        }
}

int64_t D(int64_t k, int64_t n)
{
    if (n == 1)
        return 0LL;
    if (k >= n - 1)
        return 1LL;
    if (k == 1)
        return n - 1;

    int64_t s = 0, e = k == 2 ? 2e9 : MAX_M_E;
    while (s < e)
    {
        int64_t m = (s + e) >> 1;
        if (E(k, m) >= n)
            e = m;
        else
            s = m + 1;
    }
    return e;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    int T;
    cin >> T;
    for (int t = 1; t <= T; ++t)
    {
        int64_t n, k;
        cin >> n >> k;
        cout << D(k, n) << '\n';
    }
    return 0;
}
```

### Code (Python)

```python
import sys


def input(): return sys.stdin.readline().rstrip()


INF = int(3e18)
MAX_K = 35
MAX_M_E = 1900000


class C:
    def __init__(self):
        self.e_precalc = [[0] * (MAX_M_E + 1) for _ in range(MAX_K + 1)]
        for i in range(3, MAX_K + 1):
            for j in range(MAX_M_E + 1):
                if j <= 2:
                    self.e_precalc[i][j] = self.e(i, j)
                else:
                    self.e_precalc[i][j] = min(
                        self.e(i-1, j) + self.e(i, j-1), INF)

    def e(self, k, m):
        k, m = min(k, m), max(k, m)
        if k == 0:
            return 1
        if k == 1:
            return min(m + 1, INF)
        if k == 2:
            return min((m + 2) * (m + 1) // 2, INF) if m - 3 <= (2.2 * INF) ** 0.5 else INF
        if k > MAX_K or m > MAX_M_E:
            return INF
        return self.e_precalc[k][m]

    def d(self, k, n):
        if n == 1:
            return 0
        if k >= n - 1:
            return 1
        if k == 1:
            return n - 1

        s, e = 0, 2 * 10**9 if k == 2 else MAX_M_E
        while s < e:
            m = (s + e) // 2
            if self.e(k, m) >= n:
                e = m
            else:
                s = m + 1
        return e


def main():
    c = C()
    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        print(c.d(k, n))


if __name__ == '__main__':
    main()
```

### Code (Rust)

```rust
use std::{cell::*, cmp::*, fmt::Debug, io::*, str::*};

const INF: usize = 3e18 as usize;
const MAX_K: usize = 35;
const MAX_M_E: usize = 1900000;
struct C {
    e_precalc: Vec<Vec<usize>>,
}

impl C {
    fn new() -> Self {
        let mut sol = C {
            e_precalc: vec![vec![0; MAX_M_E + 1]; MAX_K + 1],
        };
        for i in 3..=MAX_K {
            for j in 0..=MAX_M_E {
                sol.e_precalc[i][j] = if j <= 2 {
                    sol.e(i, j)
                } else {
                    min(sol.e(i - 1, j) + sol.e(i, j - 1), INF)
                };
            }
        }
        sol
    }

    fn e(&self, mut k: usize, mut m: usize) -> usize {
        if k > m {
            std::mem::swap(&mut k, &mut m);
        }
        match k {
            0 => 1,
            1 => min(m + 1, INF),
            2 => {
                if m <= 3 + (2.2 * INF as f64).sqrt() as usize {
                    min((m + 2) * (m + 1) / 2, INF)
                } else {
                    INF
                }
            }
            _ => {
                if k > MAX_K || m > MAX_M_E {
                    INF
                } else {
                    self.e_precalc[k][m]
                }
            }
        }
    }

    fn d(&self, k: usize, n: usize) -> usize {
        if n == 1 {
            return 0;
        }
        if k + 1 >= n {
            return 1;
        }
        if k == 1 {
            return n - 1;
        }

        let mut s = 0;
        let mut e = if k == 2 { 2e9 as usize } else { MAX_M_E };
        while s < e {
            let m = (s + e) >> 1;
            if self.e(k, m) >= n {
                e = m;
            } else {
                s = m + 1;
            }
        }
        e
    }
}

fn main() {
    let t = read_vec()[0];
    let c = C::new();
    for _ in 0..t {
        let nk = read_vec();
        println!("{}", c.d(nk[1], nk[0]));
    }
}

thread_local! {
    static STDIN: RefCell<StdinLock<'static>> = RefCell::new(stdin().lock());
    static STDOUT: RefCell<BufWriter<StdoutLock<'static>>> = RefCell::new(BufWriter::new(stdout().lock()));
}
fn read_vec<T: FromStr>() -> Vec<T>
where
    <T as FromStr>::Err: Debug,
{
    let mut s = String::new();
    STDIN.with(|cell| {
        cell.borrow_mut().read_line(&mut s).unwrap();
    });
    s.split_whitespace().map(|x| x.parse().unwrap()).collect()
}
#[macro_export]
macro_rules! println {
    ($($t:tt)*) => {
        STDOUT.with(|cell| writeln!(cell.borrow_mut(), $($t)*).unwrap());
    };
}
```

