What happens when $$$k$$$ is even? What happens when $$$k$$$ is odd?

for _ in range(int(input())):
    n, k = list(map(int, input().split()))
    a = list(map(lambda x: int(x) % 2, input().split()))
    b = list(map(lambda x: int(x) % 2, input().split()))
 
    if k % 2 == 0:
        print("YES" if a.count(0) <= b.count(0) else "NO")
    else:
        print("YES" if b.count(0) <= a.count(0) else "NO")

What must all strings whose answer is ``NO'' look like?

import sys
 
for _ in range(int(input())):
    n = int(input())
    print("?", 1, n)
    sys.stdout.flush()
    ct = int(input())
    if ct == 0:
        print("! NO")
        continue
    print("?", 1, ct)
    sys.stdout.flush()
    x = int(input())
    if x == ct:
        print("! NO")
    else:
        print("! YES")

Where is it useful to "cut" the array to decrease the gap value?

Consider separately the cases where the gap value is unique, occurs twice, and occurs three or more times.

#include <bits/stdc++.h>
using namespace std;
 
template <class T, T (*f)(T, T), T (*unit)()> struct Seg {
	vector<T> s; int n;
	Seg(int n = 0, T def = unit()) : s(2*n, def), n(n) {}
	void update(int pos, T val) {
		for (s[pos += n] = val; pos /= 2;)
			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
	}
	T query(int b, int e) { // query [b, e)
		T ra = unit(), rb = unit();
		for (b += n, e += n; b < e; b /= 2, e /= 2) {
			if (b % 2) ra = f(ra, s[b++]);
			if (e % 2) rb = f(s[--e], rb);
		}
		return f(ra, rb);
	}
 
	T get(int x) { return s[x+n]; }
};
 
using T = int;
T f(T a, T b) { return max(a, b); }
T unit() { return 0; }
 
int main() {
    cin.tie(0)->sync_with_stdio(0);
 
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
 
        Seg<T, f, unit> rmq(n - 1);
        vector<int> mx;
        int val = -1;
        for (int i = 0; i < n - 1; i++) {
            rmq.update(i, abs(a[i + 1] - a[i]));
            if (abs(a[i + 1] - a[i]) > val)
                mx = {i}, val = abs(a[i + 1] - a[i]);
            else if (abs(a[i + 1] - a[i]) == val)
                mx.push_back(i);
        }
 
        if (mx.size() >= 3) {
            cout << val << "\n";
            continue;
        }
 
        auto calc = [&](int i, int j) {
            int v2 = 2 * rmq.query(i, j);
            if (i > 0) v2 = max({v2, rmq.query(0, i - 1), abs(a[i - 1] - 2 * a[j])});
            if (j < n - 1) v2 = max({v2, rmq.query(j + 1, n - 1), abs(a[j + 1] - 2 * a[i])});
            return v2;
        };
 
        if (mx.size() == 2) {
            int i = mx[0], j = mx[1];
            cout << min(val, calc(i + 1, j)) << "\n";
            continue;
        }
 
        int i = mx[0];
        for (int j = 0; j <= i; j++) {
            val = min(val, calc(j, i));
        }
        for (int j = i + 1; j < n; j++) {
            val = min(val, calc(i + 1, j));
        }
 
        cout << val << "\n";
    }
}

Suppose that $$$|S|\ge 2$$$. Can you say anything about the minimum number of unstable elements in it?

Consider DP.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
 
const ll MOD = 998244353;
 
