1726A - Mainak and Array Solution - CodeForces

 Problem Link: https://codeforces.com/contest/1726/problem/A

Let's consider an array, for example the first one from the test case,

[1, 3, 9, 11, 5, 7]

As k is any positive number we can choose we can rotate the array any number of times we want. So we have no limit on how many times we rotate. However if we rotate we would have to rotate only in one range. We cannot change the value of l and r later.

Now consider two cases,

Case 1: If we would keep the first value (a_1) fixed, then what should be the value of the last element (a_n)? Of course, the one for which the absolute difference between a1 (1) and that value would be maximum right? In this case, the value should be 11 as |1-11| = 10. What range should we rotate so that we don't miss any value? It should be all the value from a_2 to a_n, isn't it? (In this case 3, 9... 7, if we keep rotating the values there will certainly a time come when 11 will be at the last). 

Case 2: Now, if we keep the last value fixed, similarly the range should be a_1 to a_(n-1). (So we would keep 7 fixed and keep rotating all the values from 1, 3...., 5).

Case 3: Now it may happen that the neither the first value, nor the last value needs to be fixed. Because there may be any other pair for which the difference is maximized. In that case what should be the range? It must be the whole array.(Think why?) Every other pair already satisfies the previous two cases if you observe it.

So, we can create a maximum variable, holding the information for the maximum possible difference. Then for case 1, we would loop through a_2 to a_n and keep updating the maximum with abs(a_1 - a_i)

Then for case2, we would loop through a_1 to a_(n-1) and keep updating the maximum with abs(a_i - a_n)

Then for the third case we can loop through the array and calculate each of the elements reflection in terms of if that element were in the first position using modulo operator (by modding with the length of the array)

Here's the solution snippet from my submission:

  1. void solve() {
  2. ll n;
  3. cin >> n;
  4. ll a[n];
  5. for(ll i=0; i<n; i++) cin >> a[i];
  6.  
  7. ll mx = LONG_MIN;
  8. for(ll i=1; i<n; i++) {
  9. mx = max(mx,a[i]-a[0]);
  10. }
  11.  
  12. for(ll i=0; i<n-1; i++) {
  13. mx = max(mx,a[n-1]-a[i]);
  14. }
  15.  
  16. mx = max(mx, a[n-1]-a[0]);
  17. for(ll i=0; i<n-1; i++) {
  18. mx = max(mx, a[i]-a[i+1]);
  19. }
  20. cout << mx << endl;
  21. }

Comments

Post a Comment