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

signed main() { int g, s, a, b; cin >> g >> s >> a >> b;

cout << ((g * a >= s * b) ? "Gold" : "Silver");
return 0;

}

Since $$$i^{th}$$$ and $$${i+k/2}^{th}$$$ character must be same, and also first half of string is equal to last half of string, this implies that the answer is "1" if and only if count of $$$1s$$$ is divisible by 4.

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

signed main() {
	int t;
	cin >> t;
	for(int i=0; i<t; i++) {
		int n;
		cin >> n;
		string s;
		cin >> s;
		int cnt = 0;
		for(int j=0; j<n; j++) {
			if(s[j] == '1') cnt++;
		}
		if(cnt % 4 == 0) cout << 1 << "\n";
		else cout << 0 << "\n";
	}
	return 0;
}

If we change an element, what will be the gcd for the rest of the array?

Suppose we want to replace $$$a_i$$$ by some number $$$x$$$. The GCD of the array in this case will be $$$gcd(a_1, a_2, ... a_{i-1}, x, a_{i+1}, ... a_n)$$$. Looking at this formula, we can see that we should pre-calculate the prefix GCDs and suffix GCDs for the array as such:

Now, the GCD of the array in the above case will be $$$gcd(pre_{i-1}, x, suf_{i+1})$$$. So what should be the optimal choice of $$$x$$$ to maximize this value? Clearly, the GCD will be some divisor of $$$gcd(pre_{i-1}, suf_{i+1})$$$. It will be thus be optimal to choose $$$x$$$ as the largest divisor of $$$gcd(pre_{i-1}, suf_{i+1})$$$ smaller than or equal to $$$r$$$. Thus, we should also pre-calculate the largest divisor of each number from 1 to $$$10^5$$$ smaller than or equal to $$$r$$$, as follows:

for (int i = r; i > 0; i--)
  for (int j = i; j <= N; j += i)
    if (!largest_divisor[j]) largest_divisor[j] = i;

It is now easy to see that the answer will be the maximum of largest_divisor[__gcd(pre[i-1], suf[i+1])] over all valid $$$i$$$, as well as the GCD of the whole array itself (where no operations are done).

Let’s root the tree at any node x and find a dfs traversal. During any traversal, we can find the current path with one end point as x and the other end point as the current point dynamically while iterating over the tree in dfs.

So as we can find all paths this way. We can also push all these paths in a trie dynamically while doing dfs.

Now this problem has been transformed into a very simple problem where given any trie which was already built. In a query, answer the number of paths in the trie lexicographically smaller than the given query, which can be easily found just by iterating over the trie in O(path_length_in_query).

So instead of rooting again after every query, building trie and iterating over the trie. This can be precomputed by trying to root at every vertex one by one and finding answer for all possible paths.

So, if have rooted at any node x. Then, find answers for all the paths in a single run on the trie just by doing a single traversal like dfs.

After all this, we can answer any query in $$$O(1)$$$ using precomputed answer.

Complexity Analysis: $$$O(N*time(trie_build+trie_iterate))$$$

time(trie_build) = $$$O(N*26)$$$ — This is the worst case theoretically for trie, but it will not get achieved mostly as there can be atmost 26 direct children and for any node and all the strings are made from just adding a single new character in some old path.

time(trie_iterate) — $$$O( N )$$$

Overall complexity will be less than $$$O((N^2)*26)$$$.

The Code of testers and setters both ran in approximately 1.5 sec without any big optimizations.

Will be added soon.

First solve the case where A = B.

Add a new black vertex and connect it with both grey vertex.

Break the chain at different positions to get different trees.

Using the absolute value of the difference between the prefix sums of subtree size.

First lets solve the case where there is only one black node initially. Root the tree at this node. Denote by Dp[v], the number of ways to colour the nodes in the subtree of v, given that v is coloured black currently, We can see that it becomes

where U is a child of v. After some manipulations we can see that

To solve the original problem, where we have got two black nodes, lets add a new node and add a edge from it to both the grey nodes. So we have got a connected graph with one cycle. If we consider this new node to have the colour black, we can see that the problem is reduced to the case where we had only on grey node, but instead of tree, we now have got a graph. Lets consider all the nodes on this cycle, when we are doing these operations at some instance exactly one of these nodes would be coloured grey and all others on the cycle would be black. Lets call this node to be the node $$$v_{i}$$$, Since this node would have got the grey colours from two differen side, what we can do is to remove on the edges on it in the cycle, and the solve the problem on the tree. So our problem can be solved the following way.

1. Initialize $$$Ans = 0$$$.
2. For each edge in cycle, delete it, compute the possible ways for this new tree, and add this to ans.

Since each way has been counted twice, so we need to divide $$$Ans$$$ by 2.

Lets now see how we can implement the above process.

We know that the answer for a tree is just

, and after deletion of edges, the nodes which are not on the cycle still have the same subtree size, so we can just precompute that part.

So our count becomes

, where size[k] is the size of the kth node on the cycle after deleting some edge.

To to this first just cut one of the edge connecting the newly added node to the black nodes, and compute the subtree sizes for all nodes on the cycle for this tree.

Now define

, which is the prefix sum of the sizes of the first $i$ nodes on the cycle, we can see that if we cut the $$$i^{th}$$$ edge, the denominator becomes

.

To compute this we can first ignore the abs size and then since pref is monotonically increasing the sign can be simply achieved by finding the count of negative terms in the product. So we need to compute

for all $$$i$$$.

If we replace $$$Pref[i]$$$ by $$$x$$$ we can see that we get the following polynomial, which needs to be evaluated at $$$k$$$ points.

for all $$$i$$$.

This is equal to

evaluated at Pref[i] for all $$$i$$$.

This problem can be solved by multipoint evaluation.