Both "YES" and "NO" are consistent answer (as long as exactly one of them is the answer).

If you print "YES" and get AC, you are getting AC by printing the sample output.

If you print "NO" and get AC, you are getting AC by not printing the sample output.

Never assume just because the carrot is big ... the sample output is correct.

print("NO")

Under what conditions do the bitwise AND of all the elements in the array equal the bitwise OR?

The bitwise AND is equal to the bitwise OR if and only if all the elements in the array are equal.

The total bitwise AND and the total bitwise OR are the same iff all the elements are the same (read hint 2).

Let's call a value $$$v$$$ good if it is possible to make all the elements equal to $$$v$$$ after some amount of operations. $$$v$$$ must contain $$$O$$$ as a submask where $$$O$$$ is the bitwise $$$O$$$ of all the elements in the array. This is true because, for any bit that is ON in any element in the original array, that bit will still be ON after the operation is applied. In turn, any bit that is ON $$$v$$$ that is not ON in $$$O$$$ must not have been ON in any of the elements in the array (otherwise $$$O$$$ would have that bit ON as well). This means the best value of $$$v$$$ to pick is $$$O$$$. To minimize the number of operations used, we should set all the elements to be $$$O$$$, this can be done in $$$1$$$ operation per element (that isn't $$$O$$$ already). So the answer for the first monkey is $$$n - \text{# } O \text{ in } a_{1 \dots n}$$$.

A similar logic applies for $$$A$$$ where $$$A$$$ is the total bitwise AND of all the elements in the array and the bits that are off.

So the final answer is to compare the number of occurrences of $$$O$$$ and $$$A$$$ in the array. $$$or$$$ if $$$O$$$ occurs more, $$$and$$$ if $$$A$$$ occurs more, or $$$sad$$$ otherwise.

Time complexity: $$$O(n)$$$, $$$O(n \log n)$$$, or $$$O(n \log a_i)$$$.

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main(){
    cin.tie(0) -> sync_with_stdio(0);
    int T; cin >> T;
    while(T--){
	int n;
	cin >> n;
	vector<int> arr(n);
	map<int, int> cnt;
    	for(int&x : arr){
    	    cin >> x;
	    cnt[x]++;
	}
    	int or_sum = arr[0], and_sum = arr[0];
    	for(int i = 1; i<n; i++){
    	    or_sum = or_sum|arr[i];
    	    and_sum = and_sum&arr[i];
    	}
	if(cnt[or_sum] == cnt[and_sum]){
	    cout << "sad\n";
    	}else if(cnt[or_sum] > cnt[and_sum]){
	   cout << "or\n";
    	}else{
	   cout << "and\n";
	}	
    }
 
}

It is optimal for each of the friends to try to defeat the first real participant that they encounter, so we can use a greedy algorithm.

We simulate the tournament directly, using friends to defeat real participants whenever possible and keeping track of participants who have already defeated a real participant (We choose friends who can still snipe someone over friends who can't).

// {{{1 my template
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()
// 1}}}
struct { template<typename T> operator T() { T x; cin>>x; return x; } } in;

int main()
{
        int tt = in;
        for(int ttn=0;ttn<tt;ttn++)
        {
                int n=in;
                vector<char> a(2*n-1);
                for (int i=0;i<n;i++) a[i+n-1] = in;
                // A is alternet
                // R is orz person
                // F is friend
                // P is friend but already chosen
                for(int i=n-2;~i;i--) {
                        int x = a[i*2+1], y = a[i*2+2];

                        char& z = a[i];
                        if (x == 'A')
                                z = y=='R'? 'R' : 'A';
                        else if (y == 'A')
                                z = x=='R'? 'R' : 'A';

                        else if (x == 'F')
                                z = y=='R'? 'P' : 'F';
                        else if (y == 'F')
                                z = x=='R'? 'P' : 'F';

                        else if (x == 'R' || y == 'R')
                                z = 'R';

                        else z = 'P';
                }

                printf("%s\n", a[0] == 'A'? "Yes" : "No");
        }
}

How many "days" will pass at most?

Another way to view the problem is this: "Set the first $$$F(1)$$$ numbers to be $$$T$$$, then set the next $$$F(2)$$$ numbers to be $$$K$$$, then set the next $$$F(3)$$$ numbers to be $$$T$$$ ..." where $$$F(x)$$$ is the $$$x$$$'th Fibonacci number ($$$F(1) = 1$$$ and $$$F(2) = 2$$$).

The Fibonacci sequence grows very quickly (approximately exponentially), so within $$$85$$$ terms the $$$10^{18}$$$'th ice cream will be covered. So we can simulate the process with a brute force, figuring out which ice creams were eaten on day $$$i$$$. Finally, we can check if the day we ate a certain ice cream is odd or even to determine the answer.

The time complexity is $$$O(n \log x_i)$$$.

#include <iostream>

using namespace std;

int answer(long long x){
	long long a = 1, b = 1;
	long long total = 0;
	int turns = 0;
	while(total < x){
		total += a;
		turns++;
		a += b;
		b = a - b;
	}
	return turns;
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int n;
	cin >> n;
	for(int i = 1; i<=n; i++){
		long long a; cin >> a;
		int t = answer(a);
		cerr << t << "\n";
		if(t%2 == 1){
			cout << "T";
		}else{
			cout << "K";
		}
	}
}	

There is one original array $$$a$$$ such that after applying the first $$$m$$$ operations, it will become sorted.

Let $$$b_{1 \dots n}$$$ be the only way to arrange the elements in $$$a$$$ such that after applying all the swaps, $$$b_{1 \dots n}$$$ becomes sorted. The question then splits into two parts:

1. Obtaining $$$b$$$

2. Checking if $$$a = b$$$.

So to obtain $$$b$$$, we can sort $$$a$$$ and apply the swaps in reverse order. This is because if we apply the swaps (in the correct order) from $$$b$$$, it will end up as the sorted version of $$$a$$$.

Then to check if $$$a = b$$$, we can maintain a counter for what indices $$$i$$$ $$$a_i = b_i$$$. We can check this for $$$a$$$ and $$$b$$$ initially, and for every query, at most $$$2$$$ indices changed. So we can manually change the counter based on that "small" change. Then the answer to every query is $$$Y$$$ if the counter shows that $$$n$$$ indices are the same across $$$a$$$ and $$$b$$$ or $$$N$$$ otherwise.

The final complexity is $$$O(n + m + q)$$$. It turns out that just comparing $$$a = b$$$ when $$$a$$$ and $$$b$$$ are both vectors can pass in C++. I guess the bounds were too loose/test data wasn't strong enough.

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
  cin.tie(0) -> sync_with_stdio(0);
    int n, m, q;
	cin >> n >> m >> q;
	vector<int> p(n);	
	vector<pair<int, int>> arr(m);
	for(int i = 0; i<n; i++){
		cin >> p[i];
	}
	for(int i = 0; i<m; i++){
		int a, b;
		cin >> a >> b;
		a--, b--;
		arr[i] = pair(a, b);
	}
	vector<int> srt(n);
	for(int i = 0; i<n; i++){
		srt[i] = p[i];
	}
	sort(srt.begin(), srt.end());
	reverse(arr.begin(), arr.end());
	for(auto [a, b] : arr){
		swap(srt[a], srt[b]);
	}
	int cnt = 0;
	for(int i = 0; i<n; i++){
		if(srt[i] == p[i]) cnt++;
	}
	string ans;
	for(int i = 0; i<q; i++){
		int a, b;
		cin >> a >> b;
		a--, b--;
		cnt -= (srt[a] == p[a]);
		cnt -= (srt[b] == p[b]);
		swap(p[a], p[b]);
		cnt += (srt[a] == p[a]);
		cnt += (srt[b] == p[b]);
		if(cnt == n) ans.push_back('Y');
		else ans.push_back('N');
	}
	cout << ans << "\n";
  
  return 0;
}

Consider two equal subsequences (by character) that differ by exactly $$$1$$$ index chosen. How can you determine if two such subsequences exist?

If for all indices $$$i$$$, there is no other $$$j$$$ such that $$$abs(i - j) \leq n - k$$$ and $$$s_i = s_j$$$ then all subsequences are unique.

We only care about subsequences that differ by exactly $$$1$$$ index chosen, since if more than $$$1$$$ were taken, we can just switch some of them to be the same without affecting the fact that all the subsequences are not unique.

We can check this condition with a for loop in $$$O(n)$$$ or $$$O(\alpha n)$$$ where $$$\alpha$$$ is the alphabet size ($$$26$$$).

 
#include <iostream>
#include <string>
#include <array>
using namespace std;

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int T;
	cin >> T;
	while(T--){
		int n, k;
		cin >> n >> k;
		string s;
		cin >> s;
		array<int, 26> occ;
		occ.fill(-1);
		int work = 1;
		for(int i = 0; i<n; i++){
			char c = s[i];
			if(occ[c-'a'] != -1){
				if((i - occ[c-'a']) <= (n - k)){
					work = 0;
				}
			}
			occ[c-'a'] = i;
		}	
		if(work) cout << "Yes\n";
		else cout << "No\n";
	}
}

The concatenation of $$$a$$$ and $$$b$$$ is $$$a \cdot 10^{\lceil \log_{10}(a) \rceil} + b$$$.

$$$10^{\lceil \log_{10}(x) \rceil}$$$ is the smallest power of $$$10$$$ no less than $$$x$$$.

For a fixed $$$b$$$, how can we count all the valid $$$a$$$ such that the concatenation is divisible by $$$K$$$?

Consider reading the two hints as the solution goes off of them.

Let's enumerate $$$tp$$$ as the power of ten which is $$$10^{\lceil \log_{10}(j) \rceil}$$$. For $$$a \cdot tp + b \equiv 0 \pmod{K}$$$, we need $$$a \cdot tp \equiv -b \pmod{K}$$$. So we can store a map of all the frequencies of $$$a \cdot tp \text{ mod } K$$$, and for each $$$b$$$, add the frequency of $$$-b \text{ mod } K$$$. It is important to only add for $$$b$$$ such that $$$10^{\lceil \log_{10}(j) \rceil} = tp$$$.

The final time complexity is $$$O(n \log x_i \log n)$$$.

def ceil10(x):
    y = 1
    while y <= x:
        y *= 10
    return y

assert ceil10(0) == 1
assert ceil10(9) == 10
assert ceil10(19) == 100
assert ceil10(1e9) == 10000000000

T = int(input())

for _ in range(T):
    N, K = map(int, input().split())
    a = list(map(int, input().split()))

    cnt = 0
    for tp in [10**p for p in range(1, 10)]:  # Similar to 1e10 in C++
        mp = {}
        for i in range(N):
            x = (K - tp % K * a[i] % K) % K  # -a[i]*tp
            mp[x] = mp.get(x, 0) + 1

        for i in range(N):
            if ceil10(a[i]) != tp:
                continue
            x = (K - tp % K * a[i] % K) % K  # -a[i]*tp
            mp[x] -= 1
            cnt += mp.get(a[i] % K, 0)
            mp[x] += 1

    print(str(cnt))

$$$abs(a - b) = \max(a, b) - \min(a, b)$$$

Consider the odd and even indices separately.

Let $$$ao$$$ and $$$ae$$$ denote the elements in $$$a$$$ in odd and even indices respectively (both should have length $$$\frac{n}{2}$$$.

Define $$$bo$$$ and $$$be$$$ similarly for $$$b$$$.

Also for the sake of simplicity, lets duplicate each array (for instance $$$ao_{i} = ao_{i + \frac{n}{2}}$$$.

Let's find the answer for each of the $$$4$$$ parts separately. To find the greatest awkwardness for $$$ao_i$$$, we need to find the max value in $$$bo_{i \dots i + k}$$$. This can be done with a sliding window in $$$O(n)$$$ or $$$O(n \log n)$$$.

A similar strategy works for $$$bo$$$ and $$$be$$$.

Let $$$p'$$$ denote the reverse of $$$p$$$. We can use the same algorithm for $$$bo'$$$ and $$$ao'$$$ and for $$$be'$$$ and $$$ae'$$$. The total complexity is $$$O(n)$$$ or $$$O(n \log n)$$$ depending on how you did the sliding window.

 
#include <iostream>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iterator>
#define all(x) x.begin(), x.end()

using namespace std;


long long answer(vector<int> A, vector<int> B, int steps){
	//same parity
	int n = A.size();
	multiset<int> ms;
	for(int i = 0; i<steps; i++){
		ms.insert(A[i]);
	}
	long long ret = 0;
	for(int i = 0; i<B.size(); i++){
		auto [mn, mx] = make_pair(*ms.begin(), *prev(ms.end()));
		ret += max(B[i] - mn, mx - B[i]);
		ms.erase(ms.lower_bound(A[i%n]));
		ms.insert(A[steps%n]);
		steps++;
	}
	return ret;
}



void solve(){
	int n; cin >> n;
	long long k; cin >> k;
	k--;
	vector<int> A(n), B(n);
	vector<int> Ao, Ae, Bo, Be; //A odd, A even, etc
	for(int i = 0; i<n; i++){
		cin >> A[i];
		if(i%2 == 0) Ae.push_back(A[i]);
		else Ao.push_back(A[i]);
	}
	for(int i = 0; i<n; i++){
		cin >> B[i];
		if(i%2 == 0) Be.push_back(B[i]);
		else Bo.push_back(B[i]);
	}

	auto ansAo = answer(Bo, Ao, min(k+1, (long long)n/2));
	auto ansAe = answer(Be, Ae, min(k+1, (long long)n/2));
	reverse(all(Ao)); reverse(all(Ae));
	reverse(all(Bo)); reverse(all(Be));
	auto ansBo = answer(Ao, Bo, min(k+1, (long long)n/2));
	auto ansBe = answer(Ae, Be, min(k+1, (long long)n/2));
	cout << ansAo + ansBo + ansAe + ansBe << "\n";
}


int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int T; cin >> T;
	for(int i = 0; i<T; i++){
		solve();
	}
	return 0;
}

I drank the solution last night. Refer to the solution code for now until I titrate another one.

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n'
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
template <class T> istream &operator>>(istream& in, vector<T> &v) {for (auto& i : v) in >> i; return in;}

#ifdef HORI
#include "../../lib/debug.h"
#else
#define dbg(...)
#endif

const int M = 18;

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, l, r; cin >> n >> l >> r;
  vi a(n); cin >> a;
  vpi s;
  FOR(b, 0, M) {
    int z = 0, o = 0;
    FOR(i, 0, n) {
      if (a[i] & (1 << b)) {
        o++;
      } else {
        z++;
      }
    }
    s.pb({z * (1 << b), o * (1 << b)});
  }
  int ans = 0;
  set<int> st;
  FOR(mask, 0, (1 << M)) {
    int sum = 0;
    FOR(i, 0, M) {
      if ((1 << i) & mask) {
        sum += s[i].f;
      } else {
        sum += s[i].s;
      }
    }
    st.insert(sum);
  }
  for (int sum : st) {
    int nr = r - sum;
    int nl = l - sum;

    if (nr >= 0) {
      ans += nr / ((1 << M) * n) + 1;
    } 
    if (nl > 0) {
      ans -= (nl - 1) / ((1 << M) * n) + 1;
    }
  }
  cout << ans << endl;
}

