void solve() {
    int n, k;
    cin >> n >> k;
    string t[n];
    int ans = n;
    for(int i = 0; i < n; i++) {
        cin >> t[i];
        if(t[i] != t[0]) {
            ans--;
        }
    }
    cout << ans << "\n";
}

void solve() {
    int n;
    cin >> n;
    if(n == 1) {
        cout << 1 << "\n";
    } else if(n % 2) {
        cout << -1 << "\n";
    } else {
        int a[n];
        iota(a, a + n, 1);
        for(int i = 0; i < n; i += 2) {
            swap(a[i], a[i + 1]);
        }
        for(auto it: a) {
            cout << it << ' ';
        }
        cout << "\n";
    }
}

#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q; cin >> n >> q;
    vi a(n);
    for(int& i : a) cin >> i;
    vi p(n-1);
    for(int i=1;i<n-1;++i) {
        int downhill = a[i-1]>=a[i] and a[i]>=a[i+1];
        p[i] = p[i-1] + downhill;
    }
    while(q--) {
        int l,r; cin >> l >> r;
        --l,--r;
        if(l==r) {
            cout << "1\n";
        } else {
            int ans = (r-l+1) - p[r-1] + p[l];
            cout << ans << '\n';
        }
    }
}

Can you find a necessary condition for whether a Fish Subgraph exists?

For the Fish Subgraph to exist, the graph must have a cycle with one node in the cycle having degree at least 4.

When the necessary condition is satisfied, actually, you can always find a Fish Subgraph. Try to prove this, and see if your proof can be turned into an algorithm.

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;

