fork download 
  1. /*
  2.     Problem: Minimum Cars Removed for Bridge Weight Limit
  3.     Company Tag: Deutsche Bank OA
  4.  
  5.     Problem Statement:
  6.         We are given:
  7.             U = maximum bridge weight limit
  8.             weight[i] = weight of i-th car in queue
  9.  
  10.         Rules:
  11.             1. Cars cross in given order.
  12.             2. At most two cars can be on bridge at same time.
  13.             3. Total weight must not exceed U.
  14.             4. We can remove some cars.
  15.             5. Remaining cars must keep original relative order.
  16.  
  17.         Return minimum number of cars to remove.
  18.  
  19.     Constraints:
  20.         1 <= weight.length <= 100000
  21.         1 <= weight[i] <= 1000000000
  22.         1 <= U <= 1000000000
  23.  
  24.     Brute Force:
  25.         Try all subsequences of cars and check which can cross.
  26.  
  27.     Why Brute Force Fails:
  28.         There are 2^n subsequences.
  29.  
  30.     Optimized Idea:
  31.         If remaining cars are:
  32.             a1, a2, a3, ...
  33.  
  34.         Then every adjacent pair must satisfy:
  35.             a[i] + a[i + 1] <= U
  36.  
  37.         So we need:
  38.             longest subsequence where adjacent pair sum <= U
  39.  
  40.         Answer:
  41.             n - longest valid subsequence length
  42.  
  43.     Explanation Block:
  44.         I use DP with Fenwick Tree.
  45.  
  46.         For current car weight x:
  47.             Previous kept car weight must be <= U - x.
  48.  
  49.         Fenwick Tree stores:
  50.             maximum subsequence length ending with a certain weight.
  51.  
  52.         Query gives:
  53.             best previous subsequence length that can connect with x.
  54.  
  55.     Dry Run:
  56.         U = 9
  57.         weight = [5, 3, 8, 1, 7, 7, 6]
  58.  
  59.         Keep:
  60.             [5, 3, 1, 6]
  61.  
  62.         Check:
  63.             5 + 3 = 8
  64.             3 + 1 = 4
  65.             1 + 6 = 7
  66.  
  67.         Removed = 7 - 4 = 3
  68.  
  69.     Time Complexity:
  70.         O(n log n)
  71.  
  72.     Space Complexity:
  73.         O(n)
  74. */
  75.  
  76. #include <bits/stdc++.h>
  77. using namespace std;
  78.  
  79. class FenwickMax {
  80. public:
  81.     int n;
  82.     vector<int> bit;
  83.  
  84.     FenwickMax(int n) {
  85.         this->n = n;
  86.         bit.assign(n + 1, 0);
  87.     }
  88.  
  89.     // Update best DP value for a compressed weight.
  90.     void update(int index, int value) {
  91.         while (index <= n) {
  92.             bit[index] = max(bit[index], value);
  93.             index += index & -index;
  94.         }
  95.     }
  96.  
  97.     // Query maximum DP value among weights from 1 to index.
  98.     int query(int index) {
  99.         int result = 0;
  100.  
  101.         while (index > 0) {
  102.             result = max(result, bit[index]);
  103.             index -= index & -index;
  104.         }
  105.  
  106.         return result;
  107.     }
  108. };
  109.  
  110. int minimumCarsRemoved(long long U, vector<long long>& weight) {
  111.     int n = weight.size();
  112.  
  113.     vector<long long> values;
  114.  
  115.     // Cars heavier than U can never be kept.
  116.     for (long long x : weight) {
  117.         if (x <= U) {
  118.             values.push_back(x);
  119.         }
  120.     }
  121.  
  122.     sort(values.begin(), values.end());
  123.     values.erase(unique(values.begin(), values.end()), values.end());
  124.  
  125.     if (values.empty()) {
  126.         return n;
  127.     }
  128.  
  129.     FenwickMax fw(values.size());
  130.  
  131.     int longest = 0;
  132.  
  133.     for (long long x : weight) {
  134.         // If one car itself is heavier than U, it must be removed.
  135.         if (x > U) {
  136.             continue;
  137.         }
  138.  
  139.         // Previous kept car must have weight <= U - x.
  140.         long long allowedPrevious = U - x;
  141.  
  142.         // Find how many compressed weights are <= allowedPrevious.
  143.         int pos = upper_bound(values.begin(), values.end(), allowedPrevious) - values.begin();
  144.  
  145.         // Best valid subsequence before current car.
  146.         int bestPrevious = fw.query(pos);
  147.  
  148.         // Keep current car.
  149.         int dp = bestPrevious + 1;
  150.  
  151.         int compressedIndex = lower_bound(values.begin(), values.end(), x) - values.begin() + 1;
  152.  
  153.         fw.update(compressedIndex, dp);
  154.  
  155.         longest = max(longest, dp);
  156.     }
  157.  
  158.     return n - longest;
  159. }
  160.  
  161. int main() {
  162.     long long U = 9;
  163.  
  164.     vector<long long> weight = {5, 3, 8, 1, 7, 7, 6};
  165.  
  166.     cout << minimumCarsRemoved(U, weight) << endl;
  167.  
  168.     return 0;
  169. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
3
https://ideone.com/BCDXcR
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!