CF Educational Round 11. C. Hard Process

1.Problem

Problem - C - Codeforces

2.Idea

Standard two pointers method

3.Source

 void solve()  
 {  
      int n, k;  
      cin >> n >> k;  
      vector<int> a(n);  
      REP(i, n) cin >> a[i];  
      pi res(0, 0);  
      int right = 0;  
      int cnt = 0;  
      for (int left = 0; left < n; ++left) {  
           while (right < n && cnt + (!a[right]) <= k) {  
                cnt += (!a[right]);  
                right++;  
           }  
           if (res.first < right - left) {  
                res.first = right - left;  
                res.second = left;  
           }  
           if (left == right) right++;  
           else cnt -= (!a[left]);  
      }  
      cout << res.first << endl;  
      REP(i, n) {  
           if (i >= res.second && i < res.second + res.first) cout << 1 << " ";  
           else cout << a[i] << " ";  
      }  
      cout << endl;  
 }  

Two Pointers Problems in Leetcode

 1.Running from both ends of an array

 - 2 Sum problem

Two Sum II - Input array is sorted - LeetCode

3Sum - LeetCode

4Sum - LeetCode

Number of Subsequences That Satisfy the Given Sum Condition - LeetCode

Two Sum IV - Input is a BST - LeetCode

Sum of Square Numbers - LeetCode

Boats to Save People - LeetCode

Minimize Maximum Pair Sum in Array - LeetCode

3Sum With Multiplicity - LeetCode

 - Trapping Water 
Container With Most Water - LeetCode

Trapping Rain Water - LeetCode

 - Next Permutation

Next Permutation - LeetCode

Next Greater Element III - LeetCode

Minimum Adjacent Swaps to Reach the Kth Smallest Number - LeetCode

 - Reversing / Swapping

Valid Palindrome - LeetCode

Reverse String - LeetCode

Reverse Vowels of a String - LeetCode

Valid Palindrome II - LeetCode

Reverse Only Letters - LeetCode

Remove Element - LeetCode

Sort Colors - LeetCode

Flipping an Image - LeetCode

Squares of a Sorted Array - LeetCode

Sort Array By Parity - LeetCode

Sort Array By Parity II - LeetCode

Pancake Sorting - LeetCode

Reverse Prefix of Word - LeetCode

Reverse String II - LeetCode

Reverse Words in a String - LeetCode

Reverse Words in a String III - LeetCode

 - Others

Bag of Tokens - LeetCode

DI String Match - LeetCode

Minimum Length of String After Deleting Similar Ends - LeetCode

Sentence Similarity III - LeetCode

Find K Closest Elements - LeetCode

Shortest Distance to a Character - LeetCode

2.Slow & Fast Pointers

 

 

 - Linked List Operations

Linked List Cycle - LeetCode

Linked List Cycle II - LeetCode

Remove Nth Node From End of List - LeetCode

Rotate List - LeetCode

Reorder List - LeetCode

Palindrome Linked List - LeetCode

 - Cyclic Detection

Find the Duplicate Number - LeetCode

Circular Array Loop - LeetCode

 - Sliding Window Like

Number of Subarrays with Bounded Maximum - LeetCode

Find K-th Smallest Pair Distance - LeetCode

Moving Stones Until Consecutive II - LeetCode

Count Pairs Of Nodes - LeetCode

Count Binary Substrings - LeetCode

K-diff Pairs in an Array - LeetCode

 - Rotation

Rotating the Box - LeetCode

Rotate Array - LeetCode

 - String

String Compression - LeetCode

Last Substring in Lexicographical Order - LeetCode

 - Remove Duplicate

Remove Duplicates from Sorted Array - LeetCode

Remove Duplicates from Sorted Array II - LeetCode

Remove Duplicates from Sorted List II - LeetCode

Duplicate Zeros - LeetCode

 - Others

Statistics from a Large Sample - LeetCode

Partition Labels - LeetCode

Magical String - LeetCode

Friends Of Appropriate Ages - LeetCode

Longest Mountain in Array - LeetCode

Shortest Subarray to be Removed to Make Array Sorted - LeetCode

3.Running from beginning of 2 arrays / Merging 2 arrays

  - Sorted arrays

Merge Sorted Array - LeetCode

Heaters - LeetCode

