The optimal strategy in this game is to always choose the maximum available option. By doing so, a player maximizes their own score while minimizing the opponent's potential gain. This means that one choice of your opponent is already fixed, and you can't do anything about it. However, you should not end up giving your opponent a better choice.

Therefore, choosing the maximum of the two options is the best strategy.

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll , ll > pl;
typedef pair<int ,int > pa;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
#define MP make_pair
#define PB push_back
#define p (ll)(1e9 + 7)

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        vl a(n);
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        int Alice=0;
        int Bob=0;
        for(int i=0;i<n-1;i++)
        {
            if(a[i]>=a[i+1])
            {
                if(i%2==0)
                {
                    Alice+=a[i];
                }
                else {
                    Bob+=a[i];
                }
            }
            else {
            if(i%2==0)
            {
                Alice+=a[i+1];
            }
            else {
                Bob+=a[i+1];
            }
            a[i+1]=a[i];
            }

        }
        if((n-1)%2==0)
        {
            Alice+=a[n-1];
        }
        else {
            Bob+=a[n-1];
        }
        if(Alice>Bob)
        {
            cout<<"ALICE\n";
        }
        else if(Alice==Bob)
        {
            cout<<"DRAW\n";
        }
        else {
            cout<<"BOB\n";
        }
    }
}

If the grid is already beautiful, that is each row sum is equal to its corresponding column sum, any coordinate $$$(i, j)$$$ can be chosen and its original value can be chosen as the modified value.

If the grid is not beautiful ,then let sum of the $$$i^{th}$$$ row and the sum of the $$$i^{th}$$$ column differ, adjustments can be made to a cell, $$$a_{ij}$$$, to equalize these sums. However, modifying $$$a_{ij}$$$ to equalize the $$$i^{th}$$$ row and column also affects the sum of the $$$j^{th}$$$ column, resulting in a new imbalance.

Thus, it is necessary to identify pairs of rows and columns where the sums differ by the same magnitude but in opposite directions. Also note that decreasing the sum of the $$$i^{th}$$$ row leads to an decrease in the $$$j^{th}$$$ column sum. Since we can only change a cell to a non-negative integer, negative changes can be avoided by choosing to increase the $$$i^{th}$$$ column instead thereby increasing the $$$j^{th}$$$ column satisfying the beautiful condition.

More formally, if $$$i$$$ and $$$j$$$ represent the coordinates of the cell to be modified, instead of directly decreasing $$$a_{ij}$$$ by the difference between the $$$i^{th}$$$ row and column sum, which is denoted as $$$\text{diff}(\text{row}_i, \text{col}_i)$$$, an alternative approach is to increase $$$a_{ji}$$$ by this difference.

If there are more than 2 rows whose sum differs from their column, it can be proven that its impossible to make the grid beautiful.

Time Complexity: $$$O(n^{2})$$$

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

