Credits: _deactivated_, dnshgyl21, Sawarnik, Xzirium
A. AC or not?
B. ABBA
We solve this problem in cases:
Firstly, we take the case where all the characters of the string are either ‘a’ or ‘b’. For this do not require to perform any operations as every character of the string is equal.
Secondly, we take the case where ‘a’ and ‘b’ both exist at least once. Here we can either make all the characters ‘a’ or ‘b’. We try to calculate the minimum operations required to make all characters ‘a’. We also observe that there exists a character ‘b’ with adjacent character ‘a’ since ‘a’ and ‘b’ both exist at least once. We convert this ‘b’ to ‘a’ with an operation. Again if there exist ‘b’ then by similar argument we can perform this operation. We repeatedly perform this operation until all the characters become ‘a’. The number of operation would be number of ‘b’ characters. Similarly, in order to make all the characters of the string ‘b’ the number of operation would be number of ‘a’ characters. Therefore the final answer would be the minimum of these two.
C. Anya's triplets
D. Anya's queries
E. XOR
To solve this problem we need few observations, Observation # 1: Value(A,B) = Value(Root,A) Xor Value (Root,B) We can write any value of any path in the following way. Observation #2: If we solve the problem for any single bit of binary format then for existence of unique value every bit should give a unique answer. On the other hand if any bit will give invalid answer then overall answer will not exist. If answer is valid for all bits and for atleast one bit multiple answer exists then overall answer will be multiple. So problem can be modified in this way. Let’s solve for any single bit.
Assume Ans(A) = Value(Root,A) for any single bit. Where Ans(Root)=0, we have just taken it in this way to reduce confusion while solving modified problem. For any query of path if Value(A,B)=0 then Ans(A) should be equal to Ans(B) again mentioning we are solving it for any single bit. And if in case Value(A,B)=1 then Ans(A) should be different from Ans(B).
So above problem can be seen as simple 2-sat problem. For more details about 2-sat: https://cp-algorithms.com/graph/2SAT.html After solving for each bit we can see if any answer exists or not and if exists then it is unique or not. If unique answer exists we can find exact answer by using 2 sat. Complexity = O((n+m)logn) As we are solving for each bit individually that’s why logn factor came. And for each bit while doing 2 sat we are iterating over all edges and nodes that’s why O(n+m) factor came.
F. Lets Count
Lets first begin by solving an easier problem, where the constraint on h and w were upto 20.
In this case we can proceed via inclusion and exclusion. For this define R constraint each corresponding to the given rectangle, which indicates that the min inside this given rectangle is exactly equal to the given value. Like in inclusion exclusion, we can define the violation for a given rectangle to be that the minimum is strictly greater than the given v.
Now if we decide which of the rectangles are causing violation, like in the case of inclusion exclusion, we can go though all the rectangle and all the position and grid, and update the value to be the max value over all possible rectangles, and then simple take the product of values across all the grid cells.
Now looping through all subsets of violation, our answer simply becomes
Ans = Summation over subsets of violation( No of ways considering these are violated)
Now in the general case where h and w are large, we can see that we can simply compress the coordinate so that the size of the grid becomes small, and then we can process as above.
