You can simply turn all characters to lowercase (to make a case insensitive comparison), then you should check the 3 conditions: A is greater than B, B is greater than A, A equals B. Time and space complexity is O(L) where L is the max length of the strings.

Here the main observation is that in any square of length 2N there are exactly 4 "bad" cells: if you chose one of these bad cells then you will not be able to divide the square. We're talking about the 4 "center" cells.

Example with 2N = 4

So, given 2N, X, Y, you should check that point (X,Y) is not equal to one of these 4 points: (N,N), (N,N+1), (N+1,N), (N+1,N+1).

Time and space complexity is O(1).

We have to chose the biggest (a₁ + a₂ + ... + a_n) possible, but less than or equal to Y. We will choose Y, because this is the best way to maximize the sum of squares.

Now, we understood we have to split Y in N little numbers. We are free to choose the numbers that compose this sum.

The key observation here is that if we want to maximize (a₁² + a₂² + ... + a_n²) then we should maximize ONE number inside this list. Why? Well if you have two numbers A, B. If A²+B² > (A+B)² then we're wrong! because it's not good to maximize one term, but it's better to split this term and then take the square of each "piece". But this is always false! At least for positive A and B... Take a look at this plot.

So, how do we maximize one term? If we have N places for N numbers, and the sum must be equal to Y, then we start filling the first N-1 places with ones (1) and, in the last place, we write Y-(N-1), that is: the remaining part after summing N-1 times "1".

Example: N=5, X=15, Y=15

A solution is {4, 4, 1, 1, 2}, in fact its sum (12) is less than Y and the sum of squares (38) is greater than X.

Now let's try constructing our "greedy" solution... We fill with ones the first 4 places, and then we insert Y-(N-1). The result is {1,1,1,1,11}. Its sum (15) is ok, and its square sum (11x11 + 4 = 125) is the absolutely best we can achieve (and in this case it is okay for given X).

The main idea is to iterate over the list of numbers while keeping an array "pos", with pos[x]=y meaning that the last time we have seen divisor x we were on the y-th iteration. For each iteration (so for each query A, B), we search all divisors of the given number A, but we pay attention (using the "pos" array) to not count a divisor if we have seen less than B iterations ago. Now it's simple to code an algorithm that initializes to "-1" the array "pos" (alternatively, to a very low value, so the condition fails and you can count that divisor) and then iterates over the query list, updating pos[x] with the current iteration index each time we encounter divisor x. Time complexity is O(N * X) where N is the number of queries and X is the max value of A. This is about 10¹⁰, too slow! We should do an optimization to have the algorithm running in O(N*sqrt(X)).

We can check for divisors in a few ways, the simpler is O(A) where we iterate over all possible divisors of A. We can do better by thinking this way: if D is a divisor of A, then A/D is also a divisor of A. So we iterate over all possible divisors D less than or equal to sqrt(A), and then we consider 2 divisors instead of 1 (D and A/D).

Time complexity O(N*sqrt(X)), space O(N)