Each operation increases the sum by exactly $$$x$$$, regardless of the index to which the operation was applied.

Let $$$A$$$ be the initial sum of the array $$$a$$$. Each operation adds $$$x$$$ to $$$A$$$. We need to check whether $$$A$$$ can become equal to $$$S$$$. First, $$$S$$$ must not be smaller than $$$A$$$. Second, their difference must be divisible by $$$x$$$, that is, $$$x$$$ must divide $$$(S - A)$$$.

#include <bits/stdc++.h>

using namespace std;

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

	while( t -- )
	{
		int n, s, x;
		cin >> n >> s >> x;
		int a[n + 5], sum = 0;

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

		if( sum > s || (s - sum) % x != 0 ) cout << "NO\\n";
		else cout << "YES\\n";
	}
}

• Great problem
• Normal problem
• Bad problem
• Didn’t solve

If $$$p_1 = n$$$, then there is no reason to change it. If $$$p_1 = n$$$ and $$$p_2 = n-1$$$, then the second element also does not need to be changed, and so on. Thus, we need to find the first index $$$i$$$ for which $$$p_i \neq n-i+1$$$ and increase it. Our goal is to make $$$p_i$$$ equal to $$$n-i+1$$$ (then the permutation will be lexicographically maximal). Find an index $$$j$$$ such that $$$p_j = n-i+1$$$ and perform the operation on $$$[i, j]$$$.

#include <bits/stdc++.h>

using namespace std;

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

	while( t -- )
	{
		int n;
		cin >> n;

		int p[n + 5], ind = 1;

		for( int i = 1; i <= n; i ++ )
		{
			cin >> p[i];
		}
		while( ind <= n && p[ind] == n - ind + 1 ) ind ++;
		int id = -1;

		for( int i = ind; i <= n; i ++ )
		{
			if( p[i] == n - ind + 1 ) id = i;
		}
		for( int i = 1; i < ind; i ++ ) cout << p[i] << ' ';

		if( id != -1 )
		{
			for( int i = id; i >= ind; i -- ) cout << p[i] << ' ';
			for( int i = id + 1; i <= n; i ++ ) cout << p[i] << ' ';
		}
		cout << '\\n';
	}
}

• Great problem
• Normal problem
• Bad problem
• Didn’t solve

First, try to maximize all elements of $$$a$$$, and then answer the queries.

First, try to maximize all elements of $$$a$$$, and then answer the queries. Iterate $$$i$$$ from $$$n$$$ to $$$1$$$ and set $$$a_i$$$ equal to the maximum among $$$a_i$$$, $$$b_i$$$, and $$$a_{i+1}$$$. Thus, each $$$a_i$$$ reaches its maximum value. Now we can build prefix sums on array $$$a$$$ to answer each query in $$$O(1)$$$ time.

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
signed main()
{
    int t; cin >> t;
    
    while( t -- )
    {
    	int n, q; cin >> n >> q;
    	int a[n + 5], b[n + 5], pref[n + 5], ans = 0;
    	
    	for( int i = 1; i <= n; i ++ ) cin >> a[i];
    	for( int i = 1; i <= n; i ++ ) cin >> b[i];

	a[n + 1] = 0;

	for( int i = n; i > 0; i -- ) a[i] = max({a[i], a[i + 1], b[i]});
    	
    	pref[0] = 0;
    	for( int i = 1; i <= n; i ++ ) pref[i] = pref[i - 1] + a[i];
    	
    	for( int i = 1; i <= q; i ++ ){
    	    int L, R; cin >> L >> R;
    	    cout << pref[R] - pref[L - 1] << " ";
    	}
    	cout << "\n";
    }
}

• Great problem
• Normal problem
• Bad problem
• Didn’t solve

Sort all swords by strength in descending order. Then if the difficulty is equal to $$$a_i$$$, the number of swords that can be used equals $$$i$$$. As the difficulty decreases, the number of swords increases, and therefore the number of levels that can be completed increases. We can maintain a pointer to the number of levels and take the maximum score among all difficulties. Such a pointer-based solution works in $$$O(n)$$$ operations.

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
const int N = 2e5 + 12;
 
int t, n, a[N], b[N];
 
int main()
{
    cin >> t;
    
    while( t -- )
    {
        cin >> n;
        
        for( int i = 1; i <= n; i ++ ) cin >> a[i];
        for( int i = 1; i <= n; i ++ ) cin >> b[i];
        
        int h = 0, sum = 0; ll ans = 0;
        sort(a + 1, a + n + 1); reverse(a + 1, a + n + 1);
        
        for( int i = 1; i <= n; i ++ )
        {
            while( h < n && sum + b[h + 1] <= i ) h ++, sum += b[h];
            ans = max(ans, a[i] * 1ll * h);
        }
        cout << ans << '\n';
    }
}

