fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int lightsabers(vector<int> &A, vector<int> &B) {
  5.     map<int, int> required; // Map to store value of Array B in map Data Structure pair(i+1, A[i])
  6.     map<int, int> mb; // Map to store the values with count in the current window eg, pair(1, 4) means 1 occured 4 times in current window.
  7.     int ini=-1, tini = -1, minn = INT_MAX, tminn = INT_MAX; // ini(initial pointer) tracks the start location of window and minn stores minimum number of elements to be removed from A, t for temporary storage of these value
  8.     long long threshold = 0, thresholdPass = 0; // threshold keeps track of the count of the elements to check the requirement as the B array,  threshold pass is the requirement as of the B array 
  9.     int n = A.size();
  10.     int m = B.size();
  11.     for(int i=0;i<m;i++) {
  12.         mb[i+1] = 0; // initialize mb with required elements as key and count as value all zero 
  13.         required[i+1] = B[i]; // storing required map according to B
  14.         thresholdPass+=B[i]; //  threshold pass storing count of the total elements required to achielve the goal
  15.     }
  16.     for(int i=0;i<n;i++) { // iterating through every element of arr A
  17.         int c = A[i]; // ith element stored in c
  18.         if(mb.find(c)!=mb.end()) { // check if c is there in map mb that's checks if this element is relevent and contributing in requirement count
  19.             if(mb[c]>=required[c]) { // if c is required the is the count more than & equal to required -> means the count is already fulfilled as requirement
  20.                 if(A[tini] == c) { // check if the first element in window is the same element as c -> then needs to reduce the window size and also the count
  21.                     tminn++; // first add the current element before reducing the size -> simply adding will increase extra element count
  22.                     mb[c]++; // inc the count
  23.                     int p = tini; 
  24.                     for(p=tini;p<i;p++) { // now looping from ini to the current position to decrease the window size
  25.                         int x = A[p];
  26.                         if(mb.find(x)!=mb.end()) {  // if the element is present in the current window count map(it will always be present in the map but still a check in case of error) -> not of much use but in case of exception
  27.                             if(mb[x]>required[x]){ // if the current element's count in the current window is more than required
  28.                                 mb[x]--; // decrease the count, remove the element
  29.                                 tminn--; // decrease the count of extra elements
  30.                                 continue;
  31.                             }
  32.                             else { // if the current element's count in the current window is not more than/equal to required then no more decrease the window size and break this loop
  33.                                 break;
  34.                             }
  35.                         }
  36.                     }
  37.                     tini = p; // we got our new start position of the new window
  38.                 }
  39.                 else {// if the first element in window is not the same element as c then just increment the count and window size
  40.                     tminn++; // Just increase extra elements count
  41.                     mb[c]++; // also adding it to the current window map
  42.                 }
  43.             }
  44.             else { // if c is required the is the count but current window's this element's count is less than required
  45.                 if(threshold==0) { // if we found our first required element, initialising our two pointers here
  46.                     tini = i;
  47.                     tminn = 0;
  48.                 }
  49.                 threshold++; // incrementing the current window threshold count as new element added was required
  50.                 // tminn = i - tini +1;
  51.                 mb[c]++; // incr the element count in curr window map
  52.             }
  53.  
  54.         }
  55.         else { // if the element is not required 
  56.             if(threshold==0) continue; // if the element is not required and window is not inotiated yet, then ignore this element 
  57.             // tminn = i - tini +1;
  58.             tminn++; // but we need to add it in our window hoping next element is the required one
  59.         }
  60.         if(threshold == thresholdPass) { // if the condition satisfyies the just checking if the new window size is less than prev one and then updating for the smallest window
  61.             if(minn>tminn) {
  62.                 minn = tminn;
  63.                 ini = tini;
  64.             }
  65.         }
  66.     }
  67.     int ans = -1;
  68.     if(threshold == thresholdPass)
  69.         ans = minn;
  70.     return ans;
  71.  
  72. }
  73.  
  74. int main() {
  75. 	// your code goes here
  76. 	vector<int> A{1, 2, 3, 4, 1};
  77. 	vector<int> B{2, 1, 1, 0};
  78. 	int ans = lightsabers(A, B);
  79. 	cout<<"Solution is: "<<ans<<endl;
  80. 	vector<int> A2{3, 3, 3, 3, 3, 4, 2, 1, 1, 3, 1, 2, 1, 1, 1, 4, 4, 1, 1, 1, 2, 1, 2, 3, 3, 3, 2, 2, 2, 4};
  81. 	vector<int> B2{2, 0, 4, 0};
  82. 	int ans2 = lightsabers(A2, B2);
  83. 	cout<<"Solution2 is: "<<ans2<<endl;
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Solution is: 1
Solution2 is: 2
https://ideone.com/VGBVUH
Lightsabers
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!