# November Lunchtime Editorials

Hello Guys…

This time I’m not posting any editorial because of an unavoidable reason (not being able to solve any problem complete ), but i still invite you all to share your approach for any of the four problems.

Even then, some of the users have shared their approaches for various problems, which are mentioned below:

SMRSTR

This problem has been discussed at here by @vipin_bhardwaj

SHUFFL

This problem has been discussed here by @aayushkapadia

L-R Queries using sqrt decomposition by @avi224

Break the array into blocks of size \sqrt{N} and then use a map containing frequencies of numbers in each block. For update, remove A[l] from the block containing index l( i.e. l/block\_size) by decreasing its frequency and then add y to it.

The key to solving the problem is to notice that we have to minimize the quadratic expression (x-A[l])*(x-A[r]) such that x=A[m] and l\le m \le r. Note that the global minimum occurs at x_0=0.5*(A[l]+A[r]). We have to find this A[m] nearest to x_0. This can be done using binary search (lower_bound() function in c++) on the frequency maps.

For query, just iterate from l onwards and calculate normally until you find the start of a block. Iterate through every block as long as index r is outside the block, and find the nearest A[m]. After the last block, calculate normally until index r is reached.

The preprocessing part takes O(N*log(N)) and complexity is O(\sqrt(N)*log(N)) per query.

Refer to solution here

STRQUER

All credits to @mgch, the setter of this problem. (I can call this one as Official Editorial) (Copied from answers)

Hi, let me explain the 4th problem. let’s make a couple observations:

1.If we have two connected segments that have a common part [a..b] [x..y], we can create two segments that have no common part with connections between their first and second ends respectively.

2.It gives us next idea(let’s sort our set, and divide it into connected groups), but if the size of a connected group \ge 4 we can split into two groups of sizes [group/2] and group-[group/2], the answer will be smaller, and every number will be connected.

3.Let we have order of set A[1..N], DP[1..i] - the minimal cost to connect prefix A[1…i],

DP$2 = A2 - A1$

DP$3 = A3 - A1$

DP[x] = min(DP[x - 3] + A[x] - A[x - 2], DP[x - 2] + A[x] - A[x - 1]),

we checking where to connect x \implies to x-1, or to x-2.

Let’s rewrite that DP, DP[i][j] denotes connection of the prefix 1..i, j=0 denotes that i is connected to 1..i-1, j=1 denotes that i should be connected to i+1.

DP[i] = DP[i-1], DP[i] = min(DP[i-1],DP[i-1])+A[i]-A[i-1], for i \ge 3.

But how to maintain add/erase queries? Let’s make one more observation we can keep DP for the segment l..r in a similar way:

DP[l..r][i][j] (r-l\ge1) denotes minimal value to connect everything in the segment l..r, if i=1, l should be connected to l-1, otherwise it’s connected to the segment l..r.

If j=1, r = should be connected to r+1, otherwise connected to the segment l..r.

For r-l==1 and r-l==2 better to recalculate DP with hands.

For r-l \ge 3, we can split segment into to l..m, and m+1..r, and recalculate DP[l..r][x][y] as min(DP[l..m][x][i] + DP[m+1..r][j][y] + (1 - i) * (1 - j) * (A[m + 1] - A[m])).

Only in one case we don’t need to take A[m+1]-A[m], if A[m] is connected to l..m and A[m+1] is connected to m+1..r. We need to add some data structure for the solution, we can use cartesian tree/splay tree, but it’s very painful to write that, (I did it, I know what I’m saying about )

Let’s use implicit segment tree(also, we can read all queries, compress the values and use normal segment tree) and for each node to save (min and max on the segment in the segment tree, dp and other things), after that we can combine two segments into one, by operations as described above.

We have a solution with complexity O(Q log N) but with huge constant around (~log N). My solution with cartesian is very hard to understand, you can write yours, maybe my debugging solution will help understand what’s going on: https://pastebin.com/PuFTvuNy

And i hope you guys would like to share your approach as always. 7 Likes

LRQUER(Prerequisite: Square-root decompositon, binary search, STL map)

I solved LRQUER using square-root decomposition. Break the array into blocks of size \sqrt{N} and then use a map containing frequencies of numbers in each block. For update, remove A[l] from the block containing index l( i.e. l/block\_size) by decreasing its frequency and then add y to it.

The key to solving the problem is to notice that we have to minimize the quadratic expression (x-A[l])*(x-A[r]) such that x=A[m] and l\le m \le r. Note that the global minimum occurs at x_0=0.5*(A[l]+A[r]). We have to find this A[m] nearest to x_0. This can be done using binary search (lower_bound() function in c++) on the frequency maps.

For query, just iterate from l onwards and calculate normally until you find the start of a block. Iterate through every block as long as index r is outside the block, and find the nearest A[m]. After the last block, calculate normally until index r is reached.

