November Lunchtime Editorials

editorial
lrquer
ltime54
shuffl
smrstr
strquer

#1

Hello Guys…

This time I’m not posting any editorial because of an unavoidable reason (not being able to solve any problem complete :frowning: ), 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*[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*[1] = DP[i-1][0], DP*[0] = min(DP[i-1][0],DP[i-1][1])+A*-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]*[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]* + 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 :slight_smile: )

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[2][2] 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. :slight_smile:


#2

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 :slight_smile:


#3

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.


#4

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.


#5

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


#6

@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 :slight_smile:


#7

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


#8

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


#9

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] = A[2] - A[1]
DP[3] = A[3] - A[1]
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*[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*[1] = DP[i-1][0], DP*[0] = min(DP[i-1][0],DP[i-1][1])+A*-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]*[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]* + 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 :slight_smile: )

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[2][2] 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


#10

@arun_001 your solution for SMRSTR was almost correct except if input element becomes zero. Divide by zero can’t be possible hence avoid dividing by input.Here is what I have changed slightly in your code and got A.C:
https://www.codechef.com/viewsolution/16377847


#11

@lunchcook , firstly thank you for the reply, but it is clear that 1 ≤ Xi, Di ≤ 10e9, how “was almost correct except if input element becomes zero. Divide by zero can’t be possible hence avoid dividing by input” is possible?


#12

@vijju123, could you please tell me : Have ratings for November Lunchtime been updated ?


#13

For SMRSTR, you could use a language which supports large integer values (python or Java).


#14

In the solution of the 4th question, I do not understand, how he has defined the dp states.


#15

can anyone please explain the second observation in the @mgch’s answer


#16

Here, im going to explain the second observation in @mgch’s solution.

Take an example, given a set {a,b,c,d} (assume a< b< c< d for sake of simplicity)

Let us assume that a group of 4 leads to optimal solution.

Then the cost of above set will be |b- a| + |c - b| +|d -c|.

But, another possible arrangement is to connect a with b and c with d, creating two groups {a,b} and {c, d}

In this arrangement, cost will be |b-a| + | d-c|

This way, cost of second arrangement is less than cost of first arrangement by |c-b|.

This contradict our assumption that a group of 4 can result in optimal solution.

So, optimal solution contains only groups of 2 and 3 (only 1 group of 3 in case size of given set is odd).

Hope it makes everything clear.


#17

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


#18

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


#19

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


#20

Oh… :slight_smile: missed that…