void solve() {
    int n,m; cin >> n >> m;
    vvi adj(n);
    while(m--) {
        int u,v; cin >> u >> v;
        --u,--v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // find cycle and node with big degree.
    for(int u=0;u<n;++u) if(adj[u].size()>=4) for(int v : adj[u]) {
        // find path from u to v, without edge (u,v)
        vi cur;
        vi p;
        vector<bool> vis(n);
        auto dfs = [&](auto&& self, int at) -> void {
            vis[at]=1;
            cur.push_back(at);
            if(at==v) {
                p=cur;
                return;
            }
            for(int to : adj[at]) if(!vis[to]) {
                if(at==u and to==v) continue;
                self(self,to);
                if(!p.empty()) return;
            }
            cur.pop_back();
        };
        dfs(dfs,u);
        if(p.empty()) continue;
        // found cycle, with a node with degree >=4
        vi extra = adj[u];
        extra.resize(4);
        int mn = p.size();
        for(auto i : extra) {
            auto it = find(all(p),i);
            if(it!=p.begin()+1) {
                mn = min(mn,int(it-p.begin())+1);
            }
        }
        p.resize(mn);
        partition(all(extra),[&](int i) {return count(all(p),i)==0;});
        extra.resize(2);

        cout << "YES\n";
        cout << p.size()+2 << '\n';
        auto out = [&](int a, int b) {cout << a+1 << ' ' << b+1 << '\n';};
        int prv=p.back();
        for(auto i : p) {
            out(i,prv);
            prv=i;
        }
        out(u,extra[0]);
        out(u,extra[1]);
        return;
    }

    cout << "NO\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t; cin >> t;
    while(t--) solve();
}

const int mod = 1e9 + 7;

namespace algebra {
    const int maxn = 3e6 + 42;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 

    template<typename T>
    T bpow(T x, size_t n) {
        if(n == 0) {
            return T(1);
        } else {
            auto t = bpow(x, n / 2);
            t = t * t;
            return n % 2 ? x * t : t;
        }
    }

    const int m = mod;
    struct modular {
        int r;
        constexpr modular(): r(0) {}
        constexpr modular(int64_t rr): r(rr % m) {if(r < 0) r += m;}
        modular inv() const {return bpow(*this, m - 2);}
        modular operator - () const {return r ? m - r : 0;}
        modular operator * (const modular &t) const {return (int64_t)r * t.r % m;}
        modular operator / (const modular &t) const {return *this * t.inv();}
        modular operator += (const modular &t) {r += t.r; if(r >= m) r -= m; return *this;}
        modular operator -= (const modular &t) {r -= t.r; if(r < 0) r += m; return *this;}
        modular operator + (const modular &t) const {return modular(*this) += t;}
        modular operator - (const modular &t) const {return modular(*this) -= t;}
        modular operator *= (const modular &t) {return *this = *this * t;}
        modular operator /= (const modular &t) {return *this = *this / t;}
        
        bool operator == (const modular &t) const {return r == t.r;}
        bool operator != (const modular &t) const {return r != t.r;}
        bool operator < (const modular &t) const {return r < t.r;}
        
        explicit operator int() const {return r;}
        int64_t rem() const {return 2 * r > m ? r - m : r;}
    };
    
    istream& operator >> (istream &in, modular &x) {
        return in >> x.r;
    }
    
    ostream& operator << (ostream &out, modular const& x) {
        return out << x.r;
    }
    
    vector<modular> F(maxn), RF(maxn);
    
    template<typename T>
    T fact(int n) {
        static bool init = false;
        if(!init) {
            F[0] = T(1);
            for(int i = 1; i < maxn; i++) {
                F[i] = F[i - 1] * T(i);
            }
            init = true;
        }
        return F[n];
    }
    
    template<typename T>
    T rfact(int n) {
        static bool init = false;
        if(!init) {
            RF[maxn - 1] = T(1) / fact<T>(maxn - 1);
            for(int i = maxn - 2; i >= 0; i--) {
                RF[i] = RF[i + 1] * T(i + 1);
            }
            init = true;
        }
        return RF[n];
    }
}

using namespace algebra;

using base = modular;


void solve() {
    int d;
    cin >> d;
    vector<base> A(d + 1), B(d + 1);
    copy_n(istream_iterator<base>(cin), d + 1, begin(A));
    copy_n(istream_iterator<base>(cin), d + 1, begin(B));
    base s = 0, k2 = 0;
    auto coef = [&](int i) {
        return base((d - i) % 2 ? -1 : 1) * rfact<base>(i) * rfact<base>(d - i);
    };
    for(int i = 0; i <= d; i++) {
        s += (A[i] - B[i]) * coef(i) * (d * (d + 1) / 2 - i);
        k2 += (A[i] + B[i]) * coef(i);
    }
    s *= base(2) / (k2 * d);
    cout << s << "\n";
}

Instead of caring about the positions of all the toys, we only need to care about the position of the special toy with index $$$k$$$. The other toys can be treated as undistinguishable.

The intended way of solving this problem is playing the game in the webpage, trying to come up with some simple combinations of operations that make the special toy move to another position in a predictable way. Using these building blocks in a smart way, finding a way to move the special toy to the topleft.

As the size of the grid can be up to $$$100\,000$$$ and we can make $$$1\,000\,000$$$ moves, we will be aiming for a solution which does a linear number of moves.

There are lots of potential solutions which use a linear number of moves, here is a relatively painless one:

Do casework on $$$k$$$:

• Case $$$1$$$: If $$$1 \leq k < \frac{n-1}{2}$$$, we initally make one $$$\texttt{R}$$$ button press to align the toys with the right boundary. After this, there is an easy pattern to expose all the toys in the left halve, one by one: $$$\texttt{DRURDRUR...}$$$ repeated. When the special toy is exposed, the repeating pattern is stopped, and $$$\texttt{DL}$$$ are pressed. Toy $$$k$$$ will be moved to the topleft corner.

• Case $$$2$$$: If $$$k = \frac{n-1}{2}$$$, the puzzle can be solved in two moves: $$$\texttt{DL}$$$.

• Case $$$3$$$: If $$$\frac{n-1}{2} < k \leq n-2$$$, we try to reduce back to case $$$1$$$, by moving the special toy to the left halve, and ensuring that all other toys are in the top row. Using symmetry, we can apply case $$$1$$$ to $$$k^\prime = n-1 - k$$$, but mirror all horizontal moves, to move the toy to the topright corner. The other toys are no longer all in the top row. To fix this, the last pattern we need is again $$$\texttt{DRURDRUR...}$$$ repeated. After a while of repeating this, all toys will be in the right halve of the board, occupying the top and bottom row. To finish moving the special toy (which stayed in the topright corner), we do the buttons presses $$$\texttt{LDRU}$$$. All toys end up in the top row, and the special toy will be at position $$$k_\text{new} = \frac{n-1}{2} - 1$$$, so this successfully reduces to case $$$1$$$.

How many moves does this take? In case $$$1$$$ the pattern $$$\texttt{DRUR}$$$ needs to be repeated at most $$$\approx \frac{n}{2}$$$ times. In case $$$3$$$, we need to use the first pattern $$$\frac{n}{2}$$$ times, and we use the second pattern $$$\frac{n}{2}$$$ times. We reduce down to case $$$1$$$, but luckily the special toy is already close to the correct position, so only a constant number of extra moves are done.

So in total, this solution uses $$$O(1) + \max \left( 4\frac{n}{2}, 4 \cdot 2 \frac{n}{2} \right) = 4n + O(1)$$$ moves. So this solution fits well within the constraints, although it is pretty wasteful.

Bonus: Can you prove that the optimal number of moves needed in the worstcase (over all $$$k$$$) for a width of $$$n$$$ is $$$\Omega(n)$$$? We only did some testing of small cases, with a bruteforce BFS solution, and found that the worstcase is around $$$n/2$$$ button presses.

#include "bits/stdc++.h"
using namespace std;

int main() {
    int n,k; cin >> n >> k;
    --k;
    int half = (n-3)/2;
    string res = "";
    if(k==half) {
        res = "DL";
    } else {
        while(true) {
            if(k<half) {
                res+="R";
                int need = half-1-k;
                while(need--) {
                    res+="DRUR";
                }
                res+="DL";
                break;
            } else {
                int need = k-half-1;
                while(need--) {
                    res+="LDLU";
                }
                res+="LDR";
                for(int i=0;i<half+1;++i) {
                    res+="DRUR";
                }
                res+="LDRU"; 
                k = half-1;
            }
        }
    }
    cout << res << '\n';
}

// split into 1, ..., k and k+1, ..., n
pair<int, istring> check_k(istring const& a, int k) {
    int n = size(a);
    istring A(n, 0), B(n, 0);
    for(int i = 0; i < n; i++) {
        if(i <= k) {
            A[min(k, i + 1)] += a[i];
        } else {
            B[min(n - k - 2, n - i)] += a[i];
        }
    }
    // multiply by 2^(n - i - 1) instead of dividing by 2^i
    reverse(all(A));
    reverse(all(B));
    int carry = 0;
    // subtract A from B and normalize base 2
    for(int i = 0; i < n; i++) {
        B[i] -= A[i] - carry;
        carry = B[i] >> 1; // floor(B[i] / 2)
        B[i] &= 1;
    }
    if(carry < 0) {
        return {-1, {}}; // it's always possible to make it positive
    }
    while(carry) {
        B.push_back(carry & 1);
        carry >>= 1; 
    }
    while(!B.empty() && B.back() == 0) {
        B.pop_back();
    }
    reverse(all(B));
    return {(int)size(B) - n, B};
}

const int mod = 1e9 + 7;

int bpow(int x, int n) {
    if(!n) {
        return 1;
    } else if(n % 2) {
        return int64_t(x) * bpow(x, n - 1) % mod;
    } else {
        return bpow(int64_t(x) * x % mod, n / 2);
    }
}

int inv(int x) {
    return bpow(x, mod - 2);
}

void solve() {
    int n;
    cin >> n;
    istring a(n, 0);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(all(a));
    auto cand = check_k(a, 0);
    int cnt = 0;
    for(int i = 1; i < n; i++) {
        if(a[i] != a[i - 1]) {
            cand = max(cand, check_k(a, i - 1));
            cnt++;
            if(cnt == 30) {
                break;
            }
        }
    }
    cnt = 0;
    istring b = a;
    reverse(all(b));
    for(int i = 1; i < n; i++) {
        if(b[i] != b[i - 1]) {
            cand = max(cand, check_k(a, n - i - 1));
            cnt++;
            if(cnt == 30) {
                break;
            }
        }
    }
    auto [sz, ansf] = cand;
    int ans = 0;
    for(size_t i = 0; i < size(ansf); i++) {
        ans = (ans + bpow(2, (mod - 1) + (sz - i)) * ansf[i]) % mod;
    }
    cout << ans << "\n";
}

map<char, int> to[maxn];
int len[maxn], link[maxn];
int last, sz = 1;

void add_letter(char c) {
    int p = last;
    last = sz++;
    len[last] = len[p] + 1;
    for(; to[p][c] == 0; p = link[p]) {
        to[p][c] = last;
    }
    int q = to[p][c];
    if(q != last) {
        if(len[q] == len[p] + 1) {
            link[last] = q;
        } else {
            int cl = sz++;
            len[cl] = len[p] + 1;
            link[cl] = link[q];
            to[cl] = to[q];
            link[last] = link[q] = cl;
            for(; to[p][c] == q; p = link[p]) {
                to[p][c] = cl;
            }
        }
    }
}

int term[maxn];
int used[maxn], comp[maxn], dist[maxn];
vector<int> in_comp[maxn];

void dfs(int v = 0) {
    comp[v] = v;
    dist[v] = 0;
    used[v] = 1;
    for(auto [c, u]: to[v]) {
        if(!used[u]) {
            dfs(u);
        }
        if(to[v].size() == 1 && !term[v]) {
            comp[v] = comp[u];
            dist[v] = dist[u] + 1;
        }
    }
    in_comp[comp[v]].push_back(v);
}

void solve() {
    string s;
    cin >> s;
    for(auto c: s) {
        add_letter(c);
    }
    for(int p = last; p; p = link[p]) {
        term[p] = 1;
    }
    term[0] = 1;
    dfs();
    int64_t ans = 0;
    for(int v = 0; v < sz; v++) {
        if(in_comp[v].size()) {
            int m = in_comp[v].size();
            sort(all(in_comp[v]), [&](int a, int b) {
                return dist[a] > dist[b];
            });
            vector<int64_t> A(m), B(m);
            for(int i = 0; i < m; i++) {
                int u = in_comp[v][i];
                int L = dist[u];
                int R = L + len[link[u]];
                // L' must be larger than R
                int cnt = len[u] - len[link[u]];
                A[i] = (int64_t)cnt * L;
                B[i] = cnt;
                if(i > 0) {
                    A[i] += A[i - 1];
                    B[i] += B[i - 1];
                }
                auto it = upper_bound(all(in_comp[v]), R, [&](int R, int b) {
                    return R > dist[b];
                }) - begin(in_comp[v]);
                if(it) {
                    it--;
                    ans += A[it] - B[it] * R;
                }
            }
        }
    }
    cout << ans << "\n";
}