fork download
copy 
  1. /*
  2. PROBLEM: Minimize Maximum Difference with Card Flips
  3.  
  4. Given:
  5. - N cards, each card i has two values: A[i] (front) and B[i] (back)
  6. - You can flip at most M cards (change from front to back)
  7. - Initially all cards show their front value A[i]
  8.  
  9. Task: Choose which cards to flip (at most M) to minimize the difference
  10. between the largest and smallest visible values.
  11.  
  12. Example:
  13. N=3, M=1
  14. Cards: (A[0]=1, B[0]=10), (A[1]=5, B[1]=6), (A[2]=9, B[2]=2)
  15. Initially showing: [1, 5, 9] → max-min = 9-1 = 8
  16. If we flip card 2: [1, 5, 2] → max-min = 5-1 = 4
  17. Answer: 4
  18.  
  19. Key Insight:
  20. - Goal: Pack all N visible values into smallest possible range
  21. - Binary search on answer: "Can we achieve max-min <= X?"
  22. - Use sliding window on sorted values to find valid ranges
  23.  
  24. Approach:
  25. 1. Collect all 2N possible values (both sides of each card)
  26. 2. Sort these values
  27. 3. Binary search on answer X
  28. 4. For each X, sliding window to check if any range of size X works:
  29.    - Must include at least one value from EVERY card
  30.    - Count cards where only back value is in range (these MUST be flipped)
  31.    - If flips needed <= M, then X is achievable
  32.  
  33. Time: O(N log N + log(range) * N)
  34. */
  35.  
  36. #include <bits/stdc++.h>
  37. using namespace std;
  38.  
  39. int main() {
  40.     ios::sync_with_stdio(false);
  41.     cin.tie(nullptr);
  42.  
  43.     int n, m;
  44.     cin >> n >> m;
  45.  
  46.     vector<long long> a(n), b(n);
  47.  
  48.     // Store all values: {value, card_number, which_side}
  49.     // which_side: 0 = front (a), 1 = back (b)
  50.     vector<tuple<long long, int, int>> v;
  51.  
  52.     long long mn = LLONG_MAX, mx = LLONG_MIN;
  53.  
  54.     for (int i = 0; i < n; i++) {
  55.         cin >> a[i] >> b[i];
  56.  
  57.         v.push_back({a[i], i, 0});
  58.         v.push_back({b[i], i, 1});
  59.  
  60.         mn = min(mn, min(a[i], b[i]));
  61.         mx = max(mx, max(a[i], b[i]));
  62.     }
  63.  
  64.     // Sort all values
  65.     sort(v.begin(), v.end());
  66.  
  67.     // Check if we can fit all cards in a range of size x
  68.     auto ok = [&](long long x) -> bool {
  69.         // Track which side of each card is in current window
  70.         vector<bool> hasA(n, false);  // Is front in window?
  71.         vector<bool> hasB(n, false);  // Is back in window?
  72.  
  73.         int l = 0;
  74.  
  75.         // Try all possible windows
  76.         for (int r = 0; r < 2 * n; r++) {
  77.             auto [val, id, side] = v[r];
  78.  
  79.             // Add right value to window
  80.             if (side == 0) hasA[id] = true;
  81.             else hasB[id] = true;
  82.  
  83.             // Shrink window if range too big
  84.             while (val - get<0>(v[l]) > x) {
  85.                 auto [lval, lid, lside] = v[l];
  86.  
  87.                 // Remove left value from window
  88.                 if (lside == 0) hasA[lid] = false;
  89.                 else hasB[lid] = false;
  90.  
  91.                 l++;
  92.             }
  93.  
  94.             // Count cards covered and flips needed
  95.             int covered = 0;  // Cards with at least one value in window
  96.             int flips = 0;    // Cards with only back in window (must flip)
  97.  
  98.             for (int i = 0; i < n; i++) {
  99.                 // Does card i have any value in window?
  100.                 if (hasA[i] || hasB[i]) covered++;
  101.  
  102.                 // Does card i have ONLY back in window?
  103.                 if (!hasA[i] && hasB[i]) flips++;
  104.             }
  105.  
  106.             // Valid if all cards covered and flips allowed
  107.             if (covered == n && flips <= m) return true;
  108.         }
  109.  
  110.         return false;
  111.     };
  112.  
  113.     // Binary search on answer
  114.     long long lo = 0, hi = mx - mn;
  115.  
  116.     while (lo < hi) {
  117.         long long mid = lo + (hi - lo) / 2;
  118.  
  119.         if (ok(mid)) {
  120.             hi = mid;  // Can do mid, try smaller
  121.         } else {
  122.             lo = mid + 1;  // Can't do mid, try bigger
  123.         }
  124.     }
  125.  
  126.     cout << lo << "\n";
  127.  
  128.     return 0;
  129. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/xEXvxU
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!