Solve each test case in $$$O(R - L)$$$ time.

Let $$$f(i)$$$ be $$$0$$$ if $$$i$$$ is not divisible by $$$3$$$ or the number of $$$3$$$'s in the base-$$$10$$$ representation of $$$i$$$ otherwise.

As there are $$$(R - i + 1)(L - i + 1)$$$ choices of $$$l$$$ and $$$r$$$ such that $$$L \leq l \leq i \leq r \leq R$$$.

Can you simplify the formula?

We can rewrite the terms as

We can consider the sum to be $$$A \sum_{i = L}^{r} f(i) + B \sum_{i = L}^{R} if(i) + C \sum_{i = L}^{R} i^2f(i)$$$ where $$$A$$$, $$$B$$$, and $$$C$$$, are constants only dependant on $$$L$$$ and $$$R$$$. In particular (in the $$$3$$$rd hint), $$$A = (R + 1)(- L + 1), B = (-(-L + 1) + (R + 1)), C = -1$$$.

We can precompute prefix sums on $$$\sum f(i)$$$, $$$\sum if(i)$$$, and $$$\sum i^2f(i)$$$ to evaluate those parts of the sum in constant time. The final complexity is $$$O(R)$$$ precomputation and $$$O(1)$$$ per test case. Be careful of integer overflow.

 
#include <iostream>
using namespace std;
#define ll long long 

const int MX = 1e6+10;
const ll mod = 998244353;

ll pre[MX], prelin[MX], presq[MX];

int f(int x){
	if(x == 0) return 0;
	return (x%10 == 3) + f(x/10);
}

//(r - i + 1)(i - l + 1)f(i)
//(r+1)(-l+1)sum[i] + (-(-l+1) + r+1)*i*sum[i] + -i^2*sum[i]

void solve(){
	int l, r;
	cin >> l >> r;
	ll a = 1ll*(r+1)*(1+mod-l)%mod*(pre[r] + mod - pre[l-1])%mod;
	ll b = 1ll*(mod + -(-l + 1) + r + 1)*(prelin[r] + mod - prelin[l-1])%mod;
	ll c = 1ll*(mod -1)*(presq[r] + mod - presq[l-1])%mod;
	cout << (a + b + c)%mod << "\n";
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	for(int i = 1; i<=(int)(1e6); i++){
		if(i%3 == 0){
			int F = f(i);
			pre[i] = F;
			prelin[i] = F*i;
			presq[i] = 1ll*F*i*i%mod;
		}
		pre[i] += pre[i-1];
		prelin[i] += prelin[i-1];
		presq[i] += presq[i-1];
		if(prelin[i] >= mod) prelin[i] %= mod;
		if(presq[i] >= mod) presq[i] %= mod;
	}
	int T; cin >> T;
	while(T--){
		solve();
	}
	return 0;
}
 

Each edge can be treated as being undirected

Consider each connected component separately.

Each connected component is a tree with an edge. How would you solve it on a tree without the extra edge?

If there was no extra edge, this is an MIS (maximum independent set) on a tree. This can be done with a tree dp (dynamic programming) of $$$dp[u][0/1]$$$ denotes the max sum for the subtree of node $$$u$$$ with $$$0/1$$$ denoting whether or not we took node $$$u$$$ or not.

$$$dp[u][0] = \sum\limits_{v \text{ is adjacent to }u} \max(dp[v][0], dp[v][1])$$$

$$$dp[u][0] = a_u + \sum\limits_{v \text{ is adjacent to }u} dp[v][0]$$$

For each connected component, we can pick some edge $$$(r, p)$$$ such that the graph such that it becomes a tree. Let's root the tree at $$$r$$$. The only change this extra edge makes to the answer is that we cannot take both nodes $$$p$$$ and node $$$r$$$ at the same time.

So this motivates adding another flag to the dp to check if we took node $$$u$$$ or not. Let $$$dp[u][0/1][0/1]$$$ denote the best answer for the subtree of node $$$u$$$ with the first flag checking if we took node $$$u$$$ or not and the second flag checking if we took node $$$p$$$ (if $$$p$$$ isn't in the subtree of node $$$u$$$, $$$dp[u][0/1][1]$$$ isn't defined). You can check the code below for transitions.

The total time complexity is $$$O(n)$$$.

The code may look long but the transitions are almost all the same.

#include <iostream>
#include <cmath>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <array>


#define sz(x) ((int)(x.size()))
#define all(x) x.begin(), x.end()
#define pb push_back

using ll = long long;
const int MX = 2e5 +10, int_max = 0x3f3f3f3f;

using namespace std;

int par[MX];

ll dp[MX][2][2]; //took/not took | took good node/took bad node

vector<int> adj[MX];

int cost[MX], vis[MX], dsu[MX];
int n;

int find(int u){
	if(dsu[u] != u) dsu[u] = find(dsu[u]);
	return dsu[u];
}

void gpar(int u, int p){ //generate the parents
	par[u] = p;
	for(int v : adj[u]){
		if(v == p) continue;
		gpar(v, u);
	}
}

void gvis(int u){ //mark all the ancestors of a node
	if(u == 0) return ;
	vis[u] = 1;
	gvis(par[u]);
}	

void dfs(int u, int p, int bad){
	for(int v : adj[u]){
		if(v == p) continue;
		dfs(v, u, bad);
	}
	if(vis[u] == 0){
		ll sum0 = 0, sum1 = 0;
		for(int v : adj[u]){
			if(v == p) continue;
			sum0 += max(dp[v][0][0], dp[v][1][0]);
			sum1 += dp[v][0][0];
		}
		dp[u][0][0] = sum0;
		dp[u][1][0] = sum1 + cost[u];
	}else if(u == bad){
		ll sum0 = 0, sum1 = 0;
		for(int v : adj[u]){
			if(v == p) continue;
			sum0 += max(dp[v][0][0], dp[v][1][0]);
			sum1 += dp[v][0][0];
		}
		dp[u][0][0] = sum0;
		dp[u][1][1] = sum1 + cost[u];	
	}else{
		for(int j = 0; j<2; j++){
			ll sum0 = 0, sum1 = 0;
			for(int v : adj[u]){
				if(v == p) continue;
				if(vis[v]){
					sum0 += max(dp[v][0][j], dp[v][1][j]);
					sum1 += dp[v][0][j];
				}else{
					sum0 += max(dp[v][0][0], dp[v][1][0]);
					sum1 += dp[v][0][0];
				}
			}
			dp[u][0][j] = sum0;
			dp[u][1][j] = sum1 + cost[u];
		}
	}
}

ll go(pair<int, int> bad){
	auto [u, v] = bad;
	if(u == v) return 0;
	gpar(u, 0);
	gvis(v);
	dfs(u, 0, v);
	return max({dp[u][0][0], dp[u][0][1], dp[u][1][0]});
}

int main(){
	cin >> n;
	for(int i = 1; i<=n; i++) dsu[i] = i;
	vector<pair<int, int>> bad;
	for(int i =1; i<=n; i++){
		cin >> cost[i];
		int j;
		cin >> j;
		if(find(i) == find(j)){
			bad.push_back({i, j});
		}else{
			dsu[find(i)] = find(j);
			adj[i].pb(j);
			adj[j].pb(i);
		}
	}
	ll ans = 0;
	for(auto p : bad){
		ans += go(p);
	}
	cout << ans << "\n";
}

Let $$$lcp(i, j)$$$ denote the longest common prefix of the suffixes starting at $$$s_i$$$ and $$$s_j$$$. This can also be seen as the maximum number of characters that can be extended from $$$s_i$$$ and $$$s_j$$$ such that both substrings are still equal.

Let $$$len = r - l + 1$$$. Note that an answer of $$$l' \ r'$$$ can also be seen as $$$l' \ l' + len$$$.

For a fixed $$$l$$$, $$$l'$$$ will provide an answer for an interval of $$$len$$$. At some $$$len$$$, there will be no different characters between $$$s_{l \dots l + len}$$$ and $$$s_{l' \dots l' + len}$$$. At some larger $$$len$$$, there will be more than one different character.

