n = int(input())
if n % 9 == 0:
	print(n)
else:
	print(-1)

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

void solve(){
    int n,ans=0;
    cin >> n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    vector <int> eq;
    for(int i=0;i<n;i++){
        if(arr[i]==arr[(i+1)%n]){
            eq.push_back(i);
            ans++;
        }
    }
    for(int i=0;i<eq.size();i++){
        if(arr[(eq[i]+1)%n]==arr[eq[(i+1)%eq.size()]]&&(eq[i]+1)%n!=eq[(i+1)%eq.size()]){
            ans++;
        }
    }
    if(ans==0){
        ans=1;
    }
    cout << ans << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

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

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

    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> head(n + 1, -1);
    vector<int> to(max(0, 2 * (n - 1)));
    vector<int> nxt(max(0, 2 * (n - 1)));
    int ec = 0;

    auto add_edge = [&](int u, int v) {
        to[ec] = v;
        nxt[ec] = head[u];
        head[u] = ec++;
    };

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    // root the tree at 1
    vector<int> parent(n + 1, 0);
    vector<int> order;
    order.reserve(n);

    order.push_back(1);
    parent[1] = -1;

    for (size_t idx = 0; idx < order.size(); ++idx) {
        int u = order[idx];
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (v == parent[u]) continue;
            parent[v] = u;
            order.push_back(v);
        }
    }

    long long ans = 0;

    for (int u = 1; u <= n; ++u) {
        int parity = (a[u] == 0); // need[u] = 1 xor a[u]

        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (parent[v] == u) {
                parity ^= (a[v] == 0);
            }
        }

        ans += parity;
    }

    cout << ans << '\n';
    return 0;
}

The maximum of lines always make a convex function. This means that if $$$M = 0$$$, $$$f(x)$$$ is guaranteed to be convex.

Observe that $$$f(x)$$$ taking the minimum at any point creates a "spike" or "dip" in the function, causing it to no longer be convex. This means that in order for $$$f(x)$$$ to be convex, the minimum of all $$$N$$$ lines must be equal to the maximum of all $$$N$$$ lines at every $$$x \in S$$$. In other words, all $$$N$$$ lines must intersect at every $$$x \in S$$$.

Case $$$M = 0$$$: As the hint states, $$$f(x)$$$ is guaranteed to be convex.

Case $$$M = 1$$$: Check if all $$$N$$$ lines intersect at $$$S_0$$$ by plugging in $$$S_0$$$ into every line. $$$f(x)$$$ is convex if and only if all lines have the same value at $$$S_0$$$.

Case $$$M \gt = 2$$$ (assume $$$S$$$ has at least 2 distinct values): Since different lines cannot intersect at more than one point, if more than one distinct line is given, $$$f(x)$$$ cannot be convex. Otherwise, if all $$$N$$$ lines given are the same (in which case they intersect at every point), $$$f(x)$$$ is convex.

The final time complexity is $$$O(N+M).$$$

#include <bits/stdc++.h>
using namespace std;
#define int long long

bool solve() {
    int n,m; cin >> n >> m;
    vector<pair<int,int>> a(n); vector<int> s(m);
    for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
    for(int i = 0; i < m; i++) cin >> s[i];

    if(m==0) return true;

    else if(m==1) {
        int y = a[0].first*s[0]+a[0].second;

        for(int i = 1; i < n; i++) if(a[i].first*s[0]+a[i].second != y) return false;
        return true;
    }

    else {
        for(int i = 1; i < n; i++) if(a[i] != a[0]) return false;
        return true;
    }
}

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

    int t; cin >> t;
    while(t--) {
        if(solve()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

If a red node is connected to a green node, then every red node is connected to a green node.

Following Hint 1, note that if a blue node is distance 2 from a green node, that means that every blue node is distance 2 from a green node. This is because if the path is blue node 1 -> red node 2 -> green node 3, that means that every red node is connected to a green node and also every blue node is connected to a red node, so it must be distance 2 from a green node.

Following this logic, lets set our origin node to be $$$x$$$ and let's find the distance from $$$x$$$ to any red node. It's clear by an extension of the above reasoning that if $$$x$$$ is distance $$$k$$$ from a red node, that means that every node of the same color as $$$x$$$ is distance $$$k$$$ from a red node. This means that the nodes themselves don't matter, but only the colors! And this makes the problem easier because there are only $$$L\le 500$$$ colors.

It follows that we can just find the color of the node that we are in, and find the distance to each of the exit colors, and take the minimum distance. To do this fast, we can precompute the distances using multiple BFS's or Floyd-Warshall. The solution runs in $$$O(N + L^2 + Q\cdot\sum l)$$$ time.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, e, L;
    cin >> n >> e >> L;

    vector<pair<int,int>> raw_edges(e);
    for (auto& [u, v] : raw_edges) cin >> u >> v;

    vector<int> label(n + 1);
    for (int i = 1; i <= n; i++) cin >> label[i];

    // Build label graph
    vector<set<int>> label_adj_set(L + 1);
    for (auto [u, v] : raw_edges) {
        int a = label[u], b = label[v];
        if (a != b) {
            label_adj_set[a].insert(b);
            label_adj_set[b].insert(a);
        }
    }
    vector<vector<int>> label_adj(L + 1);
    for (int a = 1; a <= L; a++)
        label_adj[a].assign(label_adj_set[a].begin(), label_adj_set[a].end());

    // BFS from each label
    const int INF = 1e9;
    vector<vector<int>> dist(L + 1, vector<int>(L + 1, INF));
    for (int src = 1; src <= L; src++) {
        dist[src][src] = 0;
        queue<int> bfs;
        bfs.push(src);
        while (!bfs.empty()) {
            int a = bfs.front(); bfs.pop();
            for (int b : label_adj[a]) {
                if (dist[src][b] == INF) {
                    dist[src][b] = dist[src][a] + 1;
                    bfs.push(b);
                }
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int v, l;
        cin >> v >> l;
        vector<int> labs(l);
        for (int& a : labs) cin >> a;

        int ans = INF;
        for (int a : labs)
            ans = min(ans, dist[label[v]][a]);
        cout << (ans == INF ? -1 : ans) << "\n";
    }

    return 0;
}

If the turtles' paths do not intersect, they form the shape of a spiral!

Let $$$A$$$ and $$$B$$$ contain the individual line segments of the red and blue turtles' paths. In which case $$$A_i$$$ and $$$B_i$$$ are the line segments created by the red and blue turtle during the $$$i-th$$$ step, respectively.

Following hint 1, observe that the spiral shape implies that for any $$$i$$$, if $$$A_i$$$ does intersect with any line segments from $$$B$$$, it will at least intersect $$$B_{i+3}$$$. Similarly, if $$$B_i$$$ does intersect with any line segments from $$$A$$$, it will at least intersect $$$A_{i+3}$$$.

The above observation proves that it is sufficient to check for each $$$i$$$ if $$$A_i$$$ intersects with $$$B_{i+3}$$$ and if $$$B_i$$$ intersects with $$$A_{i+3}$$$.

The final time complexity is $$$O(N+M).$$$

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<pair<int,int>> dirs = {{0,-1},{-1,0},{0,1},{1,0}};

vector<vector<int>> buildPaths(const vector<int>& moves, int currDir) {
    vector<vector<int>> paths; // Each vector in the form of (x1,y1,x2,y2)
    pair<int,int> pos = {0,0};

    bool firstMove = true; // Flag to skip the initial (0,0)

    for(int d : moves) {
        pair<int,int> newPos = {pos.first+d*dirs[currDir].first, pos.second+d*dirs[currDir].second};

        if(firstMove) {
            pos.first+=1*dirs[currDir].first;
            pos.second+=1*dirs[currDir].second;
        }
        firstMove = false;

        currDir = (currDir+1)%(dirs.size());

        paths.push_back({pos.first,pos.second,newPos.first,newPos.second});
        pos = newPos;
    }
    return paths;
}

bool intersect(vector<int> A, vector<int> B) {
    if(A[0] != A[2] || B[1] != B[3]) swap(A,B); // For convenience, make A the horizontal one and B the vertical one

    if(A[1] > A[3]) swap(A[1],A[3]); if(B[0] > B[2]) swap(B[0],B[2]);

    // Check if B falls between A
    if(!(B[1] >= A[1] && B[1] <= A[3])) return false;

    // Check if A falls between B
    if(!(A[0] >= B[0] && A[0] <= B[2])) return false;

    return true;
}

bool solve() {
    int n,m; cin >> n >> m;
    vector<int> a(n), b(m);
    for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < m; i++) cin >> b[i];

    vector<vector<int>> pathsA = buildPaths(a,0), pathsB = buildPaths(b,2);

    // Only check between A[i] and B[i+3] and vice versa
    for(int i = 0; i < n && i+3 < m; i++) if(intersect(pathsA[i],pathsB[i+3])) return true;
    for(int i = 0; i < m && i+3 < n; i++) if(intersect(pathsA[i+3],pathsB[i])) return true;

    return false;
}

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

    int t; cin >> t;
    while(t--) {
        if(solve()) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    return 0;
}

Consider the graph formed by treating constraints as edges.

We need a tree. What happens when we take a spanning tree of each connected component?

Read the hints.

Let $$$\operatorname{path}(u, v)$$$ be the path XOR between nodes $$$u$$$ and $$$v$$$ on the final tree. First, we observe that the path XOR between two nodes is equal to the XOR of the path XORs between the two nodes and an intermediate node, that is,

\begin{equation*}\operatorname{path}(u, w) = \operatorname{path}(u, v) \oplus \operatorname{path}(v, w)\end{equation*} for three nodes $$$u$$$, $$$v$$$, and $$$w$$$.

Proof. We root the tree at $$$v$$$. Then, edges from $$$\operatorname{lca}(u, w)$$$ to $$$v$$$ appear in both paths, so they don't contribute to the overall path XOR. The remaining edges precisely form the path from $$$u$$$ to $$$w$$$.

This relationship extends to any number of intermediate nodes, i.e.,

\begin{equation*} \operatorname{path}(u, w) = \operatorname{path}(u, v_1) \oplus \operatorname{path}(v_1, v_2) \oplus \cdots \oplus \operatorname{path}(v_k, w)\end{equation*}

for $$$k$$$ intermediate nodes $$$v_1, v_2, \dots, v_k$$$.

As a consequence, when we treat the constraints $$$\operatorname{path}(u, v) = w$$$ as edges, the path XOR between any two nodes in each connected component will be the same for all valid trees if any tree exists. Therefore, it suffices to take a spanning tree of each connected component and check that each constraint is satisfied. Note that since this graph may be disconnected, we will need to add edges of arbitrary weight between two nodes.

Creating the spanning tree can be done in multiple ways. The model solution uses a DSU to only add an edge if it unites two connected components.

To verify that the constraints are satisfied, we need to be able to find the path XOR between two nodes. This can be done efficiently using

\begin{equation*}\operatorname{path}(u, v) = \operatorname{path}(u, 1) \oplus \operatorname{path}(1, v)\end{equation*}

from above, so we need to only need to compute path XORs starting from $$$1$$$ or any other arbitrary node.

Time complexity: $$$\mathcal{O}(n\alpha(n))$$$ (with DSU) or $$$\mathcal{O}(n)$$$ (without DSU)

/**
 * @author n685
 * @date Saturday, April 11, 2026 2:14:29 PM
 */
#include <bits/stdc++.h>

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

struct DSU {
  std::vector<int> val;
  int cnt{};
  DSU() = default;
  explicit DSU(int n) : val(n, -1), cnt(n) {}
  int find(int i) { return val[i] < 0 ? i : (val[i] = find(val[i])); }
  bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v)
      return false;
    if (val[u] > val[v])
      std::swap(u, v);
    val[u] += val[v];
    val[v] = u;
    --cnt;
    return true;
  }
  bool connected(int u, int v) { return find(u) == find(v); }
  int size(int u) { return -val[find(u)]; }
  int count() const { return cnt; }
};

void tc() {
  int n, m;
  std::cin >> n >> m;

  DSU dsu(n);
  std::vector<std::tuple<int, int, int>> ans, constr(m);
  std::vector<std::vector<std::pair<int, int>>> adj(n);
  for (auto& [u, v, w] : constr) {
    std::cin >> u >> v >> w;
    --u;
    --v;
    if (dsu.unite(u, v)) {
      ans.emplace_back(u, v, w);
      adj[u].emplace_back(w, v);
      adj[v].emplace_back(w, u);
    }
  }

  int pre = -1;
  for (int i = 0; i < n; ++i) {
    if (dsu.val[i] < 0) {
      if (pre != -1) {
        ans.emplace_back(pre, i, 0);
        adj[pre].emplace_back(0, i);
        adj[i].emplace_back(0, pre);
      }
      pre = i;
    }
  }

  std::vector<int> path(n);
  auto dfs = [&](auto&& self, int node, int par) -> void {
    for (auto [w, i] : adj[node]) {
      if (i == par)
        continue;
      path[i] = path[node] ^ w;
      self(self, i, node);
    }
  };
  dfs(dfs, 0, -1);

  for (auto [u, v, w] : constr) {
    if ((path[u] ^ path[v]) != w) {
      std::cout << "NO\n";
      return;
    }
  }

  std::cout << "YES\n";
  for (auto [u, v, w] : ans)
    std::cout << u + 1 << ' ' << v + 1 << ' ' << w << '\n';
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int t;
  std::cin >> t;
  for (int i = 1; i <= t; ++i)
    tc();
}

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

static const int MAXA = 1'000'000;

struct Occ {
	int p;
	int e;
};

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

	int n, k;
	cin >> n >> k;

	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];

	// smallest prime factor sieve
	vector<int> spf(MAXA + 1, 0), primes;
	spf[1] = 1;
	for (int i = 2; i <= MAXA; ++i) {
		if (!spf[i]) {
			spf[i] = i;
			primes.push_back(i);
		}
		for (int p : primes) {
			long long v = 1LL * i * p;
			if (v > MAXA || p > spf[i]) break;
			spf[(int)v] = p;
		}
	}

	// collect one entry per distinct prime factor per number
	vector<Occ> occs;
	occs.reserve(7 * n);

	for (int x : a) {
		while (x > 1) {
			int p = spf[x];
			int e = 0;
			while (x % p == 0) {
				x /= p;
				++e;
			}
			occs.push_back({p, e});
		}
	}

	sort(occs.begin(), occs.end(), [](const Occ& lhs, const Occ& rhs) {
		return lhs.p < rhs.p;
	});

	vector<int> gcdPrimes;
	vector<int> gcdExps;
	vector<vector<int>> gcdCosts;

	for (size_t l = 0; l < occs.size(); ) {
		size_t r = l;
		int p = occs[l].p;

		array<int, 21> hist{};
		hist.fill(0);

		long long totalExp = 0;
		int occCount = 0;

		while (r < occs.size() && occs[r].p == p) {
			hist[occs[r].e]++;
			totalExp += occs[r].e;
			++occCount;
			++r;
		}

		hist[0] = n - occCount;

		int emax = (int)(totalExp / n);
		if (emax > 0) {
			vector<int> cost(emax + 1, 0);

			long long cntLess = hist[0];
			long long sumLess = 0;
			for (int e = 1; e <= emax; ++e) {
				cost[e] = (int)(1LL * e * cntLess - sumLess);
				if (e < (int)hist.size()) {
					cntLess += hist[e];
					sumLess += 1LL * e * hist[e];
				}
			}

			gcdPrimes.push_back(p);
			gcdExps.push_back(emax);
			gcdCosts.push_back(move(cost));
		}

		l = r;
	}

	int m = (int)gcdPrimes.size();
	vector<int> best(k + 1, 0);

	function<void(int, int, int)> dfs = [&](int idx, int value, int used) {
		if (used > k) return;
		if (idx == m) {
			best[used] = max(best[used], value);
			return;
		}

		int cur = 1;
		for (int e = 0; e <= gcdExps[idx]; ++e) {
			int nxtUsed = used + gcdCosts[idx][e];
			if (nxtUsed <= k) {
				dfs(idx + 1, value * cur, nxtUsed);
			}
			cur *= gcdPrimes[idx];
		}
	};

	dfs(0, 1, 0);

	for (int i = 1; i <= k; ++i) {
		best[i] = max(best[i], best[i - 1]);
	}

	for (int i = 1; i <= k; ++i) {
		cout << best[i] << (i == k ? '\n' : ' ');
	}

	return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define all(x) begin(x), end(x)