• Great problem
• Normal problem
• Bad problem
• Didn’t solve

Try a DP approach to the problem.

We will write a dynamic programming solution. $$$dp[x]$$$ is the answer for the number $$$x$$$. Initially $$$dp[a_i] = 1$$$ for all $$$i$$$ from $$$1$$$ to $$$n$$$, and all other elements of $$$dp$$$ are equal to $$$10^9$$$. Iterate $$$x$$$ from $$$1$$$ to $$$n$$$ and consider the transition:

• Iterate over all divisors $$$y$$$ of $$$x$$$.
• Update $$$dp[x]$$$ with $$$min(dp[x], dp[y] + dp[\frac{x}{y}])$$$.

Replace all $$$dp[x]$$$ equal to $$$10^9$$$ with $$$-1$$$ and output all values of $$$dp$$$. In this solution we iterate over all numbers from $$$1$$$ to $$$n$$$ and their divisors, which totals $$$O(n \log n)$$$ operations.

#include <bits/stdc++.h>
 
using namespace std;
const int maxn = 1'000'012;
 
int a[maxn], dp[maxn];
int n, q;
 
void solve() {
    cin >> n;
 
    for(int i = 1; i <= n; i++) {
        dp[i] = 1e9;
    }
    for(int i = 1; i <= n;i++) {
        cin >> a[i];
        dp[a[i]] = 1;
    }
 
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j += i) {
            dp[j] = min(dp[j], dp[i] + dp[j / i]);
        }
    }
 
    for(int i = 1; i <= n; i++) {
        if(dp[i] == 1e9) {
            dp[i] = -1;
        }
        cout << dp[i] << " \n"[i == n];
    }
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

• Great problem
• Normal problem
• Bad problem
• Didn’t solve

We split the delivery points into groups with the same $$$x_i$$$. Number the groups from $$$0$$$ to $$$m+1$$$ in increasing order of $$$x_i$$$, where $$$m$$$ is the number of distinct $$$x_i$$$. Group $$$0$$$ is the starting point and group $$$m+1$$$ is the finishing point.

Since we cannot move left, we must deliver pizza to all points of group $$$i$$$ before moving to group $$$i+1$$$. Let $$$high_i$$$ be the point with the maximum $$$y$$$ and $$$low_i$$$ be the point with the minimum $$$y$$$ in group $$$i$$$. Since all points in the group lie between them, the point that will be delivered last in the group will be one of these. This means that when moving from group $$$i$$$ to group $$$i+1$$$, we will go through either $$$high_i$$$ or $$$low_i$$$.

Now we can write a DP for the problem. $$$dp[i][0]$$$ is the minimum time to deliver pizza to all groups from $$$0$$$ to $$$i$$$, delivering last to $$$high_i$$$, and $$$dp[i][1]$$$ is the same but delivering last to $$$low_i$$$. Initially, $$$dp[0][0] = 0$$$ and $$$dp[0][1] = 0$$$. For all other $$$i \gt 0$$$, the transitions are:

• $$$dp[i][0] = \min(dp[i - 1][0] + dist(high_{i-1}, low_i), dp[i - 1][1] + dist(low_{i-1}, low_i)) + dist(low_i, high_i);$$$
• $$$dp[i][1] = \min(dp[i - 1][0] + dist(high_{i-1}, high_i), dp[i - 1][1] + dist(low_{i-1}, high_i)) + dist(high_i, low_i);$$$

Here $$$dist(a, b)$$$ denotes the Manhattan distance between points $$$a$$$ and $$$b$$$. Thus, sorting all points into groups takes $$$O(n\log n)$$$ operations, and computing the DP takes $$$O(n)$$$ operations.

#include <bits/stdc++.h>
 
#define F first
#define S second
#define int long long
 
using namespace std;
 
int t, n, ax, ay, bx, by;
 