Then for a fixed $$$l$$$, the interval of len for which $$$l'$$$ is a valid answer is (define $$$c = lcp(l, l')$$$) $$$[c + 1, lcp(l + c + 1, l' + c + 1)]$$$. This is because for any $$$len < c + 1$$$, there are $$$0$$$ differences between $$$s_{l \dots l + len}$$$ and $$$s_{l' \dots l' + len}$$$. More importantly, however, is that $$$lcp(l + c + 1, l' + c + 1)$$$ denotes the longest common prefix after one error is accounted for (hence the $$$+c + 1$$$. So any $$$len > lcp(l + c + 1, l' + c + 1)$$$ will have at least $$$2$$$ differences.

Use these facts to make an $$$O(n^2 \log n + q)$$$ solution.

For each $$$l$$$, we can first generate all the intervals of $$$len$$$ for each $$$l'$$$. Then we can do a sweep where we maintain a set of "active" intervals for each $$$len$$$. At $$$len = c+1$$$, we can insert $$$l'$$$ to our active set, then at $$$len = lcp(l + c + 1, l' + c + 1) + 1$$$, we can remove it from our set. For each $$$len$$$, we check if any interval is active, and if so, store its $$$l'$$$ as a valid answer for a query with that $$$l$$$ and $$$len$$$.

vector<int> process(vector<array<int, 3>> arr){ //stores the intervals as [lo, hi, l']
	set<int> pres;
	vector<vector<int>> events(n+2);
	for(auto [a, b, c] : arr){
		events[a].pb(c);
		events[b+1].pb(-c);
	}
	vector<int> ans(n+1, 0);
	for(int i = 0; i<=n; i++){
		for(int x : events[i]){
			if(x < 0) pres.erase(-x);
			else pres.insert(x);
		}
		if(pres.size()) ans[i] = *pres.begin();
		else ans[i] = 0;
	}
	return ans;
}

This gives an $$$O(n^2 \log n + q)$$$ solution as we need a set.

$$$O(n^2 \log n)$$$ can't seem to pass with $$$n \leq 7000$$$, so can we cut off the log?

Please read the hints above, most of the solution is contained in there.

Yes, we can cut the log, and there are many ways to do so. Here I will present one of them.

So for a fixed $$$l$$$, over many choices of $$$l'$$$ such that the interval of valid $$$len$$$ starts at some $$$lo$$$, we would want to pick the $$$l'$$$ that has the highest $$$hi$$$ of valid $$$len$$$. This is since greedily, a $$$l'$$$ with more candidates is better. Then we can sort these intervals in linear time with counting sort; we can sort by left endpoint by simply storing for each left endpoint the best right endpoint (and its $$$l'$$$) and just looping over the left endpoints in order from $$$1 \dots n$$$.

So after we have sorted these intervals, we can set $$$len \in [intervals_{i, left}, \min(intervals_{i, right}, intervals_{i+1, left}-1)]$$$ with the $$$l'$$$ associated with that interval. This will amortize as each $$$len$$$ is acted on at most once by some interval (or not acted on at all).

The final complexity is $$$O(n)$$$ processing for each $$$l$$$, giving a total of $$$O(n^2 + q)$$$.

The contestant yam had such a clean code, I just stole his instead of the model. :thumbs:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

const int N = 7007;
int n, q;
string s;
int p[N][N], ans[N][N];

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

    cin >> n >> q >> s;
    s = " " + s;

    for (int i = n; i >= 1; i--)
        for (int j = n; j >= 1; j--)
            p[i][j] = (s[i] == s[j] ? p[i + 1][j + 1] + 1 : 0);

    for (int i = 1; i <= n; i++) {
        vector<array<int, 2>> pts(n + 1);

        for (int j = 1; j <= n; j++) {
            int l = i + p[i][j], r = j + p[i][j];

            if (max(l, r) > n)
                continue;

            // range: l -> l + p[l + 1][r + 1]
            pts[l] = max(pts[l], {l + p[l + 1][r + 1], j});
        }

        int r = -1;
        for (int j = 1; j <= n; j++) {
            for (int k = max(r + 1, j); k <= pts[j][0]; k++)
                ans[i][k] = pts[j][1];
            r = max(r, pts[j][0]);
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;

        if (!ans[l][r])
            cout << 0 << ' ' << 0 << '\n';
        else {
            cout << ans[l][r] << ' ' << ans[l][r] + (r - l) << '\n';
        }
    }

    return 0;
}

By the linearity of expectation, we can find the expected number of steps to go from node $$$u$$$ to node $$$v$$$ as the expected amount of time to cross each edge for the first time.

Solve the subtask for $$$t = 1$$$. How do you compute the expected number of steps needed go to from node $$$u$$$ to its parent?

Let $$$P_u(v)$$$ be the probability you go to node $$$v$$$ in $$$1$$$ step if you start at node $$$u$$$.

Let $$$E_u(v)$$$ denote the expected number of steps needed to go from node $$$u$$$ to node $$$v$$$ (note that $$$E_u(v)$$$ is not necessarily equal to $$$E_v(u)$$$).

Let $$$p_u$$$ denote the parent of node $$$u$$$ ($$$p_1$$$ is undefined).

Let $$$c_u$$$ denote the children of node $$$u$$$, or all the nodes adjacent to node $$$u$$$ other than $$$p_u$$$ (if it exists).

Let $$$up_u$$$ denote the expected number of steps needed to go from $$$u$$$ to $$$p_u$$$ (as before, $$$up_1$$$ is undefined). The most important observation is that we can define $$$up_u$$$ as a linear equation consisting of $$$up_u$$$, $$$up_v$$$ for $$$v \in c_u$$$ and $$$P_u(v)$$$ (with $$$up_u$$$ on both sides of the equation).

This is because there is a $$$P_u(p)$$$ chance to "escape" instantly and a $$$P_v(u)$$$ chance to go into the subtree of any $$$v$$$ which is a child of $$$u$$$. Most important, the expected amount of steps it takes is $$$1 + up_v + up_u$$$. You take $$$1$$$ step to go to node $$$v$$$, then you take $$$up_v$$$ steps to get back to node $$$u$$$, and finally, you take $$$up_u$$$ steps to "escape."

Let $$$down_u$$$ denote the expected number of steps needed to go from $$$p_u$$$ to $$$u$$$ (as before, $$$down_1$$$ is undefined). The same trick works for defining $$$down_u$$$.

Let $$$prob(u)$$$ denote the probability you go from node $$$p_u$$$ to node $$$u$$$. In particular, $$$prob(1) = 0$$$.

We can precompute $$$up_u$$$ with a bottom-up dfs and $$$down_u$$$ with a top-down dfs.

Finally, to answer a query of $$$s \ t$$$, let's first find the lca (least common ancestor) $$$l$$$ of $$$s$$$ and $$$t$$$. We then need to sum $$$up_u$$$ on the path from $$$s$$$ to $$$l$$$ (excluding $$$l$$$) and sum $$$down_u$$$ on the path from $$$l$$$ to $$$t$$$ (excluding $$$l$$$).

This can be done with prefix sums and any reasonable lca algorithm like binlifting or HLD. The final complexity is $$$O(n \log mod + n \log n)$$$.

#include <iostream>
#include <cmath>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <array>
#include <functional>

#define sz(x) ((int)(x.size()))
#define all(x) x.begin(), x.end()
#define pb push_back

#ifndef LOCAL
#define cerr while(0) cerr
#endif

using ll = long long;

const ll mod = (1 << (23)) * 119 +1, ll_max = 1e18;
const int MX = 2e5 +10, int_max = 0x3f3f3f3f;

struct {
  template<class T>
  operator T() {
    T x; std::cin >> x; return x;
  }
} in;

using namespace std;



struct hld{
	vector<int> dep, sz, par, head, tin, out, tour;
	vector<vector<int>> adj;
	int n, ind;
	hld(){}
	hld(vector<pair<int, int>> edges, int rt = 1){
		n = sz(edges) + 1;
		ind = 0;
		dep = sz = par = head = tin = out = tour = vector<int>(n+1, 0);
		adj = vector<vector<int>>(n+1);
		for(auto [a, b] : edges){
			adj[a].pb(b);
			adj[b].pb(a);
		}
		dfs(rt, 0);
		head[rt] = rt;
		dfs2(rt, 0);
	}
	void dfs(int x, int p){
		sz[x] = 1;
		dep[x] = dep[p] + 1;
		par[x] = p;
		for(auto &i : adj[x]){
			if(i == p) continue;
			dfs(i, x);
			sz[x] += sz[i];
			if(adj[x][0] == p || sz[i] > sz[adj[x][0]]) swap(adj[x][0], i);
		}
	}
	void dfs2(int x, int p){
		tour[ind] = x;
		tin[x] = ind++;
		for(auto &i : adj[x]){
			if(i == p) continue;
			head[i] = (i == adj[x][0] ? head[x] : i);
			dfs2(i, x);
		}
		out[x] = ind;
	}
	
	int k_up(int u, int k){
		if(dep[u] <= k) return -1;
		while(k > dep[u] - dep[head[u]]){
			k -= dep[u] - dep[head[u]] + 1;
			u = par[head[u]];
		}
		return tour[tin[u] - k];
	}

	int lca(int a, int b){
		while(head[a] != head[b]){
			if(dep[head[a]] > dep[head[b]]) swap(a, b);
			b = par[head[b]];
		}
		if(dep[a] > dep[b]) swap(a, b);
		return a;
	}
} tr;

ll sum[MX], inv[MX], weight[MX]; //1/sum[u], weight to escape
vector<pair<int, ll>> adj[MX]; //node v and weight from u -> v
int par[MX], dep[MX];

ll up[MX], down[MX];
ll pup[MX], pdown[MX];

int n, q;

ll binpow(ll a, ll b = mod-2){
	if(a == 0 && b == mod-2){
		cout << "-1\n";
		exit(1);
	}
	ll ans = 1;
	for(int i = 1; i<=b; i*=2){
		if(i&b) (ans *= a) %= mod;
		(a *= a) %= mod;
	}
	return ans;
}

void dfs(int u, int p){
	par[u] = p;
	dep[u] = dep[p]+1;
	sum[u] = 0;
	for(auto [v, w] : adj[u]){
		sum[u] += w;
		if(v == p){
			weight[u] = w;
		}else{
			dfs(v, u);
		}
	}
	inv[u] = binpow(sum[u]);
}
//up[u] denotes the EV to start at node u and escape to the parent
//up[1] is undefined

//up[u] = sum(prob(of going to v)(up[v] + up[u] + 1)) + (prob of escaping now)
//up[u](1 + sum of probs) = sum of prob * (up[v] + 1) + prob of escaping now

//down[u] denotes the EV to start at the parent of node u and escape to node u
//down[1] is undefined
//down[u] = (prob of going up)(down[par[u]] (or 0 if u is the root) + down[u] + 1) + (prob of going to v when v != u)(up[v] + down[u] + 1) + (prob of going to u)
//(1 - prob of going up -prob of going to v for v != u from p)down[u] = prob of going up*(down[par[u]]+1) + prob of going to v * (up[v] + 1) + prob of going to u


void get_up(int u, int p){
	ll go_down = 0, prob = 0;
	for(auto [v, w] : adj[u]){
		if(v == p) continue;
		get_up(v, u);
		ll pr = 1ll*w*inv[u]%mod;
		go_down += pr*(up[v] + 1)%mod;
		prob += pr;
	}
	go_down %= mod;
	prob %= mod;
	if(p != 0){
		ll escape = weight[u]*inv[u]%mod;
		up[u] = (go_down + escape)*binpow(1 + mod - prob)%mod;
	}
}

void get_down(int u, int p){
	//find it for all the children
	ll go_down = 0;
	ll go_up = (p == 0 ? 0 : (weight[u]*inv[u])%mod*(down[u] + 1)%mod);
	ll prob = (p == 0 ? 0 : (weight[u]*inv[u]%mod));
	for(auto [v, w] : adj[u]){
		if(v == p) continue;
		ll pr = 1ll*w*inv[u]%mod;
		go_down += pr*(up[v]+1)%mod;
		prob += pr;
	}
	go_down %= mod;
	prob %= mod;
	for(auto [v, w] : adj[u]){
		if(v == p) continue;
		ll pr = 1ll*w*inv[u]%mod;
		go_down += mod - pr*(up[v]+1)%mod; 
		prob += mod - pr;
		prob %= mod;
		go_down %= mod;
		down[v] = (go_up + go_down + pr)*binpow(1 + mod - prob)%mod;
		prob += pr;
		go_down += pr*(up[v]+1)%mod;
		prob %= mod;
		go_down %= mod;
		get_down(v, u);
	}
}

void get_psum(int u, int p){
	for(auto [v, w] : adj[u]){
		if(p == v) continue;
		pup[v] = (pup[u] + up[v])%mod;
		pdown[v] = (pdown[u] + down[v])%mod;
		get_psum(v, u);
	}
}	


ll answer(int s, int t){
	int l = tr.lca(s, t);
	ll u = pup[s] + mod - pup[l];
	ll d = pdown[t] + mod - pdown[l];
	return (u + d)%mod;
}

void cl(){
	for(int i = 1; i<=n; i++){
		adj[i].clear();
		par[i] = weight[i] = inv[i] = dep[i] = 0;
		up[i] = down[i] = pup[i] = pdown[i] = 0;
	}
}

void solve(){
	n = in, q = in;
	vector<pair<int, int>> edges;
	for(int i = 2; i<=n; i++){
		int u = in, v = in;
		int a = in, b = in;
		adj[u].pb({v, a});
		adj[v].pb({u, b});
		edges.push_back({u, v});
	}
	tr = hld(edges);
	dfs(1, 0);
	get_up(1, 0);
	get_down(1, 0);
	get_psum(1, 0);

	for(int i = 1; i<=q; i++){
		int s = in, t = in;
		cout << answer(s, t) << "\n";
	}
	cl();
}

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

  int T = 1;
	cin >> T;
  for(int i = 1; i<=T; i++){
		solve();
	}
  return 0;
}

You can know the winner of a prefix with simulation.

You can know the winner of a suffix with dp and an stack.

Think about the parity of the length of the subarray $$$[l, r]$$$.

The hints briefly sum up the solution of the problem step by step, but we will provide a more detailed explanation now.

Each query splits the array into three parts, the subarray $$$[0, l-1]$$$, the subarray $$$[l, r]$$$, and the subarray $$$[r + 1, n]$$$.

First, we need to calculate the winner of each prefix with a simple simulation, let the winner of the $$$i$$$-th prefix be $$$pre_{i}$$$.

We also have to calculate the winner of each suffix with dp and an stack to find the closest element greater or equal to the right.

To know what happens in the suffix $$$[l, n-1]$$$ we have to think about three cases:

If $$$a_{pre_{i}}$$$ is greater than every element in the suffix $$$[l, n-1]$$$ the winner of the tournament will be $$$pre_{i}$$$.

If value $$$x$$$ of the query is greater or equal to $$$a_{pre_{i}}$$$ we have to check the parity of the length subarray and if it's even the answer will be the winner of the suffix $$$[r+1, n-1]$$$.

Otherwise, if the length of the subarray is odd, the winner will be either $$$r$$$, or the winner of the subarray $$$[r+1, n-1]$$$. This can be checked in the same way as the first case and if x is not greater than every element in the subarray $$$[r+1, n-1]$$$ it can be shown the answer will be the winner of the suffix $$$[r+1, n-1]$$$.

Time Complexity: $$$O(n)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;
 
const int N = 69e4 + 4, inf = INT_MAX;
 
int t, n, q, a[N], nxt[N], dp[N], pre[N];
pair<int, int> sufMx[N];
stack<int> st;
 
int solve(int idx, int x, int r) {
    if (x > sufMx[r].first) return idx;
    else if (x == sufMx[r].first) return dp[sufMx[r].second+1];
    else return dp[r];
}
 
signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> t;
  while (t--) {
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }
 
    st = stack<int>();
    for (int i = n-1; i >= 0; i--) {
      while (!st.empty() && a[st.top()] < a[i]) st.pop();
      
      int x = (st.empty() ? n : st.top());
 
      if (st.empty()) {
        dp[i] = i;
        nxt[i] = n;
      }
      else if (a[x] == a[i]) {
        dp[i] = (x+1 < n ? dp[x+1] : n);
        nxt[i] = x+1;
      }
      else {
        dp[i] = dp[x];
        nxt[i] = x;
      }
 
      st.push(i);
    }
    nxt[n] = dp[n] = pre[n] = n;
 
    int x = 0;
    for (int i = 0; i < n; i++) {
        if (nxt[x] == i) x = nxt[x];
        pre[i] = x;
    }
    
    sufMx[n] = make_pair(-inf, n);
    for (int i = n-1; i >= 0; i--) {
        if (a[i] > sufMx[i+1].first) sufMx[i] = make_pair(a[i], i);
        else sufMx[i] = sufMx[i+1];
    }
    
    while (q--) {
        int l, r, x;
        cin >> l >> r >> x;
        l--; r--;
        
        int y = (l ? pre[l-1] : -1);
        
        if (y == -1 || a[y] < x) {
            if (!((r-l+1) & 1)) cout << dp[r+1]+1 << "\n";
            else {
                cout << solve(r, x, r+1)+1 << "\n";
            }
        }
        else if (a[y] == x) {
            if (!((r-l+2) & 1)) cout << dp[r+1]+1 << "\n";
            else {
                cout << solve(r, x, r+1)+1 << "\n";
            }
        }
        else { // a[y] > x
            cout << solve(y, a[y], r+1)+1 << "\n";
        }
    }
  }
}

Solve the problem in $$$O(n)$$$ or $$$O(n \log n)$$$.

Let $$$p = \frac{a}{100}$$$ and $$$q = 1 - p$$$.

The answer is

$$$i$$$ enumerates the number of sniper chips obtained.

$$$\lfloor{\frac{a}{b}}\rfloor = \frac{a}{b} - \frac{a \text{ mod } b}{b}$$$

How can we frame the question in terms of $$${n - i} \text{ mod } {x}$$$?

For simplicity, let's have $$$i$$$ enumerate the number of caster chips instead of the sniper chips.

Then using the definition of floor, we can rewrite this as

$$$\sum_{i = 0}^{n} {n \choose i}p^{i}q^{n - i} i = pn$$$ (this can be interpreted as "If you have a coin that flips heads with probability $$$p$$$ and tails with probability $$$1 - p$$$, what is the expected number of heads you obtain after $$$n$$$ flips?")