using i4 = array<int, 4>;
using i2 = array<int, 2>;

int getd() {
    char c;
    cin >> c;
    if (c == 'R') return 0;
    if (c == 'L') return 1;
    if (c == 'U') return 2;
    return 3;
}

void solve() {
    int n;
    cin >> n;
    vector xy(2, vector<int>(n));
    vector<int> t(n), d(n, -1);
    map<int, vector<i2>> m[2];
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> xy[0][i] >> xy[1][i];
        if (t[i] == 3) d[i] = getd();
        for (int c = 0; c < 2; c++) m[c][xy[c^1][i]].push_back({xy[c][i], i});
    }

    // make graph
    // seg: c, y, x1, x2
    vector<vector<int>> adj(n);
    vector<i4> eseg[n], oseg[n];
    for (int c = 0; c < 2; c++) {
        for (auto& [y, s] : m[c]) {
            sort(all(s));
            int sz = size(s);
            for (int c2 = 0; c2 < 2; c2++) {
                int cd = 2*c + c2;
                for (int ix = 0; ix < sz-1; ix++) {
                    int i = s[ix][1], j = s[ix+1][1];
                    if (t[i] == 2) continue;
                    if (t[i] == 3 && d[i] != cd) continue;
                    auto [x1, x2] = minmax(xy[c][i], xy[c][j]);
                    i4 seg = {c, y, x1, x2};
                    if (t[j] == 2) {
                        oseg[i].push_back(seg);
                        continue;
                    }
                    adj[i].push_back(j);
                    eseg[i].push_back(seg);
                }

                // arev
                reverse(all(s));
            }
        }
    }

    // find cc
    vector<vector<int>> radj(n);
    for (int i = 0; i < n; i++) for (int j : adj[i]) radj[j].push_back(i);

    auto dfs = [&]() {
        vector<bool> v(n);
        v[0] = 1;
        queue<int> q{{0}};
        while (size(q)) {
            int i = q.front();
            q.pop();
            for (auto j : adj[i]) {
                if (v[j]) continue;
                v[j] = 1;
                q.push(j);
            }
        }
        return v;
    };
    auto v = dfs();
    swap(adj, radj);
    auto v2 = dfs();
    swap(adj, radj);
    for (int i = 0; i < n; i++) v[i] = v[i] & v2[i];

    // segments
    map<int, set<i2>> segs[2];
    auto ins = [&](i4 &seg) {
        auto [c, y, x1, x2] = seg;
        segs[c][y].insert({x1, x2});
    };
    for (int i = 0; i < n; i++) {
        if (!v[i]) continue;
        for (auto &s : oseg[i]) ins(s);
        for (int k = 0; k < size(adj[i]); k++) {
            int j = adj[i][k];
            if (v[j]) ins(eseg[i][k]);
        }
    }

    int ans = 0;
    for (int c = 0; c < 2; c++) {
        for (auto& [y, s] : segs[c]) {
            for (auto it = next(begin(s)); it != end(s); it++) {
                auto [cl, cr] = *it;
                auto [pl, pr] = *prev(it);
                if (cl <= pr) {
                    s.erase(prev(it));
                    s.erase(it);
                    it = s.insert({pl, max(pr, cr)}).first;
                }
            }
            for (auto [x1, x2] : s) ans += x2 - x1 + 1;
        }
    }

    // segment intersection
    vector<i4> ev;
    for (auto& [y, s] : segs[0]) {
        for (auto [x1, x2] : s) {
            ev.push_back({x1, 0, y, 0});
            ev.push_back({x2, 2, y, 0});
        }
    }
    for (auto& [x, s] : segs[1]) {
        for (auto [y1, y2] : s) {
            ev.push_back({x, 1, y1, y2});
        }
    }
    sort(all(ev));
    oset<int> os;
    for (auto& [x, t, y1, y2] : ev) {
        if (t == 0) os.insert(y1);
        else if (t == 2) os.erase(y1);
        else {
            int c1 = os.order_of_key(y1), c2 = os.order_of_key(y2 + 1);
            ans -= c2 - c1;
        }
    }

    // ans
    cout << ans << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
}

For a cow travelling either North or South, what's the bound on the number of seconds they can survive? What about a cow travelling East or West?

You should have found that the bounds are $$$n$$$ and $$$m$$$ respectively. What is $$$\min(n, m)$$$ bounded by?

Try reducing the grid to a state where only cows travelling on the same axis (e.g. North/South or East/West) are present.

Make sure to read the hints, as they are important to the solution.

As mentioned in Hint 3, we want to reach a state where all cows are either going North/South or East/West, as simulating the state for these cows can be done efficiently. Thus, we first want to process all cow collisions between cows travelling along different axis.

The times at which such collisions can occur is bounded by $$$\min(n, m)$$$. It turns out that $$$\min(n, m) \leq \sqrt{nm}$$$, since $$$\min(n, m) \cdot \min(n, m) \leq nm$$$. This allows us to simulate $$$\sqrt{nm}$$$ seconds of the process, resulting in a grid where all cows travel alongst the same axis.

Now, the only question is efficiently calculating the answer for our reduced grid. For the sake of simplicity, we can consider solving this problem for a line of cows traveling East or West, as this is equivalent to solving the reduced grid.

We sweep from left to right on this line, and apply the following algorithm:

• If this cow goes towards the West, we find the nearest cow whose position has the same parity that is travelling East. We can calculate their collision time by dividing their distance by 2. If such a cow does not exist, we know the current cow simply goes off the grid.
• If this cow goes towards the East, we put it into a stack of cows, making sure to differentiate cows by their parity.

Distinguishing cows by their parity is necessary, as two cows that are adjacent and travelling towards each other do not intersect.

With that, we solve the problem in $$$\mathcal{O}(nm\sqrt{nm})$$$, which runs comfortably in time.

#include <bits/stdc++.h>

using ll = long long;

char dirs[]{'N', 'E', 'S', 'W'};
int dr[]{-1, 0, 1, 0};
int dc[]{0, 1, 0, -1};

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::array<int, 3>> cows(k);
    std::vector cur_cow(n, std::vector<int>(m, -1));
    for (int i = 0; i < k; i++) {
        auto &[r, c, d] = cows[i];
        char dir;
        std::cin >> r >> c >> dir;
        --r, --c;
        for (int t = 0; t < 4; t++) {
            if (dirs[t] == dir) {
                d = t;
            }
        }

        cur_cow[r][c] = i;
    }

    std::vector<int> times(k);

    const int sims = 1 + std::min(n, m);
    for (int t = 0; t < sims; t++) {
        std::vector<std::array<int, 2>> del;
        std::vector nxt(n, std::vector<int>(m, -1));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (cur_cow[i][j] == -1) continue;
                int ind = cur_cow[i][j];
                ++times[ind];

                int dir = cows[ind][2];
                int nr = i + dr[dir];
                int nc = j + dc[dir];
                if (0 <= nr && nr < n && 0 <= nc && nc < m) {
                    if (nxt[nr][nc] != -1) del.push_back({nr, nc});
                    nxt[nr][nc] = ind;
                }
            }
        }

        for (const auto &[i, j] : del) {
            nxt[i][j] = -1;
        }

        cur_cow = std::move(nxt);
    }

    auto sim = [&](std::vector<int> lane, bool is_vert) -> void {
        std::array<std::vector<int>, 2> go_r{};
        for (int i = 0; i < lane.size(); i++) {
            if (lane[i] == -1) continue;
            int d = cows[lane[i]][2];
            bool is_l = is_vert ? dr[d] == -1 : dc[d] == -1;
            if (is_l) {
                if (!go_r[i % 2].empty()) {
                    int j = go_r[i % 2].back();
                    go_r[i % 2].pop_back();

                    times[lane[i]] += (i - j) / 2;
                    times[lane[j]] += (i - j) / 2;
                } else {
                    times[lane[i]] += i + 1;
                }
            } else {
                go_r[i % 2].push_back(i);
            }
        }

        for (int t = 0; t < 2; t++) {
            for (int i : go_r[t]) {
                times[lane[i]] += lane.size() - i;
            }
        }
    };

    if (n < m) {
        for (int i = 0; i < n; i++) {
            sim(cur_cow[i], false);
        }
    } else {
        for (int j = 0; j < m; j++) {
            std::vector<int> arr;
            for (int i = 0; i < n; i++) {
                arr.push_back(cur_cow[i][j]);
            }

            sim(arr, true);
        }
    }

    for (int i = 0; i < k; i++) {
        std::cout << times[i] << " \n"[i == k - 1];
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}

import sys

data = sys.stdin.read().split()
it = iter(data)

dirs = {'N': 0, 'E': 1, 'S': 2, 'W': 3}
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

out = []

def solve():
    n, m, k = int(next(it)), int(next(it)), int(next(it))

    cows = [[0, 0, 0] for _ in range(k)]
    cur_cow = [[-1] * m for _ in range(n)]

    for i in range(k):
        r, c = int(next(it)) - 1, int(next(it)) - 1
        d = dirs[next(it)]
        cows[i] = [r, c, d]
        cur_cow[r][c] = i

    times = [0] * k

    sims = 1 + min(n, m)
    for _ in range(sims):
        del_list = []
        nxt = [[-1] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                ind = cur_cow[i][j]
                if ind == -1:
                    continue
                times[ind] += 1

                d = cows[ind][2]
                nr = i + dr[d]
                nc = j + dc[d]
                if 0 <= nr < n and 0 <= nc < m:
                    if nxt[nr][nc] != -1:
                        del_list.append((nr, nc))
                    nxt[nr][nc] = ind

        for i, j in del_list:
            nxt[i][j] = -1

        cur_cow = nxt

    def sim(lane, is_vert):
        go_r = [[], []]
        for i, cow_idx in enumerate(lane):
            if cow_idx == -1:
                continue
            d = cows[cow_idx][2]
            is_l = (dr[d] == -1) if is_vert else (dc[d] == -1)
            if is_l:
                if go_r[i % 2]:
                    j = go_r[i % 2].pop()
                    times[lane[i]] += (i - j) // 2
                    times[lane[j]] += (i - j) // 2
                else:
                    times[lane[i]] += i + 1
            else:
                go_r[i % 2].append(i)

        lane_len = len(lane)
        for t in range(2):
            for i in go_r[t]:
                times[lane[i]] += lane_len - i

    if n < m:
        for i in range(n):
            sim(cur_cow[i], False)
    else:
        for j in range(m):
            sim([cur_cow[i][j] for i in range(n)], True)

    out.append(' '.join(map(str, times)))

t = int(next(it))
for _ in range(t):
    solve()

sys.stdout.write('\n'.join(out) + '\n')

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

static const int MOD = 1'000'000'007;

static int mod_pow(long long a, long long e) {
    long long r = 1;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return (int)r;
}

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

    int n, k;
    cin >> n >> k;

    vector<int> head(n + 1, -1);
    vector<int> to(max(0, 2 * (n - 1)));
    vector<int> nxt(max(0, 2 * (n - 1)));
    int ec = 0;

    auto add_edge = [&](int u, int v) {
        to[ec] = v;
        nxt[ec] = head[u];
        head[u] = ec++;
    };

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    // factorials for nCk modulo MOD
    vector<int> fact(n + 1), ifact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = 1LL * fact[i - 1] * i % MOD;
    ifact[n] = mod_pow(fact[n], MOD - 2);
    for (int i = n; i >= 1; --i) ifact[i - 1] = 1LL * ifact[i] * i % MOD;

    auto C = [&](int s) -> int {
        if (s < k) return 0;
        return 1LL * fact[s] * ifact[k] % MOD * ifact[s - k] % MOD;
    };

    // root the tree at 1
    vector<int> parent(n + 1, 0), order;
    order.reserve(n);
    parent[1] = -1;

    vector<int> st;
    st.reserve(n);
    st.push_back(1);

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order.push_back(u);

        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (v == parent[u] || parent[v] != 0) continue;
            parent[v] = u;
            st.push_back(v);
        }
    }

    vector<int> sz(n + 1, 1);
    for (int i = n - 1; i > 0; --i) {
        int u = order[i];
        sz[parent[u]] += sz[u];
    }

    vector<int> delta(n + 1, 0), ans(n + 1, 0);
    long long base = 0;

    for (int v = 2; v <= n; ++v) {
        int s = sz[v];
        int left = C(s);
        int right = C(n - s);
        base += left;
        if (base >= MOD) base -= MOD;

        delta[v] = right - left;
        if (delta[v] < 0) delta[v] += MOD;
    }

    ans[1] = (int)base;

    for (int i = 1; i < n; ++i) {
        int v = order[i];
        int p = parent[v];
        int x = ans[p] + delta[v];
        if (x >= MOD) x -= MOD;
        ans[v] = x;
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << (i == n ? '\n' : ' ');
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int mod=1000000007;
constexpr int i2=500000004;

static inline int c0(int p){
    return (p*p+3*p+2)%mod;
}

static inline int c1(int p){
    return (2*p+3)%mod;
}

struct Point {
    int pos,val;
    bool operator<(const Point& o) const{
        return pos<o.pos;
    }
};

struct Query {
    int pos;
    bool is_left;
    int id;
    bool operator<(const Query& o) const{
        return pos<o.pos;
    }
};

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<Point> points;
    points.reserve(4*n);
    while(n--){
        int op,l,r;
        cin >> op >> l >> r;
        int len=r-l+1;
        if(op==1){
            points.push_back({l,1});
            points.push_back({l+1,mod-1});
            points.push_back({r+1,mod-1});
            points.push_back({r+2,1});
        }
        else{
            points.push_back({l,1});
            points.push_back({r+1,mod-len-1});
            points.push_back({r+2,len});
        }
    }
    sort(points.begin(),points.end());
    points.push_back({mod, 0});
    int q;
    cin >> q;
    int ans[q];
    for(int i=0;i<q;i++) ans[i]=0;
    vector<Query> query;
    query.reserve(2*q);
    for(int i=0;i<q;i++){
        int l,r;
        cin >> l >> r;
        query.push_back({l-1,1,i});
        query.push_back({r,0,i});
    }
    sort(query.begin(),query.end());
    int s0=0,s1=0,s2=0,ptr=0;
    for(int i=0;i<2*q;i++){
        while(points[ptr].pos<=query[i].pos){
            int k=points[ptr].pos,d=points[ptr].val;
            s0=(s0+d)%mod; s1=(s1+k*d)%mod; s2=(s2+(k*k%mod)*d)%mod;
            ptr++;
        }
        int p=query[i].pos;
        int ret=((c0(p)*s0-c1(p)*s1+s2)%mod+mod)%mod*i2%mod;
        if(query[i].is_left) {
            if(ret>0) ret=mod-ret;
        }
        ans[query[i].id]+=ret;
        if(ans[query[i].id]>=mod) ans[query[i].id]-=mod;
    }
    for(int i=0;i<q;i++){
        cout << ans[i] << '\n';
    }
    return 0;
}

