fork download
copy 
  1. /*
  2. QUESTION 14: D.E. Shaw OA — Removing Two Columns for Best Minimum Row Score
  3.  
  4. Problem Statement:
  5. You are given a matrix with N rows and M columns.
  6.  
  7. You must delete exactly two columns.
  8.  
  9. After deletion, each row gets a score equal to the maximum value remaining in that row.
  10.  
  11. Your goal is to maximize the minimum score among all rows.
  12.  
  13. Return the largest possible minimum row score.
  14.  
  15. Hard Constraints:
  16. 1 <= N
  17. 3 <= M
  18. N * M <= 200000
  19. 1 <= matrix[i][j] <= 1e9
  20.  
  21. Example:
  22. matrix =
  23. [
  24.   [8, 1, 5, 4],
  25.   [3, 7, 2, 6],
  26.   [9, 4, 1, 3]
  27. ]
  28.  
  29. Expected Output:
  30. 7
  31.  
  32. Explanation:
  33. Remove columns 3 and 4.
  34.  
  35. Remaining:
  36. row 1 -> max(8, 1) = 8
  37. row 2 -> max(3, 7) = 7
  38. row 3 -> max(9, 4) = 9
  39.  
  40. Minimum row score = 7
  41.  
  42. Brute Force:
  43. Try every pair of columns to remove.
  44. For each pair, scan all rows and compute the maximum remaining value.
  45.  
  46. Time Complexity:
  47. O(M^2 * N * M)
  48.  
  49. Optimized Approach:
  50. Binary search the answer X.
  51.  
  52. For every row, find columns where value >= X.
  53.  
  54. Cases:
  55. - 0 good columns: impossible
  56. - 1 good column: that column must stay
  57. - 2 good columns: those two cannot both be removed
  58. - 3 or more good columns: row is always safe
  59.  
  60. Check whether there exists a pair of columns that can be removed.
  61.  
  62. Time Complexity:
  63. O(N * M * log V)
  64.  
  65. Space Complexity:
  66. O(N + M)
  67. */
  68.  
  69. #include <bits/stdc++.h>
  70. using namespace std;
  71.  
  72. class Solution {
  73. public:
  74.     bool can(vector<vector<int>>& matrix, int target) {
  75.         int n = matrix.size();
  76.         int m = matrix[0].size();
  77.  
  78.         vector<int> mustKeep(m, 0);
  79.         set<pair<int, int>> forbiddenPairs;
  80.  
  81.         for (int i = 0; i < n; i++) {
  82.             vector<int> good;
  83.  
  84.             for (int j = 0; j < m; j++) {
  85.                 if (matrix[i][j] >= target) {
  86.                     good.push_back(j);
  87.                 }
  88.             }
  89.  
  90.             if (good.empty()) return false;
  91.  
  92.             if (good.size() == 1) {
  93.                 mustKeep[good[0]] = 1;
  94.             } else if (good.size() == 2) {
  95.                 int a = good[0];
  96.                 int b = good[1];
  97.  
  98.                 if (a > b) swap(a, b);
  99.  
  100.                 forbiddenPairs.insert({a, b});
  101.             }
  102.         }
  103.  
  104.         vector<int> removable;
  105.  
  106.         for (int j = 0; j < m; j++) {
  107.             if (!mustKeep[j]) {
  108.                 removable.push_back(j);
  109.             }
  110.         }
  111.  
  112.         long long c = removable.size();
  113.  
  114.         if (c < 2) return false;
  115.  
  116.         long long totalPairs = c * (c - 1) / 2;
  117.         long long badPairs = 0;
  118.  
  119.         for (auto [a, b] : forbiddenPairs) {
  120.             if (!mustKeep[a] && !mustKeep[b]) {
  121.                 badPairs++;
  122.             }
  123.         }
  124.  
  125.         return totalPairs > badPairs;
  126.     }
  127.  
  128.     int maximizeMinimumRowValue(vector<vector<int>>& matrix) {
  129.         int low = 0;
  130.         int high = 1000000000;
  131.         int ans = 0;
  132.  
  133.         while (low <= high) {
  134.             int mid = low + (high - low) / 2;
  135.  
  136.             if (can(matrix, mid)) {
  137.                 ans = mid;
  138.                 low = mid + 1;
  139.             } else {
  140.                 high = mid - 1;
  141.             }
  142.         }
  143.  
  144.         return ans;
  145.     }
  146. };
  147.  
  148. int main() {
  149.     Solution sol;
  150.  
  151.     vector<vector<int>> matrix = {
  152.         {8, 1, 5, 4},
  153.         {3, 7, 2, 6},
  154.         {9, 4, 1, 3}
  155.     };
  156.  
  157.     cout << sol.maximizeMinimumRowValue(matrix) << endl;
  158.  
  159.     return 0;
  160. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7
https://ideone.com/HPruyg
language:
C++14 (gcc 8.3)
created:
9 hours 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!