mt19937 rng(time(0));
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		vector<int> a(n);
		rep(i,0,n) cin >> a[i];
 
		vector<bool> s;
		s.push_back(true);
		for (int i = 1; i < n; i++) {
			if (a[i] == a[i - 1] + 1) {
				s.push_back(1);
			} else if (a[i] == a[i - 1] + 2) {
				s.push_back(0); s.push_back(1);
			} else {
				s.push_back(0); s.push_back(0); s.push_back(1);
			}
		}
		s.push_back(0);
 
		int m = sz(s);
		assert(m < 3 * n);
		ll ans = (1ll * (n + 1) * n / 2) % MOD; // n + (n C 2)
		vector<ll> dp1(m + 1, 1); // ((1110)|(110))*
		vector<ll> dp2(m + 1, 0); // 10((1110)|(110))*
		for (int i = 1; i < m; i++) {
			if (s[i - 1]) dp2[i + 1] = 1;
			if (i >= 2 && s[i - 1] && s[i - 2]) {
				dp1[i + 1] += dp1[i - 2];
				dp2[i + 1] += dp2[i - 2];
			}
			if (i >= 3 && s[i - 1] && s[i - 2] && s[i - 3]) {
				dp1[i + 1] += dp1[i - 3];
				dp2[i + 1] += dp2[i - 3];
			}
			dp1[i + 1] %= MOD;
			dp2[i + 1] %= MOD;
			ans += dp1[i + 1] - 1 + dp2[i + 1];
		}
		for (int i = 1; i < m; i++) {
			if (s[i - 1]) { // can end in 10
				ans += dp1[i - 1] + dp2[i - 1];
			}
		}
		s.push_back(0); s.push_back(0);
		// we've overcounted 2 * 10, 110, 101 substrings
		for (int i = 0; i < m; i++) {
			if (s[i]) ans -= 2;
			if (s[i] && s[i + 1]) ans -= 1;
			if (s[i] && s[i + 2]) ans -= 1;
		}
 
		cout << ((ans + MOD) % MOD) << "\n";
 
	}
 
}

What should the array look like after applying your operations? (Equivalently, what operations should you apply?)

Consider casing on the second largest element.

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	while (t--) {
		int n; ll L; cin >> n >> L;
		vector<ll> a(n);
		rep(i,0,n) cin >> a[i];
		sort(all(a));
		if (L == 1) {
			cout << accumulate(all(a), 0ll) - a[n - 1] << "\n";
			continue;
		}
		if (a[n - 1] * a[n - 2] < L) {
			cout << "0\n";
			continue;
		}
		ll x = a[n - 1];
		ll y = 1;
		while ((y + 1) * (y + 1) < L) ++y;
		int start = n - 2;
		ll curr = 0;
 
		auto mx = [&](ll z) {
			if (z == 0) return 0ll;
			return max(0ll, x - (L - 1) / z);
		};
 
		while (start >= 0 && a[start] >= y) {
			curr += (a[start] - y);
			--start;
		}
		ll ans = curr + mx(y);
		--y;
		for (; y >= 0; --y) {
			curr += (n - 2 - start);
			while (start >= 0 && a[start] >= y) --start;
			ans = min(ans, curr + mx(y));
		}
		cout << ans << "\n";
	}
}

The graph is quite huge. Do you need all of it?

Try to show that you only need to keep around $$$O(m + n)$$$ edges while preserving the shortest path.

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
 
mt19937 rng(time(0));
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
	int t; cin >> t;
	while (t--) {
		int n, m; cin >> n >> m;
		int w, x, y, z; cin >> w >> x >> y >> z; --w, --x, --y, --z;
		vector<array<int, 2>> edges(m);
		vector<array<int, 2>> v;
		rep(i,0,n) {
			v.push_back({w, i});
			v.push_back({y, i});
			v.push_back({i, i});
		}
 
		rep(i,0,m) {
			int a, b; cin >> a >> b; --a, --b;
			edges[i] = {a, b};
			v.push_back({a, b});
			v.push_back({b, a});
		}
 
		sort(all(v));
		v.resize(unique(all(v)) - v.begin());
 
		int N = sz(v);
 
		auto find = [&](int i, int j) -> int {
			return lower_bound(all(v), array{i, j}) - v.begin();
		};
 
		vector<vector<int>> h(N);
		for (auto [a, b] : edges) {
			int wa = find(w, a), wb = find(w, b),
			    ya = find(y, a), yb = find(y, b),
			    aa = find(a, a), ab = find(a, b),
			    ba = find(b, a), bb = find(b, b);
 
			for (auto [p1, p2] : vector{array{wa, wb}, {ya, yb}, {aa, ab}, {ba, bb}, {ab, ba}}) {
				h[p1].push_back(p2);
				h[p2].push_back(p1);
			}
		}
 
		vector<int> dist(N, -1);
		queue<pair<int, int>> q;
		q.emplace(find(w, x), 0);
		while (!q.empty()) {
			auto [vtx, d] = q.front();
			q.pop();
			if (dist[vtx] >= 0) continue;
			dist[vtx] = d;
			for (auto a : h[vtx]) {
				if (dist[a] < 0) q.emplace(a, d + 1);
			}
		}
 
		cout << dist[find(y, z)] << "\n";
	}
}

