fork download
copy 
  1. /*
  2.     Problem: Maximum Size of Infinity Stone
  3.     Company Tag: Media.net OA
  4.  
  5.     Problem Statement:
  6.         We are given a 2D array A of size N x k.
  7.  
  8.         There are N shops.
  9.         Each shop sells k types of nanocrystals.
  10.  
  11.         A[i][j] means the size of type j crystal sold by shop i.
  12.  
  13.         We can choose at most 2 shops.
  14.  
  15.         For every type j:
  16.             best[j] = maximum crystal size among chosen shops
  17.  
  18.         To make an infinity stone of size X:
  19.             cost for type j = ceil(X / best[j])
  20.  
  21.         Total cost must be <= S.
  22.  
  23.         Return maximum possible X modulo 1e9 + 7.
  24.  
  25.     Constraints:
  26.         1 <= N <= 100000
  27.         1 <= k <= 7
  28.         1 <= A[i][j] <= 100000
  29.         1 <= S <= 1000000000
  30.  
  31.     Brute Force:
  32.         Try every pair of shops and every possible value of X.
  33.  
  34.     Why Brute Force Fails:
  35.         N can be 100000.
  36.         Trying every pair of shops is O(N^2), which is too slow.
  37.  
  38.     Optimized Idea:
  39.         I binary search the answer X.
  40.  
  41.         For fixed X:
  42.             I check whether X can be made within budget S using at most 2 shops.
  43.  
  44.         Since k <= 7, I use bitmasking.
  45.  
  46.         If k = 3:
  47.             mask 101 means crystal types 0 and 2 are handled by one shop.
  48.  
  49.     Explanation Block:
  50.         For every shop, I calculate how much it costs to produce size X
  51.         for each crystal type.
  52.  
  53.         Then for every subset mask:
  54.             best[mask] = minimum cost to cover that subset using one shop.
  55.  
  56.         Since I can choose at most 2 shops:
  57.             I split all crystal types into two groups.
  58.  
  59.         If:
  60.             best[group1] + best[group2] <= S
  61.  
  62.         then X is possible.
  63.  
  64.     Dry Run:
  65.         A =
  66.         [
  67.             [9, 4, 1],
  68.             [2, 5, 10],
  69.             [6, 8, 3]
  70.         ]
  71.  
  72.         S = 10
  73.  
  74.         Choose shop 2 and shop 3:
  75.             best = [6, 8, 10]
  76.  
  77.         For X = 24:
  78.             ceil(24 / 6)  = 4
  79.             ceil(24 / 8)  = 3
  80.             ceil(24 / 10) = 3
  81.  
  82.         Total cost = 10
  83.  
  84.         Answer = 24
  85.  
  86.     Time Complexity:
  87.         O(log(maxAnswer) * N * 2^k)
  88.  
  89.     Space Complexity:
  90.         O(2^k)
  91. */
  92.  
  93. #include <bits/stdc++.h>
  94. using namespace std;
  95.  
  96. using ll = long long;
  97.  
  98. const ll MOD = 1000000007LL;
  99.  
  100. bool canMakeStone(vector<vector<int>>& A, ll S, ll X) {
  101.     int n = A.size();
  102.     int k = A[0].size();
  103.  
  104.     int totalMasks = 1 << k;
  105.  
  106.     // Any cost greater than S is useless because budget is only S.
  107.     ll INF = S + 1;
  108.  
  109.     // best[mask] = minimum cost to cover this subset using one shop.
  110.     vector<ll> best(totalMasks, INF);
  111.     best[0] = 0;
  112.  
  113.     for (int i = 0; i < n; i++) {
  114.         vector<ll> cost(k);
  115.  
  116.         // Calculate cost of each crystal type from current shop.
  117.         for (int j = 0; j < k; j++) {
  118.             cost[j] = (X + A[i][j] - 1) / A[i][j];
  119.  
  120.             if (cost[j] > S) {
  121.                 cost[j] = INF;
  122.             }
  123.         }
  124.  
  125.         vector<ll> subsetCost(totalMasks, 0);
  126.  
  127.         // Calculate cost for every subset of crystal types for this shop.
  128.         for (int mask = 1; mask < totalMasks; mask++) {
  129.             int bit = __builtin_ctz(mask);
  130.             int previousMask = mask ^ (1 << bit);
  131.  
  132.             subsetCost[mask] = subsetCost[previousMask] + cost[bit];
  133.  
  134.             if (subsetCost[mask] > S) {
  135.                 subsetCost[mask] = INF;
  136.             }
  137.         }
  138.  
  139.         // Update minimum one-shop cost for every subset.
  140.         for (int mask = 0; mask < totalMasks; mask++) {
  141.             best[mask] = min(best[mask], subsetCost[mask]);
  142.         }
  143.     }
  144.  
  145.     int fullMask = totalMasks - 1;
  146.  
  147.     // Split all crystal types into two groups.
  148.     // One group is handled by one shop, the other by another shop.
  149.     for (int mask = 0; mask < totalMasks; mask++) {
  150.         int other = fullMask ^ mask;
  151.  
  152.         if (best[mask] + best[other] <= S) {
  153.             return true;
  154.         }
  155.     }
  156.  
  157.     return false;
  158. }
  159.  
  160. int maximumInfinityStoneSize(vector<vector<int>>& A, ll S) {
  161.     int maxCrystal = 0;
  162.  
  163.     for (auto& row : A) {
  164.         for (int x : row) {
  165.             maxCrystal = max(maxCrystal, x);
  166.         }
  167.     }
  168.  
  169.     ll low = 0;
  170.     ll high = 1LL * maxCrystal * S;
  171.     ll ans = 0;
  172.  
  173.     // Binary search maximum possible stone size.
  174.     while (low <= high) {
  175.         ll mid = low + (high - low) / 2;
  176.  
  177.         if (canMakeStone(A, S, mid)) {
  178.             ans = mid;
  179.             low = mid + 1;
  180.         } else {
  181.             high = mid - 1;
  182.         }
  183.     }
  184.  
  185.     return ans % MOD;
  186. }
  187.  
  188. int main() {
  189.     vector<vector<int>> A = {
  190.         {9, 4, 1},
  191.         {2, 5, 10},
  192.         {6, 8, 3}
  193.     };
  194.  
  195.     long long S = 10;
  196.  
  197.     cout << maximumInfinityStoneSize(A, S) << endl;
  198.  
  199.     return 0;
  200. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
24
https://ideone.com/l0Rg7F
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!