Can Someone Share their approach for August Lunchtime problem XTGR for Second subtask (30 points) and Original Contraints.
First suppose we have only a single array and we have to solve for the same problem. So, what we can do is reduce all the numbers of the array to arr[i]%x and now the answer is either the current state (i.e. arr[n] - arr1 assuming that array is sorted) or the answer is (arr[i+1] - arr[i]). Why? : suppose the current state is not a stable one and we can further do better and it means that we can subtract ‘x’ from some arr[i]. Now, note that subtracting x from any index will lead to a negative number (as we have all arr[i] < x by modulo we have taken above) and so,that will become the new smallest number and now we want to find the smallest greatest number possible. For this what we can do is subtract x from all the indexes ‘> i’ and by that we are guaranteed that the greatest number is the arr[i-1] as all the greater number are now smaller thatn this (note that any of the greater number will not become the smallest number as we have subtracted x from ‘i’ also and (arr[i] <= arr[j] ) for all (j > i) so, arr[i] - x <= arr[j] - x.). so, it follows that in that case our optimal answer is (arr[i] - arr[i-1]).
We are done. What we can do is iterate over all the indices and find (arr[i-1] - arr[i]+x) and the minimum of that with (arr[n] - arr1) is our optimal answer.
Now, we look at two arrays. For that the first thing is any number of steps can be given as (integral multiple of gcd(n, m) + x). First, we calculate the steps to make all the array elements to it’s corresponding modulo x. And suppose it takes tt and ts steps for the array s and t respectively. Now, it may happen that we cannot satisfy both array simultaneously in same number of steps and the number of steps needed more can be given by tt%gcd and ts%gcd for both the array respectively. And as we know that either the current state is the optimal one (arr[n] - arr1) or one of the (arr[i] - arr[i-1]). And also that each of these steps we need i steps more only (try to prove it). now, we can iterate over the first array and find the minimum and iterating over any of the array we are sure that we can get the minimum answer of the first array for all values of tt in range [0, gcd) as N and M both are multiple of gcd only. Now, we are done. We can now iterate over the second array and get the minimum of that array for all values of [0, gcd) and atlast sum them all and find the minuimum over that entire range i.e. in [0, gcd).
I couldn’t solve this question at contest time but I get it from @ace002 's solution. So, all the credit goes to him.
Sorry for my poor english.
1 Like
I don’t know the exact method for 100 points but for passing the second subtask (50 points), I used a clean little trick although I don’t know if it is indeed the legit way of passing the subtask as the editorials are not out yet.
First observe that we are required to calculate the difference between the max and min element of the arrays. To do so we can only deduct x from an element from the two arrays S and T. Here, it is worth noting that any operation made on any element other than the max element in any array(S and T) is useless as it does not minimize the difference between the max and min element. Hence the process goes like this : in an iteration, you find the max element in S and T, and deduct x from both of them, find the min element and find the value of the expression (max_s + max_t) - (min_s + min_t), in the next iteration, again find the max element in S and T, and again deduct x from both and calculate the expression and so on. Calculating the max or min value in the array takes O(N) in each iteration. Hence use a sorted mutable data structure like priority_queue or multiset to get the max and min value in O(1) time in each iteration. I personally used priority_queue over multiset which I’ll explain later why, but many people passed with multiset too, so you can use that too to obtain 50 pts.
Now the crucial part, suppose you do Z iterations following the algorithm above, you need to maintain the min value of the expression obtained among all the Z iterations, which is the final answer. Now what should be the value of Z actually be ? The lesser it is, the less chances are of us getting the correct answer as we are considering less scenarios, the more the value of Z the better. But if the value of Z becomes too high, it will give TLE. Here using priority_queue over multiset gives you an edge as you can take a higher value of Z as priority_queue is much faster than multiset.
After many submissions, increasing and decreasing the value of Z in each submission( a binary search kind of approach :P), I finally found that when Z is around 10^6 , it passes second subtask easily but gives WA on 3rd subtask.
Hope you liked my approach, here is my solution link for better understanding:
2 Likes
“For that the first observation is we can move only at steps which is an integral multiple of gcd(n,m) (call it gcd)”
Can you explain this in more detail?
sorry for that. You can have a look at the edited answer.
I passed this problem in the contest. The main idea of this problem is Bézout’s identity.
this is a link about Bézout’s identity:https://en.wikipedia.org/wiki/Bézout’s_identity
We can get the total number of steps for each element ai of the a array to become ai%x, which is recorded as step1.
The total number of steps in which each element bi of the b array becomes bi%x is recorded as step2,
then we can Easily know the max-min in the a array of step1+k1*n+t1 steps. Similarly, you can also know the max-min in the b array of step2+k2*m+t2.
so step1+k1*n+t1 = step2+k2*m+t2
k1*n+k2*m=(t2+step2)-(t1+step1).
Then according to Bézout’s identity. (t2+step2) % gcd(n,m) = (t1+step1) % gcd(n,m), so we can preprocess the max-min value of a array operation (t1+step1) % gcd(n,m) times, the b array is the same.
So this problem is easy to solve.
And this is my solution: https://www.codechef.com/viewsolution/19871785
2 Likes
What does k1n, t1 and k2n, t2 represents ?
Thanks… for your solution
Why can’t you put tags in your editorial?
I invented the task and I didn’t know that main idea is Bézout’s identity 
I tried to implement the solution of @ace002 in JAVA, but I can’t make it pass. Two last tests always fail. Any ideas?
My failing solution in java:
https://www.codechef.com/viewsolution/19931733