Can you upper bound the answer?

The answer is at most $$$2\cdot 25 - 1 = 49$$$. Can you use this fact to construct a solution running in time $$$O(n\cdot 2^{49})$$$?

Please refer to the previous hint first. Can you make your solution faster to $$$O(n\cdot \varphi^{49})$$$?

Consider Meet In The Middle.

#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define sq(a) ((a)*(a))
 
#define per(i,a,b) for (int i = (b)-1; i >= a; i--)
#define rep(i,a,b) for (int i=a; i<b; i++)
 
#define FOR(i,a,b) for (int i=a; i<b; i++)
#define F0R(i,a) for (int i=0; i<a; i++)
#define ROF(i,a,b) for (int i = (b)-1; i >= a; i--)
#define R0F(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << endl, 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << endl;
#define _ << " _ " <<
 
#define ll long long
 
template<class T> bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool ckmax(T&a, T&b) { bool B = a < b; a = max(a,b); return B; }
 
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ld,ld> pld;
typedef complex<ld> cd;
 
typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<vector<int>> vvi;
 
const ld PI = acos(-1.0);
const ld EPS = 1e-7;
const int MOD = 998244353;
 
const int MX = 25;
const int BIG = 100;
 
void solve() {
  int n; cin >> n;
  vector<int> a(n);
  rep(i, 0, n) {
    cin >> a[i];
  }
  
  if (*min_element(all(a)) == 0) {
      cout << "0" << "\n";
      return;
  }
 
  vector<pair<int, int>> seen;
 
  auto left = [&](auto && self, int i, int cost, int v) {
    int op = v ^ a[i];
    seen.push_back({op, cost});
 
    if (i == 0) return;
    if (cost + 1 <= MX) {
      self(self, i - 1, cost + 1, op);
    }
 
    if (cost + 2 <= MX) {
      self(self, i - 1, cost + 2, v);
    }
  };
 
  int best = BIG;
 
  auto right = [&](auto && self, int i, int cost, int v) {
    int op = v ^ a[i];
 
    auto it = upper_bound(all(seen), mp(op, -1));
    if (it != seen.end()) {
      auto [u, v] = *it;
      if (u == op) best = min(best, cost + v - 1);
    }
 
    if (i + 1 == n) return;
    if (cost + 1 <= MX) {
      self(self, i + 1, cost + 1, op);
    }
 
    if (cost + 2 <= MX) {
      self(self, i + 1, cost + 2, v);
    }
  };
 
  if (n > MX) {
    best = 2 * MX - 1;
  }
 
  rep(i, 0, n - 1) {
    seen.clear();
    seen.reserve(514228);
 
    left(left, i, 1, 0);
    assert (sz(seen) <= 514228);
    sort(all(seen));
 
    right(right, i + 1, 1, 0);
  }
 
  if (best == BIG) best = -1;
  cout << best << endl;
}
 
int32_t main() { FAST
  int t;
  cin >> t;
 
  while (t--) solve();
 
  return 0;
}

Recall how one wins in Nim. Next, note that this problem essentially reduces to solving each prefix quickly.

This is, under the hood, a matroid problem. For each new value, try to construct an "exchange" graph using the matroid basis exchange property to determine if it's possible to insert the element.

Please refer to the previous hint first. It gives an $$$O(n^3\log^2 n)$$$ time algorithm. To improve this, consider if you need the full graph or if you can "thin" it.