So now the question boils down to finding the expected value of $$$ \text{# caster chips mod } x$$$.

Let $$$f_m(n)$$$ denote the probability that after $$$n$$$ clears, the number of caster chips is $$$m \text{ mod } x$$$. We can observe that $$$f_0(0) = 1$$$ and $$$f_m(n) = p f_{m}(n-1) + q f_{(m + x - 1) \text { mod }}^(n-1)$$$. With probability $$$p$$$, we can get a sniper chip from a state where $$$\text{# caster chips} \equiv m \pmod{x}$$$ and with probability $$$q$$$, we can get a caster chip from a state where $$$\text{# caster chips} \equiv m - 1 \pmod{x}$$$. Additionally, with $$$0$$$ stage clears, there is a probability of $$$1$$$ that the number of caster chips is $$$0 \text {mod } x$$$ (as it is $$$0$$$).

This motivates matrix exponentiation as the method to compute $$$f_m(n)$$$, as the sum we desire is $$$\sum_{i = 0}^{x-1} if_{i}(n)$$$. We can make a matrix $$$A$$$ where on row $$$i$$$, $$$A_{i}{i} = p$$$ and $$$a_{i}{(i + 1) \text{ mod } x} = q$$$ and all other cells are $$$0$$$. By raising this to the power of $$$n$$$, we can find $$$f_m(n)$$$ as $$$A_{0}{m}$$$.

The final sum is

The total complexity is $$$O(x^3 \log n)$$$ with binary exponentiation for the matrix.

 
#include <iostream>
#include <cmath>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <array>


#define sz(x) ((int)(x.size()))
#define all(x) x.begin(), x.end()
#define pb push_back

using ll = long long;
const ll mod = (1 << (23)) * 119 +1; 

using namespace std;


ll binpow(ll a, ll b = mod-2){
	a %= mod;
	ll ans = 1;
	for(ll i = 1; i<=b; i*=2ll){
		if(i&b){
			(ans *= a) %= mod;
		}
		(a *= a) %= mod;
	}
	return ans;
}


#define matrix vector<vector<ll>>

matrix mult(matrix& a, matrix& b){
	matrix c = a;
	for(auto& x : c){
		fill(all(x), 0);
	}
	for(int i = 0; i<sz(a); i++){
		for(int j = 0; j<sz(a); j++){
			if(a[i][j] == 0) continue;
			for(int k = 0; k<sz(a); k++){
				c[i][k] += a[i][j]*b[j][k]%mod;
			}
		}
	}
	for(int i = 0; i<sz(c); i++){
		for(int j = 0; j<sz(c); j++){
			c[i][j] %= mod;
		}
	}
	return c;
}

matrix binpow(matrix a, ll b){
	matrix ans = a;
	for(int i = 0; i<sz(ans); i++){
		fill(all(ans[i]), 0);
		ans[i][i] = 1;
	}
	for(ll i = 1; i<=b; i*=2){
		if(i&b){
			ans = mult(ans, a);
		}
		a = mult(a, a);
	}
	return ans;
}

void solve(){
	int a;
	ll x, y, n;
	cin >> a >> x >> y >> n;
	ll inv = binpow(x);
	ll p = a*binpow(100)%mod;
	ll q = 1 + mod - p;
	ll ans = p*(n%mod)%mod + inv*y%mod*q%mod*(n%mod);
	ans %= mod;
	matrix base(x, vector<ll>(x, 0));
	for(int i = 0; i<x; i++){
		base[i][i] = p;
		base[i][(i + 1)%x] = q;
	}
	auto mat = binpow(base, n);
	for(int i = 0; i<x; i++){
		ans += (mod - inv)*y%mod*i%mod*mat[0][i]%mod;
		ans %= mod;
	}
	cout << ans << "\n";
}

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

    int T = 1;
    cin >> T;
    for(int i = 1; i<=T; i++){
		solve();
	}
    return 0;
}
 

Solve in $$$O(x^2 \log n)$$$

Solve in $$$O(x \log x \log n)$$$

We only realized this solution existed after the contest was over.

You can submit at problem G in this mashup.

Think about Kruskal Reconstruction Tree.

We will use the common technique in bitwise problems of adding the bits one by one from most to least significant.

We want to check if we can add a bit to the answer in $$$O(k)$$$, to do so we can precompute so values which will help us determine if the children of a node that are not in the query (i.e those that can't be removed), have the value of the AND we want as a submask.

You can do this "naively" with an AND sparse table for each adjacency list.

Alternatively, we can just count the number of children that have each bit for every node, and then for each query precompute the maximal set of bits that the AND can have for that node to be good.

The hints briefly sum up the solution of the problem step by step, but we will provide a more detailed explanation now.

For the minimum value of a tree to change, so that the value of the whole forest can increment, it is needed that the minimum node is removed. With this in mind, we can build another tree recursively in the following way (we will call it $$$G$$$ for clarity):

• Given a tree, if the tree consists of a single node, we stop there.
• If there it consists of at least $$$2$$$ nodes, we take the node with the minimum value and and remove it from the tree, decomposing it into several other trees. We take the minimum nodes of those trees and add them as children in $$$G$$$ to the node we removed from the original tree. Then, do the same for the decomposed trees.

$$$G$$$ is also known as the Kruskal Reconstruction Tree, so we will refer to it as Kruskal Tree from now on.

Once we've build the Kruskal tree, we will iterate for each query over the bits of the answer from most significant bit to less significant bit, and try to add those to the AND as we progress. For a specific desired value of AND $$$mask$$$, we will define each node $$$v$$$ as good if and only if $$$mask$$$ is a submask of its value (i.e. $$$v \ AND \ mask = mask$$$) or it can be removed (i.e. there's some $$$i$$$ such that $$$x_i = v$$$) and all of its children are good. If we manage to quickly compute if the root of the Kruskal Tree is good, we can know whether it is possible to have $$$mask$$$ as a submask of the answer or not.

There are multiple ways to do this in $$$O(k)$$$, resuling in a total complexity of $$$O(k \log n)$$$ per query. I will present two.

The first one, which was the original intended solution proposed by the author, is to build an AND sparse table for each adjacency list. Therefore, for each value of $$$mask$$$, one can do a DFS and, for each node, check if it is good. Firstly, we check if it has $$$mask$$$ as a submask, because if it does it is already good. If it doesn't, we will proceed with the DFS with the children that are in the query, and check if those are good, if any of those is not good, then the node will already not be good. Additionally, to check that the children which are not in the query (and therefore cannot be removed) have $$$mask$$$ as a submask, we will query for each interval between the indices of the children in the query the AND of those children, to get the AND of all the children that are not in the query. All that is left to check is that $$$mask$$$ is a submask of the AND the children for the node to be good.

The second way to check if a node is good fast is to precalculate for each node the count of the ocurrences of each bit in its children. Then, in a query, you can precalculate before checking if any $$$mask$$$ is good a "bad mask", which will contain all of the bits that $$$mask$$$ cannot have for that node to be good. In other words, we will store for which bits there exists a children of the node which cannot be removed and does not have that bit on. To do so, we go over every node in the query and, for each node, we iteare over all the bits. For each bit, we will iterate over all the children that are in the query and, if they do not have that bit on add it to the count of children with the bit on (because, as we only want to know if the children which can't be removed have the bit on, this does not affect us and makes the implementation easier). Therefore, each bit will not be bad if and only if its count is equal to the number of children (both in and not in the query) of the node, because all the children that are in the query will have added to the count, therefore if it is not equal to the number of children one child which is not in the query must not have it.

#include <bits/stdc++.h>

using namespace std;

const int LOG = 20;

struct DSU{
	vector<int> v, mn;
	void init(int n){
		v.assign(n, -1);
		mn.resize(n);
		for(int i = 0; i < n; i++) mn[i] = i;
	}
	int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);}
	void unite(int x, int y){
		x = get(x); y = get(y);
		if(x == y) return;
		if(v[x] > v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;
		mn[x] = min(mn[x], mn[y]);
	}
	int getMn(int i){
		return mn[get(i)];
	}
};

void buildSparse(vector<int>& v, vector<vector<int>>& sparse){
	int n = (int)v.size();
	sparse.assign(LOG, vector<int>(n));
	for(int k = 0; k < LOG; k++){
		for(int i = 0; i < n; i++){
			if(k == 0) sparse[k][i] = v[i]+1;
			else{
				if(i - (1 << (k-1)) < 0) sparse[k][i] = sparse[k-1][i];
				else sparse[k][i] = (sparse[k-1][i] & sparse[k-1][i - (1 << (k-1))]);
			}
		}
	}
}

int getAnd(int l, int r, vector<vector<int>>& sparse){
	if(l > r) return (1 << LOG) - 1;
	int k = 31 - __builtin_clz(r-l+1);
	return (sparse[k][r] & sparse[k][l + (1 << k) - 1]);
}

int taken;

bool DFS(int x, vector<vector<int>>& adj, vector<vector<int>>& specialAdj, vector<vector<vector<int>>>& sparses, int curr){
	if(((x+1) & curr) == curr) {taken++; return true;}
	//It needs to be removed;
	int lst = -1;
	int ans = (1 << LOG) - 1;
	for(int ind : specialAdj[x]){
		if(!DFS(adj[x][ind], adj, specialAdj, sparses, curr)) return false;
		ans &= getAnd(lst + 1, ind-1, sparses[x]);
		lst = ind;
	}
	ans &= getAnd(lst + 1, (int)adj[x].size() - 1, sparses[x]);
	if((ans & curr) == curr) return true;
	else return false;
}

void undo(vector<int>& x, vector<int>& parent, vector<vector<int>>& specialAdj){
	for(int i : x){
		if(parent[i] != -1) specialAdj[parent[i]].pop_back();
	}
}

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

	int tt; cin >> tt;
	while(tt--){
		int n, q; cin >> n >> q;
		vector<vector<int>> originalAdj(n);
		for(int i = 0; i < n - 1; i++){
			int u, v; cin >> u >> v; u--; v--;
			originalAdj[u].push_back(v);
			originalAdj[v].push_back(u);
		}
		vector<vector<int>> adj(n);
		vector<int> ind(n, -1), parent(n, -1);
		DSU UF; UF.init(n);
		for(int i = n - 1; i >= 0; i--){
			for(int node : originalAdj[i]){
				if(node < i) continue;
				adj[i].push_back(UF.getMn(node));
				UF.unite(i, node);
			}
			sort(adj[i].begin(), adj[i].end());
			for(int j = 0; j < (int)adj[i].size(); j++){
				ind[adj[i][j]] = j;
				parent[adj[i][j]] = i;
			}
		}
		vector<vector<vector<int>>> sparses(n);
		for(int i = 0; i < n; i++){
			buildSparse(adj[i], sparses[i]);
		}
		vector<vector<int>> specialAdj(n);
		while(q--){
			int k; cin >> k;
			vector<int> x(k);
			bool zero = false;
			for(int i = 0; i < k; i++){
				cin >> x[i]; x[i]--;
				if(!x[i]) zero = true;
				if(parent[x[i]] != -1){
					specialAdj[parent[x[i]]].push_back(ind[x[i]]);
				}
			}
			if(!zero){
				cout << 1 << "\n";
				undo(x, parent, specialAdj);
				continue;
			}
			int ans = 0;
			int curr = 0;
			for(int b = LOG - 1; b >= 0; b--){
				curr += (1 << b);
				taken = 0;
				if(DFS(0, adj, specialAdj, sparses, curr) && (taken > 0 || k != n)) ans = curr;
				else curr -= (1 << b);
			}
			cout << ans << "\n";
			undo(x, parent, specialAdj);
		}
	}
}

#include <bits/stdc++.h>

using namespace std;

const int LOG = 20;

struct DSU{
	vector<int> v, mn;
	void init(int n){
		v.assign(n, -1);
		mn.resize(n);
		for(int i = 0; i < n; i++) mn[i] = i;
	}
	int get(int x){return v[x] < 0 ? x : v[x] = get(v[x]);}
	void unite(int x, int y){
		x = get(x); y = get(y);
		if(x == y) return;
		if(v[x] > v[y]) swap(x, y);
		v[x] += v[y]; v[y] = x;
		mn[x] = min(mn[x], mn[y]);
	}
	int getMn(int i){
		return mn[get(i)];
	}
};

int taken;

bool DFS(int x, vector<vector<int>>& specialAdj, vector<int>& badMask, int curr){
	if(((x+1) & curr) == curr) {taken++; return true;}
	if(badMask[x] & curr) return false;
	//It needs to be removed;
	for(int node : specialAdj[x]){
		if(!DFS(node, specialAdj, badMask, curr)) return false;
	}
	return true;
}

void setBad(int x, vector<vector<int>>& adj, vector<vector<int>>& specialAdj, vector<vector<int>>& cnt, vector<int>& badMask){
	for(int k = 0; k < LOG; k++){
		int hvTotal = cnt[k][x];
		for(int node : specialAdj[x]){
			if(!((1 << k) & (node+1))) hvTotal++;
		}
		if(hvTotal != (int)adj[x].size()) badMask[x] += (1 << k);
	}
	for(int node : specialAdj[x]){
		setBad(node, adj, specialAdj, cnt, badMask);
	}
}

void undo(vector<int>& x, vector<int>& parent, vector<vector<int>>& specialAdj, vector<int>& badMask){
	for(int i : x){
		badMask[i] = 0;
		if(parent[i] != -1) specialAdj[parent[i]].pop_back();
	}
}

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

	int tt; cin >> tt;
	while(tt--){
		int n, q; cin >> n >> q;
		vector<vector<int>> originalAdj(n);
		for(int i = 0; i < n - 1; i++){
			int u, v; cin >> u >> v; u--; v--;
			originalAdj[u].push_back(v);
			originalAdj[v].push_back(u);
		}
		vector<vector<int>> adj(n);
		vector<int> parent(n, -1);
		DSU UF; UF.init(n);
		for(int i = n - 1; i >= 0; i--){
			for(int node : originalAdj[i]){
				if(node < i) continue;
				adj[i].push_back(UF.getMn(node));
				UF.unite(i, node);
			}
			sort(adj[i].begin(), adj[i].end());
			for(int j = 0; j < (int)adj[i].size(); j++){
				parent[adj[i][j]] = i;
			}
		}
		vector<vector<int>> cnt(LOG, vector<int>(n, 0));
		for(int k = 0; k < LOG; k++){
			for(int i = 0; i < n; i++){
				for(int node : adj[i]){
					if((1 << k) & (node+1)) cnt[k][i]++;
				}
			}
		}
		vector<vector<int>> specialAdj(n);
		vector<int> badMask(n, 0);
		while(q--){
			int k; cin >> k;
			vector<int> x(k);
			bool zero = false;
			for(int i = 0; i < k; i++){
				cin >> x[i]; x[i]--;
				if(!x[i]) zero = true;
				if(parent[x[i]] != -1){
					specialAdj[parent[x[i]]].push_back(x[i]);
				}
			}
			if(!zero){
				cout << 1 << "\n";
				undo(x, parent, specialAdj, badMask);
				continue;
			}
			setBad(0, adj, specialAdj, cnt, badMask);
			int ans = 0;
			int curr = 0;
			for(int b = LOG - 1; b >= 0; b--){
				curr += (1 << b);
				taken = 0;
				if(DFS(0, specialAdj, badMask, curr) && (taken > 0 || k != n)) ans = curr;
				else curr -= (1 << b);
			}
			cout << ans << "\n";
			undo(x, parent, specialAdj, badMask);
		}
	}
}

Solve in $$$O(R - L)$$$.

Let $$$f(i)$$$ be $$$0$$$ if $$$i$$$ is not divisible by $$$3$$$ or the number of $$$3$$$'s in the base-$$$10$$$ representation of $$$i$$$ otherwise.

Unfortunately, we cannot evaluate this in $$$O(R - L)$$$ as $$$R$$$ is very large.

We can reduce the problem to finding $$$\sum_{i = 1}^{x-1} f(i)$$$, $$$\sum_{i = 1}^{x-1} if(i)$$$, and $$$\sum_{i = 1}^{x-1} i^2f(i)$$$ for a very large $$$x$$$.

Let $$$d(x)$$$ denote the sum of digits in the base-$$$10$$$ representation $$$\text{ mod } 3$$$. For instance $$$d(1) = 1, d(55) = 1, d(3366) = 0$$$.

Let $$$val(i, j) = \sum\limits_{d(x) = j, \log_{10}(x) < i} x^0$$$.

Let $$$lin(i, j) = \sum\limits_{d(x) = j, \log_{10}(x) < i} x^1$$$.

Let $$$squ(i, j) = \sum\limits_{d(x) = j, \log_{10}(x) < i} x^2$$$.

Let $$$sum(i, j) = \sum\limits_{d(x) = j, \log_{10}(x) < i} x^0f(x)$$$.

Let $$$slin(i, j) = \sum\limits_{d(x) = j, \log_{10}(x) < i} x^1f(x)$$$.

Let $$$ssqu(i, j) = \sum\limits_{d(x) = j, \log_{10}(x) < i} x^2f(x)$$$.

I would give math formulas for all of these, but its easier to just attach code.

void precomp(int n){
	ll p = 1;
	for(int i = 0; i<=n; i++){
		ip10[i] = p;
		(p *= 10ll) %= mod;
	}
	p = 1;
	val[0][0] = 1;
	for(int i = 0; i<=n; i++){
		for(int j = 0; j<3; j++){
			for(int k = 0; k<10; k++){
				ll d = p*k%mod;
				if(k == 3){
					//(cnt(i) + 1)
					//1
					(sum[i+1][(j+k)%3] += val[i][j]) %= mod;
					//(i + d)(cnt(i) + 1)
					//i
					//d
					(slin[i+1][(j+k)%3] += val[i][j]*d%mod + lin[i][j]) %= mod;
					//(i + d)(i + d)(cnt(i) + 1)
					//i^2
					//id
					//di
					//d^2
					(ssqu[i+1][(j+k)%3] += val[i][j]*d%mod*d%mod + 2ll*lin[i][j]*d%mod + squ[i][j]) %= mod;
				}
				//(cnt(i))
				//cnt(i)
				(sum[i+1][(j+k)%3] += sum[i][j]) %= mod;
				//(i + d)(cnt(i))
				//icnt(i)
				//dcnt(i)
				(slin[i+1][(j+k)%3] += sum[i][j]*d%mod + slin[i][j]) %= mod;
				//(i + d)(i + d)(cnt(i))
				//i^2 cnt[i]
				//idcnt(i)
				//dicnt(i)
				//d^2cnt(i)
				(ssqu[i+1][(j+k)%3] += sum[i][j]*d%mod*d%mod + 2ll*slin[i][j]*d%mod + ssqu[i][j]) %= mod;
				(val[i+1][(j+k)%3] += val[i][j]) %= mod;
				(lin[i+1][(j+k)%3] += val[i][j]*d%mod + lin[i][j]) %= mod;
				(squ[i+1][(j+k)%3] += val[i][j]*d%mod*d%mod + 2ll*lin[i][j]*d%mod + squ[i][j]) %= mod;
			}
		}
		(p *= 10) %= mod;
	}
}

