fork download
copy 
  1. /*
  2.     Problem: Minimum Maximum Request Transfer Latency
  3.     Company Tag: Media.net OA
  4.  
  5.     Problem Statement:
  6.         We are given two arrays:
  7.             requests[i] = number of requests currently present on server i
  8.             max_req[i]  = maximum number of requests server i can finally handle
  9.  
  10.         We can move requests from one server to another.
  11.  
  12.         Moving one request from server i to server j has latency:
  13.             abs(i - j)
  14.  
  15.         After redistribution:
  16.             final_requests[i] <= max_req[i]
  17.  
  18.         Our task is to minimize the maximum latency among all moved requests.
  19.  
  20.         If total requests are greater than total capacity, return -1.
  21.  
  22.     Constraints:
  23.         1 <= n <= 100000
  24.         0 <= requests[i] <= 1000000000
  25.         0 <= max_req[i] <= 1000000000
  26.  
  27.     Brute Force:
  28.         Try all possible ways of moving requests.
  29.  
  30.     Why Brute Force Fails:
  31.         requests[i] can be very large.
  32.         We cannot simulate every single request movement.
  33.  
  34.     Optimized Idea:
  35.         I binary search the answer.
  36.  
  37.         For a fixed distance d:
  38.             Extra requests from server i can only move to servers in range:
  39.                 [i - d, i + d]
  40.  
  41.         Then I greedily place extra requests into available free capacity.
  42.  
  43.     Explanation Block:
  44.         First, I check if total requests <= total capacity.
  45.  
  46.         Then I store all servers which have free capacity.
  47.  
  48.         For a fixed d:
  49.             I process surplus servers from left to right.
  50.             For each surplus server, I move its extra requests to the nearest
  51.             possible free-capacity server within distance d.
  52.  
  53.         If all extra requests are placed, d is valid.
  54.         Then I try smaller d using binary search.
  55.  
  56.     Dry Run:
  57.         requests = [1, 3, 2, 4]
  58.         max_req  = [2, 1, 5, 3]
  59.  
  60.         Server 1 has 2 extra requests.
  61.         Server 3 has 1 extra request.
  62.         Server 2 has free capacity 3.
  63.  
  64.         With d = 1:
  65.             Move 2 requests from server 1 to server 2.
  66.             Move 1 request from server 3 to server 2.
  67.  
  68.         Answer = 1
  69.  
  70.     Time Complexity:
  71.         O(n log n)
  72.  
  73.     Space Complexity:
  74.         O(n)
  75. */
  76.  
  77. #include <bits/stdc++.h>
  78. using namespace std;
  79.  
  80. using ll = long long;
  81.  
  82. int minimumMaximumLatency(vector<ll>& requests, vector<ll>& max_req) {
  83.     int n = requests.size();
  84.  
  85.     ll totalRequests = 0;
  86.     ll totalCapacity = 0;
  87.  
  88.     // First I check whether redistribution is possible.
  89.     for (int i = 0; i < n; i++) {
  90.         totalRequests += requests[i];
  91.         totalCapacity += max_req[i];
  92.     }
  93.  
  94.     if (totalRequests > totalCapacity) {
  95.         return -1;
  96.     }
  97.  
  98.     vector<int> freePos;
  99.     vector<ll> freeCap;
  100.  
  101.     // Store only servers that have free capacity.
  102.     for (int i = 0; i < n; i++) {
  103.         if (max_req[i] > requests[i]) {
  104.             freePos.push_back(i);
  105.             freeCap.push_back(max_req[i] - requests[i]);
  106.         }
  107.     }
  108.  
  109.     auto possible = [&](int d) -> bool {
  110.         vector<ll> remaining = freeCap;
  111.  
  112.         // ptr points to current free-capacity server.
  113.         int ptr = 0;
  114.  
  115.         for (int i = 0; i < n; i++) {
  116.             // Extra requests that must be moved out from server i.
  117.             ll extra = max(0LL, requests[i] - max_req[i]);
  118.  
  119.             while (extra > 0) {
  120.                 // If a free server is too far left,
  121.                 // current and future surplus servers cannot use it.
  122.                 while (ptr < (int)freePos.size() && freePos[ptr] < i - d) {
  123.                     ptr++;
  124.                 }
  125.  
  126.                 // If no free server exists, or nearest free server is too far right,
  127.                 // then distance d is not enough.
  128.                 if (ptr == (int)freePos.size() || freePos[ptr] > i + d) {
  129.                     return false;
  130.                 }
  131.  
  132.                 // Move as many requests as possible to this server.
  133.                 ll take = min(extra, remaining[ptr]);
  134.  
  135.                 extra -= take;
  136.                 remaining[ptr] -= take;
  137.  
  138.                 // If this free server becomes full, move to the next one.
  139.                 if (remaining[ptr] == 0) {
  140.                     ptr++;
  141.                 }
  142.             }
  143.         }
  144.  
  145.         return true;
  146.     };
  147.  
  148.     int low = 0;
  149.     int high = n - 1;
  150.     int ans = n - 1;
  151.  
  152.     // Binary search the minimum possible maximum latency.
  153.     while (low <= high) {
  154.         int mid = low + (high - low) / 2;
  155.  
  156.         if (possible(mid)) {
  157.             ans = mid;
  158.             high = mid - 1;
  159.         } else {
  160.             low = mid + 1;
  161.         }
  162.     }
  163.  
  164.     return ans;
  165. }
  166.  
  167. int main() {
  168.     vector<ll> requests = {1, 3, 2, 4};
  169.     vector<ll> max_req = {2, 1, 5, 3};
  170.  
  171.     cout << minimumMaximumLatency(requests, max_req) << endl;
  172.  
  173.     return 0;
  174. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/ho6Avj
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!