fork download
copy 
  1. /*
  2.     Problem: Minimum Top-Ranked Elements Needed to Form a Majority Subarray
  3.     Company Tag: Trilogy OA problem
  4.  
  5.     Problem Statement:
  6.         We are given A books in a row.
  7.  
  8.         B[i] is the thickness of the i-th book.
  9.         All thicknesses are unique.
  10.  
  11.         If we cover a book of thickness x, then every book thicker than x
  12.         must also be covered.
  13.  
  14.         So we can only choose the k thickest books.
  15.  
  16.         We need the minimum k such that there exists a contiguous subarray
  17.         of length at least C where:
  18.  
  19.             number of covered books > number of uncovered books
  20.  
  21.     Constraints:
  22.         1 <= A <= 100000
  23.         1 <= B[i] <= A
  24.         B[i] values are unique.
  25.         1 <= C <= A
  26.  
  27.     Simple Brute Force:
  28.         Try every k.
  29.         For every k, check every possible subarray.
  30.  
  31.     Why Brute Force Fails:
  32.         There can be 100000 books.
  33.         Checking all subarrays for every k is too slow.
  34.  
  35.     Better Idea:
  36.         Binary search the answer k.
  37.  
  38.         For a fixed k:
  39.             - Mark the k thickest books as +1.
  40.             - Mark all other books as -1.
  41.  
  42.         Now the question becomes:
  43.             Is there any subarray of length at least C with sum > 0?
  44.  
  45.         If yes, covered books are more than uncovered books in that subarray.
  46.  
  47.     Dry Run:
  48.         A = 6
  49.         B = [6, 1, 4, 2, 5, 3]
  50.         C = 4
  51.  
  52.         Try k = 3.
  53.         Covered books are 6, 5, and 4.
  54.  
  55.         Converted array:
  56.             [1, -1, 1, -1, 1, -1]
  57.  
  58.         Subarray [6, 1, 4, 2, 5] has sum 1.
  59.         So it has more covered books.
  60.  
  61.         Answer = 3
  62.  
  63.     Time Complexity:
  64.         O(A log A)
  65.  
  66.     Space Complexity:
  67.         O(A)
  68. */
  69.  
  70. #include <bits/stdc++.h>
  71. using namespace std;
  72.  
  73. bool canCreateMajoritySubarray(int A, vector<int>& B, int C, int k) {
  74.     vector<int> prefix(A + 1, 0);
  75.  
  76.     /*
  77.         Since B contains unique values from 1 to A,
  78.         the k thickest books have thickness >= A - k + 1.
  79.     */
  80.     int minimumCoveredThickness = A - k + 1;
  81.  
  82.     for (int i = 0; i < A; i++) {
  83.         int value;
  84.  
  85.         if (B[i] >= minimumCoveredThickness) {
  86.             value = 1;
  87.         } else {
  88.             value = -1;
  89.         }
  90.  
  91.         prefix[i + 1] = prefix[i] + value;
  92.     }
  93.  
  94.     int minimumPrefixSeen = 0;
  95.  
  96.     for (int right = C; right <= A; right++) {
  97.         /*
  98.             For a subarray ending at right and having length at least C,
  99.             the left prefix can be at most right - C.
  100.         */
  101.         minimumPrefixSeen = min(minimumPrefixSeen, prefix[right - C]);
  102.  
  103.         int bestSum = prefix[right] - minimumPrefixSeen;
  104.  
  105.         if (bestSum > 0) {
  106.             return true;
  107.         }
  108.     }
  109.  
  110.     return false;
  111. }
  112.  
  113. int solution(int A, vector<int> B, int C) {
  114.     int low = 1;
  115.     int high = A;
  116.     int answer = A;
  117.  
  118.     while (low <= high) {
  119.         int mid = low + (high - low) / 2;
  120.  
  121.         if (canCreateMajoritySubarray(A, B, C, mid)) {
  122.             answer = mid;
  123.             high = mid - 1;
  124.         } else {
  125.             low = mid + 1;
  126.         }
  127.     }
  128.  
  129.     return answer;
  130. }
  131.  
  132. int main() {
  133.     int A, C;
  134.     cin >> A;
  135.  
  136.     vector<int> B(A);
  137.  
  138.     for (int i = 0; i < A; i++) {
  139.         cin >> B[i];
  140.     }
  141.  
  142.     cin >> C;
  143.  
  144.     cout << solution(A, B, C) << endl;
  145.  
  146.     return 0;
  147. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/4elOpK
language:
C++14 (gcc 8.3)
created:
5 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!