Let's fix some numbers $$$y$$$ and $$$k$$$ such that $$$y + 10^k \leq x$$$. We can easily obtain the sum of $$$f(i)$$$, $$$if(i)$$$, and $$$i^2f(i)$$$ for this range $$$[y, y+10^k)$$$ with the precomputed six precomputed functions above as we have no restrictions on the digits; The sum of $$$f(i)$$$, $$$if(i)$$$, and $$$i^2f(i)$$$ within this range depends solely on $$$y$$$, $$$d(y)$$$, $$$k$$$, and the precomputed functions above.

Let $$$n$$$ denote the number of digits in $$$x$$$.

To use this fact efficiently, let's enumerate the number of digits $$$y$$$ has in common with $$$x$$$. If at the $$$k$$$'th digit from the left, the digit in $$$y$$$ is strictly less than the digit $$$x$$$ (it cannot be strictly more, and if they are the same, $$$k$$$ will increase). We can set the last $$$n - k$$$ of $$$y$$$ to be $$$0$$$ and evaluate the sum for $$$[y, y + 10^{n - k})$$$.

This way, every number $$$ < x$$$ will be accounted for.

This takes $$$O(\log_{10}(R))$$$ precompute and $$$O(\log_{10}(R))$$$ per testcase. Read the code for more impl details. Note that a traditional digit dp where you store a flag of whether or not the current digit is strictly less than $$$x$$$ or not also works, but it runs slower.

//misaka, hitori, and elaina will carry me to red

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <iostream>
#include <cmath>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <array>
#include <cstdio>
#include <cstring>
#include <functional>
#include <numeric>
#include <set>
#include <queue>
#include <map>
#include <chrono>
#include <random>

#define sz(x) ((int)(x.size()))
#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
#define kill(x, s) {if(x){ cout << s << "\n"; return ; }}

//#ifndef LOCAL
#define cerr while(0) cerr
//#endif

using ll = long long;
using lb = long double;

const lb eps = 1e-9;
//const ll mod = 1e9 + 7, ll_max = 1e18;
const ll mod = (1 << (23)) * 119 +1, ll_max = 1e18;
const int MX = 2e5 +10, int_max = 0x3f3f3f3f;

struct {
  template<class T>
  operator T() {
    T x; std::cin >> x; return x;
  }
} in;

using namespace std;


//(r - i+1)(i - l+1)sum[i]
//(r+1)(-l+1)sum[i] + (-(-l+1) + r+1)*i*sum[i] + -i^2*sum[i]

ll val[MX][3]; //the number of ways to pick i digits such that they sum to j mod 3
ll sum[MX][3]; //the number of 3's across all those ways
ll lin[MX][3]; //sum of dig for all x that satisfy (i, j)
ll squ[MX][3]; //sum of dig*dig for all x that satisify (i, j)
ll slin[MX][3]; //sum of sum*dig for all x
ll ssqu[MX][3]; //sum of sum*dig*dig for all x

ll ip10[MX]; //ipman orz!


void precomp(int n){
	ll p = 1;
	for(int i = 0; i<=n; i++){
		ip10[i] = p;
		(p *= 10ll) %= mod;
	}
	p = 1;
	val[0][0] = 1;
	for(int i = 0; i<=n; i++){
		for(int j = 0; j<3; j++){
			for(int k = 0; k<10; k++){
				ll d = p*k%mod;
				if(k == 3){
					//(cnt(i) + 1)
					//1
					(sum[i+1][(j+k)%3] += val[i][j]) %= mod;
					//(i + d)(cnt(i) + 1)
					//i
					//d
					(slin[i+1][(j+k)%3] += val[i][j]*d%mod + lin[i][j]) %= mod;
					//(i + d)(i + d)(cnt(i) + 1)
					//i^2
					//id
					//di
					//d^2
					(ssqu[i+1][(j+k)%3] += val[i][j]*d%mod*d%mod + 2ll*lin[i][j]*d%mod + squ[i][j]) %= mod;
				}
				//(cnt(i))
				//cnt(i)
				(sum[i+1][(j+k)%3] += sum[i][j]) %= mod;
				//(i + d)(cnt(i))
				//icnt(i)
				//dcnt(i)
				(slin[i+1][(j+k)%3] += sum[i][j]*d%mod + slin[i][j]) %= mod;
				//(i + d)(i + d)(cnt(i))
				//i^2 cnt[i]
				//idcnt(i)
				//dicnt(i)
				//d^2cnt(i)
				(ssqu[i+1][(j+k)%3] += sum[i][j]*d%mod*d%mod + 2ll*slin[i][j]*d%mod + ssqu[i][j]) %= mod;
				(val[i+1][(j+k)%3] += val[i][j]) %= mod;
				(lin[i+1][(j+k)%3] += val[i][j]*d%mod + lin[i][j]) %= mod;
				(squ[i+1][(j+k)%3] += val[i][j]*d%mod*d%mod + 2ll*lin[i][j]*d%mod + squ[i][j]) %= mod;
			}
		}
		(p *= 10) %= mod;
	}
}

#define info array<ll, 3>
//sum, slin, ssqu

info operator + (info a, info b){
	return info{(a[0]+b[0])%mod, (a[1]+b[1])%mod, (a[2]+b[2])%mod};
}

info comb(int c, ll d, info a, info b){
	//a is sum/slin/ssqu 
	//b is val/lin/squ
	info r = {0ll, 0ll, 0ll};
	r[0] = (a[0]+c*b[0]%mod)%mod;
	r[1] = (a[1] + 1ll*c*b[1] + 1ll*d*a[0]%mod + 1ll*b[0]*d%mod*c%mod)%mod;
	r[2] = (1ll*c*(b[2] + 2ll*d*b[1]%mod + d*d%mod*b[0]%mod)%mod + a[2] + 2ll*d*a[1]%mod + d*d%mod*a[0]%mod)%mod;
	return r;
}

void pr(info& a){
	for(auto x : a) cerr << x << " "; cerr << "\n";
}

info eval(string s){
	ll d = 0;
	int c = 0;
	int m3 = 0;
	info ret = {0ll, 0ll, 0ll};
	cerr << "eval " << s << "\n";
	for(int i = sz(s); i>=1; i--){
		cerr << d << " " << c << " " << m3 << "\n";
		for(int j = 0; j<s[sz(s)-i]-'0'; j++){
			int nc = c + (j == 3);
			ll nd = d + 1ll*j*ip10[i-1]%mod;
			int nm3 = (m3 + j)%3;
			cerr << i << " " << (char)(j + '0')  << "\n";
			info a = {sum[i-1][(3 - nm3)%3], slin[i-1][(3 - nm3)%3], ssqu[i-1][(3 - nm3)%3]};
			info b = {val[i-1][(3 - nm3)%3], lin[i-1][(3 - nm3)%3], squ[i-1][(3 - nm3)%3]};
			pr(a); pr(b);
			auto tmp = comb(nc, nd, a, b);
			pr(tmp);
			ret = ret + tmp;
		}
		if(s[sz(s)-i] == '3') c++;
		(m3 += (s[sz(s)-i] - '0')) %= 3;
		(d += 1ll*(s[sz(s)-i] - '0')*ip10[i-1]) %= mod;
		cerr << "\n";
	}
	return ret;
}

ll conv(string s){
	ll ans = 0;
	for(int i = sz(s)-1; i>=0; i--){
		cerr << s[sz(s) - i-1] << " " << i << "\n";
		ans += 1ll*(s[sz(s) - i-1]-'0')*ip10[i]%mod;
	} cerr << "\n";
	return ans%mod;
}



string add(string l){
	for(int i = sz(l)-1; i>=0; i--){
		if(l[i] == '9'){
			l[i] = '0';
		}else{
			l[i]++;
			break ;
		}
	}
	if(l == string(l.size(), '0')){
		l.pb('1');
		reverse(all(l));
	}
	return l;
}

ll binpow(ll a, ll b = mod - 2){
	ll ans = 1;
	for(ll i = 1; i<=b; i*=2ll){
		if(i&b) (ans *= a) %= mod;
		(a *= a) %= mod;
	}
	return ans;
}

void solve(){
	string l = (string) in;
	string r = (string) in;
	auto sl = eval(l);
	auto sr = eval(add(r));
	ll L = conv(l), R = conv(r);
	//(r+1)(-l+1)sum[i] + (-(-l+1) + r+1)*i*sum[i] + -i^2*sum[i]
	pr(sl);
	pr(sr);
	ll ans = 1ll*(R + 1)*(mod-L+1)%mod*(sr[0] + mod - sl[0])%mod + \
					 1ll*(L + mod - 1 + R + 1)*(sr[1] + mod - sl[1])%mod + \
					 1ll*(mod - 1)*(sr[2] + mod - sl[2])%mod;
	ans %= mod;
	ll len = (R + mod - L + 1)%mod;
	cerr << ans << "\n";
	cerr << L << " " << R << " " << len << "\n";
	cout << ans%mod << "\n";
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);
	precomp(100010);
  int T = 1;
  cin >> T;
  for(int i = 1; i<=T; i++){
		//cout << "Case #" << i << ": ";
		solve();
	}
  return 0;
}

 

No code is provided. There are $$$49$$$ accepted answers to this problem. Try to find them all!

Iterate through the mountain from left to right and maintain a counter for the number of times the altitude increases consecutively. Make sure to reset this counter whenever the altitude does not increase. Also, ensure that each sequence of consecutive altitude increases is counted only once to avoid overcounting mountains.

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

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

	int cnt = 0;
	int prev = -1;
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;

		if (a > prev && i) cnt++;
		else if (a <= prev) cnt = 0;
		if (cnt == 2) ans++;
		prev = a;
	}

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

There is only $$$1$$$ scenario in any game where Thomas sweeps. So we should do complementary counting and count the total number of ways to assign winners and subtract $$$1$$$ from that. Each game there $$$(k + 1)$$$ possible winners, the $$$k$$$ problemsetters and Thomas. As there are $$$n$$$ rounds, the final result is that in $$$(k + 1)^n - 1$$$ games Thomas will not sweep.

n,k=input().split()
print((int(k) + 1) ** int(n) - 1)

We can guess that the number is the smallest prime $$$ > n$$$. Our intuition is right but the proof is a little harder that that.

This gives us an $$$O(72 \sqrt{n})$$$ solution. The $$$72$$$ comes from the fact that for any integer $$$n \leq 10^5$$$ there is a prime that is at most $$$n + 72$$$.

#include <cstdio>

int isp(int x){
    for(int i = 2; i*i <= x; i++){
        if(x%i == 0) return 0;
    }
    return 1;
}

int main(){
    int n;
    scanf("%d", &n);
    do{
        n++;  
    }while(isp(n) == 0);
    printf("%d\n", n);
    return 0;
}

How many elements change between two adjacent cyclic shifts?

First, notice that there always exists an optimal series of operations where the cycle operation, if performed at all, is done first. There are only $$$\mathcal{O}(n)$$$ possible different cycle operations, and the answer afterwards is the sum over the absolute differences between $$$a$$$ and $$$b$$$ for each index.

Consider the first and second such cyclic shift of length $$$5$$$ on an array $$$a=[1, 2, \dots, 8]$$$:

Observe that between the first and second shift, only a small number of elements change positions. In fact, for a cyclic shift of length $$$k$$$ starting at $$$i$$$, only the elements at positions $$$i$$$, $$$i+k$$$, and $$$i+k-1$$$ change positions when transitioning to the cyclic shift at $$$i+1$$$. Thus, we can loop over all possible cyclic shifts, maintaining the sum and updating the indicies accordingly. Because there are only a constant number of updates for each cyclic shift, this runs in $$$\mathcal{O}(n)$$$.

#include <bits/stdc++.h>
 
long long calculate_cost(int n, const std::vector<long long> &a, const std::vector<long long> &b) {
	long long ret = 0;
	for (int i = 0; i < n; i++)
		ret += llabs(a[i] - b[i]);
	return ret;
}
 
template<typename I>
void rotate_left(I l, I r) { std::rotate(l, std::next(l), r); }
 
int main() {
	using namespace std;
 
	int TC;
	cin >> TC;
	while (TC--) {
		int N, K;
		cin >> N >> K;
		vector<long long> A(N), B(N);
		for (auto &a : A)
			cin >> a;
		for (auto &b : B)
			cin >> b;
		long long ans = calculate_cost(N, A, B);
		rotate_left(A.begin(), A.begin() + K);
		long long cur = calculate_cost(N, A, B);
		ans = min(ans, cur + 1);
		for (int i = 1; i + K - 1 < N; i++) {
			cur -= llabs(A[i - 1] - B[i - 1]) + 
				llabs(A[i + K - 2] - B[i + K - 2]) + 
				llabs(A[i + K - 1] - B[i + K - 1]);
			auto tem = A[i - 1];
			A[i - 1] = A[i + K - 2];
			A[i + K - 2] = A[i + K - 1];
			A[i + K - 1] = tem;
			cur += llabs(A[i - 1] - B[i - 1]) + 
				llabs(A[i + K - 2] - B[i + K - 2]) + 
				llabs(A[i + K - 1] - B[i + K - 1]); 
			ans = min(ans, cur + 1);
		}
		cout << ans << '\n';
	}
}

Let's define $$$a, b, c, d$$$ as they were defined in the statement. We first must pick $$$d$$$ as a multiple of $$$l = lcm(a, b)$$$. This is to guarantee that $$$d$$$ can be divided by both $$$a$$$ and $$$b$$$. Then instead of thinking of taking some number $$$p \cdot l$$$ mod $$$c$$$, we can instead imagine it as $$$p \cdot l - q \cdot c$$$. By Bezout's identity it is always possible to represent $$$g = gcd(c, l)$$$ with some choice of $$$p$$$ and $$$q$$$. As a consequence, $$$g, 2g, 3g, \dots, (\frac{c}{g}-1)g$$$ are possible results modulus $$$c$$$ for some choice of $$$d$$$ and the maximal of these will be $$$ (\frac{c}{g}-1)g$$$.