The preprocessing part takes O(N*log(N)) and complexity is O(\sqrt(N)*log(N)) per query.

My solution

Feel free to ask in case of any doubts 4 Likes

Mate, shouldn’t the expression be (x-A[l])*(A[r]-x)??

I have shared my approach for SHUFFLE here : https://discuss.codechef.com/questions/118543/nov-lunchtime-unofficial-editorial-shuffl

1 Like

Ya, we had to maximise that. So, I took the negative and minimized it. It was a bit clearer.

Oh… missed that…

I’ve fixed it During contest, I first thought of this solution only. But I thought time complexity will be too much. So as your time complexity is O(TQsqrt(N)log(N)) and let T=2 and N=Q=1e5. So that summation is less than 2e5. Then 2 X 1e5*sqrt(1e5)*log(1e5) comes out to be roughly 1e9. I thought that 1e9 will not work in 4 sec. Nice to see it worked. I coded segment tree during contest to remove sqrt factor and place logN factor. So my solution is O(QNlogNlogN). My solution for segment tree : https://www.codechef.com/viewsolution/16370436

1 Like

Here is my LRQUER solution.

(A_M-A_L)*(A_R-A_M) = (A_R+A_L)*A_M-A_M^2-A_L*A_R. The last term is constant, so it doesn’t matter. You are looking for maximum of (A_R+A_L)*A_M-A_M^2 thus minimum of A_M^2-(A_R+A_L)*A_M. You can notice, that A_M^2-(A_R+A_L)*A_M = (A_M-\frac{A_R+A_L}{2})^2-(\frac{A_R+A_L}{2})^2. The second term is constant, so it doesn’t matter. Thus you are looking for minimum of (A_M-\frac{A_R+A_L}{2})^2 which is the same as minimum of \left|A_M-\frac{A_R+A_L}{2}\right|, so you need to find the element with minimum absolute difference from \frac{A_R+A_L}{2}.

In a node store all the array numbers in a multiset, which are below the node.

This segment tree has N*\log{N} space complexity, which fits in ML for N \leq 10^5. Building the segment tree can be done as usually, you have to merge the two children’s sets in a node.

When updating, you can erase the old value from the set, and insert the new one. It takes O(\log{N}) to update a node, and you have to update O(\log{N}) nodes, so overall updating is O(\log^2{N}).

When querying, you can go through the O(\log{N}) nodes which contains the values of the segment. At each node, you can do a lower_bound on the set for \frac{A_L+A_R}{2}, and thus check the elements closest to it. It takes O(\log{N}), so overall query is O(\log^2{N}).

This results in O(Q\log^2{N}) time complexity.

8 Likes

Can you explain how the frequency map is constructed?

Why is this solution failing in first subtask even though I used long where it is needed. After that I used long for all the variables where they won’t even overflow as they were given in constraint as 1<=Ai,
Y<=10e9. The same solution with every variable’s data type set as long even where it is not needed is passing here. Please explain.

Replied on your post. Data types int vs long.

1 Like

How do we solve the 3rd and the fourth question?

that multiset idea was really cool i have done the same but used sqrt decomposition for handing that(using vectors) but this was really awesome !

thanks for sharing this @skpro19, for the 3rd problem SHUFFL you just have to apply the operations in reverse. I’ll explain this straightforward solution by @heart_blue: 16365417. Consider 0-based indexing, so what the problem says odd index will be even index now and vice versa.

In the end the array size is 2, and the two elements are at indices 0 and 1. We want to trace back where there elements were in the previous array state, and repeat that M/2-1 times.
Consider the general case. Let current array size be 2i, and some index we want to track back be a. Then to do reverse of the merge, we split the array into left and right halves. If a \ge i, it means it lies in the right half, and we adjust it to a-i, otherwise we leave it as is. Now this half array of size i was obtained after deleting an element, so before deletion its size was i+1. Which means the deleted element was at \lfloor(i+1)\ x/y\rfloor. So if a \ge this deleted index, a was originally a+1. Next we have to do the reverse of the even-odd split. Notice that any even index e becomes e/2 and any odd index o becomes (o-1)/2. We are doing the reverse, so if a is now in the left half that means it came from an even index and should be updated to 2a, and if in the right half it should become 2a+1.

Hopefully the explanation is clear. If not, working out a few steps on paper helps. If that too fails, feel free to ask below 1 Like

@ramini For each block, we use a map maintaining the frequency of all (distinct) elements in that block.

we don’t have multiset in java any suggestion for this case

Can any one help me with the problem SMRSTR, I’m getting either 75 points or 25 points, I could not make it to 100… Here is the link to my solution link to my solution

Can anyone tell me why my solution for problem LRQUER is giving wrong answer on subtask #2 but correct answer on subtasks #1 and #3. https://www.codechef.com/viewsolution/16377252