We can notice that the possible values of $$$a_3$$$ ranges from $$$-99$$$ to $$$200$$$. Thus, we can iterate over all values of $$$a_3$$$ from $$$-99$$$ to $$$200$$$, and for each value, compute the Fibonacciness of the sequence. The maximal of all these values gives the solution to the problem.

Time Complexity : $$$O(3*a_{max})$$$

$$$a_3$$$ can be represented as either of the following:

$$$a_3 = a_1 + a_2$$$, or

$$$a_3 = a_4 - a_2$$$, or

$$$a_3 = a_5 - a_4$$$.

These are at most 3 possible values. Notice that any value of $$$a_3$$$ which increases the Fibonacciness must belong to one of the above values (Think why!). So, in order to increase the Fibonacciness of the sequence, we should choose the most frequent of the above values. Then, in the end, we can calculate the Fibonacciness of the sequence after choosing the best value for $$$a_3$$$.

Time Complexity : $$$O(1)$$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

void tc () {
    vll ve(4);
    for (ll &i : ve) cin >> i;
    set <ll> st;
    st.insert(ve[3]-ve[2]);
    st.insert(ve[2]-ve[1]);
    st.insert(ve[0]+ve[1]);
    cout << 4-st.size() << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Assume the cows are initially ordered correctly. A solution exists if the first cow can place $$$0$$$, the second cow can place $$$1$$$, and so on, continuing with the first cow placing $$$n$$$, the second cow placing $$$n+1$$$, and so forth. Observing the pattern, the first cow must be able to place $$${0, n, 2n, \dots}$$$, the second $$${1, n+1, 2n+1, \dots}$$$, and in general, the $$$i$$$-th cow (where $$$i \in [0, n-1]$$$) must be able to place $$${i, n+i, 2n+i, \dots}$$$.

For each cow, sorting their cards reveals whether they satisfy this condition: the difference between adjacent cards in the sorted sequence must be $$$n$$$. If any cow's cards do not meet this criterion, the solution does not exist, and we output $$$-1$$$.

If the cows are not ordered correctly, we need to rearrange them. To construct the solution, find the index of the cow holding card $$$i$$$ for each $$$i \in [0, n-1]$$$. Since the cards of each cow are sorted, denote $$$\texttt{min_card}$$$ as the smallest card a cow holds. Using an array $$$p$$$, iterate over each cow $$$c$$$ from $$$0$$$ to $$$n-1$$$ and set $$$p_\texttt{min_card} = c$$$. Finally, iterate $$$i$$$ from $$$0$$$ to $$$n-1$$$ and output $$$p_i$$$.

Time Complexity : $$$O(nmlog(m))$$$. Note that sorting is not necessary, and a solution with complexity up to $$$O((nm)^2)$$$ will still pass.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

void tc () {
    ll n, m;
    cin >> n >> m;
    vector <vll> ve(n, vll(m));
    vll p(n, -16);
    bool val = true;
    ll c = 0;
    for (vll &we : ve) {
        for (ll &i : we) cin >> i;
        ll minN = *min_element(we.begin(), we.end());
        if (minN < n) p[minN] = c++;
        val &= minN < n;
        sort(we.begin(), we.end());
        ll last = we[0]-n;
        for (ll i : we) {
            val &= last+n == i;
            last = i;
        }
    }
    if (!val) {
        cout << "-1\n";
        return;
    }
    for (ll i : p) cout << i+1 << ' ';
    cout << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Note that Bob has all the power in this game, because the order in which Alice picks numbers is irrelevant, since Bob can always pick the optimal number to give himself a point. Therefore, we can just ignore Alice and play the game from Bob's perspective.

From this point on, a "paired" number is any number $$$a$$$ on the blackboard such that there exists a $$$b$$$ on the blackboard such that $$$a+b=k$$$.

Bob's strategy is as follows:

• if Alice picks a paired number, Bob should pick the other number in the pair.

• if Alice picks an unpaired number, Bob can pick any other unpaired number, it doesn't matter which.

This always works because the number of "unpaired numbers" is always even, since $$$n$$$ is even and the number of "paired numbers" will always be even. Therefore, for every unpaired number Alice picks, Bob will always have an unpaired number to respond with.

Therefore, the final score is just the number of pairs in the input. To count them, use a map of counts $$$c$$$ such that $$$c_x$$$ is the number of occurrences of $$$x$$$ on the whiteboard. Then, for each number from $$$1$$$ to $$$\lfloor \frac{k}{2} \rfloor$$$, take the minimum of $$$c_x$$$ and $$$c_{k-x}$$$, and add that to the total. Remember the edge case where $$$k$$$ is even and $$$x = \frac{k}{2}$$$. The number of pairs here is just $$$\lfloor \frac{c_x}{2} \rfloor$$$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

void tc () {
    ll n, k;
    cin >> n >> k;
    vll ve(n);
    for (ll &i : ve) cin >> i;
    vll th(k+1, 0);
    for (ll i : ve) {
        if (i >= k) continue;
        th[i]++;
    }
    ll ans = 0;
    for (ll i = 1; i < k; i++) {
        if (i == k-i) {
            ans += th[i]/2;
            continue;
        }
        ll minN = min(th[i], th[k-i]);
        th[i] -= minN;
        th[k-i] -= minN;
        ans += minN;
    }
    cout << ans << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

For clarity, let's denote $$$op_i$$$ as an operation performed on $$$a_i$$$ and $$$a_{i+1}$$$.

Claim: if it is possible, then the sequence of operations $$$op_1,op_2,\ldots,op_{n-1}$$$ will sort the array.

Proof: Let $$$b$$$ be any sequence of operations that will sort the array. Let's transform the sequence $$$b$$$ such that it becomes $$$[op_1,op_2,\ldots,op_{n-1}]$$$.

First, let's note that an $$$op_i$$$ does nothing if $$$a_i=0$$$ or $$$a_{i+1}=0$$$. Additionally, after $$$op_i$$$, at least one of $$${a_i,a_{i+1}}$$$ will become zero. Thus, we can remove all duplicates in $$$b$$$ without altering the result.

Now, let $$$x$$$ be the largest number such that $$$op_x$$$ is in $$$b$$$. Since at least one of $$$a_x,a_{x+1}$$$ will be zero, operations must be performed such that each of $$$a_1,a_2,\ldots,a_{x-1}$$$ are zero. Let $$$S$$$ be the set of indices with $$$i \lt x$$$ such that $$$op_i$$$ is not in $$$b$$$. Note that we can simply append each operation in $$$S$$$ at the end of $$$b$$$ without altering the result, since all elements before $$$a_x$$$ are already zero.

Our sequence of operations now contain a permutation of $$$op_1,op_2,\ldots,op_x$$$, and we have ensured that all of $$$a_1,a_2,\ldots,a_x=0$$$. Since the sequence is now sorted, we can in fact continue performing $$$op_{x+1},op_{x+2},\ldots,op_{n-1}$$$ in this order. Notice that this sequence of operations will keep our array sorted, as $$$op_y$$$ will make $$$a_y=0$$$ (since $$$a_y \lt a{y+1}$$$).

Let's show that we can rearrange our operations such that $$$1$$$ comes first. There are two cases: either $$$op_1$$$ comes before $$$op_2$$$, or $$$op_2$$$ comes before $$$op_1$$$. In the first case, notice that no operation done before $$$op_1$$$ will impact either the value of $$$a_1$$$ or $$$a_2$$$, so rearranging such that $$$op_1$$$ comes first does not impact the final results. In the second case, notice that after $$$op_2$$$ is done, we must have $$$a_1=a_2$$$, as otherwise $$$op_1$$$ will not simultaneously make $$$a_1=a_2=0$$$. This implies that right before $$$op_2$$$ is performed, we must have $$$a_1+a_3=a_2$$$. Then, rearranging the operations such that $$$op_1$$$ comes first will not impact the final result.

Using the same line of reasoning, we can make $$$op_2$$$ the second operation, then $$$op_3$$$, and so on. To solve the problem, we can simply simulate the operations in this order, and then check if the array is sorted at the end.

Time Complexity : $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

void tc () {
    ll n;
    cin >> n;
    vll ve(n);
    for (ll &i : ve) cin >> i;
    ll j = 0;
    for (ll i = 1; i < n; i++) {
        if (ve[i-1] > ve[i]) j = i;
    }
    if (j == 0) { // all done
        cout << "YES\n";
        return;
    }
    auto fop = [&](ll i) {
        ll minN = min(ve[i], ve[i+1]);
        ve[i] -= minN;
        ve[i+1] -= minN;
    };
    for (ll i = 0; i < j; i++) {
        fop(i);
    }
    cout << (is_sorted(ve.begin(), ve.end()) ? "YES" : "NO") << '\n';
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll T; cin >> T; while (T--) { tc(); }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Let's solve the problem for each operation.

First, consider the operation that removes an edge from $$$ F $$$. Divide $$$ G $$$ into its connected components and assign each vertex a component index. Then, for each edge in $$$ F $$$, if it connects vertices with different component indices, remove it and increment the operation count.

This guarantees no path between $$$ x $$$ and $$$ y $$$ in $$$ F $$$ if there is none in $$$ G $$$. Next, to ensure a path exists between $$$ x $$$ and $$$ y $$$ in $$$ F $$$ if there is one in $$$ G $$$, we divide $$$ F $$$ into connected components. After removing excess edges, each component of $$$ F $$$ only contains vertices of the same component index. The number of operations needed now is the difference between the number of connected components in $$$ F $$$ and $$$ G $$$.

All operations can be efficiently performed using DFS or DSU.

#include <bits/stdc++.h>

#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long double ld;
typedef long long ll;

using namespace std;

mt19937 rnd(time(nullptr));

const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;

void Gdfs(int v, vector<vector<int>> &sl, vector<int> &col, int c){
    col[v] = c;
    for(int u: sl[v]){
        if(col[u] == 0){
            Gdfs(u, sl, col, c);
        }
    }
}

int Fdfs(int v, vector<vector<int>> &sl, vector<int> &col, vector<int> &old_col, int c){
    col[v] = c;
    int res = 0;
    for(int u: sl[v]){
        if(col[u] == 0){
            if(old_col[u] != c) res++;
            else res += Fdfs(u, sl, col, old_col, c);
        }
    }
    return res;
}

void read_con_list(vector<vector<int>> &sl, int m){
    for(int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v;
        sl[--u].emplace_back(--v);
        sl[v].emplace_back(u);
    }
}

void solve(int tc){
    int n, mf, mg;
    cin >> n >> mf >> mg;
    vector<vector<int>> fsl(n), gsl(n);
    read_con_list(fsl, mf);
    read_con_list(gsl, mg);

    vector<int> fcol(n), gcol(n);
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(gcol[i] == 0){
            Gdfs(i, gsl, gcol, i + 1);
        }
        if(fcol[i] == 0){
            ans += Fdfs(i, fsl, fcol, gcol, gcol[i]);
            if(gcol[i] < i + 1) ans++;
        }
    }
    cout << ans;
}

bool multi = true;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    if (multi)cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve

When $$$n$$$ is large, many of the array's elements will be $$$1$$$.

The number of non-$$$1$$$ elements can't be so large.

Try to precompute all arrays without $$$1$$$ and then use combinatorics.

The naive solution is to define $$$f_k(n)$$$ as the number of arrays containing $$$n$$$ elements with a product of $$$k$$$. We could then try to compute this by considering the last element of the array among the divisors of $$$k$$$, giving us:

with $$$f_k(1)=1$$$.

The answers would then be $$$\sum_{i=1}^{n}f_1(i),\sum_{i=1}^{n}f_2(i),\dots,\sum_{i=1}^{n}f_k(i)$$$. However, this leads to an $$$O(nk\log k)$$$ solution, which exceeds our time constraints. We need to optimize this approach.

We can prove that there are at most $$$16$$$ non-$$$1$$$ elements in our arrays. This is because:

• The prime factorization of $$$k=p_1p_2\cdots p_t$$$ divides $$$k$$$ into the most non-$$$1$$$ elements.
• With $$$17$$$ non-$$$1$$$ elements, the smallest possible value would be $$$k=2^{17}=131072 \gt 10^5$$$.

Based on this observation, we can define our dynamic programming state as:

• Let $$$dp[i][j]$$$ represent the number of arrays with product $$$i$$$ containing only $$$j$$$ non-$$$1$$$ elements.
• The recurrence relation becomes: $$$dp[i][j]=\sum_{p|i,p \gt 1}dp[\frac{i}{p}][j-1]$$$.
• Base case: $$$dp[i][1]=1$$$ for $$$i \gt 1$$$.

This computation has a time complexity of $$$O(k\log^2k)$$$, as we perform $$$\sum_{j=1}^{k}d(j)=O(k\log{k})$$$ additions for each $$$i$$$.

To calculate $$$f_k(n)$$$, we:

1. Enumerate the number of non-$$$1$$$ elements from $$$1$$$ to $$$16$$$.
2. For $$$j$$$ non-$$$1$$$ elements in the array:

• We have $$$n-j$$$ elements that are $$$1$$$.
• We need to choose $$$j$$$ positions for non-$$$1$$$ elements.
• Fill these positions with $$$dp[k][j]$$$ possible sequences.

This gives us:

Therefore:

Note that $$$\sum_{i=1}^{n}\binom{i}{j} = \binom{n+1}{j+1}$$$ is given by the Hockey Stick Identity.

Each answer can be calculated in $$$O(\log^2k)$$$ time, giving an overall time complexity of $$$O(k\log^2k)$$$.

Let's revisit the naive approach and define $$$S_k(n)=\sum_{i=1}^{n}f_{k}(n)$$$ as our answers. We can observe:

Accumulating Formula $$$(1)$$$ yields:

By induction, we can prove that both $$$f_{k}(n)$$$ and $$$S_k(n)$$$ are polynomials. Let's denote:

• Degree of $$$f_k(n)$$$ as $$$p(k)$$$.
• Degree of $$$S_k(n)$$$ as $$$q(k)$$$.

From the definition of $$$S_k(n)$$$, we have $$$q(k)=p(k)+1$$$. Formula $$$(2)$$$ gives us:

with $$$p(1)=0$$$. By induction, we can show that $$$p(k)$$$ equals the number of primes in $$$k$$$'s prime factorization. Therefore, $$$p(k)\le16$$$ and $$$q(k)\le17$$$.

Since $$$q(k)$$$ doesn't exceed $$$17$$$, we can:

1. Precompute $$$S_k(1),S_k(2),S_k(3),\dots,S_k(18)$$$.
2. Use Lagrange Interpolation to compute any $$$S_k(n)$$$.

This also yields an $$$O(k\log^2k)$$$ time complexity.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Runtime.Serialization.Json;
using System.Text;
using System.Threading.Tasks;
using TemplateF;

#if !PROBLEM
SolutionF a = new();
a.Solve();
#endif

namespace TemplateF
{
    internal class SolutionF
    {
        private readonly StreamReader sr = new(Console.OpenStandardInput());
        private T Read<T>()
            where T : struct, IConvertible
        {
            char c;
            dynamic res = default(T);
            dynamic sign = 1;
            while (!sr.EndOfStream && char.IsWhiteSpace((char)sr.Peek())) sr.Read();
            if (!sr.EndOfStream && (char)sr.Peek() == '-')
            {
                sr.Read();
                sign = -1;
            }
            while (!sr.EndOfStream && char.IsDigit((char)sr.Peek()))
            {
                c = (char)sr.Read();
                res = res * 10 + c - '0';
            }
            return res * sign;
        }

        private T[] ReadArray<T>(int n)
            where T : struct, IConvertible
        {
            T[] arr = new T[n];
            for (int i = 0; i < n; ++i) arr[i] = Read<T>();
            return arr;
        }

        public void Solve()
        {
            StringBuilder output = new();
            const int maxk = 100000, mod = 998244353, bw = 20;
            List<int>[] d = new List<int>[maxk + 1];
            for (int i = 1; i <= maxk; ++i) d[i] = new() { 1 };
            for (int i = 2; i <= maxk; ++i) {
                for (int j = i; j <= maxk; j += i) d[j].Add(i);
            }
            int[,] dp = new int[bw + 1, maxk + 1], S = new int[bw + 1, maxk + 1];
            for (int k = 1; k <= maxk; ++k) dp[1, k] = S[1, k] = 1;
            for (int i = 2; i <= bw; ++i) {
                for (int j = 1; j <= maxk; ++j) {
                    foreach (var k in d[j]) {
                        dp[i, j] += dp[i - 1, k];
                        dp[i, j] %= mod;
                    }
                    S[i, j] = (S[i - 1, j] + dp[i, j]) % mod;
                }
            }
            int T = Read<int>();
            while (T-- > 0)
            {
                int k = Read<int>(), n = Read<int>();
                if (n <= bw) {
                    for (int j = 1; j <= k; ++j) output.Append(S[n, j]).Append(' ');
                } else {
                    int _k = k;
                    for (k = 1; k <= _k; ++k)  {
                        long ans = 0;
                        for (int i = 1; i <= bw; ++i) {
                            long t = S[i, k];
                            for (int j = 1; j <= bw; ++j) {
                                if (j == i) continue;
                                t *= n - j;
                                t %= mod;
                                t *= Inv((mod + i - j) % mod, mod);
                                t %= mod;
                            }
                            ans = (ans + t) % mod;
                        }
                        output.Append(ans).Append(' ');
                    }
                }
                output.AppendLine();
            }
            Console.Write(output.ToString());
        }
        public static long Inv(long a, long Mod) {
            long u = 0, v = 1, m = Mod;
            while (a > 0) {
                long t = m / a;
                m -= t * a; (a, m) = (m, a);
                u -= t * v; (u, v) = (v, u);
            }
            return (u % Mod + Mod) % Mod;
        }
    }
}

• Heat
• Mid
• Horrendous
• Didn't Solve

Consider $$$(a_i, b_i)$$$ as the $$$i$$$-th pair. Can two elements ever become unpaired?

The operations allow us to swap two pairs, but it also results in both of them getting flipped. Is there any way to swap two pairs without flipping anything?

Can you flip two pairs without swapping them?

Can you flip one pair on its own?

Read the hints first.

Key observation:

In the final solution, the pairs must be sorted in increasing order of $$$\min(a_i, b_i)$$$. We prove this by contradiction. Suppose there exists a pair $$$(a_i, b_i)$$$, where $$$a_i \lt b_i$$$ and $$$a_i$$$ is smaller than the minimum element in the previous pair. In this case, it becomes impossible to place this pair after the previous one, as $$$a_i$$$ would always be smaller than the preceding element, regardless of orientation.

Since all $$$a_i$$$ and $$$b_i$$$ are distinct, there is exactly one valid final ordering of the pairs. Moreover, this ordering is always reachable because we previously proved that any two pairs can be swapped without flipping their elements. Since swapping any two items in an array an arbitrary number of times allows for sorting by definition, we can sort the pairs in this order. Thus, the solution is to initially sort the pairs based on $$$\min(a_i, b_i)$$$.

Solution:

The problem simplifies to determining whether flipping pairs allows sorting. We can solve this using dynamic programming (DP), defined as follows:

$$$dp[1][i] = 1$$$ if it's possible to sort up and including pair $$$i$$$ using an even number of flips, where pair $$$i$$$ is not flipped.
$$$dp[2][i] = 1$$$ if it's possible to sort up and including pair $$$i$$$ using an even number of flips, where pair $$$i$$$ is flipped.
$$$dp[3][i] = 1$$$ if it's possible to sort up and including pair $$$i$$$ using an odd number of flips, where pair $$$i$$$ is not flipped.
$$$dp[4][i] = 1$$$ if it's possible to sort up and including pair $$$i$$$ using an odd number of flips, where pair $$$i$$$ is flipped.

The base cases are as follows:

$$$dp[1][1] = 1$$$, because this represents the state where the first pair is not flipped, resulting in zero flips (which is even)
$$$dp[4][1] = 1$$$, because this represents the state where the first pair is flipped, resulting in one flip (which is odd).

There are eight possible transitions, as you can reach each of the four states from two previous states: you either choose to flip the current element or you don't.

The final answer is $$$dp[1][n]$$$ $$$\texttt{OR}$$$ $$$dp[2][n]$$$, because by Hints 3 and 4, we can only reach states where an even number of pairs are flipped from the starting position.

#include <bits/stdc++.h>
using namespace std;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define print pair<int, int>
#define vp vector<print>
#define ALL(x) (x).begin(), (x).end()

void solve()
{
    int n;
    cin >> n;
    vp pairs(n);
    F0R(i, n)
    {
        cin >> pairs[i].first;
    }
    F0R(i, n)
    {
        cin >> pairs[i].second;
    }

    sort(ALL(pairs), [](print a, print b)
         { return min(a.first, a.second) < min(b.first, b.second); });

    vector<vector<int>> dp(4, vector<int>(n, 0));
    dp[0][0] = 1;
    dp[3][0] = 1;
    FOR(i, 1, n)
    {
        if (pairs[i - 1].first < pairs[i].first and pairs[i - 1].second < pairs[i].second)
        {
            dp[0][i] |= dp[0][i - 1];
            dp[1][i] |= dp[1][i - 1];
            dp[2][i] |= dp[3][i - 1];
            dp[3][i] |= dp[2][i - 1];
        }
        if (pairs[i - 1].first < pairs[i].second and pairs[i - 1].second < pairs[i].first)
        {
            dp[0][i] |= dp[2][i - 1];
            dp[1][i] |= dp[3][i - 1];
            dp[2][i] |= dp[1][i - 1];
            dp[3][i] |= dp[0][i - 1];
        }
    }
    cout << ((dp[0][n - 1] | dp[2][n - 1]) ? "YES" : "NO") << endl;
}

signed main()
{
    int tests;
    cin >> tests;
    F0R(test, tests)
    {
        solve();
    }

    return 0;
}

• Heat
• Mid
• Horrendous
• Didn't Solve