This gives us a $$$O(\log(\max(a, b, c))$$$ sol per testcase as just outputting $$$c - gcd(c, lcm(a, b))$$$.

#include <iostream>
#include <cmath>
using ll = long long;
using namespace std;
ll gcd(ll a, ll b){
	if(b == 0) return a;
	return gcd(b, a%b);
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int T;
	cin >> T;
	while(T--){
		ll a, b, c;
		cin >> a >> b >> c;
		ll lcm = a*b/gcd(a, b);
		ll step = gcd(lcm, c);
		cout << c - step << "\n";
	}
}

Can you calculate what is the complexity of simulating the process greedily?

You can use harmonic series to calculate it.

We will use a greedy algorithm. We will always go the farthest shield at a distance $$$\le t$$$ from where we are and stay there until a dagger is thrown. We will repeat the same process until we are at a distance $$$\le t$$$ from $$$n$$$, then we can just arrive at $$$n$$$ and pass the level, or until there is no shield at a distance $$$\le t$$$ from where we are, then we can't pass the level. This is obviously optimal because we spend the least possible amount of time waiting in the same position.

The next step is to calculate on how many shields do we actually stop at for each level. We claim that the answer is at most $$$2\cdot \lceil \frac{n}{t} \rceil$$$.

Now we know that the number of shields that we will visit after the $$$n$$$ levels is at most $$$2 \cdot \sum \limits_{t=1}^{n} \lceil \frac{n}{t} \rceil$$$. Using harmonic series we get to the conclusion that after the $$$n$$$ levels we will have stopped at around $$$n \ln n$$$ shields, which actually isn't much and can lead to fast solutions.

Everything that's left now is to be able to quickly get the location of the farthest shield at a distance $$$\le t$$$ from where we are. We can do this with sets and the function upper_bound(), which has a complexity of $$$\mathcal{O}(\log{n})$$$. That results in the complexity of the solution being $$$\mathcal{O}(n \log^2{n})$$$.

#include <bits\stdc++.h>
 
using namespace std;
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, q; cin >> n >> q;
	set<int> shields;
	for(int t = 1; t <= q; t++){
		int x; cin >> x;
		shields.insert(x);
		long long ans = 0;
		int curr = 0;
		bool done = 0;
		while(!done){
			if(n - curr <= t){
				cout << ans + n - curr << "\n";
				done = 1;
			}else{
				auto it = shields.upper_bound(curr + t);
				if(it == shields.begin() || *(--it) == curr){
					cout << -1 << "\n";
					done = 1;
				}else{
					curr = *it;
					ans += t;
				}
			}
		}
	}
}

$$$dist(i, j) = dep[i] + dep[j] - 2 \cdot dep[lca(i, j)]$$$

How does splitting into $$$3$$$ terms help? Can we count each one individually?

Let's define $$$d$$$ as the depth of the tree and $$$n = 2^d - 1$$$ or the number of nodes on the tree.

We want to find

Let's try to count for each node $$$u$$$ how many times $$$dep[u]$$$ will be counted by this sum. There are $$$2n$$$ times from when $$$i = u$$$ or $$$j = u$$$ but counting $$$lca(i, j) = u$$$ will take a little more work.

For $$$lca(i, j) = u$$$ we need $$$i$$$ and $$$j$$$ to be in different subtrees of $$$u$$$ (or if $$$i = u$$$ or $$$j = u$$$). Define $$$sub[u] = 2^{(d - dep[u] + 1)} - 1$$$ or $$$sub[u] = $$$ the number of nodes in node $$$u$$$'s subtree. We can also define $$$chsub[u] = \frac{sub[u]-1}{2}$$$ or $$$chsub[u] = $$$ the number of nodes in the subtree of node $$$u$$$'s children.

Then the number of pairs of $$$(i, j)$$$ with $$$lca(i, j) = u$$$ is

The final observation is that all nodes with the same depth behave the same so it suffices to find the total contribution of one node of some depth and multiply that by the number of nodes on that depth.

Our final sum will be

This formula can be evaluated in $$$O(n)$$$ or $$$O(n \log n)$$$ per test case depending on whether or not you precomputed powers of $$$2$$$.

There is another, much more beautiful solution to this problem that involves counting the contribution of each edge but I won't explain it here :).

#include <iostream>

using ll = long long;

const ll mod = 1e9 + 7;
const int MX = 2e5 +10;

using namespace std;

int two[MX];

void solve(){
	int d; cin >> d;
	ll ans = 0;
	ll n = two[d] - 1;
	for(int i = 0; i<d; i++){
		ll ch = (i == d-1) ? 0 : 2;
		ll ch_sub = two[d-1 - i]-1;
		ll sub = ch*ch_sub + 1;
		ll cnt = two[i];
		ans += cnt*((n*i%mod + n*i%mod + (mod - 2)*i%mod*(sub + ch*ch_sub%mod*(sub - ch_sub)%mod))%mod)%mod;
		ans %= mod;
	}
	cout << ans << "\n";
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
	two[0] = 1;
	for(int i = 1; i<=1e5; i++){
		two[i] = 2*two[i-1]%mod;
	}
    int T = 1;
	cin >> T;
    for(int i = 1; i<=T; i++){
		solve();
	}
    return 0;
}

Lets first solve the subtask with negligible fog to build up to our final solution. We need to find the nearest point to the left and right of a given point $$$p$$$ with an altitude at least as high as $$$p$$$. There are a couple ways of doing this, but using a stack, we can precompute these points efficiently. We iterate through the points from left to right, and at each point $$$p$$$, we remove all stack elements with altitude at most $$$p$$$ before adding $$$p$$$ to the stack. This process identifies points $$$q$$$ to the left of $$$p$$$ for which $$$p$$$ is the first non-visible point from $$$q$$$. We repeat this process, iterating from right to left, to find the nearest points to the left and right of each point $$$p$$$ with altitude greater than or equal to $$$p$$$. Note that the stack remains sorted throughout the process, ensuring each point is visited at most twice, resulting in linear complexity.

To incorporate the fog in our solution, we need to find the number of points within visible range for point $$$p$$$ excluding points below the fog altitude (given that the fog is not above $$$p$$$). Note that we are essentially finding the number of elements in a subarray which are less than a certain value. A Binary Index Tree might come to mind, but it's not entirely clear how updates would work. Here, it's important to make the observation that the queries can be done offline. If we answer each query in order of the fog altitude, we can maintain a BIT such that all points below the fog have a value of 1, while all other points have value 0. We can then query on the visible range for a point $$$p$$$ to see how many points are not visible due to the fog, which is subtracted from the result from the stack method, to get the final solution. The overall complexity is $$$O(N \log N)$$$.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
#define MAXN 1000001
#define MAXQ 100001
vector<pair<int, int> > points;
vector<pair<pair<int, int>, int> > qs;
int N, Q, a[MAXN], BIT[MAXN], r[MAXN], l[MAXN], sols[MAXQ];

int getSum(int index)
{
    int sum = 0;
    index = index + 1;
    while (index > 0)
    {
        sum += BIT[index];
        index -= index & (-index);
    }
    return sum;
}

void updateBIT(int index)
{
    index = index + 1;

    while (index <= N)
    {
        BIT[index] += 1;
        index += index & (-index);
    }
}

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

    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
        points.push_back({ a[i], i }); // used to iterate in increasing altitude
    }

    for (int i = 0; i < Q; i++)
    {
        int p, f;
        cin >> p >> f;
        qs.push_back({ {f, p - 1}, i }); //offline queries
    }

    for (int i = 0; i < N; i++) r[i] = N, l[i] = -1;
    vector<pair<int, int> > sr, sl;
    for (int i = 0; i < N; i++) {
        int alt = a[i];

        while (sr.size() && sr.back().first <= alt)
        {
            r[sr.back().second] = i;
            sr.pop_back();
        }
        sr.push_back(points[i]);

        int ind = N - i - 1;
        alt = a[ind];

        while (sl.size() && sl.back().first <= alt)
        {
            l[sl.back().second] = ind;
            sl.pop_back();
        }
        sl.push_back(points[ind]);
    }

    sort(qs.begin(), qs.end());
    sort(points.begin(), points.end());

    int ind = 0;
    for (int i = 0; i < Q; i++)
    {
        int fog = qs[i].first.first;
        while (ind < N && points[ind].first < fog) {
            updateBIT(points[ind].second);
            ind++;
        }

        //point index of query
        int qp = qs[i].first.second;

        //no fog
        int ans = r[qp] - l[qp] - 1;

        //amt can't see cuz fog
        int sub = getSum(r[qp] - 1) - getSum(l[qp]);

        if (a[qp] >= fog) ans -= sub;

        sols[qs[i].second] = ans;
    }

    for (int i = 0; i < Q; i++) cout << sols[i] << "\n";

    return 0;
}

Many solutions for this problem invoke Sprague Grundy, but I will present a solution that does not.

Let us first solve the subtask for $$$n = 1$$$.

So now to solve for an array of integers, we will have to generalize our approach quite a bit.

As a side note. This is actually the exact same resulting solution if you used Sprague Grundy (SG) to solve.

#include <iostream>
#include <vector>
#include <array>
using namespace std;

int dig(int x){
	while(x >= 6){
		x /= 6;
	}
	return x;
}

void solve(){
	int n;
	cin >> n;
	array<int, 6> cnt; cnt.fill(0);
	for(int i = 0; i<n; i++){
		int x; cin >> x;
		cnt[dig(x)]++;
	}
	int x = (cnt[2] + cnt[3])%2;
	int y = (cnt[4] + cnt[5])%2;
	if((x%2)|(y%2)) cout << "Nino\n";
	else cout << "Miku\n";
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    int T = 1;
    cin >> T;
    for(int i = 1; i<=T; i++){
		solve();
	}
    return 0;
}

Solve the first subtask for tests $$$1 - 4$$$.

We will ignore the expected value for now and compute the sum of unique strings over all ways to fill in question marks.

//hina best girl

#include <iostream>
#include <vector>
#include <cassert>
#include <array>
#include <string>

#define ll long long
#define sz(x) ((int)(x.size()))
const int mod = 1e9 + 7;
const int MX = 1e3 +10;
using namespace std;

ll fac[MX], ifac[MX];


ll binpow(ll a, ll b = mod - 2){
	ll ans = 1;
	for(int i = 1; i<=b; i*=2){
		if(i&b) (ans *= a) %= mod;
		(a *= a) %= mod;
	}
	return ans;
}

void precomp(int n){
	fac[0] = 1;
	for(int i = 1; i<=n; i++){
		fac[i] = 1ll*i*fac[i-1]%mod;
	}
	ifac[n] = binpow(fac[n]);
	for(int i = n; i>=1; i--){
		ifac[i-1] = 1ll*i*ifac[i]%mod;
	}
	assert(ifac[0] == 1);
}

vector<ll> mult(vector<ll> a, vector<ll> b){
	vector<ll> c(sz(a) + sz(b) - 1, 0ll);
	for(int i = 0; i<sz(a); i++){
		for(int j = 0; j<sz(b); j++){
			c[i + j] += a[i]*b[j]%mod;
		}
	}
	for(int i = 0; i<sz(c); i++) c[i] %= mod;
	return c;
}

void solve(){
	string s; cin >> s;
	int n = sz(s);
	array<int, 26> cnt = {0};
	int q = 0;
	for(char c : s){
		if(c != '?'){
			cnt[c - 'a']++;
		}else{
			q++;
		}
	}
	vector<ll> ans = {1};
	for(int i = 0; i<26; i++){
		vector<ll> cur;
		for(int j = 0; j<=cnt[i] + q; j++){
			if(j < cnt[i]) cur.push_back(0);
			else cur.push_back(ifac[j] * ifac[j - cnt[i]]%mod);
		}
		ans = mult(ans, cur);
		if(sz(ans) > n+1) ans.erase(ans.begin() + n + 1, ans.end());
	}
	assert(sz(ans) == n+1);
	ll oup = ans[n] * fac[n]%mod *fac[q]%mod;
	oup *= binpow(binpow(26, q));
	oup %= mod;
	cout << oup << "\n";
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	precomp(1000);
	int T; cin >> T;
	for(int i = 0; i<T; i++){
		solve();
	}

	return 0;
}

Draw the line from $$$(0, 0)$$$ to $$$(x_1, y_1)$$$. Notice that any time that this line touches the boundary between two bricks our answer increases by one.

Let's count the number of times we jump from a brick to a brick that is above it. This happens $$$y_1-1$$$ times since we always move to a new brick whenever we cross some line $$$y = a$$$ for $$$1 \le a \le y_1-1$$$.

Now count the number of times we jump from a brick to a brick that is to the right. To do this, write the equation for our line. It is $$$y_1x - x_1y = 0$$$. We check if this line crosses a boundary between two bricks at $$$x = b$$$. We find the intersection that these lines have with each other, $$$(c, d)$$$. If both $$$c$$$ and $$$d$$$ are integers, we do not count the movement to the right since we already counted the movement upwards to the next brick. Now we check if $$$(c, d)$$$ is a point between two horizontally adjacent bricks or in the space inside a brick. To do this, we notice that for any odd $$$x$$$ value, the point brings us to a new brick if it's $$$y$$$ coordinate is in any range $$$[1, 2], [3, 4], \dots$$$ while for even values of $$$x$$$ the point brings us to a new brick if it's $$$y$$$ coordinate is any range $$$[0, 1], [2, 3], \dots$$$. My code checks this by looking at the parity of the x coordinate and the floor of the y coordinate of this point. If their parity is the same, it means that we move to a new brick to the right at that point. This gives an $$$O(x_1)$$$ solution.

For the complete solution, we have to deal with cases when $$$x_1$$$ is large. To do this, notice that if it is then for every range $$$y_1, y_2$$$ we cross right boundary lines multiple times. You can solve this by calculations based on the boundary points for each consecutive pairs of $$$y$$$, or by scaling down $$$x_1$$$ when you notice that if $$$x > 2y_1$$$ we are guaranteed to pass through a range of $$$(2y_1)$$$ when we move to a point 1 coordinate upwards, so we can calculate the answer by adding $$$y_1$$$ with the answer to $$$(x_1-2y_1, y_1)$$$. Through this we can make use of mods to bring the $$$x$$$ coordinate down to $$$2y$$$. Then our time complexity is $$$O(\min(x, y))$$$.