Find the Distance Value Between Two Arrays - LeetCode

 - Intersection / LCA like

Intersection of Two Linked Lists - LeetCode 

Intersection of Two Arrays - LeetCode

Intersection of Two Arrays II - LeetCode

 - Sub String

Implement strStr() - LeetCode

Longest Word in Dictionary through Deleting - LeetCode

Long Pressed Name - LeetCode

Longest Uncommon Subsequence II - LeetCode

Compare Version Numbers - LeetCode

Camelcase Matching - LeetCode

Expressive Words - LeetCode

 - Median Finder

Find Median from Data Stream - LeetCode

 - Meet-in-the-middle / Binary Search

Partition Array Into Two Arrays to Minimize Sum Difference - LeetCode

Closest Subsequence Sum - LeetCode

Ways to Split Array Into Three Subarrays - LeetCode

3Sum Closest - LeetCode

Valid Triangle Number - LeetCode

 - Others

Shortest Unsorted Continuous Subarray - LeetCode

Most Profit Assigning Work - LeetCode

Largest Merge Of Two Strings - LeetCode

Swap Adjacent in LR String - LeetCode

4.Split & Merge of an array / Divide & Conquer

 

 - Partition 

Partition List - LeetCode

 - Sorting

Sort List - LeetCode

LeetCode.1438 Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1.Problem
https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

2.Idea
MaxMinQueue + 2 Pointers method

3.Source

 class MaxMinQueue {  
 public:  
      MaxMinQueue() {}  
      bool empty() { return elements.empty(); }  
      int size() { return elements.size(); }  
      void push(int val) {  
           elements.push(val);  
           while (!maxElements.empty() && val > maxElements.back()) maxElements.pop_back();  
           maxElements.push_back(val);  
           while (!minElements.empty() && val < minElements.back()) minElements.pop_back();  
           minElements.push_back(val);  
      }  
      int pop() {  
           int val = elements.front();  
           elements.pop();  
           if (val == maxElements.front()) maxElements.pop_front();  
           if (val == minElements.front()) minElements.pop_front();  
           return val;  
      }  
      int peekMax() {  
           return maxElements.front();  
      }  
      int peekMin() {  
           return minElements.front();  
      }  
 private:  
      queue<int> elements;  
      deque<int> maxElements;  
      deque<int> minElements;  
 };  
 class Solution {  
 public:  
      MaxMinQueue q;  
      int longestSubarray(vector<int>& nums, int limit) {  
           int n = nums.size();  
           int ans = 0;  
           int p1 = 0;  
           while (p1 < n) {  
                q.push(nums[p1]);  
                while(q.size() > 0 && (q.peekMax() - q.peekMin() > limit)) {  
                     q.pop();  
                }  
                ans = max(ans, q.size());  
                p1++;  
           }  
           return ans;  
      }  
 };  
 int main()  
 {  
      Solution obj;  
      vector<int> in = { 8,2,4,7 };  
      obj.longestSubarray(in, 4);  
      return 0;  
 }  

POJ.2566 Bound Found

1.Problem
http://poj.org/problem?id=2566

2.Idea
Two Pointers

3.Source

 struct Item {  
      int sum;  
      int end;  
      bool operator < (const Item &a)const {  
           return sum < a.sum;  
      }  
 } items[100005];  
 int N, K, T;  
 void solve()  
 {  
      int x, y, s = 0, t = 0, ans = 1000000007, maxn = 1000000007;  
      while (s <= N && t <= N && maxn) {  
           if (s == t) {  
                t++;  
           }  
           else {  
                int sum = items[t].sum - items[s].sum;  
                if (maxn > abs(sum - T)) {  
                     ans = sum;  
                     maxn = abs(sum - T);  
                     x = min(items[s].end, items[t].end) + 1;  
                     y = max(items[s].end, items[t].end);  
                }  
                if (sum > T) {  
                     s++;  
                }  
                if (sum < T) {  
                     t++;  
                }  
           }  
      }  
      printf("%d %d %d\n", ans, x, y);  
 }  
 int main()  
 {  
      while (scanf("%d%d", &N, &K) > 0, N + K) {  
           items[0].end = 0;  
           items[0].sum = 0;  
           for (int i = 1; i <= N; i++) {  
                int x;  
                scanf("%d", &x);  
                items[i].end = i;  
                items[i].sum = items[i - 1].sum + x;  
           }  
           sort(items, items + N + 1);  
           for (int i = 0; i < K; i++) {  
                scanf("%d", &T);  
                solve();  
           }  
      }  
      return 0;  
 }  

