[Editorial] Newton School December 2021 Contest

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Credits: _deactivated_, dnshgyl21, Sawarnik, Xzirium

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

Hint 1

Hint 2

Solution

D. Anya's queries

Hint

Solution

We can observe that for a fixed $$$a$$$, $$$\text{lcm}(a, a+1, a+2, ... b)$$$ will increase very rapidly as $$$b$$$ increases. In particular, for any $$$a$$$, we can show that $$$\text{lcm}(a, a+1, a+2, ... a+43) < 10^{16}$$$. This is because the product of all primes upto $$$43$$$ is already greater than $$$10^{16}$$$, and for each prime upto $$$43$$$ we know that there is at least one element in $$$[a, a+43]$$$ divisible by that prime implying that the lcm is divisible by that prime as well.

Further, note that for any $$$a$$$, $$$\text{lcm}(a, a+1, a+2) \geq \frac{a(a+1)(a+2)}{2}$$$. Thus, we also have that for $$$b \geq 3\cdot 10^5$$$, $$$\text{lcm}(b-2, b-1, b) \geq 10^{16}$$$. So for all segments with lengths $$$\geq 3$$$, the right endpoint must be smaller than $$$3\cdot 10^5$$$, and for each such endpoint we only need to go through a handful of segments with that endpoint. Thus, we have the following solution:

Iterate through the right endpoints $$$r$$$ from $$$2$$$ to $$$3\cdot 10^5$$$. For each such number, start iterating through the left endpoints $$$l$$$ backwards from $$$r - 1$$$ until $$$\text{lcm}(l, ... r - 1, r)$$$ exceeds $$$10^{16}$$$ (be careful of overflows).
Maintain a global map, counting for each lcm its frequency. This is the map that we will update as we iterate through the segments as explained above. Now, once we are done with a particular endpoint $$$r$$$, we can answer each query with bounds equal to $$$r$$$ there.
We are now left to answer queries with $$$r > 3\cdot 10^5$$$. Clearly, the answer for such a query is the value stored in the map after we are done iterating, along with possibly some number of segments of length $$$2$$$ with that lcm. Thus, we now only need to find out for which $$$a$$$, is $$$\text{lcm}(a, a+1) = x$$$. As $$$\text{lcm}(a, a+1) = a(a+1)$$$, we only need to solve a quadratic equation to find the value of $$$a$$$. If the value of $$$a$$$ is an integer and smaller than $$$r$$$, we can add $$$1$$$ to the value in map. Thus, all queries have been answered in sufficient time.

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.

dnshgyl21's blog