#include <bits/stdc++.h>
using namespace std;
void solve() {
	long long x, y; cin>>x>>y;
	{
		long long ans = y;
		if (x > 2 * y) {
			long long c = (x-1) / (2*y);
			ans += c * (y);
			x = ((x-1) % (2 * y)) + 1;
		}
		for (int i = 1; i < x; i++) {
			long long y1 = (y * i)/x;
			if (y1*x==y*i) continue;
			if (i%2==1 && y1%2==1) {
				ans++;
			}
			else if (i%2==0 && y1%2==0) {
				ans++;
			}
		}
		cout<<ans<<endl;
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.sync_with_stdio(0);
	int t = 1;
	cin>>t;
	while (t--)
		solve();
	return 0;
}

$$$k$$$ is very large, that should guide you in your solution.

Every $$$n$$$ seconds, the array goes back to its initial position.

Have you thought of matrix exponentiation or binary lifting?

We can compute a $$$dp[a][b][t]$$$, which will keep track of the minimum amount of gas possible to go from $$$a$$$ to $$$b$$$ in $$$t$$$ seconds. That means that the answer is $$$\min \limits_{b=1}^{n} dp[1][b][k]$$$. The problem is that, given the size of $$$k$$$, we can't compute the $$$dp$$$ for all $$$t \le k$$$.

The key observation that we must make is that the changes on the array are cyclic, that means that every $$$n$$$ seconds the array returns to the initial position. Because of that, we can compute the matrix $$$dp[a][b][n]$$$ and elevate it to the exponent $$$\lfloor \frac{k}{n} \rfloor$$$, and that will give us $$$dp[a][b][n \cdot \lfloor \frac{k}{n} \rfloor]$$$. All that's left now is computing the matrix for the remaining seconds, which is $$$dp[a][b][k \mod n]$$$, and adding the answers.

Complexity of the solution: $$$\mathcal{O}(n^{2} \cdot (n + m) + n^{3}\log{n})$$$.

Note that if you don't know about matrix exponentiation, there is a similar solution with the same complexity using binary lifting. You could compute all $$$dp[a][b][n \cdot 2^t]$$$, and add all those such that the bit in position $$$t$$$ of the binary representation of $$$\lfloor \frac{k}{n} \rfloor$$$ is $$$1$$$.

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
 
const int MOD = 1e9 + 7;

void mult(vector<vector<ll>>& a, vector<vector<ll>>& b){
	int n = (int)a.size();
	vector<vector<ll>> nw(n, vector<ll>(n));
	ll mx = 1e18;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int q = 0; q < n; q++){
				if(q == 0) nw[i][j] = min(a[i][q] + b[q][j], mx);
				else nw[i][j] = min(nw[i][j], min(a[i][q] + b[q][j], mx));
			}
		}
	}
	a = nw;
}

vector<vector<ll>> exp(vector<vector<ll>> dp, int e){
	if(e == 1) return dp;
	if(e % 2 == 0){
		vector<vector<ll>> dp2 = exp(dp, e / 2);
		mult(dp2, dp2);
		return dp2;
	}else{
		vector<vector<ll>> dp2 = exp(dp, e / 2);
		mult(dp2, dp2); mult(dp2, dp);
		return dp2;
	}
}

void solve(){
	int n, m, k; cin >> n >> m >> k;
	vector<int> a(n);
	for(auto &i : a) cin >> i;
	vector<vector<int>> adj(n);
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v; u--; v--;
		adj[u].push_back(v);
	}
	int additional = k % n;
	k /= n;
	vector<vector<ll>> ad(n);
	vector<vector<ll>> dp(n);
	for(int i = 0; i < n; i++){
		vector<ll> curr(n, 1e18);
		curr[i] = 0;
		for(int t = 1; t <= n; t++){
			vector<ll> lst = curr;
			curr.assign(n, 1e18);
			for(int j = 0; j < n; j++){
				curr[j] = min(curr[j], lst[j] + a[(j + (t - 1)) % n]);
				for(int x : adj[j]){
					curr[x] = min(curr[x], lst[j] + a[(j + (t - 1)) % n]);
				}
			}
			if(t == additional){
				ad[i] = curr;
			}
		}
		dp[i] = curr;
	}
	if(k == 0){
		vector<vector<ll>> ans = ad;
		ll res = 1e18;
		for(int i = 0; i < n; i++) res = min(res, ans[0][i]);
		cout << res << endl;
		return;
	}
	vector<vector<ll>> ans = exp(dp, k);
	if(additional > 0) mult(ans, ad);
	ll res = 1e18;
	for(int i = 0; i < n; i++) res = min(res, ans[0][i]);
	cout << res << endl;
}

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

    //~ int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long int ll;
 
const int MOD = 1e9 + 7;

void mult(vector<vector<ll>>& a, vector<vector<ll>>& b){
	int n = (int)a.size();
	vector<vector<ll>> nw(n, vector<ll>(n));
	ll mx = 1e18;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			for(int q = 0; q < n; q++){
				if(q == 0) nw[i][j] = min(a[i][q] + b[q][j], mx);
				else nw[i][j] = min(nw[i][j], min(a[i][q] + b[q][j], mx));
			}
		}
	}
	a = nw;
}

void solve(){
	int n, m, k; cin >> n >> m >> k;
	vector<int> a(n);
	for(auto &i : a) cin >> i;
	vector<vector<int>> adj(n);
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v; u--; v--;
		adj[u].push_back(v);
	}
	int additional = k % n;
	k /= n;
	vector<vector<ll>> ad(n);
	vector<vector<ll>> dp(n);
	for(int i = 0; i < n; i++){
		vector<ll> curr(n, 1e18);
		curr[i] = 0;
		for(int t = 1; t <= n; t++){
			vector<ll> lst = curr;
			curr.assign(n, 1e18);
			for(int j = 0; j < n; j++){
				curr[j] = min(curr[j], lst[j] + a[(j + (t - 1)) % n]);
				for(int x : adj[j]){
					curr[x] = min(curr[x], lst[j] + a[(j + (t - 1)) % n]);
				}
			}
			if(t == additional){
				ad[i] = curr;
			}
		}
		dp[i] = curr;
	}
	if(k == 0){
		vector<vector<ll>> ans = ad;
		ll res = 1e18;
		for(int i = 0; i < n; i++) res = min(res, ans[0][i]);
		cout << res << endl;
		return;
	}
	vector<vector<ll>> ans = dp;
	k--;
	for(int b = 0; b < 30; b++){
		if((1 << b) > k) break;
		if((1<<b) & k){
			mult(ans, dp);
		}
		mult(dp, dp);
	}
	if(additional > 0) mult(ans, ad);
	ll res = 1e18;
	for(int i = 0; i < n; i++) res = min(res, ans[0][i]);
	cout << res << endl;
}

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

    //~ int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        solve();
    }
}

The min function is hard to deal it, so how can we separate the two terms?

If we can split the tree into two subtrees and find the maximum path in each subtree, then this will be the optimal solution for that split. If we find the maximum of this over all possible splits, then we have our answer.

It is easy to see that all possible splitting of the tree can be obtained by removing an edge and looking at the remaining subtrees. This leads us to an $$$O(N^2)$$$ solution where we try splitting the tree over every edge, then run a dp in each of the two remaining subtrees.

We can define $$$dp[x][0] = \text{maximum path that contains node x}$$$ and $$$dp[x][1] = \text{maximum path in the subtree of x}$$$. $$$dp[x][0]$$$ can be calculated by using the maximum $$$dp[i][0]$$$, where $$$i$$$ is a child of $$$x$$$. Meanwhile, $$$dp[x][1]$$$ can be calculated by using the two maximum $$$dp[i][0]$$$ and maximum $$$dp[i][1]$$$. With these dp states, we can easily update the values when attaching or removing children from a node. If we maintain a multiset storing all of the $$$dp[i][0]$$$ and $$$dp[i][1]$$$, then attaching a child becomes inserting a value into the multiset, and removing a child becomes removing a value from the multiset. $$$dp[x][0]$$$ then transitions to the largest value in the multiset of $$$dp[i][0]$$$, while $$$dp[x][1]$$$ transitions to the two largest values of $$$dp[i][0]$$$ and the largest value of the multiset of $$$dp[i][1]$$$.

Now, if our tree is rooted at $$$x$$$, we can effectively split the tree over every edge attached to $$$x$$$ by removing and adding children. We can also use this method to efficiently reroot the tree, thus allowing us to be able to split the tree over every edge. Lets say we are rerooting our tree from node $$$a$$$ to node $$$b$$$. To do this, we can remove $$$b$$$ from being a child of $$$a$$$, then attach $$$a$$$ to be a child of $$$b$$$ using the values computed after the first removal. Using this described method yields a solution of $$$O(N \text{ log } N)$$$, which if well implemented, will pass. However, we can actually optimize this further by only storing the three maximum values for each multiset instead of all of them. It is easy to see that those are all we need to support our operations.

There also exists other solutions such as binary searching on the answer for $$$O(N \text{ log } N)$$$ complexity and a greedy solution involving diameters for $$$O(N)$$$.

#pragma GCC optimize("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MOD = 1e9 + 7;

vector<pii> g[500005];

ll dp[500005][2];
multiset<ll, greater<ll>> deg[500005][2];

void dfs1(int x, int p = -1){
    deg[x][0].insert(0), deg[x][0].insert(0);
    for(pii i : g[x]){
        if(i.ff == p) continue;
        dfs1(i.ff, x);
        deg[x][0].insert(dp[i.ff][0] + i.ss);
        deg[x][1].insert(dp[i.ff][1]);
    }
    deg[x][1].insert(*deg[x][0].begin() + *next(deg[x][0].begin()));
    dp[x][0] = *deg[x][0].begin();
    dp[x][1] = *deg[x][1].begin();
    while(deg[x][0].size() > 3) deg[x][0].erase(prev(deg[x][0].end()));
    while(deg[x][1].size() > 3) deg[x][1].erase(prev(deg[x][1].end()));
}

ll ans;

void rem(int x, int t, ll v){
    multiset<ll, greater<ll>>::iterator it = deg[x][t].find(v);
    if(it != deg[x][t].end()) deg[x][t].erase(it);
}

void ins(int x, int t, ll v){
    deg[x][t].insert(v);
    while(deg[x][t].size() > 3) deg[x][t].erase(prev(deg[x][t].end()));
}

void move(int a, int b, int c){
    rem(a, 1, dp[b][1]);
    rem(a, 1, *deg[a][0].begin() + *next(deg[a][0].begin()));
    rem(a, 0, dp[b][0] + c);
    ins(a, 1, *deg[a][0].begin() + *next(deg[a][0].begin()));
    dp[a][0] = *deg[a][0].begin();
    dp[a][1] = *deg[a][1].begin();
    ans = max(ans, min(dp[a][1], dp[b][1]));
    rem(b, 1, *deg[b][0].begin() + *next(deg[b][0].begin()));
    ins(b, 0, dp[a][0] + c);
    ins(b, 1, *deg[b][0].begin() + *next(deg[b][0].begin()));
    ins(b, 1, dp[a][1]);
    dp[b][0] = *deg[b][0].begin();
    dp[b][1] = *deg[b][1].begin();
}

void dfs2(int x, int p = - 1){ 
    for(pii i : g[x]){
        if(i.ff == p) continue;
        move(x, i.ff, i.ss);
        dfs2(i.ff, x);
        move(i.ff, x, i.ss);
    }
}

const int BUFSIZE = 20 << 21;
char Buf[BUFSIZE + 1], *buf = Buf;

template<class T>
void scan(T &x){
    int neg = 1;
    for(x = 0; *buf < '0' || *buf > '9'; buf++) if(*buf == '-') neg = -1;
    while(*buf >= '0' && *buf <= '9') x = x*10 + (*buf - '0'), buf++;
    x *= neg;
}

void setIO(){
    fread(Buf, 1, BUFSIZE, stdin);
}

int main(){
    setIO();
    int t;
    scan(t);
    for(int tt = 1; tt <= t; tt++){
        int n;
        scan(n);
        for(int i = 0; i < n - 1; i++){
            int a, b, c;
            scan(a), scan(b), scan(c);
            g[a].pb({b, c});
            g[b].pb({a, c});
        }
        ans = 0;
        dfs1(1);
        dfs2(1);
        cout << ans << endl;
        for(int i = 1; i <= n; i++){
            g[i].clear();
            deg[i][0].clear();
            deg[i][1].clear();
        }
    }
}

Create an array $$$b$$$ such that $$$b_i = a_i - \sum \limits_{j=1}^{i-1} a_j$$$.

Can you determine which indices satisfy the conditions using the array $$$b$$$?

How do the queries affect the array $$$b$$$?

Please, read all the hints if you haven't.

We can see that the $$$i$$$ which satisfy the conditions are those such that $$$2 \le i \le n$$$ and $$$b_i \ge 0$$$. Now, the key idea to solve the problem relies on the answer to the third hint. After every query, only $$$b_l$$$ can go from negative to positive. That is because the array $$$b$$$ changes in the following way:

• The elements with index $$$i < l$$$ remain unchanged.

• For the elements with index $$$l \le i \le r$$$, $$$b_i: =b_i -x \cdot (i - l - 1)$$$. $$$b_l$$$ increases, $$$b_{l+1}$$$ remains the same, and the rest decrease.

• For the elements with index $$$i > r$$$, $$$b_i: =b_i - x \cdot (r - l + 1)$$$. They all decrease.

Keeping this in mind, we know that we can maintain a set with all the potential answers. Each time that some $$$b_i$$$ becomes positive, we add $$$i$$$ to the set, knowing that we will do at most $$$n + q$$$ insertions. Then, to answer the queries, we just traverse the set from lower to greater, erasing the elements until we find one that is positive, and we print it, or the set becomes empty, then we output $$$-1$$$. To know whether some $$$b_i$$$ is positive or not, we can use a lazy segment tree supporting range update range queries.

Complexity of the solution: $$$\mathcal{O}((n+q)\log{(n+q)})$$$.

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

struct segTree{
    vector<long long> v;
    vector<long long> upd;
    int size;
    void init(int n){
        size = 1;
        while(size < n) size *= 2;
        v.assign(2 * size, 0);
        upd.assign(2 * size, 0);
    }
    void set(int l, int r, int x, int lx, int rx, long long u){
        if(lx >= l && rx <= r){
            v[x] += u * (rx - lx);
            upd[x] += u;
            return;
        }
        if(lx >= r || l >= rx) return;
        int m = (lx + rx) / 2;
        set(l, r, 2 * x + 1, lx, m, u);
        set(l, r, 2 * x + 2, m, rx, u);
        v[x] = v[2 * x + 1] + v[2 * x + 2] + upd[x] * (rx - lx);
    }
    void set(int l, int r, long long u){
        return set(l, r, 0, 0, size, u);
    }

    void build(vector<int>& a, int x, int lx, int rx){
        if (rx - lx == 1){
            if (lx < (int)a.size()){
                v[x] = a[lx];
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, m);
        build(a, 2 * x + 2, m, rx);
        v[x] = v[2 * x + 1] + v[2 * x + 2];
    }
    void build(vector<int>& a){
        build(a, 0, 0, size);
    }

    pair<long long, int> sum(int l, int r, int x, int lx, int rx){
        if(lx >= l && rx <= r) return {v[x], rx - lx};
        else if(lx >= r || rx <= l) return {0, 0};
        int m = (lx + rx) / 2;
        pair<long long, int> s1 = sum(l, r, 2 * x + 1, lx, m);
        pair<long long, int> s2 = sum(l, r, 2 * x + 2, m, rx);
        return {s1.first + s2.first + upd[x] * (s1.second + s2.second), (s1.second + s2.second)};
    }

    long long sum(int l, int r){
        pair<long long, int> p = sum(l, r, 0, 0, size);
        return p.first;
    }
};


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
	int n, q; cin >> n >> q;
	vector<int> a(n);
	set<int> positive; //Contains all the indices which could be potential answers.
	long long sum = 0;
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		a[i] = x;
		if(i > 0 && x - sum >= 0) positive.insert(i);
		sum += x;
	}
	segTree st; st.init(n); st.build(a);
	while(q--){
		int l, r, x; cin >> l >> r >> x; l--; r--;
		st.set(l, r + 1, (long long)x);
		if(l > 0 && st.sum(l, l + 1) - st.sum(0, l) >= 0) positive.insert(l);
		bool done = 0;
		while((int)positive.size() > 0 && done == 0){
			int ind = *positive.begin();
			if(st.sum(ind, ind + 1) - st.sum(0, ind) >= 0){
				done = 1;
				cout << ind + 1 << "\n";
			}else{
				positive.erase(positive.begin());
			}
		}
		if(!done) cout << -1 << "\n";
	}
}