Make sure your XOR basis operations are of optimal complexity.

#include <bits/stdc++.h>
using namespace std;
 
constexpr int LOG = 14;
 
struct xor_basis {
	vector<int> inner;
	vector<int> base;
	vector<int> comb;
 
	xor_basis(): base(LOG), comb(LOG) {}
 
	int represent(int mask) {
		int c = 0;
		for (int i = 0; i < LOG; i++) {
			if (!(mask & (1 << i))) continue;
			if (!base[i]) return -1;
			mask ^= base[i], c ^= comb[i];
		}
		return c;
	}
 
	bool independent(int mask) {
		for (int i = 0; i < LOG; i++) {
			if (!(mask & (1 << i))) continue;
			if (!base[i]) return true;
			mask ^= base[i];
		}
		return false;
	}
 
	void swap(int out, int in) {
		int pos = find(inner.begin(), inner.end(), out) - inner.begin();
		int c = represent(in);
		inner[pos] = in;
		for (int i = 0; i < LOG; i++) if (comb[i] >> pos & 1) comb[i] ^= c ^ (1 << pos);
	}
 
	bool insert(int mask) {
		int sv = mask, c = 1 << inner.size();
		for (int i = 0; i < LOG; i++) {
			if (!(mask & (1 << i))) continue;
 
			if (!base[i]) {
				base[i] = mask, comb[i] = c, inner.push_back(sv);
				return true;
			}
			mask ^= base[i], c ^= comb[i];
		}
		return false;
	}
};
 
void solve() {
    int n; cin >> n;
	vector<int> a(n), s(n);
	for (int i = 0; i < n; i++) cin >> a[i];
 
	vector<xor_basis> bases;
	bases.emplace_back();
 
	auto add = [&](int idx) {
		for (int i = 0; i < bases.size(); i++) {
	        if (bases[i].independent(s[idx])) {
	            bases[i].insert(s[idx]); // special case
	            return;
	        }
	    }
 
		int N = 2*n + bases.size();
 
		vector<int> smap(N, -1);
		for (int i = 0; i < bases.size(); i++) for (auto x : bases[i].inner) smap[x - 1] = i;
		for (int i = 0; i < bases.size(); i++) smap[i + 2*n] = i;
 
		vector<int> par(N, -2);
		vector<int> q;
		q.push_back(s[idx] - 1); par[s[idx] - 1] = -1;
		int found = -1;
		for (int head = 0; head < q.size(); head++) {
			int vtx = q[head];
 
            int x = vtx + 1, next_idx = (smap[vtx] + 1) % bases.size();
 
            if (x == s[idx] || bases.size() > 1) {
                if (bases[next_idx].independent(x)) {
                    par[2 * n + next_idx] = vtx, found = 2 * n + next_idx;
                    break;
                }
				int z = bases[next_idx].represent(x);
				for (int p = 0; p < bases[next_idx].inner.size(); p++) {
					if (z >> p & 1) {
						int y = bases[next_idx].inner[p] - 1;
						if (par[y] == -2) par[y] = vtx, q.push_back(y);
					}
				}
            }
		}
 
		if (found < 0) { // easy case -- no path
			bases.emplace_back();
			bases.back().insert(s[idx]);
			return;
		} else {
			int p = par[found];
			assert(bases[smap[found]].insert(p + 1));
			while (p + 1 != s[idx]) {
				int prev = par[p];
				bases[smap[p]].swap(p + 1, prev + 1);
				p = prev;
			}
		}
	};
 
	auto print_sol = [&]() {
		cout << bases.size() << "\n";
		for (const auto& base : bases) {
			cout << base.inner.size();
			for (auto x : base.inner) {
				cout << " " << x;
			}
			cout << "\n";
		}
	};
 
	for (int i = 0; i < n; i++) {
		int k = (i == 0 ? 0 : bases.size());
		s[i] = a[i] ^ k;
		add(i);
	}
	print_sol();
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
 
    int t; cin >> t;
    while (t--) solve();
}