signed main()
{
    cin >> t;
    
    while( t -- )
    {
        cin >> n >> ax >> ay >> bx >> by;
        vector <int> x(n + 5), y(n + 5), dp[2];
        
        dp[0] = dp[1] = vector <int> (n + 5, 0);
        map <int, int> mx, mn;
        
        mn[ax] = mx[ax] = ay;
        mn[bx] = mx[bx] = by;
        
        for( int i = 0; i < n; i ++ ) cin >> x[i];
        for( int i = 0; i < n; i ++ ) cin >> y[i];
        
        for( int i = 0; i < n; i ++ )
        {
            mx[x[i]] = max(mx[x[i]], y[i]);
            
            if(!mn.count(x[i])) mn[x[i]] = y[i];
            else mn[x[i]] = min(mn[x[i]], y[i]);
        }
        int lst = ax, cnt = 0;
        
        for( auto i : mx )
        {
            if( i.F == ax )
            {
                dp[0][0] = dp[1][0] = 0;
                continue;
            }
            int need = (i.F - lst) + (mx[i.F] - mn[i.F]);
            cnt ++;
            
            dp[0][cnt] = min(dp[0][cnt - 1] + abs(mx[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mx[i.F] - mx[lst])) + need;
            dp[1][cnt] = min(dp[0][cnt - 1] + abs(mn[i.F] - mn[lst]), dp[1][cnt - 1] + abs(mn[i.F] - mx[lst])) + need;
            
            lst = i.F;
        }
        cout << dp[0][cnt] << '\n';
    }
}

• Great problem
• Normal problem
• Bad problem
• Didn’t solve

Try dividing the vertices into pairs and ask the interactor about these pairs.

First, write the numbers of all tree vertices into a sequence $$$p$$$ in DFS order. Split the elements of sequence $$$p$$$ into pairs $$$(p_1, p_2)$$$, $$$(p_3, p_4)$$$, and so on. If $$$n$$$ is odd, temporarily ignore the last element.

Iterate $$$i$$$ from 1 to $$$\frac{n}{2}$$$ and make the following query to the interactor: $$$?$$$ $$$p_{2i-1}$$$ $$$p_{2i}$$$.

• If these are two adjacent vertices, then when the interactor answers $$$1$$$, we will know for sure that at least one of the vertices lies on the path. In this case, with an additional query, we can find out which of the two vertices lies on the path.
• Otherwise, look at the simple path between the two vertices. All pairs before this pair have been queried, so only these two vertices have not been queried on their path. Then we are back to the same situation, where one of the vertices definitely lies on the path (if the interactor answers positively).
• If we find a suitable vertex, stop the process.

When $$$n$$$ is odd, one vertex remains unqueried. If we did not find a vertex from the hidden path in any pair, then we can confidently say that the remaining vertex is the one that lies on the hidden path. In the end, we obtain a solution that works in exactly $$$\lfloor\frac{n}{2}\rfloor + 1$$$ queries.

#include <bits/stdc++.h>
 
#define sz(x) (int)(x.size())
#define pb push_back
 
using namespace std; 
const int N = 2e5 + 12;
 
int n, x, y, a, b;
vector <int> L, g[N];
 
void dfs( int v, int p = 0 )
{
	L.pb(v);
	
	for( auto to : g[v] )
	{
		if( to != p ) dfs(to, v);
	}
}
int ask( int a, int b )
{
	cout << "? " << a << ' ' << b << endl;
	int res; cin >> res; return res;
}
void solve()
{
	cin >> n;
	
	L.clear();
	for( int i = 1; i <= n; i ++ ) g[i].clear();
	
	for( int i = 1; i < n; i ++ )
	{
		cin >> a >> b;
		g[a].pb(b), g[b].pb(a);
	}
	dfs(1, 0);
	
	for( int i = 0; i < sz(L) - 1; i += 2 )
	{
		a = L[i], b = L[i + 1];
		
		if( ask(a, b) == 1 )
		{
			if( ask(a, a) == 1 ) cout << "! " << a << endl;
			else cout << "! " << b << endl;
			return;
		}
	}
	cout << "! " << L.back() << endl;
}
int main()
{
	int t; cin >> t;
	while( t -- ) solve();
}

##

• Great problem
• Normal problem
• Bad problem
• Didn’t solve

First, take all elements modulo $$$2$$$. Now all elements are ones and zeros. It can be noticed that if we remove all $$$a_i$$$ that are equal to zero, then $$$S_v$$$ for the remaining vertices does not change. Remove all $$$a_i$$$ equal to zero whose initial $$$S_v$$$ is odd; if $$$S_v$$$ is zero, then there is no answer. Those vertices $$$v$$$ whose $$$S_v$$$ is even are removed as the ones are removed.

Now we need to deal with the ones. Remove all vertices $$$v$$$ with $$$a_v = 0$$$ from the graph, leaving a forest (a graph of several disconnected trees) of ones. Solve the problem for each new tree of ones. For a tree of ones of size $$$n$$$, there is no answer when $$$n$$$ is even. When $$$n$$$ is even, the number of edges is odd, but each removal deletes one vertex and an even number of edges. Subtracting even numbers from the initial odd number of edges, we will never reach zero edges (i.e., an empty graph). Now we claim that when $$$n$$$ is odd, an answer always exists.

Let us say that for a pair of adjacent vertices $$$(v, u)$$$, vertex $$$v$$$ contributes to $$$u$$$ if after removing $$$u$$$, the component containing vertex $$$v$$$ becomes even-sized. Denote $$$f(v)$$$ as the number of vertices contributing to $$$v$$$. It can be understood that we need to delete a vertex with $$$f(v)=0$$$. The components of all neighbors of such a vertex are odd-sized, and to obtain an odd $$$n$$$, we need it to have an even number of neighbors (so we can delete it from the graph uniquely). Now it is claimed that such a vertex always exists.

It can be noticed that after deleting vertex $$$v$$$, values of $$$f$$$ change only for neighbors of $$$v$$$. For all neighbors $$$u$$$ of vertex $$$v$$$, the value $$$f(u)$$$ decreases by $$$1$$$, because the contribution was from $$$v$$$ to $$$u$$$. We compute all values of $$$f$$$ once, and using BFS we delete vertices with $$$f=0$$$. We also should not forget that some zeros need to be deleted as ones are removed. This solution runs in $$$O(n)$$$ operations.

Let us say that the root of the tree is vertex $$$1$$$. We will write a DP for the problem. Define it as follows:

• $$$dp_v = 0$$$ if vertex $$$v$$$ cannot be deleted.
• $$$dp_v = 1$$$ if to delete vertex $$$v$$$, its parent must necessarily be deleted before $$$v$$$.
• $$$dp_v = 2$$$ if to delete vertex $$$v$$$, vertex $$$v$$$ must necessarily be deleted before its parent.
• $$$dp_v = 3$$$ if for deleting vertex $$$v$$$ it does not matter whether we delete the parent or the vertex first.

If for at least one vertex $$$v$$$, $$$dp_v = 0$$$, then there is no answer. Let $$$p_v$$$ be the parent of vertex $$$v$$$, and let $$$s_v$$$ be the sum of all values $$$a_u$$$ where $$$u$$$ is a child of $$$v$$$ and $$$dp_u$$$ equals $$$1$$$ or $$$3$$$. For $$$dp_v$$$ to be $$$1$$$, at least one of the following conditions must hold:

• The parity of $$$s_v$$$ is not equal to $$$a_v$$$.
• The parity of $$$s_v$$$ equals $$$a_v$$$, but the vertex has a child $$$u$$$ with $$$dp_u = 3$$$ and $$$a_u = 1$$$. That is, we can delete $$$u$$$ before $$$v$$$, thereby changing the parity of $$$s_v$$$.

Add $$$a_{p_v}$$$ to $$$s_v$$$ and check the conditions again for $$$dp_v = 2$$$. If both cases satisfy the conditions, then $$$dp_v = 3$$$, and if none of them does, then $$$dp_v = 0$$$. It remains only to restore the answer from the DP; details can be found in the implementation. The time complexity of the solution is $$$O(n)$$$.

#include <bits/stdc++.h>
#define ent '\n'
#define int long long
 
using namespace std;
const int maxn = 200'012;
const int mod = 1e9 + 7;
 
int cnt[maxn], a[maxn], del[maxn];
int sz[maxn], bad[maxn], used[maxn];
vector<int> g[maxn], e[maxn], g2[maxn];
int n, m;
 
void dfs(int v, int p) {
    sz[v] = 1;
    used[v] = true;
    for(int to : g[v]) {
        if(to == p) {
            continue;
        }
 
        dfs(to, v);
 
        if(sz[to] % 2 == 0) {
            e[to].push_back(v);
            bad[v]++;
        }
        else {
            e[v].push_back(to);
            bad[to]++;
        }
 
        sz[v] += sz[to];
    }
}
 
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] %= 2;
        del[i] = cnt[i] = sz[i] = 0;
        bad[i] = used[i] = 0;
        g[i].clear();
        g2[i].clear();
        e[i].clear();
    }
 
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
 
        cnt[u] += a[v], cnt[v] += a[u];
 
        if(a[u] && a[v]) {
            g[u].push_back(v);
            g[v].push_back(u);
        }
        if( a[u] && !a[v] ) g2[u].push_back(v);
        if( a[v] && !a[u] ) g2[v].push_back(u);
    }
    queue <int> q;
 
    for(int i = 1; i <= n; i++) {
        if(!cnt[i] && !a[i]) {
            cout << "NO\n";
            return;
        }
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] && !used[i]) {
            dfs(i, 0);
            if(sz[i] % 2 == 0) {
                cout << "NO\n";
                return;
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        if(a[i] && !bad[i]) {
            q.push(i);
        }
    }
    cout << "YES\n";
    int zero[n + 5];
    
    for( int i = 1; i <= n; i ++ ){
        zero[i] = 0;
        
        if( !a[i] && cnt[i] % 2 ) cout << i << ' ';
        else if( !a[i] ) zero[i] = 1;
    }
    while(!q.empty()) {
        int v = q.front(); q.pop();
        cout << v << ' ';
        for(int to : g2[v]){
            if(zero[to]) cout << to << ' ', zero[to] = 0;
        }
        for(int to : e[v]) {
            bad[to]--;
            if(bad[to] == 0) q.push(to);
        }
    }
    cout << ent;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
}

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 12;
const int inf = 1e9 + 1;