To count the sum of all subarrays in an array, we can count how many subarrays each element belongs to, then multiply by the element value. In other words, the sum over all subarrays is $$$\sum a_i \cdot i \cdot (N - i + 1)$$$

You can maintain this on a segtree.

For each $$$a_i$$$ in the range $$$[l, r]$$$, we want to add $$$a_i \cdot (r - i + 1) \cdot (i - l + 1)$$$ to the answer. Expanding this, we get $$$-a_i \cdot i^2 + a_i \cdot i \cdot l + a_i \cdot i \cdot r - a_i \cdot l \cdot r - a_i \cdot l + a_i \cdot r + a_i$$$. To maintain this on a segtree, we can just maintain $$$\sum a_i \cdot i^2$$$, $$$\sum a_i \cdot i$$$, $$$\sum a_i$$$, $$$\sum i$$$, and $$$\sum i^2$$$ for each node. Then, when querying, we can just find the sum of these values and put them in the formula to retrieve the answer. Updates can be done using lazy propagation similar to range add, using $$$\sum i$$$ and $$$\sum i^2$$$ to update $$$\sum a_i \cdot i$$$ and $$$\sum a_i \cdot i^2$$$, respectively.

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MOD = 1e9 + 7;

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
}

int n, q;
int arr[200005];

struct node {

    int iia, ia, a, ii, i, sz;

    node(){
        iia = ia = a = sz = 0;
    }
};

node seg[800005];
int tag[800005];

void push_down(int x){
    if(!tag[x]) return;
    for(int i = x*2 + 1; i <= x*2 + 2; i++){
        seg[i].a = (seg[i].a + (ll)seg[i].sz*tag[x]%MOD)%MOD;
        seg[i].ia = (seg[i].ia + (ll)seg[i].i*tag[x]%MOD)%MOD;
        seg[i].iia = (seg[i].iia + (ll)seg[i].ii*tag[x]%MOD)%MOD;
        tag[i] = (tag[i] + tag[x])%MOD;
    }
    tag[x] = 0;
}

node pull(node a, node b){
    node ret;
    ret.iia = (a.iia + b.iia)%MOD;
    ret.ia = (a.ia + b.ia)%MOD;
    ret.ii = (a.ii + b.ii)%MOD;
    ret.a = (a.a + b.a)%MOD;
    ret.i = (a.i + b.i)%MOD;
    ret.sz = (a.sz + b.sz)%MOD;
    return ret;
}

void build(int l = 1, int r = n, int cur = 0){
    if(l == r){
        seg[cur].sz = 1;
        seg[cur].i = l;
        seg[cur].a = arr[l];
        seg[cur].ii = (ll)l*l%MOD;
        seg[cur].ia = (ll)l*arr[l]%MOD;
        seg[cur].iia = (ll)l*l%MOD*arr[l]%MOD;
        return;
    }
    int mid = (l + r)/2;
    build(l, mid, cur*2 + 1);
    build(mid + 1, r, cur*2 + 2);
    seg[cur] = pull(seg[cur*2 + 1], seg[cur*2 + 2]);
}

int get(node x, int l, int r){
    int ret = MOD - x.iia;
    (ret += (ll)x.ia*l%MOD) %= MOD;
    (ret += (ll)x.ia*r%MOD) %= MOD;
    (ret += MOD - (ll)x.a*l%MOD*r%MOD) %= MOD;
    (ret += MOD - (ll)x.a*l%MOD) %= MOD;
    (ret += (ll)x.a*r%MOD) %= MOD;
    (ret += x.a) %= MOD;
    return ret;
}

int query(int l, int r, int ul = 1, int ur = n, int cur = 0){
    if(l <= ul && ur <= r){
        return get(seg[cur], l, r);
    }
    if(ur < l || ul > r) return 0;
    push_down(cur);
    int mid = (ul + ur)/2;
    return (query(l, r, ul, mid, cur*2 + 1) + query(l, r, mid + 1, ur, cur*2 + 2))%MOD;
}

void update(int l, int r, int v, int ul = 1, int ur = n, int cur = 0){
    if(l <= ul && ur <= r){
        seg[cur].a = (seg[cur].a + (ll)seg[cur].sz*v%MOD)%MOD;
        seg[cur].ia = (seg[cur].ia + (ll)seg[cur].i*v%MOD)%MOD;
        seg[cur].iia = (seg[cur].iia + (ll)seg[cur].ii*v%MOD)%MOD;
        tag[cur] = (tag[cur] + v)%MOD;
        return;
    }
    push_down(cur);
    int mid = (ul + ur)/2;
    if(l <= mid) update(l, r, v, ul, mid, cur*2 + 1);
    if(r > mid) update(l, r, v, mid + 1, ur, cur*2 + 2);
    seg[cur] = pull(seg[cur*2 + 1], seg[cur*2 + 2]);
}

int main(){
    setIO();
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    build();
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        if(t == 1){
            cout << query(l, r) << endl;
        } else {
            int v;
            cin >> v;
            update(l, r, v);
        }
    }
}

# O(N*log(precision + MAXA*log(MAXA))

# ANALYZING WHY WE CAN'T EXPRESS ALL VALUES:
#
# The sum changes at x = b/z if for some i, z | a[i].
# However, there may be multiple such i, and so the sum "skips" a few values
# since multiple a transition (floor(ax) increases). This is why we can't express all integers.
#
# IDEA:
#
# The number of expressible integers = the number of x such that the sum increases.
#
# SOLUTION:
#
# Realize that for a fixed max x, we can do a dp on divisors to compute:
# transition_points[i] = # of x such that x in simplest form = b/i
#
# Then, the sum is increased to a new value at transition_points[i] x's if there exists an
# a that transitions at those points x = b/i => i | a.
#
# Thus, we can find # of expressible numbers below r and l-1 by binary searching on the maximum x
# (be careful about precision!).
# We can binary search on the integer part and then the fractional part.
# Subtract the values for the answer.


from math import floor

MAXA = 10**5


def expressible_numbers_below_bound(a, right_bound):
    # Binary search to find max_x

    # First binary search on the integer part of max_x
    l = 0
    r = 10**18

    while l != r:
        m = (l + r + 1) // 2

        tot_sum = sum(floor(m*val) for val in a)

        if tot_sum <= right_bound:
            l = m
        else:
            r = m-1

    # Now binary search on the fractional part of max_x
    fractional_l = 0
    fractional_r = 1
    # We can stop at <= 2e-10 actually
    while fractional_r - fractional_l > 1e-12:
        m = (fractional_l + fractional_r) / 2

        # This fails if abs(m - b/val) < 1e-15 and we have nlog(precision) calculations.
        # Thus, there is a 1e-9 chance of occurring over all calculations
        tot_sum = sum(l*val + floor(m*val) for val in a)

        if tot_sum <= right_bound:
            fractional_l = m
        else:
            fractional_r = m

    max_x_integer = l
    max_x_fractional = fractional_l

    # Now we find the number of expressible integers using 0 <= x <= max_x

    cnt = [0] * (MAXA + 1)

    for i in a:
        cnt[i] += 1

    divisors = [[] for _ in range(MAXA+1)]
    number_of_a_that_transition = [0] * (MAXA + 1)

    for i in range(1, MAXA+1):
        for j in range(i, MAXA+1, i):
            divisors[j].append(i)

            number_of_a_that_transition[i] += cnt[j]

    transition_points = [0] * (MAXA + 1)

    for i in range(1, MAXA + 1):
        for div in divisors[i]:
            if div != i:
                transition_points[i] -= transition_points[div]

        transition_points[i] += i*max_x_integer + floor(i*max_x_fractional)

    return sum((number_of_a_that_transition[i] > 0) * transition_points[i] for i in range(1, MAXA + 1))


n, l, r = map(int, input().split())
a = list(map(int, input().split()))

ans = expressible_numbers_below_bound(a, r) &mdash; expressible_numbers_below_bound(a, l-1)

print(ans)

Consider each valid row/column as a bitmask with at most $$$5$$$ bits. Then we can consider a query as an order to turn on bits in a size $$$20$$$ bitmask. If at any point a row/column appears in this bitmask we can know the game ends, and if we can determine the minimum ID that forms a working row/column we will have solved the problem.

The best algorithm to use for this is a bitmask dp/SOS dp. For each valid row/column we can write in the minimum ID that has that row/column. Then for all the other masks we can compute the minimum mask out of all of the submasks. This gives us an $$$O(k 2^k + q)$$$ solution.

I, as the problemsetter, made a mistake and did not realize that $$$25 \cdot 2^{25}$$$ runs comfortably in the time limit and watched my problem get cheesed by a subtask sol :<.

The intended solution is built off the subtask solution. We still want to use the bitmask idea. Consider splitting the $$$k$$$ possible numbers into $$$5$$$ parts with sizes $$$a_1, a_2, a_3, a_4, a_5$$$. We will build a bitmask dp that covers any mask which spans at most $$$4$$$ of these parts and we will manually enumerate the masks which span all $$$5$$$ every query. This gives us an $$$O({5 \choose 4} \cdot 2^{(k - \min(a_i))} + q \cdot \prod a_i)$$$ solution. For $$$k = 25$$$ we should pick $$$a = [5, 5, 5, 5, 5]$$$ and for $$$ k = 27$$$ we should pick $$$k = [6, 6, 5, 5, 5]$$$ which should fit comfortably within the limit.

There are also ways to ac by constant optimizing out a $$$k \choose 4$$$ per query.

//misaka, hitori, and elaina will carry me to red
#include <iostream>
#include <cmath>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <array>
#include <cstdio>
#include <cstring>
#include <functional>
#include <numeric>
#include <set>
#include <queue>
#include <map>
#include <chrono>
#include <random>

#define sz(x) ((int)(x.size()))
#define all(x) x.begin(), x.end()
#define pb push_back
#define eb emplace_back
#define kill(x, s) {if(x){ cout << s << "\n"; return ; }}
#define lsb(x) ((x)&(-(x)))
#define lg2(x) (31 &mdash; __builtin_clz(x))
#define pcnt(x) __builtin_popcount(x)


#ifndef LOCAL
#define cerr while(0) cerr
#endif

using ll = long long;
using lb = long double;

const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
//const ll mod = (1 << (23)) * 119 +1, ll_max = 1e18;
const int MX = 2e5 +10, int_max = 0x3f3f3f3f;

struct {
  template<class T>
  operator T() {
    T x; std::cin >> x; return x;
  }
} in;

using namespace std;

const int k = 5;
const int p = 5;
const int A = 25;

vector<int> mem[40];

array<int, A*A*A*A*A> val;
int cond(int x, int mask){
	int ans = 0, b = 1;
	for(int i = 0; i<k; i++){
		if(mask&(1 << i)){
			ans += ((x&(((1 << p)-1) << (i*p))) >> (i*p)) * b;
			b *= (1 << p);
		}
	}
	return ans;
}

int check(int x, int mask){
	for(int i = 0; i<k; i++){
		if(!(mask&(1 << i))){
			if(x&(((1 << p)-1) << (i*p))) return 0;
		}
	}
	return 1;
}
vector<int> sos(vector<int> a){
	int n = lg2(sz(a));
	for(int i = 0; i<n; i++){
		for(int j = 0; j<(1 << n); j++){
			if(j&(1 << i)){
				a[j] = min(a[j], a[j &mdash; (1 << i)]);
			}
		}
	}
	return a;
}
void solve(){
	int n = in;
	int mx = in;
	vector<pair<int, int>> small;
	val.fill(int_max);
	for(int i = 1; i<=n; i++){
		array<array<int, k>, k> board;
		for(int j = 0; j<k; j++){
			for(int h = 0; h<k; h++){
				board[j][h] = in;
				board[j][h]--;
			}
		}
		for(int j = 0; j<k; j++){
			unsigned int r = 0, c = 0;
			array<int, k> rr, cc;
			for(int h = 0; h<k; h++){
				r |= (1 << board[j][h]);
				c |= (1 << board[h][j]);
				rr[h] = board[j][h];
				cc[h] = board[h][j];
			}
			sort(all(rr));
			sort(all(cc));
			int r1 = 0, c1 = 0;
			int b = 1;
			for(int h = 0; h<k; h++){
				r1 += b*rr[h];
				c1 += b*cc[h];
				b *= A;
			}
			if(val[c1] == int_max){
				small.pb({c, i});
				val[c1] = i;
			}
			if(val[r1] == int_max){
				small.pb({r, i});
				val[r1] = i;
			}			
		}
	}
	for(int mask = 1; mask<(1 << k)-1; mask++){
		vector<int> a(cond((1 << (k*p))-1, mask)+1, int_max);
		for(auto [m, id] : small){
			if(check(m, mask)){
				a[cond(m, mask)] = min(a[cond(m, mask)], id);
			}
		}
		mem[mask] = sos(a);
	}	
	int q = in;
	for(int qaq = 1; qaq<=q; qaq++){
		array<int, A> perm, inv = perm;
		iota(all(perm), 0);
		for(int i = 0; i<mx; i++){
			perm[i] = in;
			perm[i]--;
		}
		for(int i = 0; i<A; i++){
			inv[perm[i]] = i;
		}
		int glob = 0;
		pair<int, int> ans = {int_max, int_max};
		for(int i = 0, wo = 0; i<A && wo == 0; i++){
			if(perm[i] < p*k)
				glob |= (1 << perm[i]);
			for(int mask = 1; mask<(1 << k)-1; mask++){
				int v = mem[mask][cond(glob, mask)];
				if(v != int_max){
					ans = min(ans, pair(i, v));
					wo = 1;
				}
			}
		}
		for(int i = 0; i<p; i++){
			for(int j = p; j<p*2; j++){
				for(int h = p*2; h<p*3; h++){
					for(int l = p*3; l<p*4; l++){
						for(int m = p*4; m<p*5; m++){
							int hsh = i + A*j + A*A*h + A*A*A*l + A*A*A*A*m;
							int t = max({inv[i], inv[j], inv[h], inv[l], inv[m]});
							if(val[hsh] != int_max) ans = min(ans, pair(t, val[hsh]));
						}
					}
				}
			}
		}
		cout << ans.second << " " << perm[ans.first]+1 << "\n";
	}
}

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

  int T = 1;
  //cin >> T;
  for(int i = 1; i<=T; i++){
		//cout << "Case #" << i << ": ";
		solve();
	}
  return 0;
}