A node can be removed if it has no neighboring nodes of type 1 that are directly connected to a node of type 2. Note that since we are only removing nodes, a node can never become unsafe to remove if it was previously safe. Furthermore, if a valid removal order exists, it is impossible for us to reach a state where we cannot continue a valid removable order (and unremovable nodes still remain), so we do not need to worry about backtracking when constructing a removal order; if we find a node that we can remove, we should remove it immediately.

So, we can easily precompute the number of adjacent nodes of type 2 for each node in the graph. Then, repeatedly loop through all unremoved nodes in the graph. For each node, check all of its unremoved type 1 neighbors; if none of them have an adjacent node of type 2, we can safely add it to our removal order. If the node we just removed is a type 2, we can subtract 1 from the precomputed type 2 adjacency count for all of its neighbors. Continue until all nodes are marked as removed or we fail to find any valid removable node in a single pass. If all nodes have been removed, output the removal order we have found; otherwise, a valid removal order cannot exist.

Since in the worst case, only one node is removed per pass across $$$n$$$ passes, this algorithm runs in O($$$n^2$$$), which is more than sufficient to pass $$$N, M \lt = 200$$$.

Note that when we remove a node, only a specific subset of its neighbors become potentially available for removal — namely,

The final time complexity is O($$$n+m$$$), since each edge is traversed a constant number of times.

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

void solve(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> adj(n+1);
    vector<bool> a(n+1),active(n+1);
    vector<int> stable(n+1),safe(n+1);
    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        a[i]=x-1;
        stable[i]=0;
        safe[i]=0;
        active[i]=1;
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++) for(int u:adj[i]) if(a[u]) stable[i]++;
    for(int i=1;i<=n;i++) for(int u:adj[i]) if((!a[u])&&(stable[u]>a[i])) safe[i]++;
    queue<int> q;
    for(int i=1;i<=n;i++) if(!safe[i]) q.push(i);
    vector<int> ans;
    while(q.size()>0){
        int f=q.front();
        q.pop();
        if(!active[f]) continue;
        active[f]=0;
        if(a[f]){
            for(int u:adj[f]){
                if(active[u]&&!a[u]){
                    stable[u]--;
                    for(int v:adj[u]){
                        if(active[v]&&stable[u]==a[v]){
                            safe[v]--;
                            if(!safe[v]) q.push(v);
                        }
                    }
                }
            }
        }
        else{
            for(int v:adj[f]){
                if(active[v]&&stable[f]>a[v]){
                    safe[v]--;
                    if(!safe[v]) q.push(v);
                }
            }
        }
        ans.push_back(f);
    }
    if(ans.size()!=n){
        cout << -1 << '\n';
        return;
    }
    for(int u:ans) cout << u << ' ';
    cout << '\n';
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

Observe that, for a valid construction, all paths from node $$$1$$$ to any other node must have the same length. This is the shortest path.

Try writing out each edge as a constraint on the distance values from node $$$1$$$. Do these inequalities look familiar?

As mentioned in the hints, the distance from node $$$1$$$ to any other node must be the same across all paths. Let this distance be $$$\text{dist}[u]$$$, denoting the distance from node $$$1$$$ to node $$$u$$$.

A directed edge $$$u \rightarrow v$$$ with weight constraint $$$[l, r]$$$ then implies that:

Doing a bit of rearranging, we get:

These inequalities actually enforce the same thing as an edge in a shortest path algorithm! An edge $$$(u, v, w)$$$ in a shortest paths problem forces $$$\text{dist}[v]$$$ to be at most $$$\text{dist}[u] + w$$$, which is essentially what these inequalities are doing.

So, we can construct a graph with these edges. How can we construct our answer, or determine it's impossible to do so?

Since each path from $$$1$$$ to $$$u$$$ has the same distance, we know that the weight of an edge from $$$u$$$ to $$$v$$$ must have weight $$$\text{dist}[v] - \text{dist}[u]$$$, otherwise it would violate the condition. So, if we were unable to calculate the true shortest paths from node $$$1$$$, it would be impossible to construct an answer.

A construction does not exist when the graph has a negative cycle, since a negative cycle would make the distances infinitely negative. The easiest way to check for a negative cycle while calculating distances is using the Bellman-Ford algorithm, but there are other ways of calculating it.

We'll omit the proof for why a negative cycle implies a construction is impossible, but it essentially boils down to chaining together inequalities and making sure that the final result is mathematically valid.

Since we run Bellman-Ford on our graph, the time complexity of the solution is $$$\mathcal{O}(nm)$$$.

#include <bits/stdc++.h>

using ll = long long;

constexpr ll inf = 1e18;

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::array<int, 4>> edges(m);
    for (auto &[u, v, l, r] : edges) {
        std::cin >> u >> v >> l >> r;
        u--, v--;
    }

    std::vector<ll> dist(n, inf);
    dist[0] = 0;

    for (int i = 1; i <= n; i++) {
        auto cpy = dist;
        for (const auto &[u, v, l, r] : edges) {
            dist[v] = std::min(dist[v], dist[u] + r);
            dist[u] = std::min(dist[u], dist[v] - l);
        }

        if (i == n && cpy != dist) {
            std::cout << "-1\n";
            return;
        }
    }

    for (int i = 0; i < m; i++) {
        const auto &[u, v, l, r] = edges[i];
        std::cout << dist[v] - dist[u] << " \n"[i == m - 1];
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        u, v, l, r = map(int, input().split())
        edges.append((u - 1, v - 1, l, r))

    INF = float('inf')
    dist = [INF] * n
    dist[0] = 0

    for i in range(1, n + 1):
        cpy = dist[:]
        for u, v, l, r in edges:
            if dist[u] < INF:
                dist[v] = min(dist[v], dist[u] + r)
            if dist[v] < INF:
                dist[u] = min(dist[u], dist[v] - l)
        if i == n and cpy != dist:
            print(-1)
            return

    results = []
    for u, v, l, r in edges:
        results.append(str(dist[v] - dist[u]))
    print(' '.join(results))

t = int(input())
for _ in range(t):
    solve()

How could divide and conquer be applied to this problem?

In order to solve this problem, we need to use a quadtree (consider it as similar to a 2D segment tree). More specifically, every time we have a grid, we divide it into $$$4$$$ roughly equal size quadrants and in this problem, we try to maintain the connectivity problem between the quadrants of the different levels.

Initially, we should first build the quadtree when given the initial state of the grid. Consider the following when building a specific quadrant:

For the base case of a grid smaller than or equal to $$$3*3$$$, assumed as the overall grid is size of $$$n*n$$$, what we could do is simply enumerate all of the internal connections of the grid and maintain it with a dsu.

For larger grids, what we should do is inherit the information from the lower layers of the sub-quadrants edges, as the inner connectivity cannot be changed with the outside information and only consider the additional information given by the connectivity of the edges from the sub-quadrants that would "intersect" with others affecting the dsu states and process of connecting the dsu only need to be one directional, i.e. only consider the two edges are correspond one to one the grids updating their dsu status.

After recursing by first building the base cases and building the higher levels based on the lower levels, we have the initial state of the quadtree.

To update a specific grid, we would first update the smallest quadrant on a level that contains the grid and gradually work the way up updating every single quadrant in the different levels that contains the flipped grid.

As the initialization of the quadtree is $$$O(n^2)$$$ and each update is $$$O(n)$$$, thus the overall complexity is $$$O(n(n+q))$$$.

#include<bits/stdc++.h>
#define pb push_back
using ll = long long;
using lb = long double;
const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
const int MX = 2009, int_max = 0x3f3f3f3f;
struct {
  template<class T>
  operator T() {
    T x; std::cin >> x; return x;
  }
} in;
using namespace std;
int grid[MX][MX];
int cc[11][MX][MX];
int dsu[MX*MX];
int c_vis[MX*MX];
int n, q;
inline int find(int u){
    return dsu[u]<0?u:dsu[u]=find(dsu[u]);
}
inline void Union(int a, int b){
    a = find(a); b = find(b);
    if(a == b)
        return;
    if(dsu[a] > dsu[b])
        swap(a, b);
    dsu[a] += dsu[b];
    dsu[b] = a;
}
vector<int> vis;
inline int comp(int x,int y){
    return x*n+y;
}
inline void merge(int x1, int x2, int y1, int y2, int op){
    if(x2 - x1 <= 3 || y2 - y1 <= 3){
        for(int i = x1; i<x2; i++)
            for(int j = y1; j<y2; j++)
                if(grid[i][j]){
                    if(i+1 < x2 && grid[i+1][j]) Union(comp(i, j), comp(i+1, j));
                    if(j+1 < y2 && grid[i][j+1]) Union(comp(i, j), comp(i, j+1));
                }
        for(int i = x1; i<x2; i++)
            for(int j = y1; j<y2; j++)
                cc[op][i][j] = find(comp(i, j));
        for(int i = x1; i<x2; i++)
            for(int j = y1; j<y2; j++)
                dsu[comp(i, j)] = -1;
    }else{
        int mx = (x1+x2)/2;
        int my = (y1+y2)/2;
        for(int i : {x1, mx-1, mx, x2-1})
            for(int j = y1; j<y2; j++){
                cc[op][i][j] = cc[op+1][i][j];
                if(!c_vis[cc[op][i][j]]) vis.pb(cc[op][i][j]);
                c_vis[cc[op][i][j]] = 1;
            }
        for(int j : {y1, my-1, my, y2-1})
            for(int i = x1; i<x2; i++){
                cc[op][i][j] = cc[op+1][i][j];
                if(!c_vis[cc[op][i][j]]) vis.pb(cc[op][i][j]);
                c_vis[cc[op][i][j]] = 1;
            }
        for(int i : {x1, mx-1, mx, x2-1})
            for(int j = y1; j<y2; j++)
                if(grid[i][j]){
                    if(i == mx-1 && grid[i+1][j]) Union(cc[op][i][j], cc[op][i+1][j]);
                    if(j+1 < y2 && grid[i][j+1]) Union(cc[op][i][j], cc[op][i][j+1]);
                }
        for(int j : {y1, my-1, my, y2-1})
            for(int i = x1; i<x2; i++)
                if(grid[i][j]){
                    if(i+1 < x2 && grid[i+1][j]) Union(cc[op][i][j], cc[op][i+1][j]);
                    if(j == my-1 && grid[i][j+1]) Union(cc[op][i][j], cc[op][i][j+1]);
                }
        for(int i : {x1, mx-1, mx, x2-1})
            for(int j = y1; j<y2; j++)
                cc[op][i][j] = find(cc[op][i][j]);
        for(int j : {y1, my-1, my, y2-1})
            for(int i = x1; i<x2; i++)
                cc[op][i][j] = find(cc[op][i][j]);
        for(int x : vis){
            c_vis[x] = 0;
            dsu[x] = -1;
        }
        vis.clear();
    }
}
inline void go(int x, int y, int x1, int x2, int y1, int y2, int op){
    if(x2 - x1 > 3 && y2 - y1 > 3){
        int mx = (x1 + x2)/2;
        int my = (y1 + y2)/2;
        if(x < mx && y < my)
            go(x, y, x1, mx, y1, my, op+1);
        else if(x < mx && y >= my)
            go(x, y, x1, mx, my, y2, op+1);
        else if(x >= mx && y < my)
            go(x, y, mx, x2, y1, my, op+1);
        else
            go(x, y, mx, x2, my, y2, op+1);
    }
    merge(x1, x2, y1, y2, op);
}
inline void build(int x1, int x2, int y1, int y2, int op){
    if(x2 - x1 > 3 && y2 - y1 > 3){
        int mx = (x1 + x2)/2;
        int my = (y1 + y2)/2;
        build(x1, mx, y1, my, op+1);
        build(x1, mx, my, y2, op+1);
        build(mx, x2, y1, my, op+1);
        build(mx, x2, my, y2, op+1);
    }
    merge(x1, x2, y1, y2, op);
}
int pre=0;
string answer(){
    pre*=2;
    if(grid[0][0] == 0 || grid[n-1][n-1] == 0)
        return "NO";
    if(cc[0][0][0] == cc[0][n-1][n-1]){
        pre++;
        return "YES";
    }
    else
        return "NO";
}
int num;
int xx[40009];
int yy[40009];
void solve(){
    memset(dsu, -1, sizeof(dsu));
    n = in;
    for(int i = 0; i<n; i++){
        string s = in;
        for(int j = 0; j<n; j++){
            grid[i][j] = s[j]-'0';
        }
    }
    build(0, n, 0, n, 0);
    q=in;
    num=in;
    num=(1<<num);
    for(int i=0;i<num;i++)
        xx[i]=in,yy[i]=in;
    for(int i= 1; i<=q; i++){
        int x = in, y = in;
        x+=xx[pre],y+=yy[pre];
        if(x>n)
            x-=n;
        if(y>n)
            y-=n;
        x--, y--;
        grid[x][y] ^= 1;
        go(x, y, 0, n, 0, n, 0);
        cout << answer() << "\n";
        pre%=num;
    }
}
signed main(){
    solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const long long int MOD=1000000007;
const long long int nul=(1LL<<62);

struct Range{
    ll L,R;
};

struct Config{
    Range r;
    ll empty_pos;
};

struct Node{
    Config cfg;
    ll ws;
    int prev,next;
};

bool intersect(Range a,Range b){
    if(a.R<b.L||b.R<a.L) return 0;
    return 1;
}

ll flodiv(ll a,ll b){
    if(a>=0||a%b==0) return a/b;
    else return a/b-1;
}

ll modd(ll a,ll b){
    return (a%b+b)%b;
}

Config newran(ll newws,ll newt){
    if(newt%2){
        ll fd=flodiv(newws,newt),m=modd(newws,newt);
        if(m==0) return {{fd-newt/2,fd+newt/2},nul};
        else return {{fd-newt/2,fd+newt/2+1},fd+newt/2+1-m};
    }
    else{
        ll fd=flodiv(newws,newt),m=modd(newws,newt);
        if(m<=newt/2) return {{fd-newt/2,fd+newt/2},fd-m};
        else if(m==newt/2) return {{fd-newt/2+1,fd+newt/2},nul};
        else return {{fd-newt/2+1,fd+newt/2+1},fd+newt+1-m};
    }
}

ll sos(ll c){
    c=modd(c,MOD);
    return (((((c*(c+1))%MOD)*(2*c+1))%MOD)*((MOD+1)/6))%MOD;
}

ll contrib(Config p){
    if(p.empty_pos==nul) return modd(sos(p.r.R)-sos(p.r.L-1),MOD);
    p.empty_pos=modd(p.empty_pos,MOD);
    return modd(sos(p.r.R)-sos(p.r.L-1)-((p.empty_pos*p.empty_pos)%MOD),MOD);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    ll initsum=0;
    Node link[n+2];
    link[0]={{{-nul,-nul},nul},nul,-1,1};
    link[n+1]={{{nul,nul},nul},nul,n,n+2};
    for(int i=1;i<=n;i++){
        long long int pos, siz;
        cin >> pos >> siz;
        link[i]={{{pos-siz/2,pos+siz/2},((siz%2)?(nul):(pos))},pos*siz,i-1,i+1};
        initsum+=(((pos*pos)%MOD)*siz)%MOD;
        initsum%=MOD;
    }
    int ptr=1;
    while(ptr<=n){
        int nex=link[ptr].next;
        if(intersect(link[ptr].cfg.r,link[nex].cfg.r)){
            ll newws=link[ptr].ws+link[nex].ws;
            ll newt=link[ptr].cfg.r.R-link[ptr].cfg.r.L
                +link[nex].cfg.r.R-link[nex].cfg.r.L
                +(link[ptr].cfg.empty_pos==nul)+(link[nex].cfg.empty_pos==nul);
            link[ptr].cfg=newran(newws,newt);
            link[ptr].ws=newws;
            int newn=link[nex].next;
            link[ptr].next=newn;
            link[newn].prev=ptr;
            ptr=link[ptr].prev;
        }
        else{
            ptr=link[ptr].next;
        }
    }
    ptr=1;
    ll finalsum=0;
    while(ptr<=n){
        finalsum+=contrib(link[ptr].cfg);
        finalsum%=MOD;
        ptr=link[ptr].next;
    }
    long long int ans=(modd(finalsum-initsum,MOD)*((MOD+1)/2))%MOD;
    cout << ans << '\n';
    return 0;
}

Is there a greedy that determines the optimal independent set?

How can we make the $$$K$$$ grids "independent"?

Think game theory. What does the graph also represent?

We can first notice that choosing the independent set can be done greedily from maximum to minimum $$$S$$$ due to $$$NM^{K \cdot S} \gt NM^{K \cdot (S-1)} (NM^K - 1)$$$. The issue now is the large value of $$$K$$$, which calls for finding a way to think of each of the $$$K$$$ boards independently. To do this, consider the following two player-game:

Initially, each grid, numbered $$$1$$$ to $$$K$$$, has one token on one of the cells. Alice and Bob take turns alternately. On each player's turn, the current player chooses some grid $$$G$$$ $$$(1 \leq G \leq K)$$$ and moves the token on cell $$$(i, j)$$$ and moves it to either $$$(k, j)$$$ $$$(0 \leq k \lt i)$$$ or $$$(i, k)$$$ $$$(0 \leq k \lt j)$$$ on grid $$$G$$$. Note that this is equivalent to traversing the graph with each move moving closer to $$$((0, 0), \dots, (0, 0))$$$. The current player loses when they cannot move.

The key realization here is that the game states in which the current player is losing is exactly our desired independent set in the graph. Because there are $$$K$$$ disjoint boards in the setting of a game, we can now think of each token position as some Grundy number. Let $$$\text{SG}(i, j)$$$ be the Grundy number if the token is at $$$(i, j)$$$. From this transformation, we see that a node $$$(P_1, P_2, \dots, P_K)$$$ is in our desired independent set if and only if $$$\text{SG}(P_1) \oplus \text{SG}(P_2), \cdots, \text{SG}(P_{K-1})\oplus \text{SG}(P_K) = 0$$$, where $$$\oplus$$$ is the bitwise XOR operator.

We can then let

Now, denoting the $$$\oplus$$$ convolution operator as $$$*$$$, the answer is $$$(\underbrace{C * ... * C}_{\text{K times}})_0$$$. Naive binary exponentiation can compute this in $$$\mathcal{O}((N + M)^2 \log K)$$$ given that $$$\max(SG(i, j))$$$ scales on the order of $$$\mathcal{O}(N + M)$$$.

These are already some very tough observations, but this still only gets $$$60/100$$$ points. There are still two more key parts to achieve a full solution.

The first part is to optimize calculating Grundy numbers of each cell, in which a naive solution takes $$$\mathcal{O}(NM (N + M))$$$. If we write a brute force and look for patterns, what we find is that $$$\text{SG}(i, j) = i \oplus j$$$. This can be proven by induction by showing that if this property holds for all cells in the square $$$((0, 0), (2^k-1, 2^k-1))$$$, then it also holds for all values in the square $$$((0, 0), (2^{k+1}-1, 2^{k+1}-1))$$$. The full proof is left as an exercise for the reader.

The second part is to optimize the $$$\oplus$$$ convolution. To do this, we must use $$$\oplus$$$ $$$\text{FWHT}$$$ (Fast WalshΓÇôHadamard transform). Denoting $$$\text{FWHT}$$$ as $$$F$$$ for short, we note that $$$C * C = F^{-1}(F(C) \cdot F(C))$$$. Applying $$$\text{FWHT}$$$ naively with binary exponentiation obtains an $$$\mathcal{O}((N + M) \log (N + M)\log K)$$$ solution.

However, we can make this faster by more closely analyzing the convolution.

Canceling the $$$F$$$ and $$$F^{-1}$$$, we get

From this, by induction, we can notice that $$$\underbrace{C * ... * C}_{\text{K times}} = F^{-1}\left(F(C)^K\right)$$$. This allows us to use binary exponentiation on each index of $$$C$$$ and only $$$2$$$ calls of $$$\text{FWHT}$$$, solving the problem in $$$\mathcal{O}((N + M) \cdot (\log (N + M) + \log K))$$$.

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

constexpr int mod = 998244353, inv2 = (mod + 1) / 2;
typedef long long ll;

int add(int x, int y) {
    if (x + y >= mod) return x + y - mod;
    if (x + y < 0) return x + y + mod;
    else return x + y;
}

int mul(int x, int y) {
    return (ll)x * y % mod;
}

int power(int x, int p) {
    int res = 1;
    while (p) {
        if (p & 1) res = mul(res, x);
        x = mul(x, x);
        p >>= 1;
    }

    return res;
}

void FWHT(vector<int> &a, bool inv = false) {
    int sz = a.size();
    for (int len = 1; 2 * len <= sz; len <<= 1) {
        for (int i = 0; i < sz; i += 2 * len) {
            for (int j = i; j < i + len; j++) {
                int x = a[j], y = a[j + len];
                if (!inv) a[j] = add(x, y), a[j + len] = add(x, -y);
                else a[j] = mul(add(x, y), inv2), a[j + len] = mul(add(x, -y), inv2);
            }
        }
    }
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int x = n * m, y = 1;
    while (y < x) y <<= 1;
    int v = power(x, k);
    vector<vector<int>> a(n, vector<int>(m));
    vector<int> f(y);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            f[i ^ j] = add(f[i ^ j], power(v, a[i][j]));
        }
    }

    FWHT(f);
    for (int i = 0; i < y; i++) {
        f[i] = power(f[i], k);
    }

    FWHT(f, 1);
    cout << f[0] << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

If we have a square $$$s$$$ and another square $$$S$$$ that completely covers $$$s$$$, then the intersection of $$$s$$$ and $$$S$$$ is a valid square.

Recall that we can pick any valid square, so long as the coordinates for both axes are in the range $$$[-10^9, 10^9]$$$.

Note that all coordinates for our squares are in the range $$$[-10^9, 10^9]$$$. Also, consider that we are allowed to print any square that satisfies the condition in the problem statement.

Consider Hint 1: if another square completely covers one square, then their intersection remains a square. Thus, the easiest construction is for our square $$$S$$$ to cover all the input squares completely.

Because of this, we can print a square with its lower-left corner at $$$(-10^9, -10^9)$$$ and its upper-right corner at $$$(10^9, 10^9)$$$.

inf = 10**9
print(-inf, -inf, inf, inf)

How do you find the optimal path? Think greedy.

The $$$\text{MEX}$$$ is the smallest number not present in the path. You already have the optimal path. Recall that all values from $$$0$$$ to $$$n + 1$$$ are present.

The key observation is that you should always take the smallest number in each layer: if you were to take another number in the layer, the evaluation score must be at most the smallest number in that layer.

To show that this is true, suppose we chose the path containing the minimum value in each layer. Let's denote the $$$\text{MEX}$$$ as $$$m$$$. For each layer, let's denote the minimum value $$$a_i$$$ where $$$i$$$ is the layer. If $$$a_i \lt m$$$, we cannot choose any other node in that layer, since the $$$\text{MEX}$$$ will become $$$a_i$$$. Otherwise, if $$$a_i \gt m$$$, it is impossible for $$$m$$$ to be in that layer, since we know $$$a_i$$$ to be the minimum value in that layer.

Knowing this, how do we find the $$$\text{MEX}$$$? One solution is to put all the chosen elements in an array and check for the smallest missing value. Another option is to notice that since all values $$$0$$$ to $$$n + 1$$$ are present, the $$$\text{MEX}$$$ must be in one of the layers. Thus, you can simply look at the second smallest value for every layer — the smallest of these will be the $$$\text{MEX}$$$. The only edge case occurs when each layer consists of only one number; the answer is just $$$n + 2$$$.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, d;
    cin >> n >> d;
    int network[d + 2];
    network[0] = 0;
    network[d + 1] = n + 1;
    for (int i = 1; i <= d; i++) {
        int m;
        cin >> m;
        int smallest = n + 5;
        for (int j = 0; j < m; j++) {
            int v;
            cin >> v;
            smallest = min(smallest, v);
        }
        network[i] = smallest;
    }
    sort(network, network + d + 2);
    for (int i = 0; i < d + 2; i++) {
        if (network[i] != i) {
            cout << i << "\n";
            return 0;
        }
    }
    cout << n + 2 << "\n";
}

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, d;
    cin >> n >> d;
    int ans = n + 2;
    for (int i = 0; i < d; i++) {
        int m;
        cin >> m;
        int s = n + 2;
        int ss = n + 2;
        for (int i = 0; i < m; i++) {
            int v;
            cin >> v;
            if (v < s) {
                ss = s;
                s = v;
            } else if (v < ss) ss = v;
        }
        ans = min(ans, ss);
    }
    cout << ans << "\n";
    return 0;
}

