Use binary search on a sequence to find two adjacent segments which differ exactly one element and have different majority color.

Ask for the first $$$n$$$ balls, say color $$$x$$$ appears more. Then binary search some position such that in the balls $$$i, \dots, i + n - 1$$$ the other color appears more, and in $$$i-1, \dots, i+n-2$$$ $$$x$$$ appears more. Note that in the last $$$n$$$ balls the other color must appear more, so at least one such transition point exists. If at $$$i, \dots, i + n - 1$$$ color $$$x$$$ appears more, then at least one transition point must occur between $$$i$$$ and $$$n$$$. If the other color appears more, then at least one much appear between $$$0$$$ and $$$i$$$. So we can find such a position in $$$1 + \log_{2}(100) \approx 8 < 10$$$ operations.

But now we know that - Ball $$$i-1$$$ has color $$$x$$$, ball $$$i+n-1$$$ has the other color - Hence both colors appear an equal number of times in $$$i, \dots, i+n-2$$$ - Hence both colors appear an equal number of times in $$$i+n, \dots, i-2$$$ (where the interval wraps around $$$2n$$$)

Now we can ask for every ball $$$j$$$ either the query with $$$j$$$ and interval $$$i, \dots, i+n-2$$$ or with $$$j$$$ and interval $$$i+n, \dots, i-2$$$. Since the intervals contain the same amount of both colors, the answer will be the color of ball $$$j$$$.

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

int askRow(int s, int n) {
	cout << "?";
	for (int i = s+1; i <= s+n; ++i) cout << ' ' << i;
	cout << endl;

	string res;
	cin >> res;
	return (res == "Red") ? 1 : -1;
}
int askEq(int i, int s, int n) {
	cout << "? " << i+1;
	for (int j = s+1; j < s+n; ++j) {
		if (j > 2*n) cout << ' ' << j - 2*n;
		else cout << ' ' << j;
	}
	cout << endl;

	string res;
	cin >> res;
	return (res == "Red") ? 1 : -1;
}

const int N = 100;
int col[2*N];

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

	int n;
	cin >> n;

	// Ask first N. Shift window right one-by-one until the answer changes.
	// Since last N must have opposite answer, this happens at some point.
	// Binary search where it happens. Note that we don't need to find the first such position.
	// 1 + log2(100) ~ 8 < 10

	int x = askRow(0, n); // Sum of first n has more of x
	int low = 1;
	int high = n;
	while(low != high) {
		int mid = (low + high) >> 1;
		int y = askRow(mid, n);
		if (x != y) high = mid;
		else low = mid + 1;
	}

	// Now askRow(low-1, n) and askRow(low, n) give different answers, hence both colors appear an equal number of times in [low, low+n-2].
	for (int i = 0; i < low; ++i) col[i] = askEq(i, low, n);
	for (int i = low; i < low + n - 1; ++i) col[i] = askEq(i, low + n, n);
	for (int i = low + n - 1; i < 2*n; ++i) col[i] = askEq(i, low, n);

	cout << "! ";
	for (int i = 0; i < 2*n; ++i) {
		if (col[i] == 1) cout << 'R';
		else cout << 'B';
	}
	cout << endl;
}

I think your solution is wrong for "1999"

As much as i could find, the order of combinations matter very less in this question, so for me it was a matter of finding answer to input sets fast and combining them (HINT : FAST EXPONENTIATION)...

We can show that the order or operations we is the same as the optimal if we keep combining the first 2 digits of the number. (I didnt prove this but it seems to work). Let's see how we can find the number of time we need to combine the first 2 digits.

Firstly notice if we were to keep combining with some number (for example 4), we will get a cycle. 4->8->12->3->7->11->2->6->1->5->9->13->4

We can work out the cycles for all these numbers by hand. Then when we see alot of repeated digits we can quickly remove alot of them because they cycle.

I think you just need to be careful with 0 and 9. Since they cycle into them selves.

code: https://atcoder.jp/contests/ddcc2020-qual/submissions/8584626

During one operation, the number of digits decreases by one and the sum of digits stays the same or the number of digits stays the same and the sum of digits decreases by 9. So the number of rounds is something like digitCount - 1 + (digitSum-1)/9.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll M, DC = 0, S = 0;
	cin >> M;
	for(int i = 0; i < M; ++i){
		ll d, c; cin >> d >> c;
		S += d*c; DC += c;
	}
	ll r = DC-1 + (S-1)/9;
	cout << r << endl;
}

I think that might require a bitmask solution, not sure though.

Consider it as a implicit graph problem
In a matrix whenever you find '#' and mark it something starting from 1 then run a dfs in a matrix till you reach the either end of that row or you find '#' in the row and mark them the same number you marked the '#'. So for k '#' you use only k numbers.
So if you have some matrix like
3 3 3
..#
.#.
.#.
then after 3 dfs calls from (1,3),(2,2),(3,1)you get something like this
1 1 1
2 2 2
3 3 3
Now the edge case is
3 3 1
...
...
..#
Now you will get something like
0 0 0
0 0 0
1 1 1
So use the trick that if ans==0 or if you have taken it -1 or some number then you must find the next non-zero number or previous non zero number in the column and you need to do it for every column
Code
https://atcoder.jp/contests/ddcc2020-qual/submissions/8582555

Actually nevermind, i read didnt read the k=# will still try to find cornercase

3 1 1
.
.
#

I think i found the test case

Sorry for delay, sometimes we can't finish editorial translation in time.

For AGC/ARC rounds (including this round) we'll publish English editorials.

Idea for F: Firstly, let $$$ga = \gcd(H, T), gb = \gcd(W, T)$$$. Then, we can partition the grid into $$$ga \times gb$$$ independent parts, and thus from here on we let $$$\gcd(H, T) = \gcd(W, T) = 1$$$ (by appropriate scaling) and raise the answer to the $$$ga \times gb$$$-th power.

The main idea is the consider when a board is invalid. Since $$$\gcd(H, T) = \gcd(W, T) = 1$$$, we have that for each row, we cannot have both R and . (or else by Bezout's Lemma there exist a time they will coincide). Similar result holds for each column.

Suppose our grid only has R or D but not both. Then, it is easy to count the number of valid grids: it's just $$$2^{H} + 2^{W} - 1$$$ (it is easy to see all such grids work).

Suppose our grid has both R and D. Note that if the R and D have coordinates $$$(x_{1}, y_{1})$$$, $$$(x_{2}, y_{2})$$$ respectively, then we cannot have $$$x_{1} + y_{1} \equiv x_{2} + y_{2} \pmod{G}$$$, where $$$G = \gcd(H, W)$$$ (you can prove this by writing out exactly when an R and D will coincide for some time $$$kT$$$). Furthermore, you can prove that if a . exist, then the grid cannot contain both R and D. Hence, for each remainder mod $$$G$$$, we must have at least one of R and D. Also, R and D must both appear. Thus, the number of ways is $$$2^{G} - 2$$$.

Combining the two cases and raising the power by $$$ga \times gb$$$ gives us the answer.

exactly! me too. I think the checker itself will be a solution of the problem

You can use #ifndef LOCAL_DEBUG instead of #ifdef ONLINE_JUDGE and add -DLOCAL_DEBUG option every time when compiling.