int n, x, y, a[N], dp[N], cnt[N], par[N];
vector <int> g[N], g2[N]; bool flag, used[N];
pair <int, int> must[N][3]; vector <int> ord;

void dfs( int v, int p = 0 )
{
	int s = 0, ok = 0, id = 0;
	par[v] = p; ord.push_back(v);
	
	for( auto to : g[v] )
	{
		if( to == p ) continue;
		
		dfs(to, v);
		if(!flag) return;
		
		if( dp[to] == 1 || dp[to] == 3 )
		{
			s ^= a[to];
			
			if( dp[to] == 3 && a[to] == 1 )
			{
				if( !ok )
				{
					ok = 1;
					id = to;
				}
			}
			if( dp[to] == 3 && id != to ) dp[to] = 1;
		}
	}
	if( !ok && s == a[v] && (s + a[p]) % 2 == a[v] )
	{
		flag = 0;
		return;
	}
	if( s != a[v] || ok )
	{
		if( s == a[v] ) must[v][1] = {id, 2};
		else if(ok) must[v][1] = {id, 1};
		
		dp[v] = 1;
	}
	s = (s + a[p]) % 2;
	
	if( s != a[v] || ok )
	{
		if( s == a[v] ) must[v][2] = {id, 2};
		else if(ok) must[v][2] = {id, 1};
		
		dp[v] += 2;
	}
}
void dfs2( int v, int tp )
{
	dp[v] = tp, used[v] = 1;
	pair <int, int> p = must[v][tp];
	if( p.first != 0 ) dfs2(p.first, p.second);
}
void solve()
{
	cin >> n;
	flag = 1;
	
	// dp[v] = 1, if p[v] before v
	// dp[v] = 2, if v before p[v]
	
	for( int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		a[i] %= 2;
		
		must[i][1] = must[i][2] = {0, 0};
		dp[i] = cnt[i] = used[i] = 0;
		g[i].clear(), g2[i].clear();
	}
	for( int i = 1; i < n; i ++ )
	{
		cin >> x >> y;
		
		g[x].push_back(y);
		g[y].push_back(x);
	}
	ord.clear();
	dfs(1);
	
	if( !flag )
	{
		cout << "No\n";
		return;
	}
	cout << "Yes\n";
	
	for( auto i : ord )
	{
		if( !used[i] )
		{
			if( dp[i] == 3 ) dfs2(i, 1);
			else dfs2(i, dp[i]);
		}
	}
	for( int v = 2; v <= n; v ++ )
	{
		if( dp[v] == 1 ) cnt[v] ++, g2[par[v]].push_back(v);
		else cnt[par[v]] ++, g2[v].push_back(par[v]);
	}
	queue <int> q;
	
	for( int i = 1; i <= n; i ++ )
	{
		if( cnt[i] == 0 ) q.push(i);
	}
	while( !q.empty() )
	{
		int v = q.front();
		q.pop(); cout << v << ' ';
		
		for( auto to : g2[v] )
		{
			cnt[to] --;
			if( !cnt[to] ) q.push(to);
		}
	}
	cout << '\n';
}
int main()
{
	ios_base::sync_with_stdio(0);
	
	int t; cin >> t;
	while(t --) solve();
}

• Great problem
• Normal problem
• Bad problem
• Didn’t solve