From a grid of size n * m, if we remove an intersection point, then the grid after removing the sticks passing through it, will of size n - 1, m - 1.
Notice when the grid consists of a single horizontal stick and m vertical sticks, If we pick any intersection point, then the updated grid will be only made of vertical sticks. You can see that there is no intersection point in the grid now.
ans(n, m) = ans(n - 1, m - 1) ^ 1.
ans(1, * ) = 1
ans( * , 1) = 1
So we can notice that answer will depend on the parity of minimum(m, n).
You can prove it using the previous equations. You can also check this by seeing the pattern.
So finally if min(n, m) is odd, then Akshat will win. Otherwise Malvika will win.
You can also observe that "players will play optimally" is useless in this case.
Complexity : O(1)
Note that if from a given sorted array, if reverse a segment, then the remaining array will be arranged in following way. First increasing sequence, then decreasing, then again increasing.
You can find the first position where the sequences start decreasing from the beginning. Call it L.
You can find the first position where the sequences start increasing from the end. Call it R.
Now we just need to reverse the segment between a[L] to a[R].
Here is outline of my solution which is easy to implement. First I map larger numbers to numbers strictly in the range 1, n.
As all the numbers are distinct, no two numbers in the mapping will be equal too.
Let us define L to be smallest index such that A[i]! = i.
Let us also define R to be largest index such that A[i]! = i.
Note that if there is no such L and R, it means that array is sorted already. So answer will be "yes", we can simply reverse any of the 1 length consecutive segment.
Otherwise we will simply reverse the array from [L, R]. After the reversal, we will check whether the array is sorted or not.
Let x 1 be number of wins of first team in the first k games.
Let x 2 be number of wins of second team in the first k games.
Let x 3 be number of wins of third team in the first k games.
Note that x 1 + x 2 + x 3 = k ---(1)
|x 1 - x 2| = d 1. — (a)
|x 2 - x 3| = d 2. — (b)
Note that |x| can be x and -x depending on the sign of x.
Case 1: Assume that x 1 > x 2 and x 2 > x 3.
x 1 - x 2 = d 1 ---(2)
x 2 - x 3 = d 2 ---(3)
Adding 1 and 2, we get
2x 1 + x 3 = d 1 + k --(4)
Adding 2 and 3, we get
x 1 - x 3 = d 1 + d 2 ---(5).
Now solve (4) and (5), we will get values of x 1 and x 3. By those values, compute value of x 2. Now we should check the constraints that x 1 ≥ x 2 and x 2 ≥ 3.
Now comes the most important part. Number of wins at the end of each team should be n / 3. So if n is not divisible by 3, then our answer will be definitely "no".
Note that if all of the x 1, x 2, x 3 are ≤ n / 3, then we can have the remaining matches in such a way that final numbers of wins of each team should be equal.
Now you have to take 4 such cases. Implementing such cases in 4 if-else statements could incur errors in implementation. You can check my code to understand a simple way to implement it.
I will explain idea of my code briefly, basically equation (a) and (b) can be opened with either positive or negative sign due to modulus.
So if our sign is negative we will change d 1 to be - d 1. So if we solve a single equation and replace d 1 by - d 1, we can get solution for the second case.
All the cases can be dealt in such way. Please see my code for more details.
Complexity: O(1) per test case.
Merging Step: We have to convert string like "aaaabbbaabaaa" into "ababa".
A substring made of the string will be a "good" palindrome if their starting and ending characters are same. If the starting and ending characters are same, then the middle characters after merging will be alternating between 'a' and 'b'. eg. "abaa" is not a palindrome, but it is a good palindrome. After merging step it becomes "aba". Note that in the string left after merging, the consecutive characters will alternate between 'a' and 'b'.
So if we are currently at the i th character, then we can have to simply check how many positions we have encountered upto now having the same character as that of i th. For counting even and odd separately, we can make count of a's and b's at even and odd positions.
So if we are at i th position, for counting even good palindromes, you just need to add count of number of characters a's at odd position. For counting odd good palindromes, you just need to add count of number of characters a's at even position.
Complexity: O(n) where n is length of string s.
Note that you can also consult following comment for alternate editorial.
The number of ways to choose N items out of R groups where each item in a group is identical is equal to the number of integral solutions to x 1 + x 2 + x 3...x R = N, where 0 ≤ x i ≤ L i, where L i is the number of items in i th group. Number of integral solutions are coefficient of x N in [Product of (1 + x + x * x + ...x L i) over all $i$].
You need to find coefficient of x s in (1 + x + x 2 + x 3 + + ..x f 1) * * * (1 + x + x 2 + x 3 + + ..x f n).
Using sum of Geometric progression we can say that (1 + x + x 2 + x 3 + + ..x f 1) = (1 - x (f 1 + 1)) / (1 - x).
Substituting in the expression, we get (1 - x (f 1 + 1)) / (1 - x) * * * (1 - x (f n + 1)) / (1 - x).
= (1 - x (f 1 + 1)) * .. * (1 - x (f n + 1)) * (1 - x)( - n).
Now we can find x s in (1 - x) - n easily. It is .
You can have a look at following link. to understand it better.
So now as s is large, we can not afford to iterate over s.
But n is small, we notice that (1 - x (f 1 + 1)) * .. * (1 - x (f n + 1)) can have at most 2 n terms.
So we will simply find all those terms, they can be very easily computed by maintaining a vector<pair<int, int> > containing pairs of coefficients and their corresponding powers. You can write a recursive function for doing this.
How to find % p. As n + s - 1 is large and s is very small. You can use lucas's theorem. If you understand lucas's theorem, you can note that we simply have to compute .
Complexity: O(n * 2 n).
Another solution based on inclusion exclusion principle.