fork download
copy 
  1. /*
  2.     Problem: Maximum Minimum Rating
  3.     Company Tag: D. E. Shaw OA
  4.  
  5.     Problem Statement:
  6.         We are given a 2D array rating of size n x m.
  7.  
  8.         There are n customers and m products.
  9.         rating[i][j] means the rating given by customer i to product j.
  10.  
  11.         We need to select exactly n - 2 products.
  12.  
  13.         After selecting products, for every customer i:
  14.             mx[i] = maximum rating customer i gave among selected products
  15.  
  16.         Then we take:
  17.             minimum value among all mx[i]
  18.  
  19.         Our task is to maximize this minimum value.
  20.  
  21.     Constraints:
  22.         2 <= n <= 100
  23.         n <= m <= 100
  24.         1 <= rating[i][j] <= 100
  25.  
  26.     Brute Force:
  27.         Try every possible set of n - 2 products.
  28.         For each set, calculate the answer.
  29.  
  30.     Why Brute Force Fails:
  31.         m can be 100, so choosing all possible product sets is too expensive.
  32.  
  33.     Optimized Idea:
  34.         I check whether a value x can be achieved.
  35.  
  36.         For x to be possible:
  37.             Every customer must have at least one selected product
  38.             with rating >= x.
  39.  
  40.         If each customer needs a separate product, we may need n products.
  41.         But we can choose only n - 2 products.
  42.  
  43.         So we need to save 2 selections.
  44.  
  45.         This can happen if:
  46.             1. One product satisfies at least 3 customers.
  47.             2. Two products together satisfy at least 4 customers.
  48.  
  49.     Explanation Block:
  50.         I convert every product into a set of customers it can satisfy for value x.
  51.  
  52.         Then:
  53.             - If any customer is not satisfied by any product, x is impossible.
  54.             - If one product satisfies 3 customers, we save 2 products.
  55.             - If two products together satisfy 4 customers, we save 2 products.
  56.  
  57.         Since rating values are from 1 to 100, I simply try every x.
  58.  
  59.     Dry Run:
  60.         rating =
  61.         [
  62.             [3, 4, 2, 2],
  63.             [3, 3, 3, 4],
  64.             [2, 4, 2, 3],
  65.             [4, 2, 4, 2]
  66.         ]
  67.  
  68.         For x = 3:
  69.             Product 0 satisfies customers 0, 1, and 3.
  70.  
  71.         One product satisfies 3 customers.
  72.         So x = 3 is possible.
  73.  
  74.         Answer = 3
  75.  
  76.     Time Complexity:
  77.         O(100 * m * m)
  78.  
  79.     Space Complexity:
  80.         O(m * n)
  81. */
  82.  
  83. #include <bits/stdc++.h>
  84. using namespace std;
  85.  
  86. bool canMake(vector<vector<int>>& rating, int x) {
  87.     int n = rating.size();
  88.     int m = rating[0].size();
  89.  
  90.     int productsToPick = n - 2;
  91.  
  92.     // If we cannot pick any product, then this checking is not meaningful.
  93.     if (productsToPick <= 0) {
  94.         return false;
  95.     }
  96.  
  97.     vector<bitset<105>> good(m);
  98.  
  99.     // good[j][i] = 1 means product j can satisfy customer i for value x.
  100.     for (int i = 0; i < n; i++) {
  101.         bool hasGoodProduct = false;
  102.  
  103.         for (int j = 0; j < m; j++) {
  104.             if (rating[i][j] >= x) {
  105.                 good[j].set(i);
  106.                 hasGoodProduct = true;
  107.             }
  108.         }
  109.  
  110.         // If any customer has no product with rating >= x,
  111.         // then x cannot be achieved.
  112.         if (!hasGoodProduct) {
  113.             return false;
  114.         }
  115.     }
  116.  
  117.     // Case 1:
  118.     // One product satisfies at least 3 customers.
  119.     // Instead of choosing 3 separate products, I choose only 1.
  120.     // So I save 2 selections.
  121.     for (int j = 0; j < m; j++) {
  122.         if ((int)good[j].count() >= 3) {
  123.             return true;
  124.         }
  125.     }
  126.  
  127.     // Case 2:
  128.     // Two products together satisfy at least 4 customers.
  129.     // Instead of choosing 4 separate products, I choose only 2.
  130.     // Again, I save 2 selections.
  131.     for (int a = 0; a < m; a++) {
  132.         for (int b = a + 1; b < m; b++) {
  133.             bitset<105> combined = good[a] | good[b];
  134.  
  135.             if ((int)combined.count() >= 4) {
  136.                 return true;
  137.             }
  138.         }
  139.     }
  140.  
  141.     return false;
  142. }
  143.  
  144. int getMaximumRating(vector<vector<int>>& rating) {
  145.     int ans = 0;
  146.  
  147.     // Since rating values are only from 1 to 100,
  148.     // I try every possible answer.
  149.     for (int x = 1; x <= 100; x++) {
  150.         if (canMake(rating, x)) {
  151.             ans = x;
  152.         }
  153.     }
  154.  
  155.     return ans;
  156. }
  157.  
  158. int main() {
  159.     vector<vector<int>> rating = {
  160.         {3, 4, 2, 2},
  161.         {3, 3, 3, 4},
  162.         {2, 4, 2, 3},
  163.         {4, 2, 4, 2}
  164.     };
  165.  
  166.     cout << getMaximumRating(rating) << endl;
  167.  
  168.     return 0;
  169. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/GyzvzC
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!