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.
How do we solve the 3rd and the fourth question?
@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
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. CodeChef: Practical coding for everyone
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[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][1] = DP[i-1][0], DP[i][0] = min(DP[i-1][0],DP[i-1][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[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: //Let we have sorted array x, and want to recalculate DP#include <bits/stdc++. - Pastebin.com
4 Likes
@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
@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?
For SMRSTR, you could use a language which supports large integer values (python or Java).
In the solution of the 4th question, I do not understand, how he has defined the dp states.
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.
1 Like
Mate, shouldn’t the expression be (x-A[l])*(A[r]-x)??
I have shared my approach for SHUFFLE here : NOV Lunchtime Unofficial Editorial (SHUFFL) - general - CodeChef Discuss
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 think your link is broken. Can you please fix it.
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 : CodeChef: Practical coding for everyone
1 Like