The amount of snow that accumulates on the tree is equal to the amount of snow that falls per day multiplied by the number of days it takes before the tree breaks.

The number of days before any individual node breaks is independent of the other nodes in the tree.

Each node will break after $$$\lfloor \frac{\text{strength}}{\text{weight of subtree}} \rfloor$$$ days. Greedily, it is optimal to strengthen the $$$k$$$ nodes which will break first. To calculate the weight of each node's subtree, we can use depth-first-search. Then, create an array storing each node's breaking point. Sort this array to determine the order in which to strengthen nodes.

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2e5;

int w[MAXN], a[MAXN], days[MAXN];
vector<int> adj[MAXN];

long long dfs(int i, int p){
    long long subtree = a[i];

    for(int j : adj[i]) if(j != p)
    	subtree += dfs(j, i);

    days[i] = w[i]/subtree;

    return subtree;
}

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

    for(int i=0; i<n; ++i) cin >> w[i];
    for(int i=0; i<n; ++i) cin >> a[i];

    for(int i=1; i<n; ++i){
    	int u, v; cin >> u >> v;
    	adj[u-1].push_back(v-1);
    	adj[v-1].push_back(u-1);
    }

    long long total = dfs(0, 0);

    sort(days, days+n);

    for(int i=0; i<n; ++i)
    	cout << total*days[i] << '\n';
}

Alice is able to determine what move Bob makes as Bob can only make one move to maximize the results.

Because Alice may choose only one entry of $$$A$$$, every other position has a fixed contribution we can precompute — specifically, how large the result would be if Bob chose that index after Alice's move. For any choice $$$i$$$ that Alice makes, Bob will pick whichever gives a larger value: either he picks $$$j = i$$$, or he picks the best index among all $$$j \neq i$$$. Alice's goal after that is to pick an index $$$i$$$ that minimizes this worse-case value.

To evaluate the best index among all $$$j \neq i$$$ efficiently for every i, we can compute the two largest values of $$$f(j) = A_j | (y-A_j)$$$ over all $$$j$$$. For a given index $$$i$$$, if the overall maximum $$$f(j)$$$ comes from $$$j = i$$$, then the best choice among the remaining indices is the second-largest. Otherwise, the best choice is the largest. Using this idea, we can check every $$$i$$$ in constant time after the initial scan, giving an $$$O(n)$$$ solution.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;

    while(t--){
        int n; ll x, y;
        cin >> n >> x >> y;

        vector<ll> vals(n);
        ll sum = 0;
        for(int i = 0; i < n; ++i) {
            cin >> vals[i];
            sum += vals[i];
        }

        vector<ll> loss(n);
        for(int i = 0; i < n; ++i) loss[i] = vals[i]-(vals[i]&y);

        ll min1 = LLONG_MAX, min2 = LLONG_MAX;
        int idx1 = -1;
        for(int i = 0; i < n; ++i) {
            if(loss[i] < min1){
                min2 = min1;
                min1 = loss[i];
                idx1 = i;
            } else if(loss[i] < min2) {
                min2 = loss[i];
            }
        }

        ll ans = LLONG_MAX;
        for(int i = 0; i < n; ++i) {
            ll alice = vals[i]|x;
            ll delta = alice-vals[i], same = alice-(alice&y);
            ll obest = ((i == idx1) ? min2 : min1);
            ll bob = min(obest, same);
            ll temp = sum+delta-bob;
            ans = min(ans, temp);
        }

        cout << ans << "\n";
    }

    return 0;
}

Recall that the trolleys are sorted such that the heaviest trolleys go first, and the lightest ones go last. If a trolley gets stopped by a cow, what does that mean for the rest of the trolleys?

If we have a trolley get stopped by a cow, then we can direct subsequent trolleys to the same cow.

Once we have one cow that can stop a trolley, all subsequent trolleys can be directed to that same cow. This means that in our array of trolleys, we will have some prefix of trolleys that won't awaken a cow, while the rest of the trolleys will result in us waking up a cow.

Let's consider binary searching on the longest prefix of trolleys that won't awaken a cow. Consider checking if a prefix length of $$$m$$$ is valid.

Let the weight of the heaviest trolley in our prefix be $$$x$$$. We need to find the minimum index $$$i$$$, such that either $$$c[i] \geq x$$$ or $$$d[i] \geq x$$$.

If we are zero-indexing, $$$i$$$ is equal to the number of cows that must be awoken before finally reaching a cow heavy enough to stop our prefix of trolleys.

As long as $$$i$$$ is less than $$$n - m$$$, the number of trolleys not in our prefix, we can force all $$$m$$$ trolleys into a cow that is heavy enough.

Thus, with this condition, we can binary search on the longest prefix. The answer is then the number of trolleys that aren't in our prefix. With that, we can solve the problem in $$$\mathcal{O}(n \log n)$$$ time.

Note that an $$$\mathcal{O}(n)$$$ solution exists, but is slightly more difficult to implement.

#include <bits/stdc++.h>

using ll = long long;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, a, b;
    std::cin >> n >> a >> b;
    std::vector<int> t(n), c(a), d(b);
    for (auto &i : t) std::cin >> i;
    for (auto &i : c) std::cin >> i;
    for (auto &i : d) std::cin >> i;

    int lo = 0, hi = n;
    while (lo < hi) {
        int m = (lo + hi + 1) / 2;

        int biggest = (m == 0) ? -1 : t[m - 1];
        int get_hit = std::min(a, b);

        for (int i = 0; i < a; i++) {
            if (biggest <= c[i]) get_hit = std::min(get_hit, i);
        }

        for (int i = 0; i < b; i++) {
            if (biggest <= d[i]) get_hit = std::min(get_hit, i);
        }

        if (get_hit <= n - m) lo = m;
        else hi = m - 1;
    }

    std::cout << n - lo << '\n';
}

We can write a set of equations to describe this.

Well, we already have a set of equations, surely the solution is just deterministic with some constraints based on the setup right?

Let's set the original series of $$$5$$$ numbers to be $$$a_1, a_2, a_3, a_4, a_5$$$ and the number of operations to be $$$x_1, x_2, x_3, y_1, y_2$$$ (where $$$x_i$$$ is the number of first operations that starts at the $$$i$$$th number, $$$y_i$$$ is the number of second operations that starts at the $i$th number). Rewriting the problem statement as mathematical statements gives us the following:

We observe that $$$a_{1...5}$$$ are all constants, so we are solving $$$x_{1, 2, 3}$$$ and $$$\space y_{1, 2}$$$ with $$$5$$$ equations, which is clearly deterministic.

We can rewrite $$$x_{1, 2, 3}$$$ and $$$\space y_{1, 2}$$$ in terms of $$$a_{1...5}$$$

