solved.ac Grand Arena #2

## Solution 1

Implement as given in the problem using a loop. The time complexity is $\mathcal O(N)$.

### Code (C++)

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

int main()
{
    int N;
    cin >> N;
    int sum_1 = 0, sum_3 = 0;
    for (int i = 1; i <= N; i++)
    {
        sum_1 += i;
        sum_3 += i * i * i;
    }
    cout << sum_1 << endl;
    cout << sum_1 * sum_1 << endl;
    cout << sum_3 << endl;
}
```

### Code (Python)

```python
def main():
    N = int(input())
    print(sum(range(1, N+1)))
    print(sum(range(1, N+1))**2)
    print(sum(i**3 for i in range(1, N+1)))


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

## Solution 2

$1+2+\cdots+N = \frac{N(N+1)}{2}$ and $1^3 + 2^3 + \cdots + N^3 = (1+2+\cdots+N)^2 = {\left(\frac{N(N+1)}{2}\right)}^2$ holds. The time complexity is $\mathcal O (1)$.

### Code (C++)

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

int main()
{
    int N;
    cin >> N;
    cout << N * (N + 1) / 2 << endl;
    cout << (N * (N + 1) / 2) * (N * (N + 1) / 2) << endl;
    cout << (N * (N + 1) / 2) * (N * (N + 1) / 2) << endl;
}
```

### Code (Python)

```python
def main():
    N = int(input())
    print(N * (N + 1) // 2)
    print((N * (N + 1) // 2) ** 2)
    print((N * (N + 1) // 2) ** 2)


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

### 증명

To prove $1+2+\cdots+N = \frac{N(N+1)}{2}$, let's calculate $2 \times (1 + 2+ \cdots + N)$.

When adding two sequences of $(1+2+\cdots+N)$, keep one sequence as it is, and reverse the other before adding. Then, upon inspecting each sum, combining $1$ with $N$ yields $N+1$, combining $2$ with $N−1$ yields $N+1$, and so on, until combining $N$ with $1$ also gives $N+1$. Hence, the total is equivalent to adding $N+1$ a total of $N$ times, which is $N(N+1)$.

Mathematically:
$$
\begin{align*}
 & \ 2 \times (1 + 2 + \cdots + N) \\
 = & \ (1 + 2 + \cdots + N) + (N + (N-1) + \cdots + 1) \\
 = & \ ((1+N) + (2+(N-1)) + \cdots + (N+1)) \\ 
 = & \ ((N+1) + (N+1) + \cdots+ (N+1)) \\
 = & \ N(N+1)
\end{align*}
$$

![Visual proof for $1+2+\cdots+N = \frac{N(N+1)}{2}$](https://static.solved.ac/arena/editorial/2/img1.png)

Let's now prove the slightly more challenging relationship $(1+2+\cdots+N)^2 = 1^3+2^3+\cdots+N^3$. We will demonstrate that both expressions have the same value for $N=1$, and the difference between the values of the expressions for $N=i-1$ and $N=i$ are the same. This will prove the two expressions are equivalent. For $N = 1$, both expressions equal 1. Let's now look at the difference between the two expressions:

Utilizing the identity $a^2 - b^2 = (a-b)(a+b)$:

$$
\begin{align*}
  & \ (1+2+\cdots+i)^2 - (1+2+\cdots+(i-1)^2)  \\
= & \ \left(\frac{i(i+1)}{2}\right)^2 - \left(\frac{i(i-1)}{2}\right)^2 \\
= & \ \left(\frac{i(i+1)}{2} - \frac{i(i-1)}{2}\right) \times \left(\frac{i(i+1)}{2} + \frac{i(i-1)}{2}\right) \\
= & \ \left(\frac{i((i+1)-(i-1))}{2}\right) \times \left(\frac{i((i+1)+(i-1))}{2}\right) \\
= & \ \left(\frac{i \times 2}{2} \right) \times \left(\frac{i \times 2i}{2} \right) \\ 
= & \ i \times i^2 = i^3
\end{align*}
$$

The difference between $1^3 + 2^3 + \cdots + (i-1)^3$ and $1^3 + 2^3 + \cdots + i^3$ is also $i^3$, so the two expressions must indeed be equivalent.

There's also a [visual method to prove this](https://math.stackexchange.com/questions/372081/intuitive-visual-proof-that-12-cdotsn2-1323-cdotsn3).

![Visual proof for $(1+2+\cdots+N)^2 = 1^3+2^3+\cdots+N^3$](https://static.solved.ac/arena/editorial/2/img2.png)



## Solution

An important observation in this problem is that, among the three lines given as input, at least one of them will be the number $i$ itself.

The string `Fizz` is printed every $3$ lines, so when looking at three consecutive lines, `Fizz` is printed at most once. Similarly, because the string `Buzz` is printed every $5$ lines, `Buzz` is also printed at most once when looking at three consecutive lines. Since `Fizz` and `Buzz` together can be printed up to a maximum of $2$ times, at least one of three lines will be the number $i$ itself.

Now, using the given $i$, we can find the number that follows the three lines and print either `Fizz`, `Buzz`, `FizzBuzz`, or $i$ following the rules.


### Code (C++)

```cpp
#include <iostream>
#include <string>
using namespace std;

string fizzbuzz(int N)
{
    if (N % 15 == 0)
        return "FizzBuzz";
    if (N % 3 == 0)
        return "Fizz";
    if (N % 5 == 0)
        return "Buzz";
    return to_string(N);
}

int main()
{
    for (int i = 0; i < 3; i++)
    {
        string s;
        cin >> s;
        if (isdigit(s[0]))
        {
            cout << fizzbuzz(stoi(s) + 3 - i) << endl;
            return 0;
        }
    }
}
```

### Code (Python)

```python
def fizzbuzz(N):
    if N % 15 == 0:
        return "FizzBuzz"
    if N % 3 == 0:
        return "Fizz"
    if N % 5 == 0:
        return "Buzz"
    return str(N)


def main():
    for i in range(3):
        s = input()
        if s[0].isdigit():
            print(fizzbuzz(int(s) + 3 - i))
            return


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

## Solution

Let's say the minimum value of the array after the operation is $v$. If the minimum value is fixed, minimizing the maximum value will minimize the answer. To minimize the maximum value, for $A_i$ which is less than $v$, we should double $A_i$ until $A_i$ is at least $v$.

Now, let's think about possible values for $v$.

- $v$ should only be among the values $A_i, 2A_i, 4A_i, \cdots$. No other values can become the minimum value through the operation.
- $v$ should only be less than or equal to $\max(A_1, \cdots, A_N)$.
  - If $v > \max(A_1, \cdots, A_N)$, we would have to perform the operation on every number at least once. If the minimum value is $\frac v 2$, then the difference between the maximum and minimum values becomes half.

Now, we can find all possible values of $v$ using a priority queue in $\mathcal O (N \log N \log A)$ time, or using a sorted array in $\mathcal O(N (\log N + \log A))$ time.

## Implementation 1

candSearch for possible $v$ values starting from the smallest. Given the numbers $A_1, \cdots, A_N$, to find the next possible value of $v$ after $v = \min(A_1, \cdots, A_N)$, we need to double the smallest value to increase $v$. So, we can follow this process:

1. Consider the difference between the maximum and minimum values of $A_1, \cdots, A_N$ as an answer candidate.
2. Find the minimum value among $A_1, \cdots, A_N$ and double it.
3. Repeat steps 1-2 until the minimum value is less than or equal to the maximum value in the input.

Now, by using a priority queue to find the minimum value and managing the minimum and maximum values, we can output the smallest answer candidate.

### Code (C++)

```cpp
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
    int N;
    cin >> N;

    priority_queue<int, vector<int>, greater<int>> Q;
    int mx = 0;
    for (int i = 0; i < N; i++)
    {
        int v;
        cin >> v;
        mx = max(mx, v);
        Q.push(v);
    }
    int curmx = mx, ans = curmx - Q.top();
    while (Q.top() < mx)
    {
        int v = Q.top();
        Q.pop();
        ans = min(ans, curmx - v);
        curmx = max(curmx, 2 * v);
        Q.push(2 * v);
    }
    cout << min(curmx - Q.top(), ans) << endl;
}
```

### Code (Python)

```python
import heapq
import sys


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


def main():
    N = int(input())
    Q = []
    mx = 0

    for v in map(int, input().split()):
        mx = max(mx, v)
        heapq.heappush(Q, v)
    curmx = mx
    ans = curmx - Q[0]
    while Q[0] < mx:
        v = heapq.heappop(Q)
        ans = min(ans, curmx - v)
        curmx = max(curmx, 2 * v)
        heapq.heappush(Q, 2 * v)
    print(min(curmx-Q[0], ans))


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

## Implementation 2

Let's make an additional observation:

- Since $v$ can only be a value less than or equal to $\max(A_1, \cdots, A_N)$, there's no need to operate on the maximum value among $A_1, \cdots, A_N$.
- If $2A_i \le \max(A_1, \cdots, A_N)$, then even if we perform an operation on $A_i$, the maximum value won't be updated, so performing the operation is beneficial.

Thus, for the given input $A_i$, we can double $A_i$ while $2A_i \le \max(A_1, \cdots, A_N)$ and still get the same answer. Now, let's think about the sorted values $A_1 \le A_2 \le \cdots \le A_N$. In this case, as $2A_i > A_N$, we only need to consider the case where the minimum value is $A_i$.

- If the minimum value is $A_1$, the maximum value is $A_N$, making the answer candidate $A_N - A_1$.
- If the minimum value is $A_i$ $(i \ge 2)$, then because we double $A_1, \cdots, A_{i-1}$, the maximum value becomes $2A_{i-1}$. The answer candidate becomes $2A_{i-1} - A_i$.

Finally, we just need to output the smallest among the answer candidates.

### Code (C++)

```cpp
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int &a : A)
        cin >> a;
    int mx = ranges::max(A);
    for (int &a : A)
        while (2 * a <= mx)
            a *= 2;
    ranges::sort(A);
    int ans = A.back() - A.front();
    for (int i = 1; i < N; i++)
        ans = min(ans, 2 * A[i - 1] - A[i]);
    cout << ans << '\n';
}
```

### Code (Python)

```python
import sys


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    mx = max(A)
    for i in range(N):
        while 2 * A[i] <= mx:
            A[i] *= 2
    A.sort()
    ans = A[N-1] - A[0]
    for i in range(1, N):
        ans = min(ans, 2 * A[i - 1] - A[i])
    print(ans)


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

## Solution

The key observation is that when you multiply by a number greater than $1$, the product increases exponentially. The maximum possible sum is $A_1 + \cdots+ A_N$. Since the product increases to at least $2^k$ when multiplied by a number greater than $1$ for $k$ times, we only need to check the cases where we multiply up to $\log_2 (A_1 + \cdots + A_N)$ numbers greater than $1$.

Let the numbers from $A_1, \cdots, A_N$ that are not $1$ be $A_{i_1}, A_{i_2}, \cdots, A_{i_K}$. Now, suppose the numbers greater than $1$ included in the interval are $A_{i_L}, \cdots, A_{i_R}$. We aim to count the number of pairs $(l, r)$ which include these numbers, i.e., $l \in (i_{L-1}, i_L]$ and $r \in [i_R, i_{R+1})$. This can be summarized as:

- The number of 1s that need to be compensated in $A_{[l, i_L)}$ and $A_{(i_R , r]}$ is $Z = (A_{i_L} \times \cdots \times A_{i_R}) - (A_{i_L} + \cdots + A_{i_R})$.
- Now, if we let $X = l - i_L$ and $Y = i_R - r$, the problem becomes counting the number of pairs $(X, Y)$ that satisfy:
  - $0 \le X \le i_L - {i_{L-1}}-1 = U$
  - $0\le Y \le i_{R+1} - i_R - 1 = V$
  - $X+Y = Z$
- When $0 \le Z \le U+V$, the number of $(X, Y)$ pairs can be found to be $\min(Z, U+V-Z, U, V) + 1$.

By counting only the products $A_{i_L} \times \cdots \times A_{i_R}$ that do not exceed $A_1 + \cdots + A_N$, and considering only $L, R$ where $R-L < \log_2 (A_1 + \cdots + A_N)$, we can solve the problem in a total of $\mathcal O(N\log (A_1 + \cdots + A_N))$ time. Don't forget also to count the integer pairs where $l=r$.

### Code (C++)

```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    int64_t tot_sum = 0;
    vector<int> A(N + 2, -1);
    for (int i = 1; i <= N; i++)
        cin >> A[i], tot_sum += A[i];

    vector<int> I;
    for (int i = 0; i <= N + 1; i++)
        if (A[i] != 1)
            I.push_back(i);

    int64_t ans = N;
    int K = I.size() - 2;
    for (int L = 1; L <= K; L++)
    {
        int64_t mul = 1, sum = 0;
        for (int R = L; R <= K; R++)
        {
            mul *= A[I[R]];
            sum += A[I[R]] - 1;
            if (mul > tot_sum)
                break;
            if (L != R)
            {
                int64_t U = I[L] - I[L - 1] - 1;
                int64_t V = I[R + 1] - I[R] - 1;
                int64_t Z = mul - (sum + I[R] - I[L] + 1);
                if (0 <= Z && Z <= U + V)
                    ans += min({Z, U + V - Z, U, V}) + 1;
            }
        }
    }
    cout << ans << endl;
}
```

### Code (Python)

```python
import sys


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    tot_sum = sum(A)
    A = [-1] + A + [-1]

    for i in range(1, N+1):
        A[i] = int(input())
        tot_sum += A[i]

    I = [i for i in range(N + 2) if A[i] != 1]

    ans = N
    K = len(I) - 2
    for L in range(1, K+1):
        mul, sum_ = 1, 0
        for R in range(L, K+1):
            mul *= A[I[R]]
            sum_ += A[I[R]] - 1
            if mul > tot_sum:
                break
            if L != R:
                U = I[L] - I[L-1] - 1
                V = I[R+1] - I[R] - 1
                Z = mul - (sum_ + I[R] - I[L] + 1)
                if 0 <= Z <= U + V:
                    ans += min(Z, U + V - Z, U, V) + 1
    print(ans)


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


## Solution

Pairs $(i, j)$ can occur in the following 3 situations:

1. Pairs $(i, j)$ that arise when inserting a single $B_1, \cdots, B_N$.
2. Pairs $(i, j)$ that arise when inserting multiple $B_1, \cdots, B_N$, from different insertions.
3. Pairs $(i, j)$ that occur from different arrays $B_1, \cdots, B_N$.

Each pair $(i, j)$ can be counted as follows:

1. Count the number of inversions in $B_1, \cdots, B_N$. Since this array is inserted $K$ times, multiply this count by $K$.
2. Count the number of pairs $(x, y)$ in $B_1, \cdots, B_N$ where $B_x \ne B_y$. Pairs $(B_x, B_y)$ corresponding to different insertions occur $K(K-1)$ times, and among these, those where $(B_x, B_y)$ are inverted constitute half. Therefore, multiply this count by $\frac {K(K-1)}{2}$.
3. To avoid counting inversions within $B_1, \cdots, B_N$, after sorting $B_1, \cdots, B_N$, count the inversions for the array where each number is inserted $K$ times.

When counting inversions, you can use merge sort or a data structure that manages the segment sum. When a number is repeated multiple times in either method, handle it as follows:

- Merge Sort: During the merge step, count the numbers on the left. When multiplying by the positions on the right, consider the duplication factor of the number.
- Segment Sum: When adding a number to the segment sum data structure, add the number's count instead of 1. When computing the answer, also multiply the result from the segment sum data structure by the number of times the number was duplicated.

The sample code below uses merge sort.


### Code (C++)

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

const int MOD = 1'000'000'007;
pair<int, vector<pair<int, int>>> count_and_sort(const vector<pair<int, int>> &A)
{
    if (A.size() <= 1)
        return {0, A};
    auto [cntL, L] = count_and_sort(vector(A.begin(), A.begin() + A.size() / 2));
    auto [cntR, R] = count_and_sort(vector(A.begin() + A.size() / 2, A.end()));
    int cnt = (cntL + cntR) % MOD, Rsz = 0;
    auto Lit = L.begin(), Rit = R.begin();
    vector<pair<int, int>> ret;

    while (Lit != L.end() || Rit != R.end())
    {
        bool fromL;
        if (Lit == L.end())
            fromL = false;
        else if (Rit == R.end())
            fromL = true;
        else
            fromL = Lit->first <= Rit->first;

        if (fromL)
        {
            if (ret.empty() || ret.back().first != Lit->first)
                ret.emplace_back(Lit->first, 0);
            cnt = (cnt + (int64_t)Rsz * Lit->second) % MOD;
            ret.back().second += Lit->second;
            if (ret.back().second >= MOD)
                ret.back().second -= MOD;
            ++Lit;
        }
        else
        {
            if (ret.empty() || ret.back().first != Rit->first)
                ret.emplace_back(Rit->first, 0);
            Rsz += Rit->second;
            if (Rsz >= MOD)
                Rsz -= MOD;
            ret.back().second += Rit->second;
            if (ret.back().second >= MOD)
                ret.back().second -= MOD;
            ++Rit;
        }
    }
    return {cnt, ret};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int M;
    cin >> M;
    int ans = 0;
    vector<pair<int, int>> A;
    while (M--)
    {
        int K, N;
        cin >> K >> N;
        vector<pair<int, int>> B(N);
        for (auto &[b, c] : B)
        {
            cin >> b;
            c = 1;
        }

        auto [internal_cnt, sortedB] = count_and_sort(B);
        int64_t rep_cnt = (int64_t)N * (N - 1) / 2;
        for (auto [b, c] : sortedB)
            rep_cnt -= (int64_t)c * (c - 1) / 2;
        ans = (ans +
               (int64_t)K * internal_cnt +
               ((int64_t)K * (K - 1) / 2 % MOD) * (rep_cnt % MOD)) %
              MOD;

        for (auto [b, c] : sortedB)
            A.emplace_back(b, (int64_t)c * K % MOD);
    }

    ans += count_and_sort(A).first;
    if (ans >= MOD)
        ans -= MOD;
    cout << ans << endl;
}
```

### Code (Python)

```python
import sys


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


MOD = 1_000_000_007


def count_and_sort(A):
    if len(A) <= 1:
        return (0, A)

    cntL, L = count_and_sort(A[:len(A) // 2])
    cntR, R = count_and_sort(A[len(A) // 2:])

    cnt = (cntL + cntR) % MOD
    Rsz = Lit = Rit = 0
    ret = []

    while Lit != len(L) or Rit != len(R):
        if Lit == len(L):
            fromL = False
        elif Rit == len(R):
            fromL = True
        else:
            fromL = L[Lit][0] <= R[Rit][0]

        if fromL:
            if not ret or ret[-1][0] != L[Lit][0]:
                ret.append((L[Lit][0], 0))
            cnt = (cnt + Rsz * L[Lit][1]) % MOD
            ret[-1] = (ret[-1][0], (ret[-1][1] + L[Lit][1]) % MOD)
            Lit += 1
        else:
            if not ret or ret[-1][0] != R[Rit][0]:
                ret.append((R[Rit][0], 0))
            Rsz = (Rsz + R[Rit][1]) % MOD
            ret[-1] = (ret[-1][0], (ret[-1][1] + R[Rit][1]) % MOD)
            Rit += 1
    return (cnt, ret)


def main():
    M = int(input())
    ans = 0
    A = []
    for _ in range(M):
        K, N = map(int, input().split())
        *B, = map(lambda b: (int(b), 1), input().split())

        internal_cnt, sortedB = count_and_sort(B)
        rep_cnt = N * (N - 1) // 2
        for b, c in sortedB:
            rep_cnt -= c * (c - 1) // 2
        ans = (ans + K * internal_cnt + K * (K - 1) // 2 * rep_cnt) % MOD

        for b, c in sortedB:
            A.append((b, c * K % MOD))

    ans = (ans + count_and_sort(A)[0]) % MOD
    print(ans)


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


## Solution

For convenience, let's assume the $i$'th option provides either $+a$ or $\times b$. Now, if we can achieve the value $K$ in the $(i-1)$'th turn, then on the $i$'th turn, we can achieve both values $K + a$ and $K \times b$. If we know all the values we can achieve up to the $(i-1)$'th turn, then following this rule, we can compute all the values we can achieve up to the $i$th turn. Similarly, we can determine all the possible values up to the $N$'th turn.

However, this approach is inefficient because the possible values can increase exponentially. Since we are only interested in whether a number is divisible by $7$, we will focus on the remainder when divided by $7$. Let's represent the remainder of $K$ divided by $7$ as $K \bmod 7$. Then the following properties hold:

- $((K \bmod 7) + a) \bmod 7 = (K + a) \bmod 7$
- $((K \bmod 7) \times b) \bmod 7 = (K \times b) \bmod 7$

To determine if $K$ is a multiple of $7$, we only need to check if $K \bmod 7$ is $0$. Thus, instead of storing all possible values, we only store the remainders when the numbers are divided by $7$.

Now, let's define a dynamic programming formula:

- $D_{i, m}$: Is it possible to have $K \bmod 7 = m$ after selecting up to the $i$th option?

This formula can be filled as follows:

- Without any selections, $K=1$. Therefore, only $D_{0, 1}$ is true.
- If $D_{i-1, x}$ is true, then $D_{i, (x+a) \bmod 7}$ and $D_{i, (x \times b) \bmod 7}$ are true.
  - If the remainder of $K$ divided by $7$ is $x$, the remainders of $(K+a)$ and $(K \times b)$ when divided by $7$ are $(x+a) \bmod 7$ and $(x \times b) \bmod 7$, respectively.
- In other cases, $D_{i, m}$ is false.


### Code (C++)

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

int calc(char op, int v1, int v2)
{
    return op == '*' ? (v1 * v2) % 7 : (v1 + v2) % 7;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for (int t = 0; t < T; t++)
    {
        int N;
        cin >> N;

        vector<vector<bool>> D(N + 1, vector<bool>(7));
        D[0][1] = true;
        for (int i = 1; i <= N; i++)
        {
            char op1, op2;
            int v1, v2;
            cin >> op1 >> v1 >> op2 >> v2;
            for (int x = 0; x < 7; x++)
                if (D[i - 1][x])
                    D[i][calc(op1, x, v1)] = D[i][calc(op2, x, v2)] = true;
        }
        cout << (D[N][0] ? "LUCKY\n" : "UNLUCKY\n");
    }
}
```

### Code (Python)

```python
import sys


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


def calc(op, v1, v2):
    if op == '*':
        return (v1 * v2) % 7
    else:
        return (v1 + v2) % 7


def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        D = [[False] * 7 for _ in range(N + 1)]
        D[0][1] = True

        for i in range(1, N + 1):
            op1, v1, op2, v2 = input().split()
            v1, v2 = int(v1), int(v2)
            for x in range(7):
                if D[i - 1][x]:
                    D[i][calc(op1, x, v1)] = True
                    D[i][calc(op2, x, v2)] = True

        print("LUCKY" if D[N][0] else "UNLUCKY")


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


## Solution

The Dijkstra Algorithm for finding the shortest path can be used here.

- In the problem, the array state $A_1, \cdots, A_N$ corresponds to the vertices of the graph.
- The operation of swapping two elements in the array changes one state of the array to another, and therefore, corresponds to the edges of the graph.

While implementing the Dijkstra Algorithm, there are cases where you need to check whether a vertex (or state) has been visited or not. In these cases, the array $(A_1, \cdots, A_N)$ can be stored in a tree or a hash set.

The time complexity is $\tilde {\mathcal{O}}(M \times N!)$.

### Code (C++)

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

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for (int &a : A)
        cin >> a;

    int M;
    cin >> M;
    vector<tuple<int, int, int>> LRC(M);
    for (auto &[l, r, c] : LRC)
        cin >> l >> r >> c, --l, --r;

    set<vector<int>> vis;
    using T = pair<int, vector<int>>;
    priority_queue<T, vector<T>, greater<T>> Q;
    Q.emplace(0, A);
    while (!Q.empty())
    {
        auto [d, v] = Q.top();
        Q.pop();
        if (vis.count(v))
            continue;
        vis.insert(v);
        if (ranges::is_sorted(v))
        {
            cout << d << endl;
            return 0;
        }
        for (auto [l, r, c] : LRC)
        {
            auto T = v;
            swap(T[l], T[r]);
            Q.emplace(d + c, T);
        }
    }
    cout << -1 << endl;
    return 0;
}
```

### Code (Python)

```python
import sys
import heapq


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


def main():
    N = int(input())
    A = list(map(int, input().split()))

    M = int(input())
    LRC = [list(map(int, input().split())) for _ in range(M)]
    for lrc in LRC:
        lrc[0] -= 1
        lrc[1] -= 1

    vis = set()
    Q = [(0, tuple(A))]
    while Q:
        d, v = heapq.heappop(Q)
        if v in vis:
            continue
        vis.add(v)
        if all(v[i] <= v[i+1] for i in range(N-1)):
            print(d)
            return
        for l, r, c in LRC:
            T = list(v)
            T[l], T[r] = T[r], T[l]
            heapq.heappush(Q, (d + c, tuple(T)))

    print(-1)

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


## Solution

Let's denote $P_i$ as the condition “Should $A_i$ be made even?”. We can transform the problem into one where we either set $P_i$ to `true` or `false`.

For ease of understanding, let’s label the even number among $A_i$ and $A_i+1$ as $E_i$, and the odd one as $O_i$. Based on the problem, the costs are:

- If $E_i = A_i$ and $P_i = \textrm{false}$, it costs $1$.
- If $O_i = A_i$ and $P_i = \textrm{true}$, it costs $1$.
- If $E_i + O_j$ is prime, $P_i = \textrm{true}$, and $P_j = \textrm{false}$, then it's not allowed.

Remember, the only even prime number is $2$. For the cases where two or more $1$'s are in A, every $1$ should be made $2$.

- If there are two or more 1's in $A$, and $A_i = 1$, then $P_i$ must be `true`.

We can now solve this problem using the concept of the minimum cut.

### Minimum Cut Modeling

Such problems can be modeled using the minimum cut.

We'll create a graph with a total of $N+2$ vertices, which includes special vertices `true` and `false` and all of the $P_i$'s. We then divide this into two sets: $T$ and $F$. Vertices in the set $T$ are set to `true`, while those in $F$ are set to `false`. The vertex `true` always belongs to $T$ and `false` always to $F$.

We then calculate the minimum cut from `true` to `false`. If an edge exists from a vertex in set $T$ to one in set $F$, then the edge's weight becomes the cost. With this in mind, our rules become:

- If $E_i = A_i$ and $P_i = \textrm{false}$, then it costs $1$.
  - Draw an edge with weight $1$ from `true` to $P_i$.
  
- If $O_i = A_i$ and $P_i = \textrm{true}$, then it costs $1$.
  - Draw an edge with weight $1$ from $P_i$ to `false`.

- If $E_i + O_j$ is prime, $P_i = \textrm{true}$, and $P_j = \textrm{false}$, then it's not allowed.
  - Draw an edge with weight $\infty$ from $P_i$ to $P_j$.

- If $A$ has two or more 1's and $A_i = 1$, then $P_i$ must be `true`.
  - Draw an edge with weight $\infty$ from `true` to $P_i$.

Now, apply the max-flow min-cut theorem. Send the maximum flow from `true` to `false`, then identify sets $T$ and $F$ and display the result according to the parity of $A_i$.

### Code (C++)

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

struct SimpleFlow
{
    SimpleFlow(int n) : N(n), G(N, vector<int>(N)) {}
    void addEdge(int u, int v, int f) { G[u][v] += f; }
    int flow(int s, int t)
    {
        int ans = 0;
        while (true)
        {
            vis = vector<bool>(N);
            if (!augment(s, t))
                return ans;
            ++ans;
        }
    }
    vector<bool> cut() { return vis; }

private:
    int N;
    vector<vector<int>> G;
    vector<bool> vis;
    bool augment(int s, int t)
    {
        vis[s] = true;
        if (s == t)
            return true;
        for (int i = 0; i < N; i++)
            if (G[s][i] && !vis[i])
            {
                if (augment(i, t))
                {
                    G[s][i]--;
                    G[i][s]++;
                    return true;
                }
            }
        return false;
    }
};

vector<int> solve(vector<int> A)
{
    int MX = *max_element(A.begin(), A.end()) * 2 + 2;
    vector<bool> P(MX + 1, true);
    P[0] = P[1] = false;
    for (int i = 2; i <= MX; i++)
        if (P[i])
            for (int j = 2 * i; j <= MX; j += i)
                P[j] = false;

    int N = A.size();
    SimpleFlow flow(N + 2);
    int T = N, F = N + 1, inf = N + 1;

    for (int i = 0; i < N; i++)
        if (A[i] % 2 == 0)
            flow.addEdge(T, i, 1);
        else
            flow.addEdge(i, F, 1);

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
        {
            int Ei = A[i], Oj = A[j];
            if (Ei % 2 == 1)
                Ei++;
            if (Oj % 2 == 0)
                Oj++;
            if (P[Ei + Oj])
                flow.addEdge(i, j, inf);
        }

    if (count(A.begin(), A.end(), 1) >= 2)
        for (int i = 0; i < N; i++)
            if (A[i] == 1)
                flow.addEdge(T, i, inf);

    flow.flow(T, F);

    auto cut = flow.cut();
    vector<int> res;
    for (int i = 0; i < N; i++)
        if ((A[i] % 2 == 1) == cut[i])
            res.push_back(i);

    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int &a : A)
        cin >> a;
    auto ans = solve(A);
    cout << ans.size() << endl;
    for (int x : ans)
        cout << 1 + x << ' ';
    cout << endl;
}
```

### Code (Python)

```python
class SimpleFlow:
    def __init__(self, n):
        self.N = n
        self.G = [[0] * n for _ in range(n)]
        self.vis = [False] * n

    def add_edge(self, u, v, f):
        self.G[u][v] += f

    def flow(self, s, t):
        ans = 0
        while True:
            self.vis = [False] * self.N
            if not self.augment(s, t):
                return ans
            ans += 1

    def cut(self):
        return self.vis[:]

    def augment(self, s, t):
        self.vis[s] = True
        if s == t:
            return True
        for i in range(self.N):
            if self.G[s][i] and not self.vis[i]:
                if self.augment(i, t):
                    self.G[s][i] -= 1
                    self.G[i][s] += 1
                    return True
        return False


def solve(A):
    MX = max(A) * 2 + 2
    P = [True] * (MX + 1)
    P[0] = P[1] = False
    for i in range(2, MX + 1):
        if P[i]:
            for j in range(2 * i, MX + 1, i):
                P[j] = False

    N = len(A)
    flow = SimpleFlow(N + 2)
    T, F, inf = N, N + 1, N + 1

    for i in range(N):
        if A[i] % 2 == 0:
            flow.add_edge(T, i, 1)
        else:
            flow.add_edge(i, F, 1)

    for i in range(N):
        for j in range(N):
            Ei, Oj = A[i], A[j]
            if Ei % 2 == 1:
                Ei += 1
            if Oj % 2 == 0:
                Oj += 1
            if P[Ei + Oj]:
                flow.add_edge(i, j, inf)

    if A.count(1) >= 2:
        for i in range(N):
            if A[i] == 1:
                flow.add_edge(T, i, inf)

    flow.flow(T, F)

    cut = flow.cut()
    return [i for i in range(N) if (A[i] % 2 == 1) == cut[i]]


def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = solve(A)
    print(len(ans))
    print(*(1+x for x in ans))


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


## Solution

There are several ways to determine if a string is a valid parenthesis string. Among them, one of the most commonly used methods is to pick two out of the following three conditions and check if both are satisfied:

1. Ensure that the number of `(` matches the number of `)`.
2. For every prefix, check that the number of `(` is at least as many as the number of `)`.
3. For every suffix, check that the number of `)` is at least as many as the number of `(`.

Let's use this method to solve the problem. First, let's divide the given string into two cases: with and without `*`.

### When $S$ does not contain `*`

Use conditions 1 and 2. The count of `(` and `)` should be the same. Since the length of the string is fixed, we can determine how many `(` and `)` should replace the `?`.

Now, we need to place `(` and `)` in place of `?`. In this scenario, greedily place `(` in the front and `)` at the back. Doing this ensures that the count of `(` in the suffix, which relates to condition 2, is maximized.

After arranging like this, check if the resultant string is a valid parenthesis string.

### When $S$ contains `*`

Every `*` can be replaced as `****`, with the answer remaining the same. Now, let's divide the string into three parts: $S = ABC$. $A$ is the string up to the first occurrence of `*`, $C$ is the string from the last occurrence of `*`, and $B$ is the string excluding both $A$ and $C$. When the string is divided this way, we know that both $A$ and $B$ end with `*`, and both $B$ and $C$ begin with `*`.

Now, if we can make each of $A, B, C$ into valid parenthesis strings, then string $S$ can also be made into a valid parenthesis string. If there are no `?` in $A, B, C$, you can check if you can make $A, B, C$ into valid parenthesis strings as follows:

- To check whether $A$ can be a valid parenthesis string, check for every prefix of $A$ that the count of `(` is at least as many as the count of `)`. If so, the first condition can be met by replacing `*` with `)` in an amount that matches.
- To check whether $C$ can be a valid parenthesis string, instead of checking every prefix of $C$ to see if the count of `(` is at least as many as the count of `)`, do the opposite: check every suffix to see if the count of `)` is at least as many as `(`. Similarly, the first condition can be satisfied by replacing `*` with `(` in a matching amount.
- $B$ can always be made into a valid parenthesis string. By adding a sufficiently large number of `(` to the first appearing `*` to meet the second condition, and adding an appropriate number of `)` to the last appearing `*` to meet the first condition.

Now let's consider the case when `?` is added. Because we need to satisfy the first condition as much as possible, replace `?` in $A$ with `(` and `?` in $B$ with `)`.

In summary:

- Starting from the front, replace `?` with `(` until you encounter `*`, and check the count of `(` is at least as many as `)`.
- Starting from the back, replace `?` with `)` until you encounter `*`, and check the count of `)` is at least as many as `(`.

If the above two conditions are met, then $S$ can be made into a valid parenthesis string.



### Code (C++)

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

bool solve(string s)
{
    int N = s.size();
    if (count(s.begin(), s.end(), '*') >= 1)
    {
        int cnt = 0;
        for (int i = 0; s[i] != '*'; ++i)
        {
            if (s[i] == ')')
                --cnt;
            else
                ++cnt;
            if (cnt < 0)
                return false;
        }
        cnt = 0;
        for (int i = N - 1; s[i] != '*'; --i)
        {
            if (s[i] == '(')
                --cnt;
            else
                ++cnt;
            if (cnt < 0)
                return false;
        }
        return true;
    }
    if (N % 2 != 0)
        return false;
    int open = ranges::count(s, '('), close = ranges::count(s, ')');
    if (open > N / 2 || close > N / 2)
        return false;

    int cnt = 0;
    for (char c : s)
    {
        if (c == '?')
        {
            if (open < N / 2)
                c = '(', ++open;
            else
                c = ')';
        }
        if (c == '(')
            ++cnt;
        else
            --cnt;
        if (cnt < 0)
            return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        string s;
        cin >> s;
        cout << (solve(s) ? "YES" : "NO") << '\n';
    }
}
```

### Code (Python)

```python
import sys


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


def solve(s):
    s = list(s)
    if s.count('*') >= 1:
        cnt = 0
        for c in s:
            if c == '*':
                break
            if c == ')':
                cnt -= 1
            else:
                cnt += 1
            if cnt < 0:
                return False
        cnt = 0
        for c in s[::-1]:
            if c == '*':
                break
            if c == '(':
                cnt -= 1
            else:
                cnt += 1
            if cnt < 0:
                return False
        return True
    if len(s) % 2 != 0:
        return False

    open_ = s.count('(')
    close = s.count(')')
    if open_ > len(s) // 2 or close > len(s) // 2:
        return False

    cnt = 0
    for c in s:
        if c == '?':
            if open_ < len(s) // 2:
                c = '('
                open_ += 1
            else:
                c = ')'
        if c == '(':
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0:
            return False
    return True


def main():
    T = int(input())
    for _ in range(T):
        s = input()
        print("YES" if solve(s) else "NO")


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