POJ.2100 Graveyard Design

1.Problem
http://poj.org/problem?id=2100

2.Idea
Two Pointers

3.Source

 ll S;  
 ll s, t;  
 int n = 10000000;  
 vector<int> ans1, ans2;  
 void solve()  
 {  
      int res = 0;  
      ll s = 0, t = 0;  
      ll sum = 0;  
      for (;;) {  
           while (t < n && sum < S) {  
                sum += t*t; t++;  
           }  
           if (sum < S) break;  
           if (sum == S) {  
                if (s == 0) s++;  
                ans1.push_back(s);  
                ans2.push_back(t - 1);  
           }  
           sum -= s*s;  
           s++;  
      }  
      printf("%d\n", ans1.size());  
      for (int i = 0; i < ans1.size(); i++) {  
           printf("%d", ans2[i] - ans1[i] + 1);  
           for (int j = ans1[i]; j <= ans2[i]; j++) printf(" %d", j);  
           printf("\n");  
      }  
 }  
 int main()  
 {  
      scanf("%lld", &S);  
      n = sqrt(1.0 * S) + 1;  
      solve();  
      return 0;  
 }  

POJ.2739 Sum of Consecutive Prime Numbers

1.Problem
http://poj.org/problem?id=2739

2.Idea
Two Pointers

3.Source

 bool isPrime[10001];  
 bool visited[10001];  
 vector<int> a;  
 int n, S;  
 int s, t;  
 void solve()  
 {  
      int res = 0;  
      int s = 0, t = 0, sum = 0;  
      for (;;) {  
           while (t < n && sum < S) sum += a[t++];  
           if (sum < S) break;  
           if (sum == S) res++;  
           sum -= a[s++];  
      }  
      printf("%d\n", res);  
 }  
 int main()  
 {  
      // get all primes   
      for (int i = 0; i < 10001; i++) isPrime[i] = true;  
      isPrime[0] = isPrime[1] = false;  
      for (int i = 2; i < 10001; i++) {  
           if (isPrime[i]) {  
                a.push_back(i);  
                for (int j = 2 * i; j < 10001; j += i) {  
                     isPrime[j] = false;  
                }  
           }  
      }  
      while (cin >> S)  
      {  
           if (!S) break;  
           n = a.size();  
           solve();  
      }  
      return 0;  
 }  

POJ.3320 Jessica's Reading Problem

1.Problem
http://poj.org/problem?id=3320

2.Idea
Two Pointers method

3.Source

 int P;  
 int a[1000006];  
 void solve()  
 {  
      set<int> all;  
      for (int i = 0; i < P; i++) all.insert(a[i]);  
      int n = all.size();  
      map<int, int> count;  
      int s = 0, t = 0, num = 0, res = P;  
      for (;;) {  
           while (t < P && num < n) {  
                if (count[a[t++]]++ == 0) num++;  
           }  
           if (num < n) break;  
           res = min(res, t - s);  
           if (--count[a[s++]] == 0) {  
                num--;  
           }  
      }  
      printf("%d\n", res);  
 }  
 int main()  
 {  
      scanf("%d", &P);  
      for (int i = 0; i < P; i++) scanf("%d", &a[i]);  
      solve();  
      return 0;  
 }  

POJ.3061 Subsequence

1.Problem
http://poj.org/problem?id=3061

2.Idea
Two Pointers method

3.Source

 int n, S;  
 int a[1000006];  
 void solve()  
 {  
      int res = n + 1;  
      int s = 0, t = 0, sum = 0;  
      for (;;) {  
           while (t < n && sum < S) sum += a[t++];  
           if (sum < S) break;  
           res = min(res, t - s);  
           sum -= a[s++];  
      }  
      if (res > n) res = 0;  
      printf("%d\n", res);  
 }  
 int main()  
 {  
      int t;  
      scanf("%d", &t);  
      while (t--) {  
           scanf("%d%d", &n, &S);  
           for (int i = 0; i < n; i++) scanf("%d", &a[i]);  
           solve();  
      }  
      return 0;  
 }