Now, If any of $$$x_{1, 2, 3}$$$ or $$$\space y_{1, 2}$$$ is negative, you won't have a solution (since we can't add). Otherwise, output $$$(x_1 + x_2 + x_3) * 1* + (y_1 + y_2) * 2$$$.

Note: due to the constraint of the problem being on the sum of the integers, individual number or final cost may exceed the limit of regular 32 bit integer. Thus, we should use 64 bit integer, like long long in C++.

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

#define ll long long

void solve() {
    ll a1, a2, a3, a4, a5;
    cin >> a1 >> a2 >> a3 >> a4 >> a5;

    ll x1 = a3 - a4, x2 = a3 - a1 - a5, x3 = a3 - a2;
    ll y1 = a1 + a4 - a3, y2 = a2 + a5 - a3;

    if (x1 < 0 || x2 < 0 || x3 < 0 || y1 < 0 || y2 < 0)
        cout << -1 << '\n';
    else
        cout << x1 + x2 + x3 + (y1 + y2) * 2 << '\n';
    return;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

Think of the maximum width $$$w$$$ as the number of nodes on the widest level. If you try to build such a tree topΓÇôdown, you need extra nodes above to ΓÇ£supportΓÇ¥ that level.

Given a candidate width $$$w$$$, how many nodes are needed in total? Start with $$$w$$$ on some level, then half of them on the level above, then half again, and so on until reaching 1. If the total $$$\leq n$$$, then width $$$w$$$ is achievable.

We binary search on the answer $$$w$$$; For a mid value $$$w$$$, compute how many nodes are required: $$$ \text{cur} = w + \left\lceil \tfrac{w}{2} \right\rceil + \left\lceil \tfrac{w}{4} \right\rceil + \dots + 1 $$$. If $$$\text{cur} \leq n$$$, then $$$w$$$ is possible, otherwise itΓÇÖs too large. The largest valid $$$w$$$ found is the answer.

This runs in $$$O(\log n \cdot \log n)$$$ per test case, fast enough for $$$n \leq 10^9$$$.

#include <bits/stdc++.h>
#define int long long
#define re(a, b, c, d) for (auto a = b; a <= c; a += d)
#define de(a, b, c, d) for (auto a = b; a >= c; a -= d)
#define ms(a, b) memset(a, b, sizeof (a))
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
#define PII pair <int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
template <typename T> bool chkmin (T &a, T b) {
	return (b < a) ? a = b, 1 : 0;
}
template <typename T> bool chkmax (T &a, T b) {
	return (b > a) ? a = b, 1 : 0;
}
using namespace std;
int T, n;
signed main () {
	cout << fixed << setprecision (0);
	ios :: sync_with_stdio (0), cin.tie (0), cout.tie (0);
	int l, r;
	cin >> T;
	wh (T) {
		cin >> n;
		l = 1, r = n;
		while (l < r) {
//			cout << l << " " << r << "\n";
			int mid = l + r + 1 >> 1;
			int cur = 1, x = mid;
			while (x > 1) cur += x, (++ x) /= 2;
			if (cur <= n) l = mid;
			else r = mid - 1;
		}
		cout << l << "\n";
	}
	return 0;
}

Try to figure out, for each element, the largest subarray length where it stays the maximum. You can do this using next greater to left/right with a monotone stack.

Once you know the max length $$$L$$$ for each element, that element is a candidate maximum for every subarray size $$$k \leq L$$$. Collect these contributions for all $$$k$$$.

Each $$$a_i$$$ dominates an interval between its next greater elements to the left and right. That gives the maximum subarray length $$$L_i$$$ where $$$a_i$$$ is the maximum.

So:

Compute $$$L_i$$$ for each element using stacks.

For each $$$L_i$$$, mark $$$a_i$$$ as available starting from subarray length $$$1$$$ up to $$$L_i$$$.

Sweep $$$k = 1 \dots n$$$, maintain which values appear, and compute the $$$\text{MEX}$$$ incrementally.

This runs in $$$O(n \log n)$$$ or $$$O(n)$$$ with careful implementation.

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

int main() {
	int n;
	cin >> n;
	vector<int> a (n);
	for (auto &x : a) cin >> x;
	vector<int> L (n, -1), R (n, n);
	stack<int> stk;
	for (int i = 0; i < n; i ++) {
		while (!stk.empty() && a[stk.top()] < a[i]) stk.pop();
		if (!stk.empty()) L[i] = stk.top();
		stk.push (i);
	}
	stk = stack<int>();
	for (int i = n - 1; i >= 0; i --) {
		while (!stk.empty() && a[stk.top()] <= a[i]) stk.pop();
		if (!stk.empty()) R[i] = stk.top();
		stk.push (i);
	}
	vector<vector<int>> contrib (n + 1);
	for (int i = 0; i < n; i ++) {
		int len = R[i] - L[i] - 1;
		contrib[len].push_back (a[i]);
	}
	vector<bool> vis (n + 1, 0);
	int mex = 0;
	vector<int> ans (n + 1);
	for (int i = n; i >= 1; i --) {
		for (int x : contrib[i]) {
			if (x <= n && !vis[x]) {
				vis[x] = 1;
				while (vis[mex]) mex ++;
			}
		}
		ans[i] = mex;
	}
	for (int i = 1; i <= n; i ++) cout << ans[i] << " ";
	cout << "\n";
}

Consider how to add a single pennant.

First, you shift the groups to the right by 1 space, with 2 operations per group. Then you add your new pennant with 1 operation.

Example:

1 1 3 3 4 5 5 5 X
Adding a pennant of rank 2:
1 1 X 3 X X 5 5 X
1 1 X 3 3 4 5 5 5
1 1 2 3 3 4 5 5 5

Consider adding $$$a$$$ pennants of rank $$$k$$$. For each group with rank greater than $$$k$$$, you must shift it to the right by $$$a$$$ spaces. (You also need $$$a$$$ additional operations to actually put the new pennants on the wall.)

To shift a group with size $$$b$$$ to the right $$$a$$$ spots, either $$$b\le a$$$, so you move the entire group in $$$2b$$$ operations. Otherwise, it takes $$$2a$$$ operations to relocate $$$a$$$ pennants from the left border to the right border. Thus, for each group, you require $$$2\cdot \min(a, b)$$$ operations.

For the subtask, this can be calculated in $$$O(n^2)$$$ time.

To solve this in $$$O(n \log n)$$$ time, we can sweep from right to left, processing queries offline. We will maintain two arrays: $$$\mathrm{cnt}[i]$$$ denotes the number of groups on the right of size $$$i$$$, and $$$\mathrm{sum}[i] = i \cdot \mathrm{cnt}[i]$$$. Then, the sum over groups of $$$\min(a, \textrm{size})$$$ is equal to $$$\sum_0^a \mathrm{sum}[i] + a \cdot \sum_{a+1}^n \mathrm{cnt}[i]$$$. We can compute these sums with a fenwick tree.

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
cintype in;

struct fenwick {
        int n;
        vector<int> t;
        fenwick(int n) : n(n), t(n) {}
        void add(int i, int x) {
                for(;i<n;i|=i+1)t[i]+=x;
        }
        int query(int i) {
                if(i>=n) i=n-1;
                int x=0;
                for(;~i;i=(i&(i+1))-1)x+=t[i];
                return x;
        }
};

int main()
{
        int n=in,q=in,l=in;
        vector<int> f(n);
        vector<int> a(n);for(auto&x:a)x=in,x--,f[x]++;

        vector<vector<array<int,2>>> qs(n);
        for(int i=0;i<q;i++) {
                int a=in,k=in;k--;qs[k].push_back({i,a});
        }

        fenwick ft(n), ft2(n);
        vector<int> ans(n);

        for(int i=n-1;~i;i--) {
                for(auto [id, a] : qs[i]) {
                        ans[id] += a;
                        ans[id] += ft.query(a-1) * 2;
                        ans[id] += a * (n-i-1-ft2.query(a-1)) * 2;
                }
                ft.add(f[i],f[i]);
                ft2.add(f[i],1);
        }

        for(auto x:ans)
                printf("%d\n",x);
}

For each word, consider the players as a bitmask.

When is it possible to have any team?

Consider the bitmasks of two words $$$a$$$ and $$$b$$$. If $$$a \,|\, b = \underbrace{111\dots11_2}_{n\text{ times}}$$$, then it is possible to have two teams with words $$$a$$$ and $$$b$$$.

There is an edge case, which happens when there is a word such that all players may have it.

Let us consider the case where the edge case in hint 3 does not appear.

First, we consider each word as a bitmask $$$w_{i,j}$$$, where $$$w_{i,j} = 1$$$ if and only if player $$$j$$$ can possibly have word $$$i$$$. Clearly, it is possible to have a team when there are two words $$$a$$$, $$$b$$$, with $$$w_a \,|\, w_b = \underbrace{111\dots11_2}_{n\text{ times}}$$$. If the two words are unique, then $$$w_a$$$ must also be the complement of $$$w_b$$$.

Using a map, we can count the number of pairs $$$(a, b)$$$ which satisfy the above condition, such that $$$w_a$$$ is the compliment of $$$w_b$$$. If there is more than one pair, the answer is NO.

The only other way for the teams to be non-unique is if two words satisfy $$$w_a \,|\, w_b = \underbrace{111\dots11_2}_{n\text{ times}}$$$, but they are not complements of each other. Then, they must have at least one bit in common.

We can run a bitmask dp with $$$\mathrm{dp}[m] = 1$$$ if and only if there is a word with a submask equal to $$$m$$$. The transitions are standard. Then, we can iterate over all word masks, and for each word, we iterate over all common bits $$$j$$$. Then, we can query $$$\sim w_a \oplus 2^j$$$ in the dp ($$$\sim$$$ is not, $$$\oplus$$$ is xor), because if there is a word with submask equal to $$$\sim w_a\oplus 2^j$$$, then the words must share common bit $$$j$$$, so the answer is NO.

In all other cases, if there exists a possible configuration of teams, the answer is YES.

For the edge case in hint 3, it is only possible to have a unique team if there is only one player who claims another word, and that word is unique (see below case):

$$$ w_0 = 0001 $$$

$$$ w_1 = 1001 $$$

$$$ w_2 = 0001 $$$

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
cintype in;

int main()
{
        int tt=in;
        for(int ttn=0;ttn<tt;ttn++)
        {
                int n=in,m=in;
                vector<int> a(m);
                for(int i=0;i<n;i++) for(int j=0;j<m;j++) a[j]|=(char(in)-'0')<<i;

                ll ok=0;
                int sol1=0, sol2=0;

                int tot = 0;
                for(int i=0;i<m;i++)tot+=__builtin_popcount(a[i]);
                for(int i=0;i<m;i++) {
                        if(a[i] == (1<<n)-1) {
                                if(tot == n+1)
                                        for(int j=0;j<m;j++)if(j!=i&&a[j]) { sol1=i; sol2=j; goto yes; }
                                goto no;
                        }
                }
                {
                        map<int,int> mp,oc;for(int i=0;i<m;i++)mp[a[i]]=i,oc[a[i]]++;
                        for(int i=0;i<m;i++) {
                                int b = ((1<<n)-1) & ~a[i];
                                if(auto it=mp.find(b);it!=mp.end()&&it->first==b) {
                                //cout<<bitset<20>(a[i])<<' '<<bitset<20>(a[it->second])<<endl;
                                        ok+=oc[it->first];sol1=i;sol2=it->second;
                                }
                        }
                        if(ok!=2) goto no;
                        vector<int> dp(1<<n);for(auto x:a)dp[x]=1;
                        for(int i=(1<<n)-1;~i;i--) {
                                for(int j=0;j<n;j++)if(i>>j&1) {
                                        dp[i^(1<<j)]|=dp[i];
                                }
                        }
                        for(auto x:a) {
                                for(int j=0;j<n;j++)if(x>>j&1) {
                                        int z = ((1<<n)-1)^x^(1<<j);
                                        if(dp[z]) goto no;
                                }
                        }
                }

                //printf("ok=%d\n",ok);
                if(ok == 2) {yes:
                        printf("Yes\n");
                        if(sol1>sol2)swap(sol1,sol2);
                        printf("%d %d\n", sol1+1, sol2+1);
                }
                else no:printf("No\n");
                //printf("ok=%d\n",ok);
        }
}

Think non-simple paths, especially the ones that use the same edge several times.

Because a path does not need to be simple, at any node $$$u$$$, we can traverse the same edge twice in a row and return to $$$u$$$. Because of this, if we consider some path from $$$s$$$ to $$$t$$$ with path weight $$$c$$$, we can always augment the path weight by $$$2 \cdot w_i$$$ arbitrarily.

Let $$$g = \gcd(w_1, w_2, \dots, w_n)$$$. Then, using the ideas of Bezout's identity and the previous observation, all path weights in the set $$$\{c, 2g + c, \dots, 2(k-1) \cdot g + c\} \mod k$$$ are obtainable. Since $$$c \mid g$$$, only $$$c = 0$$$ and $$$c = g$$$ are important given they may form different sets.

If both $$$c$$$ values are obtainable, then the obtainable set of path weights is $$$\{0, g, \dots, g(k-1)\} \mod k$$$, whose size is $$$\dfrac{k}{\gcd(k, g)}$$$.

If only one $$$c$$$ is obtainable, the obtainable set of path weights is $$$\{c, 2g + c, \dots, 2(k-1)g + c\} \mod k$$$, whose size is $$$\dfrac{k}{\gcd(k, 2g)}$$$.

Define $$$W_i = \frac{w_i}{g}$$$. Let $$$W_i$$$ be the weights of a new graph. In this graph, we notice that the existence of an even path weight corresponds to $$$c = 0$$$ and the existence of an odd path weight corresponds to $$$c = g$$$. Calculating whether an odd and/or even path exists can be done using a BFS/DFS with two states per node $$$u$$$ (whether an odd/even path exists from $$$s$$$ to $$$u$$$), solving the problem in $$$\mathcal{O}(n)$$$.

If $$$g = 0$$$, then the answer is $$$1$$$. This must be handled manually to avoid division by $$$0$$$.

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

int n, m, qq, a, b;
ll k;
void solve() {
    cin >> n >> m >> k >> a >> b;
    a--, b--;
    ll g = 0;
    vector<pair<pi, ll>> edges(m);
    vector<vector<pi>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        edges[i] = {{--u, --v}, w};
        g = gcd(g, w);
    }

    if (g == 0) {
        cout << "1\n";
        return;
    }

    for (int i = 0; i < m; i++) {
        auto [p, w] = edges[i];
        auto [u, v] = p;
        adj[u].push_back({v, (w / g) & 1});
        adj[v].push_back({u, (w / g) & 1});
    }

    vector<vector<bool>> vis(2, vector<bool>(n));
    vis[0][a] = 1;
    queue<pi> q;
    q.push({0, a});
    while (!q.empty()) {
        auto [p, u] = q.front();
        q.pop();
        for (auto [v, w] : adj[u]) {
            if (!vis[(p + w) & 1][v]) {
                vis[(p + w) & 1][v] = 1;
                q.push({(p + w) & 1, v});
            }
        }
    }

    if (!vis[0][b] || !vis[1][b]) g *= 2;
    cout << k / gcd(g, k) << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

$$$|a-b| = \max(a-b,b-a)$$$

Lets call John's nodes red and Nhoj's nodes black.

First, we can run Dijkstra's from node $$$1$$$ and node $$$2n$$$, to find the distances to every node. Let us denote these distances as $$$d_i$$$.

We wish to find the minimum value of $$$d_i + |x_i-x_j| + |y_i-y_j| + d_j$$$ for all red nodes $$$i$$$ and black nodes $$$j$$$.

Let's suppose that $$$x_i \lt x_j$$$ and $$$y_i \lt y_j$$$. Then, the above reduces to $$$(d_i-x_i-y_i)+(d_j+x_j+y_j)$$$. We can compute the minimum value of this by sweeping in the positive x direction, and using a point update / range minimum query segment tree. For all red nodes, we add the left side of the expression to the segment tree at index $$$y_i$$$. For all blue nodes, we query the segment tree for the minimum value at index $$$\le y_j$$$, and add it to the right side of the expression.

To do this for the other cases, we can rotate the grid by 90 degrees, and then run the above algorithm again. Do note that we need either a sparse segtree or coordinate compression, both should pass comfortably.

// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#include <assert.h>
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
cintype in;

#define N 200000
#define NN N*40
#define X int(1e9)

ll val[NN]; int lc[NN], rc[NN];
int vv=2;

#define vm (vl+(vr-vl)/2)
void update(int i, ll x, int& v, int vl, int vr) {
        if(v==0)v=vv++;
        val[v]=min(val[v],x);
        if(vl==vr) return;
        i<=vm?update(i,x,lc[v],vl,vm):update(i,x,rc[v],vm+1,vr);
}
ll query(int l, int r, int v, int vl, int vr) {
        if(l==vl&&r==vr) return val[v];
        if(r<=vm)return query(l,r,lc[v],vl,vm);
        else if(l>vm)return query(l,r,rc[v],vm+1,vr);
        else return min(query(l,vm,lc[v],vl,vm),query(vm+1,r,rc[v],vm+1,vr));
}

int main()
{
        int n=in,m=in;

        vector<array<int,2>> pos(2*n);for(auto&[x,y]:pos)x=in,y=in;

        vector<vector<array<int,2>>> adj(2*n);
        while(m--) {
                int u=in,v=in;u--;v--;int e=in;
                adj[u].push_back({v,e});
                adj[v].push_back({u,e});
        }

        priority_queue<array<ll,2>> pq;
        vector<ll> dist(2*n,infl);
        dist[0]=dist[2*n-1]=0;
        pq.push({-0,0});
        pq.push({-0,2*n-1});
        while(pq.size()) {
                auto [d,v]=pq.top();pq.pop();d=-d;
                if(d>dist[v])continue;

                for(auto [x,w]:adj[v]) {
                        if(d+w<dist[x]) {
                                dist[x]=d+w;
                                pq.push({-d-w,x});
                        }
                }
        }

        ll ans=infl;
        for(int it=0;it<4;it++) {
                for(int i=0;i<2*n;i++) {
                        tie(pos[i][0], pos[i][1]) = make_pair(pos[i][1], X-pos[i][0]);
                }
                memset(val,0x3f,sizeof(val));
                memset(lc,0,sizeof(lc));
                memset(rc,0,sizeof(rc));
                vv = 2;

                int rt = 1;
                vector<int> a(2*n);for(int i=0;i<2*n;i++)a[i]=i;
                sort(all(a),[&](auto u, auto v) {
                        return pos[u][0]<pos[v][0];
                });

                for(auto i:a) {
                        if(i<n) update(pos[i][1],dist[i]-pos[i][0]-pos[i][1],rt,0,X);
                        if(i>=n) ans=min(ans,query(0,pos[i][1],rt,0,X)+dist[i]+pos[i][0]+pos[i][1]);
                }
        }
        //for(int i=0;i<n;i++) {
                //for(int j=n;j<2*n;j++) {
                        //ans=min(ans,dist[i]+dist[j]+abs(pos[i][0]-pos[j][0])+abs(pos[i][1]-pos[j][1]));
                //}
        //}
        printf("%lld\n",ans);
}

Formulate a DP.

Dijkstra?

Let's solve this using DP. Let $$$d_{i, j}$$$ be the minimum number of robots required to get one robot on cell $$$(i, j)$$$. At the start, if cell $$$(i, j)$$$ is a spawn point $$$A$$$, then $$$d_{i, j} = 1$$$, otherwise $$$d_{i, j} = \text{INF} = 4 \cdot 10^{18} + 1$$$ to denote that $$$(i, j)$$$ is unreachable.

Let $$$x$$$ be some cell $$$(i, j)$$$ and $$$y$$$ be some cell orthogonally adjacent to $$$x$$$. If $$$d_x, d_y \neq \text{INF}$$$, then the robot in $$$x$$$ can push the robot in $$$y$$$ to cell $$$z$$$ (if cell $$$z$$$ is not an obstacle), setting $$$d_z$$$ to $$$\min(d_z, d_x + d_y)$$$.

Since there is no proper order to process the states, naively looping through the grid $$$nm$$$ times to calculate the states takes $$$\mathcal{O}(n^2m^2)$$$ computations. Although there is no graph nor specific edge weights, Dijkstra's algorithm can be used here. What Dijkstra does is order and process the states in non-decreasing $$$d_{i, j}$$$, eliminating wasted computations. Note that when processing cell $$$x$$$, for some orthogonally adjacent $$$y$$$, both $$$x$$$ pushing $$$y$$$ and $$$y$$$ pushing $$$x$$$ must be considered, for a total of $$$8$$$ transitions per cell. This solves the problem in $$$\mathcal{O}(nm \log nm)$$$.

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;

const int N = 1005;
const ll inf = (ll)4e18 + 1;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
char grid[N][N];
ll dist[N][N];
int n, m, k, qq;
void solve() {
    cin >> n >> m;
    int tx, ty;
    priority_queue<pair<ll, pi>, vector<pair<ll, pi>>, greater<pair<ll, pi>>> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            if (grid[i][j] == 'A') {
                dist[i][j] = 1;
                q.push({1, {i, j}});
            }

            else dist[i][j] = inf;
            if (grid[i][j] == 'B') tx = i, ty = j;
        }
    }

    auto ok = [&](int x, int y) {
        return (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '#');
    };

    while (!q.empty()) {
        auto [d, p] = q.top();
        auto [x, y] = p;
        q.pop();
        if (d != dist[x][y]) continue;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!ok(nx, ny)) continue;
            ll nd = d + dist[nx][ny];
            nx += dx[i], ny += dy[i];
            if (ok(nx, ny) && dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                q.push({nd, {nx, ny}});
            }

            nx = x - dx[i], ny = y - dy[i];
            if (ok(nx, ny) && dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                q.push({nd, {nx, ny}});
            }
        }
    }

    cout << (dist[tx][ty] == inf ? -1 : dist[tx][ty]) << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