void solve()
{
    int n;
    cin >> n;
    vector<vector<int>> matrix(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> matrix[i][j];
    }
    vector<int> columns(n);
    vector<int> rows(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            rows[i] += matrix[i][j];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            columns[i] += matrix[j][i];
    }
    
    int diff_occur = 0;
    int diff = matrix[0][0];
    int row1 = 0;
    int row2 = 0;
    for (int i = 0; i < n; i++)
    {
        if (rows[i] != columns[i] && !diff_occur)
        {
            row1 = i;
            diff = rows[i] - columns[i];
            diff_occur++;
        }
        else if (rows[i] != columns[i] && diff_occur == 1)
        {
            if (diff == columns[i] - rows[i])
            {
                diff_occur++;
                row2 = i;
            }
            else
            {
                cout << "NO" << endl;
                return;
            }
        }
        else if (rows[i] != columns[i] && diff_occur > 1)
        {
            cout << "N0" << endl;
            return;
        }
    }
    if (diff_occur == 1)
    {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
   
    if (matrix[row1][row2] - diff >= 0)
    {
        
        cout << row1 + 1 << " " << row2 + 1 << " " << endl;
        cout << matrix[row1][row2] - diff << endl;
    }
    else
    {
        cout << row2 + 1 << " " << row1 + 1 << " " << endl;
        cout << diff + matrix[row2][row1] << endl;
    }

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

Let $$$a_{i,j}$$$ denote the $$$j^{th}$$$ number in the $$$i^{th}$$$ row.

Claim : Every row is a Fibonacci sequence.

We know that the sum of the first $$$n$$$ numbers in Fibonacci sequence is $$$F_{n+2} - 1$$$.

Now, it's easy to see that the sum of the first $$$i$$$ rows $$$S_{i}$$$ is $$$F_{i+4} - (i+3)$$$.

For any query $$$(i,j)$$$, the answer is $$$S_{j} - S_{i-1} = F_{j+4} - F_{i+3} - (j-i+1)$$$.

For the Easy Version, precompute all Fibonacci numbers up to $$$10^5$$$.

For the Hard Version, use matrix exponentiation to compute Fibonacci numbers faster.

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

const ll mod = 1'000'0'000'07;

struct matrix {
    ll mat[2][2];
    matrix friend operator *(const matrix &a, const matrix &b){
        matrix c;
        for (ll i = 0; i < 2; i++) {
          for (ll j = 0; j < 2; j++) {
              c.mat[i][j] = 0;
              for (ll k = 0; k < 2; k++) {
                  c.mat[i][j] += ((a.mat[i][k])%mod * (b.mat[k][j])%mod)%mod;
                  c.mat[i][j]%=mod;
              }
          }
        }
        return c;
    }
};

matrix matpow(matrix base, ll n) {
    matrix ans{ {
      {1, 0},
      {0, 1}
    } };
    while (n) {
        if(n%2==1)
        {
            ans = ans*base;
        }
        base = base*base;
        n/=2;
    }
    return ans;
}

ll fib(ll n) {
    matrix base{ {
      {1, 1},
      {1, 0}
    } };
    return (matpow(base, n).mat[0][1])%mod;
}

int main()
{
    int q;
    cin >> q;
    while(q--)
    {
        ll i,j;
        cin >> i >> j;
        cout << ((fib(j+4)-fib(i+3)+mod)%mod-(j-i+1)%mod+mod)%mod <<'\n';
    }
    return 0;
}

This problem can be reduced to the problem of just finding a set of sectors that sum up to 360 degrees, with an equal number of type 1 and type 2 sectors. Hence, This can be solved with Dynamic Programming.

Let $$$dp[i][j][k]$$$ be True if it's possible to get a sum of $$$j$$$ degrees by using only a subset of the first $$$i$$$ sectors, with (number of type 1 sectors) — (number of type 2 sectors) = $$$k$$$.

Otherwise it's False.

Here $$$i$$$ goes from 0 to 300, $$$j$$$ from 0 to 360 and $$$k$$$ from -300 to 300 (negative index can be simulated using an offset).

Transitions:

if $$$a[i]$$$ is of type 1:

$$$dp[i][j][k] = (dp[i - 1][j][k]) || (dp[i - 1][j - a[i]][k + 1])$$$

else:

$$$dp[i][j][k] = (dp[i - 1][j][k]) || (dp[i - 1][j - a[i]][k - 1])$$$

Note that we are using 1-indexing for $$$a$$$ in this context. Also, if $$$j-a[i]$$$ becomes negative, that term is assumed to be 0.

Base cases:

$$$dp[0][j][k] = $$$ False for all $$$j$$$ and $$$k$$$ in their respective ranges except when both $$$j=0$$$ and $$$k=0$$$

$$$dp[i][0][0] = $$$ True for all $$$i$$$

The final answer will be YES if $$$dp[n][360][0] = $$$ True. NO otherwise.

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

typedef long long ll;
#define vll vector<long long>

bool dp[301][361][602];

signed main(void) {
    long long t;
    cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        vll a(n);
        vll type(n);

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

        // initialising base cases
        for (int j = 1; j <= 360; j++) {
            for (int k = -n; k <= n; k++) {
                dp[0][j][301 + k] = 0;
            }
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0][301] = 1;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 360; j++) {
                for (int k = -n; k <= n; k++) {
                    // i is 1-indexed
                    dp[i][j][301 + k] = dp[i - 1][j][301 + k];
                    if (type[i - 1] == 1) {
                        if (j - a[i - 1] >= 0) {
                            dp[i][j][301 + k] |=
                                dp[i - 1][j - a[i - 1]][301 + k + 1];
                        }
                    } else {
                        if (j - a[i - 1] >= 0) {
                            dp[i][j][301 + k] |=
                                dp[i - 1][j - a[i - 1]][301 + k - 1];
                        }
                    }
                }
            }
        }
        if (dp[n][360][301])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

First, we forget about the expectation part. We can simply find the sum and divide it by total number of pairs. Furthermore, for any position of the girl and Tom, the point where they meet will be the $$$LCA(x, y),$$$ where $$$x$$$ and $$$y$$$ are the zones that Tom and the girl live in. Also, we will call the values where Tom has a house "marked" vertices.

Therefore, the sum can be mathematically shown as $$$\sum_x\sum_y d(1, \space LCA(x,\space y))$$$, where $$$x$$$ is the possible zones Tom lives in, and $$$y$$$ can take any value.

We will first try to calculate this sum without queries.

To do so, we can do a simple dfs. Suppose we are at vertex $$$u$$$. Then, we find the number of pairs whose $$$LCA$$$ is $$$u$$$, and multiply it by the distance to $$$u$$$. Suppose $$$sz[u]$$$ is the size of the subtree with root $$$u$$$, $$$c[u]$$$ is the number of nodes that Tom has a house in in the subtree with root $$$u$$$.

To do this, we consider what cases there are such that the $$$LCA$$$ is at $$$u$$$. Let $$$child$$$ be the current child of $$$u$$$ we are iterating through.

Case 1. For any $$$y$$$ in subtree of $$$child$$$, we can choose any $$$x$$$ in any other subtree of another child of $$$u$$$. Case 2. If Tom has a house in zone $$$u$$$, we can choose any node in the subtree $$$u$$$. Case 3. If $$$y = u$$$, then we can choose any zone in the subtree of $$$u$$$ that Tom has a house in.

Case $$$1$$$ contributes $$$\sum_{child : u} (c[u] - c[child])\cdot sz[child]$$$, Case $$$2$$$ contributes $$$sz[u]$$$ if $$$u$$$ is marked, and finally Case $$$3$$$ contributes $$$c[u].$$$ Note that special care must be taken to not double count case when 2 and 3 collide.

Suppose $$$cont[u]$$$ stores the number of pairs with $$$LCA$$$ at $$$u$$$, then the answer is simply

$$$ans = \sum_u cont[u] \times d[u, 0]$$$, where $$$u$$$ = $$$1, 2 \cdots n$$$.

Now, we to answer the queries, we simply need to store some more information.

For type $$$1$$$ queries, note that the $$$LCA$$$ when $$$y = n + 1$$$ can only lie on the path from $$$i$$$ to $$$0$$$, where $$$y$$$ is the new vertex, and $$$i$$$ is the vertex that $$$y$$$ is connected to. Therefore, all we need to do is store some kind of path sum from $$$0$$$ to $$$u.$$$ While moving from some vertex $$$u$$$ to $$$v$$$, we can observe that if the addex vertex is in the subtree of $$$v$$$, then for all marked vertices in other children of $$$u$$$, we will have $$$LCA(marked \space vertex, y) = u.$$$ Therefore, these vertices will contribute an addition $$$d(u, 0)$$$ to the sum. We can precalculate this sum for every vertex using a dfs by doing

$$$pathsum = pathsum + dist[u,0] \cdot (c[u] - c[v])$$$, while moving from $$$u$$$ to $$$v$$$.

We also need to add the children in the subtree of $$$i$$$, since these will have $$$LCA$$$ as $$$i$$$.

Suppose $$$q[i]$$$ is the pathsum to $$$i$$$. Then the sum for each query of type 1 is simply :

$$$ans \space+\space q[i] \space+ \space c[i]\cdot d[i]. $$$

For type $$$2$$$ queries, each edge will be used only by the pairs whose $$$LCA$$$ is below it. That is, if $$$dep[i] < dep[j]$$$, then we simply need to find number of pairs whose $$$LCA$$$ is below or at $$$j$$$, since only these pairs will use this edge. However, we already have the number of pairs whose $$$LCA$$$ is at each node through $$$cont$$$. Therefore, the number of nodes will simply be given by the subtree sum of $$$cont$$$, which can be precalculated, in say $$$pref$$$.

The sum for each query of type 2 will become:

$$$ans \space+ \space (w_{new} - w_{old}) \cdot pref[j]$$$, where $$$j$$$ is the vertex with lower depth.

Don't forget to divide by total number of pairs $$$(n+1)\cdot m$$$, $$$n\cdot m$$$ correspondingly for type 1 and 2 queries.

Time Complexity: $$$O(n)$$$ preprocessing, $$$O(1)$$$ per query

#include<bits/stdc++.h>
#include <sys/types.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
long long power(long long x, int y, int p)
{
	long long res = 1;     // Initialize result

	x = x % p; // Update x if it is more than or
	// equal to p

	if (x == 0) return 0; // In case x is divisible by p;

	while (y > 0)
	{
		// If y is odd, multiply x with result
		if (y & 1)
			res = (res * x) % p;

		// y must be even now
		y = y >> 1; // y = y/2
		x = (x * x) % p;
	}
	return res;
}
int mod = (int)1e9 + 7;
vector<pair<int, int>> adj[N];
int f[N];
int sz[N];
int c[N];
int contrib[N];
int pref[N];
int d[N];
int ans = 0;
void dfs(int u, int dist, int p) {
	d[u] = dist;
	for (auto [x, w] : adj[u]) {
		if (x == p) continue;
		dfs(x, (dist + w) % mod, u);
		c[u] += c[x];
		c[u] %= mod;
		sz[u] += sz[x];
		sz[u] %= mod;
	}
	for (auto [x, w] : adj[u]) {
		if (x == p) continue;
		contrib[u] += (c[u] - c[x]) * (sz[x]); //choose a vertex among the houses in other paths, pick all possible vertices here
		contrib[u] %= mod;
	}
	sz[u]++;
	if (f[u]) {
		contrib[u] += sz[u];//with that as choice for 'x'
		contrib[u] %= mod;
	}
	contrib[u] += c[u];//the girls house
	contrib[u] %= mod;
	pref[u] = contrib[u];
	c[u] += f[u];
	c[u] %= mod;
}
int q1[N];
int q2[N];
void dfs1(int u, int pathsum, int p) {
	ans += (contrib[u] * d[u]) % mod;
	ans %= mod;
	q1[u] = pathsum;

	for (auto [x, w] : adj[u]) {
		if (x != p) {
			int path = 0;
			path = pathsum + ((c[u] - c[x]) * d[u]) % mod;
			path %= mod;
			dfs1(x, path, u);
		}
	}
	for (auto [x, w] : adj[u]) {
		if (x != p)
			pref[u] += pref[x];
		pref[u] %= mod;
	}
}
int32_t main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		f[--tmp] = 1;
	}
	map<pair<int, int>, int> mp;
	for (int i = 0; i < n - 1; i++) {
		int ta, tb, w;
		cin >> ta >> tb >> w;
		--ta, --tb;
		adj[ta].push_back({tb, w});
		adj[tb].push_back({ta, w});
		mp[ {ta, tb}] = w;
		mp[ {tb, ta}] = w;
	}
	dfs(0, 0, -1);
	dfs1(0, 0, -1);
// 	cout << ans << '\n';

	int q;
	cin >> q;
	while (q--) {
		int op;
		cin >> op;
		if (op == 1) {
			int i, w;
			cin >> i >> w;
			--i;
			int add = (q1[i] + (c[i] * d[i]) % mod) % mod;
			int tmp = ans;
			tmp += add;
			tmp %= mod;
			int denom = (n + 1) * m;
			denom %= mod;
			denom = power(denom, mod - 2, mod);
			tmp *= denom;
			tmp %= mod;
			cout << tmp << '\n';
		}
		else {
			int i, j, w;
			cin >> i >> j >> w;
			--i, --j;
			int lo = j;
			if (sz[i] < sz[j]) lo = i;
			int tmp = ans;
			int cur_wt = mp[ {i, j}];
			int rem = ((cur_wt) * pref[lo]) % mod;
			int add = (w * pref[lo]) % mod;
			tmp = tmp - rem + add;
			tmp %= mod;
			if (tmp < 0) tmp += mod;
			int denom = n * m;
			denom %= mod;
			denom = power(denom, mod - 2, mod);
			tmp *= denom;
			tmp %= mod;
			cout << tmp << '\n';
		}
	}

}