How do you solve the distinct element case?

How many nice intervals are there?

For the remainder of the problem, we assume zero-indexing, and we subtract $$$1$$$ from every element in the array.

Consider how to solve the problem for a single query. The problem reduces to choosing a prefix of the array, then the answer is $$$\max(a_l,a_{l+1},\dots,a_r) - (r-l)$$$.

Let's define a nice interval as an interval without any duplicate elements, and a really nice interval as a nice interval that cannot be extended left or right without either introducing duplicate elements or changing the maximum element.

In the distinct elements case, every interval is nice. Also, each node corresponds to a really nice interval, which extends left until the next highest element, and similarly to the right.

For the non-distinct elements case, we will figure it out later.

We can now describe how to solve a single case using really nice intervals. Note that for a query, either you take the entire array (and it is nice), or you take a prefix. In the latter case, it is always optimal to take a prefix that cannot be extended to the right without either introducing duplicate elements, or increasing the maximum. In all other cases, extending the prefix to the right will decrease the answer by 1. Notice that this is exactly the suffix of a really nice interval!

It is useful to maintain 2 RMQs (I used sparse table). For the first RMQ, we store the elements in the array, so we can find the maximum of any interval. For the second RMQ, we store index of the previous occurrence of every element, so that we can determine whether a subarray is nice (that is, it has no duplicate elements).

Now, we can answer each query offline. Consider sweeping left to right, processing intervals and queries at their left endpoint. We maintain a segment tree that can maintain point updates and range minimum queries. At each really nice interval, we update $$$\mathrm{mx} - r$$$ at the right endpoint in the segment tree. At each query, we query the segment tree between $$$l$$$ and $$$r$$$, and add $$$l$$$ to the answer. We also compare this to the answer if we take the entire interval of the query (we can find this using our 2 RMQs).

Now it remains to find the really nice intervals for general arrays, with possibly non-distinct elements. For each element, consider the interval formed by extending left until a larger element or a duplicate with another element on the left, and similarly right until a larger element or a duplicate with another element on the right ( not on the left ). If this interval is nice, then it must also be really nice. Otherwise, there must be at least one pair of duplicate elements, and all really nice intervals containing the same maximum element must stop at one end of one such pair of duplicate elements.

Without loss of generality, fix one of the pairs, which we will denote as $$$(i,j)$$$. Consider the interval that consists of the subarray between $$$k$$$ and $$$j-1$$$, where $$$k$$$ is the minimum possible such that this interval is nice and has the same maximum element as the subarray between $$$i$$$ and $$$j$$$. Then, this interval must be really nice. To find all such intervals, we can consider each $$$k$$$ from $$$1\dots n$$$, and binary search to extend this interval as far right as possible. The same applies in reverse (extending to the left).

Thus, there are at most $$$3\cdot n$$$ really nice intervals, and we can compute them using binary search and our 2 RMQ's in $$$O(n \log n)$$$ time. Thus, our entire solution runs in $$$O(n \log n)$$$ time.

#line 1 "full.cpp"
// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <bits/stdc++.h>
using namespace std;

#include <tr2/dynamic_bitset>
using namespace tr2;
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll

#line 15 "full.cpp"
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#endif
#define all(x) (x).begin(), (x).end()
struct cintype { template<typename T> operator T() { T x; cin>>x; return x; } };
// 1}}}
cintype in;

#line 2 "/home/jayjay/dev2/comp/lib/ds/rmq.hpp"

#line 5 "/home/jayjay/dev2/comp/lib/ds/rmq.hpp"
using namespace std;

template<typename T, int LG=20, typename Compare = less<T>>
struct RMQ {
        int n;
        vector<T> arr;
        vector<int> st;
        RMQ(int n) : n(n), arr(n), st(n*LG) {
                assert(n <= 1<<LG);
                for(int i=0;i<n;i++) st[i] = i;
        }
        int argmin(int a, int b) {
                return Compare()(arr[a],arr[b]) ? a : b;
        }
        template<typename Tp>
        void build(Tp a) {
                for(int i=0;i<n;i++) arr[i] = a[i];
                for(int l=1; l<LG; l++)
                        for(int i=0; i + (1<<(l-1)) < n; i++)
                                st[l*n+i] = argmin(
                                                st[(l-1)*n + i],
                                                st[(l-1)*n + i + (1<<(l-1))]);
        }
        int query(int l, int r) {
                r++;
                int k = __lg(r - l);
                return argmin(st[k*n + l], st[k*n + r - (1<<k)]);
        }
};
#line 2 "/home/jayjay/dev2/comp/lib/ds/isegtree.hpp"

#line 1 "/home/jayjay/dev2/comp/lib/func.hpp"
struct func_add {
        template<typename T>
        T operator()(T a, T b) const {
                return a + b;
        }
};
struct func_min {
        template<typename T>
        T operator()(T a, T b) const {
                return min(a, b);
        }
};
struct func_max {
        template<typename T>
        T operator()(T a, T b) const {
                return max(a, b);
        }
};
#line 4 "/home/jayjay/dev2/comp/lib/ds/isegtree.hpp"

template<typename T=long long, typename oper=func_add, T id={}>
struct isegtree // oper should be: associative, has identity
{
        int n; std::vector<T> t;

        isegtree(int n) : n(n), t(2*n-1, id) {}
        isegtree() : isegtree(1) {}

        void resize(int n) { // UB if tree is nonzero
                this->n=n;
                t.resize(2*n-1);
        }

        template<typename Tp>
        void build(Tp a) {
                for(int i=n-1;~i;i--) t[i+n-1] = a[i];
                for(int i=n-2;~i;i--) t[i] = oper()(t[i*2+1], t[i*2+2]);
        }

        void update(int i, T x) {
                i += n-1;
                t[i] = x;
                while(i > 0) i = (i-1)/2, t[i] = oper()(t[i*2+1], t[i*2+2]);
        }

        T query(int l, int r) {
                l += n-1; r += n-1;
                T lans = id, rans = id;
                while(l < r) {
                        if(~l&1) lans = oper()(lans, t[l++]);
                        if(r&1)  rans = oper()(t[r--], rans);
                        l = (l-1) / 2;
                        r = (r-1) / 2;
                }
                if(l == r) return oper()(oper()(lans, t[l]), rans);
                else return oper()(lans, rans);
        }
};
#line 28 "full.cpp"

int main()
{
        int n=in, q=in;vector<int> a(n);for(auto&x:a)x=in,x--;

        vector<int> prev(n);
        map<int,int> pr;
        for(int i=0;i<n;i++) {
                if(pr.count(a[i])==0)prev[i] = -1;
                else prev[i] = pr[a[i]];
                pr[a[i]] = i;
        }

        RMQ<int, 20, greater<int>> rmq(n); rmq.build(a);
        RMQ<int, 20, greater<int>> pm(n);pm.build(prev);
        //for(int i=0;i<n;i++)printf("%d ",prev[i]);
        //printf("\n");
        auto isnice = [&](int l, int r) {
                //printf("isnice %d %d = %d\n",l,r,pm.query(l,r)<l);
                return prev[pm.query(l,r)] < l;
        };

        vector<int> nl(n), nr(n);
        {
                vector<int> stk;
                for(int i=0;i<n;i++) {
                        while(stk.size() && a[stk.back()] < a[i]) stk.pop_back();
                        nl[i] = stk.size()?stk.back():-1;
                        stk.push_back(i);
                }
        }
        {
                vector<int> stk;
                for(int i=n-1;~i;i--) {
                        while(stk.size() && a[stk.back()] < a[i]) stk.pop_back();
                        nr[i] = stk.size()?stk.back():n;
                        stk.push_back(i);
                }
        }

        vector<vector<array<int,2>>> nice(n);
        for(int i=0;i<n;i++) {
                int l = nl[i]+1, r = nr[i]-1;
                if(isnice(l, r))
                        nice[l].push_back({r, a[rmq.query(l,r)]});
        }
        for(int i=0;i<n;i++) {
                int l=i,r=n-1;
                while(l<r) {
                        int m = l+(r-l+1)/2;
                        if(isnice(i,m))l=m;
                        else r=m-1;
                }
                nice[i].push_back({r,a[rmq.query(i,r)]});
        }
        for(int i=0;i<n;i++) {
                int l=0, r=i;
                while(l<r) {
                        int m = l+(r-l)/2;
                        if(isnice(m,i))r=m;
                        else l=m+1;
                }
                nice[l].push_back({i,a[rmq.query(l,i)]});
        }
        //for(int i=0;i<n;i++)for(auto [r,m]:nice[i])printf("nice %d %d %d\n",i,r,m);

        vector<int> ans(q);
        vector<vector<array<int,2>>> qs(n);
        for(int i=0;i<q;i++) {
                int l=in,r=in; l--;r--;qs[l].push_back({r,i});
        }

        isegtree<int,func_min,inf> st(n);

        for(int i=0;i<n;i++) {
                for(auto [r, mx] : nice[i]) {
                        st.update(r,mx-r);
                }

                for(auto [r, id] : qs[i]) {
                        ans[id] = st.query(i, r) + i;
                        if(isnice(i,r)) ans[id] = min(ans[id], a[rmq.query(i,r)] - r + i);
                        //printf("id=%d: %d + %d  ||  %d - %d + %d\n",id, st.query(i,r),i,a[rmq.query(i,r)],r,i);
                }
        }

        for(auto x:ans) printf("%d\n", x);
}

Look for invariants

Observation 1: Let white stones represent $$$+1$$$, and black stones represent $$$-1$$$. The difference between the values of two people's stones is constant. If the starting value of stones is $$$a_i$$$, then the ending value will be $$$a_i + C$$$, for some constant $$$C$$$.

Observation 2: Define a pair of stones to be a black stone and a white stone. Note that these pairs can be freely moved. BW,0,0 B,B,B 0,0,BW

Observation 3: If there are $$$N-2$$$ pairs, and one extra stone, they can be eliminated BW, BW, BW, B, 0 W, W, W, 0, W 0, 0, 0, B, 0

Observation 4: If there are less than $$$N-2$$$ pairs, they cannot be removed without changing $$$C$$$. Proof: Every operation changes $$$C$$$ by $$$1$$$. Thus, to not change $$$C$$$, you must perform an even number of operations. Since the total number of stones changes by $$$N-2$$$ each operation, after an even number of operations, thus changing the total number of stones by a multiple of $$$2(N-2)$$$.

Thus, for a given $$$C$$$, the minimum number of pairs can be computed. It can be shown, that the value of $$$C$$$ that minimizes the stones is the negative of the median of $$$a_i$$$, plus or minus 1. Thus, you can simply test those values.

#include <bits/stdc++.h>
#define ll long long
using namespace std;


ll n;
ll a [1005000];
ll w [1005000];
ll b [1005000];

ll tot = 0;
ll tmodev = 0;
ll tmodod = 0;

ll firstGeq(ll x, ll m, ll mod){//first number at least x that is m mod mod
    if(x == 0 && m == 0){
        return mod;
    }
    if(x%mod <= m){
        return (x/mod * mod) + m;
    }else{
        return ((x/mod + 1) * mod) + m;
    }
}

ll getCMin(ll c){
    ll ans = 0;
    for(int i = 0; i < n; i++){
        ans += max(a[i] - c, c - a[i]);
    }
    if(c%2 == 0){
        return firstGeq(ans, tmodev, 2 * (n - 2));
    }else{
        return firstGeq(ans, tmodod, 2 * (n - 2));
    }
}

void solve(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> b[i];
    }
    for(int i = 0; i < n; i++){
        cin >> w[i];
    }

    tot = 0;
    for(int i = 0; i < n; i++){
        a[i] = w[i] - b[i];
        tot += (w[i] + b[i]);
    }
    tmodev = (tot)%(2*(n-2));
    tmodod = (tot + (n-2))%(2*(n-2));
    sort(a, a+n);
    if(tot == 0){
        cout << 0 << endl;
    }else{
        ll ans = (1ll << 60);
        for(int i = n/2; i <= (n/2+1); i++){
            for(int j = -1; j <= 1; j++){
                ans = min(ans, getCMin(a[i] + j));
            }
        }
        cout << ans << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    for(int tc = 0; tc < t; tc++){
        solve();
    }
}

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const bool DEBUG=false;
struct Return{
    ll ans;
    vector<int>ord[2][2][2];// prefix/suffix, 0/min, 0/max
    Return(int i){
        ans=1;
        for(int a=0;a<8;++a)ord[a>>2][(a>>1)&1][a&1]={i};
    }
    Return(int initialAns,int vsize){
        ans=initialAns;
        for(int a=0;a<8;++a)ord[a>>2][(a>>1)&1][a&1].reserve(vsize);
    }
};

int n;
vector<int>arr,disc,cnt,mergeBuf[5];
vector<int>prefOpt[2][2];
vector<array<int,2>>halfOpt;
int infected[2][2];

template<typename Func1,typename Func2>
int mergeSort(vector<int>&bufLeft,vector<int>&bufRight,Func1&&evalLeft,Func2&&evalRight){
    int m=bufRight.size();
    int ptrLeft=0,ptrRight=m-1;
    int lstLeft=evalLeft(bufLeft[0]),lstRight=evalRight(bufRight[m-1]),lst=INT_MAX;
    int h=-1;
    while(true){
        if(lstLeft<lstRight){
            if(lst!=lstLeft)++h,lst=lstLeft;
            disc[bufLeft[ptrLeft]]=h;
            ++ptrLeft;
            if(ptrLeft<bufLeft.size())lstLeft=evalLeft(bufLeft[ptrLeft]);
            else break;
        }
        else{
            if(lst!=lstRight)++h,lst=lstRight;
            disc[bufRight[ptrRight]]=h;
            --ptrRight;
            if(ptrRight>=0)lstRight=evalRight(bufRight[ptrRight]);
            else break;
        }
    }
    while(ptrLeft<bufLeft.size()){
        lstLeft=evalLeft(bufLeft[ptrLeft]);
        if(lst!=lstLeft)++h,lst=lstLeft;
        disc[bufLeft[ptrLeft]]=h;
        ++ptrLeft;
    }
    while(ptrRight>=0){
        lstRight=evalRight(bufRight[ptrRight]);
        if(lst!=lstRight)++h,lst=lstRight;
        disc[bufRight[ptrRight]]=h;
        --ptrRight;
    }
    return h+1;
}

template<typename Func>
void mergeSort(vector<int>&bufLeft,vector<int>&bufRight,Func&&eval,vector<int>&outBuf){
    if(bufLeft.empty())return outBuf.swap(bufRight);
    if(bufRight.empty())return outBuf.swap(bufLeft);
    int ptrLeft=0,ptrRight=0;
    while(ptrLeft<bufLeft.size()&&ptrRight<bufRight.size())
        outBuf.push_back(eval(bufLeft[ptrLeft])<eval(bufRight[ptrRight])?bufLeft[ptrLeft++]:bufRight[ptrRight++]);
    while(ptrLeft<bufLeft.size())outBuf.push_back(bufLeft[ptrLeft++]);
    while(ptrRight<bufRight.size())outBuf.push_back(bufRight[ptrRight++]);
}

using Func=int(*)(int);
static const Func eval[8]={
    [](int i)->int{return arr[i]-0-0;},
    [](int i)->int{return arr[i]-0-prefOpt[0][1][i];},
    [](int i)->int{return arr[i]-prefOpt[0][0][i]-0;},
    [](int i)->int{return arr[i]-prefOpt[0][0][i]-prefOpt[0][1][i];},
    [](int i)->int{return arr[i]-0-0;},
    [](int i)->int{return arr[i]-0-prefOpt[1][1][i];},
    [](int i)->int{return arr[i]-prefOpt[1][0][i]-0;},
    [](int i)->int{return arr[i]-prefOpt[1][0][i]-prefOpt[1][1][i];}
};
Return dnq(int l,int r){
    if(r-l<=16){
        Return ret(0,r-l+1);
        prefOpt[0][0][l-1]=prefOpt[1][0][r+1]=inf,prefOpt[0][1][l-1]=prefOpt[1][1][r+1]=-inf;
        for(int a=l;a<=r;++a)prefOpt[0][0][a]=min(prefOpt[0][0][a-1],arr[a]),prefOpt[0][1][a]=max(prefOpt[0][1][a-1],arr[a]);
        for(int a=r;a>=l;--a)prefOpt[1][0][a]=min(prefOpt[1][0][a+1],arr[a]),prefOpt[1][1][a]=max(prefOpt[1][1][a+1],arr[a]);
        for(int a=0;a<8;++a){
            auto&v=ret.ord[a>>2][(a>>1)&1][a&1];
            v.resize(r-l+1);
            iota(v.begin(),v.end(),l);
            sort(v.begin(),v.end(),[&](int i,int j){
                return eval[a](i)<eval[a](j);
            });
        }
        for(int a=l;a<=r;++a){
            int accuMin=inf,accuMax=-inf;
            for(int b=a;b<=r;++b){
                accuMin=min(accuMin,arr[b]);
                accuMax=max(accuMax,arr[b]);
                ret.ans+=(accuMin+accuMax==arr[a]+arr[b]);
            }
        }
        return ret;
    }
    int mid=(l+r)/2;
    auto lres=dnq(l,mid);
    auto rres=dnq(mid+1,r);
    ll subAns=lres.ans+rres.ans;
    for(int a=mid,accuMin=inf,accuMax=-inf;a>=l;--a)halfOpt[a]={accuMin=min(accuMin,arr[a]),accuMax=max(accuMax,arr[a])};
    for(int a=mid+1,accuMin=inf,accuMax=-inf;a<=r;++a)halfOpt[a]={accuMin=min(accuMin,arr[a]),accuMax=max(accuMax,arr[a])};
    {
        static const Func halfEval[8]={
            [](int i)->int{return arr[i]-0-0;},
            [](int i)->int{return arr[i]-0-halfOpt[i][1];},
            [](int i)->int{return arr[i]-halfOpt[i][0]-0;},
            [](int i)->int{return arr[i]-halfOpt[i][0]-halfOpt[i][1];},
            [](int i)->int{return -(arr[i]-0-0);},
            [](int i)->int{return -(arr[i]-0-halfOpt[i][1]);},
            [](int i)->int{return -(arr[i]-halfOpt[i][0]-0);},
            [](int i)->int{return -(arr[i]-halfOpt[i][0]-halfOpt[i][1]);}
        }; 
        #pragma unroll
        for(int leftMask=0;leftMask<4;++leftMask){
            int rightMask=(3^leftMask);
            mergeSort(lres.ord[1][leftMask>>1][leftMask&1],rres.ord[0][rightMask>>1][rightMask&1],halfEval[0|leftMask],halfEval[4|rightMask]); 
            fill(cnt.begin(),cnt.begin()+r-l+1,0);
            int minRp=mid+1,maxRp=mid;
            for(int lp=mid;lp>=l;--lp){
                while(maxRp+1<=r&&(!(leftMask&2)||(halfOpt[maxRp+1][0]>=halfOpt[lp][0]))&&(!(leftMask&1)||(halfOpt[maxRp+1][1]<=halfOpt[lp][1])))++cnt[disc[++maxRp]];
                while(minRp<=maxRp&&(((rightMask&2)&&(halfOpt[minRp][0]>=halfOpt[lp][0]))||((rightMask&1)&&(halfOpt[minRp][1]<=halfOpt[lp][1]))))--cnt[disc[minRp++]];
                subAns+=cnt[disc[lp]];
            }
        }
    }
    Return res(subAns,r-l+1);
    prefOpt[0][0][l-1]=prefOpt[1][0][r+1]=inf,prefOpt[0][1][l-1]=prefOpt[1][1][r+1]=-inf;
    for(int a=l;a<=r;++a)prefOpt[0][0][a]=min(prefOpt[0][0][a-1],arr[a]),prefOpt[0][1][a]=max(prefOpt[0][1][a-1],arr[a]);
    for(int a=r;a>=l;--a)prefOpt[1][0][a]=min(prefOpt[1][0][a+1],arr[a]),prefOpt[1][1][a]=max(prefOpt[1][1][a+1],arr[a]);
    if(r-l+1!=n){
        mergeSort(lres.ord[0][0][0],rres.ord[0][0][0],eval[0],res.ord[0][0][0]);
        res.ord[1][0][0]=res.ord[0][0][0];
        infected[0][0]=infected[0][1]=r+1;
        infected[1][0]=infected[1][1]=l-1;
        for(int mnmx:{0,1})
            for(int a=mid+1;a<=r;++a)
                if(prefOpt[0][mnmx][a]!=prefOpt[0][mnmx][mid]){
                    infected[0][mnmx]=a;
                    break;
                }
        for(int mnmx:{0,1})
            for(int a=mid;a>=l;--a)
                if(prefOpt[1][mnmx][a]!=prefOpt[1][mnmx][mid]){
                    infected[1][mnmx]=a;
                    break;
                }
        struct Range{
            int lo,hi,mask;
        };
        //Left
        #pragma unroll
        for(int mn:{0,1}){
            #pragma unroll
            for(int mx:{0,1}){
                if(!mn&&!mx)continue;
                static Range ran[3];
                int h=0,bufh=0;
                if(infected[0][0]<=infected[0][1]){
                    if(mid+1<infected[0][0])ran[h++]={mid+1,infected[0][0]-1,0};
                    if(infected[0][0]<infected[0][1])ran[h++]={infected[0][0],infected[0][1]-1,mn<<1};
                    if(infected[0][1]<=r)ran[h++]={infected[0][1],r,mn<<1|mx};
                }
                else{
                    if(mid+1<infected[0][1])ran[h++]={mid+1,infected[0][1]-1,0};
                    if(infected[0][1]<infected[0][0])ran[h++]={infected[0][1],infected[0][0]-1,mx};
                    if(infected[0][0]<=r)ran[h++]={infected[0][0],r,mn<<1|mx};
                }
                for(int i=0;i<h;){
                    int j=i,lo=ran[i].lo,hi=ran[i].hi;
                    while(j<h&&ran[j].mask==ran[i].mask)hi=ran[j++].hi;
                    for(int k:rres.ord[0][(ran[i].mask>>1)&1][ran[i].mask&1])if(lo<=k&&k<=hi)mergeBuf[bufh].push_back(k);
                    i=j,++bufh;
                }
                assert(!mergeBuf[0].empty());
                if(lres.ord[0][mn][mx].size()>mergeBuf[1].size()+mergeBuf[2].size()){
                    mergeSort(mergeBuf[1],mergeBuf[2],eval[0|mn<<1|mx],mergeBuf[3]);
                    mergeSort(mergeBuf[0],mergeBuf[3],eval[0|mn<<1|mx],mergeBuf[4]);
                    mergeSort(lres.ord[0][mn][mx],mergeBuf[4],eval[0|mn<<1|mx],res.ord[0][mn][mx]);
                }
                else{
                    mergeSort(lres.ord[0][mn][mx],mergeBuf[0],eval[0|mn<<1|mx],mergeBuf[3]);
                    mergeSort(mergeBuf[1],mergeBuf[2],eval[0|mn<<1|mx],mergeBuf[4]);
                    mergeSort(mergeBuf[3],mergeBuf[4],eval[0|mn<<1|mx],res.ord[0][mn][mx]);
                }
                for(int x=0;x<5;++x)mergeBuf[x].clear();
            }
        }
        //Right
        #pragma unroll
        for(int mn:{0,1}){
            #pragma unroll
            for(int mx:{0,1}){
                if(!mn&&!mx)continue;
                static Range ran[3];
                int h=0,bufh=0;
                if(infected[1][0]>=infected[1][1]){
                    if(mid>infected[1][0])ran[h++]={infected[1][0]+1,mid,0};
                    if(infected[1][1]<infected[1][0])ran[h++]={infected[1][1]+1,infected[1][0],mn<<1};
                    if(l<=infected[1][1])ran[h++]={l,infected[1][1],mn<<1|mx};
                }
                else{
                    if(mid>infected[1][1])ran[h++]={infected[1][1]+1,mid,0};
                    if(infected[1][0]<infected[1][1])ran[h++]={infected[1][0]+1,infected[1][1],mx};
                    if(l<=infected[1][0])ran[h++]={l,infected[1][0],mn<<1|mx};
                }
                for(int i=0;i<h;){
                    int j=i,lo=ran[i].lo,hi=ran[i].hi;
                    while(j<h&&ran[j].mask==ran[i].mask)lo=ran[j++].lo;
                    for(int k:lres.ord[1][(ran[i].mask>>1)&1][ran[i].mask&1])if(lo<=k&&k<=hi)mergeBuf[bufh].push_back(k);
                    i=j,++bufh;
                }
                if(rres.ord[1][mn][mx].size()>mergeBuf[1].size()+mergeBuf[2].size()){
                    mergeSort(mergeBuf[1],mergeBuf[2],eval[4|mn<<1|mx],mergeBuf[3]);
                    mergeSort(mergeBuf[0],mergeBuf[3],eval[4|mn<<1|mx],mergeBuf[4]);
                    mergeSort(rres.ord[1][mn][mx],mergeBuf[4],eval[4|mn<<1|mx],res.ord[1][mn][mx]);
                }
                else{
                    mergeSort(rres.ord[1][mn][mx],mergeBuf[0],eval[4|mn<<1|mx],mergeBuf[3]);
                    mergeSort(mergeBuf[1],mergeBuf[2],eval[4|mn<<1|mx],mergeBuf[4]);
                    mergeSort(mergeBuf[3],mergeBuf[4],eval[4|mn<<1|mx],res.ord[1][mn][mx]);
                }
                for(int x=0;x<5;++x)mergeBuf[x].clear();
            }
        }
    }
    return res;
}
signed main(){
    iostream::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    arr.resize(n+2),halfOpt.resize(n+2);
    for(int i=0;i<5;++i)mergeBuf[i].reserve(n);
    for(auto i:{&disc,&cnt,&prefOpt[0][0],&prefOpt[0][1],&prefOpt[1][0],&prefOpt[1][1]})i->resize(n+2);
    for(int a=1;a<=n;++a)cin>>arr[a];
    cout<<dnq(1,n).ans<<endl;
}

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

constexpr int HALF_SUM=2000000;
constexpr int K=65535;

int solve(vector<int> a){
    static array<uint32_t,K+1> freq;
    fill(freq.begin(),freq.end(),0);
    vector<int> v; v.reserve(a.size());
    for(int x: a){
        if (x<=K) ++freq[x];
        else v.push_back(x);
    }
    for(int i=1;i<=K>>1;++i){
        if(freq[i]==0) continue;
        freq[i<<1]+=(freq[i]-1)>>1;
        freq[i]=2-(freq[i]&1);
    }
    static bitset<HALF_SUM+1> bs;
    bs.reset(); bs.set(0);
    int S=0;
    for(int i=1;i<=K;++i){
        while(freq[i]--){
            S+=i;
            bs|=(bs<<i);
        }
    }
    for(int x: v){
        S+=x;
        bs|=(bs<<x);
    }
    for(int i=S>>1;i>=0;--i) if(bs[i]) return i;
}

static inline int read_int(){
    int c=_getchar_nolock();
    while(c<'0') c=_getchar_nolock();
    int x=0;
    while(c>='0'){
        x=x*10+(c-'0');
        c=_getchar_nolock();
    }
    return x;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    const int n=read_int();
    if(n==1){
        cout << "0\n";
        return 0;
    }
    vector<int> deg(n,0);
    vector<int> xr(n,0);
    vector<int> sz(n,1);
    vector<int> mx(n,0);
    for (int i=0;i<n-1;++i){
        int u=read_int()-1;
        int v=read_int()-1;
        ++deg[u]; ++deg[v];
        xr[u]^=v; xr[v]^=u;
    }
    for (int i=0;i<n;++i){
        int v=i;
        while(deg[v]==1){
            int p=xr[v];
            sz[p]+=sz[v];
            deg[v]=0;
            --deg[p];
            xr[p]^=v;
            v=p;
        }
    }
    int root=find(sz.begin(),sz.end(),n)-sz.begin();
    xr[root]=-1;
    for(int v=0;v<n;++v){
        if(v==root) continue;
        mx[xr[v]]=max(mx[xr[v]],sz[v]);
    }
    int centroid=0,best=n;
    for(int v=0;v<n;++v){
        int comp=n-sz[v];
        int worst=max(mx[v],comp);
        if(worst<best){best=worst;centroid=v;}
    }
    vector<int> sts;
    for(int v=0;v<n;++v) if(xr[v]==centroid) sts.push_back(sz[v]);
    if(centroid!=root) sts.push_back(n-sz[centroid]);
    long long total=0;
    for(int v=0;v<n;++v) total+=sz[v];
    if(centroid!=root){
        long long delta=0;
        delta+=(long long)n-sz[centroid];
        int child=centroid;
        int par=xr[child];
        long long down=sz[child];
        while(par!=-1){
            long long oldsiz=sz[par];
            long long newsiz=n-down;
            delta+=newsiz-oldsiz;
            down=oldsiz;
            child=par;
            par=xr[par];
        }
        total+=delta;
    }
    long long k=solve(sts);
    cout << total+k*(n-1-k) << '\n';
    return 0;
}

n=int(input())
arr=[]
for i in range(n):arr.append(input().strip().replace('x',''))
for i in range(n):
    cnt=arr[i].count('y')
    arr[i]=arr[i].replace('y','')
    arr[i]+=cnt*'y'

arr=sorted(arr,key=lambda x:(-len(x),x))
print('\n'.join(arr))

Michael's solution:

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

string pi = "31415926535897932384626433832... (truncated copy-paste from internet)";

void solve() {
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++)
        if (s[i] != pi[i]) {
            cout << i << '\n';
            return;
        }
    cout << s.length() << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
}

n=int(input())
b=int(input())
x=int(input())
y=int(input())

s=4*(n-1)*y+(n-2)*(n-2)*x

// there are 4(n-1) squares on the boundary as it is 4*n - 4 (overcounted squares)
// there are (n-2)*(n-2) squares on the interior as we exclude the boundaries so the side length is n-2

print(["Walter will like this lab","Sorry Mr. Fring, no can do"][s>b])

Michael did this one, but it looks like pain...

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

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

    string s;
    cin >> s;
    int a = 0, b = 0;
    char cur = s[0];
    int len = 1;
    for (int i = 1; i < s.length(); i++) {
        if (cur != s[i]) {
            if (len >= 3) {
                if (cur == '<')
                    a -= 20 + (len - 3) * 5;
                else if (cur == '>')
                    a += 20 + (len - 3) * 5;
                else if (cur == 'v')
                    b -= 20 + (len - 3) * 5;
                else if (cur == '^')
                    b += 20 + (len - 3) * 5;
            } else {
                if (cur == '<')
                    a -= 2 * len;
                else if (cur == '>')
                    a += 2 * len;
                else if (cur == 'v')
                    b -= 2 * len;
                else if (cur == '^')
                    b += 2 * len;
            }
            len = 1;
            cur = s[i];
        } else {
            len++;
        }
    }
    if (len >= 3) {
        if (cur == '<')
            a -= 20 + (len - 3) * 5;
        else if (cur == '>')
            a += 20 + (len - 3) * 5;
        else if (cur == 'v')
            b -= 20 + (len - 3) * 5;
        else if (cur == '^')
            b += 20 + (len - 3) * 5;
    } else {
        if (cur == '<')
            a -= 2 * len;
        else if (cur == '>')
            a += 2 * len;
        else if (cur == 'v')
            b -= 2 * len;
        else if (cur == '^')
            b += 2 * len;
    }
    cout << "(" << a << "," << b << ")" << '\n';
}

Explanation coming soon.........

n=int(input())
a=[0]+[int(x)for x in input().split()]
b=0
for i in range(1,n+1):
    b+=max(a[i]-a[i-1],0)
print(b)

DFS through the tree, keeping track of time. Keep track of the node with max time and then size as tiebreaker.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include <vector>
#include <algorithm>
using namespace std;

int lastlay=-1;
int lastnode=-1;

vector<vector<int>> adj(1000);
void dfs(int v,int p,int lay){
        if(lay>lastlay)lastlay=lay,lastnode=v;
        else if(lay==lastlay&&v>lastnode)lastnode=v;
        for (auto&x:adj[v])if(x!=p)dfs(x,v,lay+1);
}

int main()
{
        int r, n; scanf("%d %d", &r, &n);
        r--;
        
        for (int i=0;i<n;i++){int u,v;scanf("%d %d",&u,&v);
                u--;v--;
                adj[u].push_back(v);
                adj[v].push_back(u);
        }
        for (auto&v:adj)sort(v.begin(),v.end());
        dfs(r,r,0);
        printf("%d\n",lastnode+1);
}

Michael did this one, so my explanation might not be great. Just brute force while keeping track of visited letters in O(3^26) time. Since the testcases are random, the average time is a lot less, so brute force works.

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

int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int n, m;
vector<string> v;

int ans = 0;

void dfs(int x, int y, vector<int> vis, int done) {
    ans = max(ans, done);
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        if (vis[v[nx][ny] - 'A']) continue;
        vector<int> vis2 = vis;
        vis2[v[nx][ny] - 'A'] = true;
        dfs(nx, ny, vis2, done + 1);
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        v.push_back(s);
    }

    vector<int> vis(27, false);
    vis[v[0][0] - 'A'] = true;
    dfs(0, 0, vis, 1);
    cout << ans << '\n';
}

Use dp: dp[i][j] represents # of ways to create a parenthesis sequence up to index i with j extra left parenthesis (

If you are on a (: Add dp[i][j] to dp[i+1][j+1]

If you are on a ): Add dp[i][j] to dp[i+1][j-1] if j>0

If you are on a B's turn or a ?: Do both

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

const int MOD = 1e9 + 7;
int add(int a, int b) { return (a + b) % MOD; }

int dp[4001][4001];

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

    int n;
    string s;
    cin >> n >> s;

    if (s[0] == ')') {
        cout << 0 << '\n';
        return 0;
    }

    memset(dp, 0, sizeof dp);

    dp[0][0] = 1;

    for (int i = 0; i < n * 2; i++) {
        for (int j = 0; j < n * 2; j++) {
            if (i & 1) {
                if (j > 0)
                    dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
                dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
            } else {
                if (s[i / 2] == ')') {
                    if (j > 0)
                        dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
                } else if (s[i / 2] == '(')
                    dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
                else if (s[i / 2] == '?') {
                    if (j > 0)
                        dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
                    dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
                } else
                    assert(false);
            }
        }
    }

    cout << dp[2 * n][0] << '\n';
}

This one was fun. We claim that the solution is the same as the previous one pretending that {}[] is the same as (), multiplied by 3 to the power of the # of ?s.

Proof:

First, we can prove that each symbol in A will map to a symbol in B. This is because symbols in A cannot match to other symbols in A, because there are an odd # of symbols in between.

Let us further suppose that there are no ?s. Then, there is a bijection from sequences containing only () restricted by A to sequences containing ()[]{} that are restricted by A because you can change the character (and its matching character in B) back to the original.

For example:

A = ({])}
simplified A = (()))
possible sequence = (((()())))
constrained by original A ({{[]()}})

Each ? means that we have 3x the possibilty for that character ([{ so we multiply by 3^# of ?s.

This is just Michael's code for P8 but modified by me.

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

const ll mod = 1e9 + 7;
ll add(ll a, ll b) { return (a + b) % mod; }

ll dp[4001][4001];

ll binpow(ll x,ll p){
        ll r=1,sq=x;
        while(p){
                if(p&1)r=r*sq%mod;
                sq=sq*sq%mod;p>>=1;
        }
        return r;
}

ll main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    string s;
    cin >> n >> s;

    if (s[0] == ')') {
        cout << 0 << '\n';
        return 0;
    }

    memset(dp, 0, sizeof dp);

    dp[0][0] = 1;

    for (ll i = 0; i < n * 2; i++) {
        for (ll j = 0; j < n * 2; j++) {
            if (i & 1) {
                if (j > 0)
                    dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
                dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
            } else {
                if (s[i / 2] == ')'||s[i / 2] == '}'||s[i / 2] == ']') {
                    if (j > 0)
                        dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
                } else if (s[i / 2] == '('||s[i / 2] == '['||s[i / 2] == '{')
                    dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
                else if (s[i / 2] == '?') {
                    if (j > 0)
                        dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
                    dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
                } else
                    assert(false);
            }
        }
    }
    ll wild=0;
    for (auto x:s)if(x=='?')wild++;

    cout << 1ll*dp[2 * n][0]*binpow(3,wild)%mod << '\n';
}

My favorite problem :) Honestly easier than P9.

Different bounds for rows and columns motivate going through by rows (we assume rows have the smaller of the two dimensions) Note that (by a brute force) there are only 60 valid possibilities for a row. Thus, we can represent bitmasks as numbers between 1-60.

We use bitmask dp: dp[row][mask][mask2] represents the max # of haybales you can get if you are at row i, the current row's haybales are mask2, and the previous row's haybales are mask. Then dp[row][mask][mask2] = max(dp[row-1][pmask][mask] + 1) over all compatible pmasks (compatible meaning that their bits are distinct).

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include <vector>
using namespace std;

#define pcnt __builtin_popcount
#define cnt(x) pcnt(tom(x))

int tom(int x) {
        switch(x) {
                case 0: return 0;case 1: return 1;case 2: return 2;case 3: return 4;case 4: return 8;case 5: return 9;case 6: return 16;case 7: return 17;case 8: return 18;case 9: return 32;case 10: return 33;case 11: return 34;case 12: return 36;case 13: return 64;case 14: return 65;case 15: return 66;case 16: return 68;case 17: return 72;case 18: return 73;case 19: return 128;case 20: return 129;case 21: return 130;case 22: return 132;case 23: return 136;case 24: return 137;case 25: return 144;case 26: return 145;case 27: return 146;case 28: return 256;case 29: return 257;case 30: return 258;case 31: return 260;case 32: return 264;case 33: return 265;case 34: return 272;case 35: return 273;case 36: return 274;case 37: return 288;case 38: return 289;case 39: return 290;case 40: return 292;case 41: return 512;case 42: return 513;case 43: return 514;case 44: return 516;case 45: return 520;case 46: return 521;case 47: return 528;case 48: return 529;case 49: return 530;case 50: return 544;case 51: return 545;case 52: return 546;case 53: return 548;case 54: return 576;case 55: return 577;case 56: return 578;case 57: return 580;case 58: return 584;case 59: return 585;
        }
        return 99;
}

int compat(int m1,int m2,int m3) {
        return pcnt(m1|m2|m3)==pcnt(m1)+pcnt(m2)+pcnt(m3);
}

int main()
{
        int n, m; scanf("%d%d",&n,&m);

        vector<int>mp(n);
        for (int i=0;i<n;i++)for(int j=0;j<m;j++){char x;scanf(" %c",&x);
                if(x=='D')mp[i]|=1<<j;
        }
        for(int i=0;i<n;i++)mp[i]=~mp[i];

        if(n == 1) {
                int mx=0;
                for (int j=0; j<60; j++) {
                        if(tom(j) & mp[0]) continue;
                        mx=max(mx,cnt(j));
                }
                printf("%d\n",mx);
                return 0;
        }


        vector<vector<vector<int>>> dp(n,vector<vector<int>>(60,vector<int>(60)));

        for (int j=0; j<60; j++) {
                for (int k=0;k<60;k++) {
                        if(tom(j)&mp[0])continue;
                        if(tom(k)&mp[1])continue;
                        if(!compat(0,tom(j),tom(k)))continue;
                        dp[1][j][k] = cnt(j)+cnt(k);
                }
        }
        for (int i=2; i<n; i++) {
                for (int j=0; j<60; j++) {
                        for (int k=0;k<60;k++) {
                                if(dp[i-1][j][k]==0)continue;
                                // printf("dp[%d][%d][%d] = %d\n",i-1,j,k,dp[i-1][j][k]);
                                for (int x=0;x<60;x++) {
                                        if(tom(x)&mp[i])continue;
                                        if(!compat(tom(j),tom(k),tom(x)))continue;
                                        dp[i][k][x] = max(dp[i][k][x],dp[i-1][j][k] + cnt(x));
                                        // printf("\t=> dp[%d][%d][%d] = %d\n",i,k,x,dp[i-1][j][k]+cnt(x));
                                }
                        }
                }
        }
        int mx=0;
        for (int j=0;j<60;j++)for(int k=0;k<60;k++)mx=max(mx,dp[n-1][j][k]);
        printf("%d\n",mx);
}