A sorted array was cyclicly shifted by unknown offset. Find min element. lc
Solution
int findMin(vector<int>& nums) {
if (nums.size() == 0) return 0;
int l = 0, r = nums.size() - 1;
while (l < r) {
int m = l + (r - l)/2;
if (nums[l] <= nums[m] && nums[m] > nums[r])
l = m + 1;
else
r = m;
}
return nums[l];
}Given matrix where numbers are sorted in each row and the first element of the next row is greater than the last in the previous. Return true if target number is in this matrix.
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n = matrix.size();
if (n == 0) return false;
int m = matrix[0].size();
if (m == 0) return false;
int l = 0, r = n*m - 1;
while (l < r) {
int med = l + (r - l)/2;
if (matrix[med/m][med%m] < target)
l = med + 1;
else
r = med;
}
return matrix[l/m][l%m] == target;
}Given sorted array find subarray of length k, such that the the distance between elements of this array and a given value x is minimized. problem
Solution
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int n = arr.size();
// bin search for the left border of the segment of interest
// consider cases how three numbers x, am, am+k are placed
int l = 0, r = arr.size() - k;
while (l < r) {
int m = l + (r-l)/2;
if (x - arr[m] > arr[m+k] - x)
l = m + 1;
else
r = m;
}
return vector<int>(arr.begin() + l, arr.begin() + l + k);
}Find k-th element in sorted matrix (by columns and by rows).
Solution
The core idea is that we search in the elements space, not in the index space.
int cnt(vector<vector<int>>& matrix, int med) {
int n = matrix.size();
int m = matrix[0].size();
int res = 0;
for (int ii = 0; ii < n; ++ii) {
auto it = lower_bound(matrix[ii].begin(), matrix[ii].end(), med);
res += it - matrix[ii].begin();
}
return res;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int l = matrix[0][0] , r = matrix.back().back() + 1;
// i don't get it but if i use more classical l < r condition -- will not work
while (l+1 < r) {
int med = l + (r - l)/2;
int curCnt = cnt(matrix, med);
if (curCnt < k)
l = med;
else {
r = med;
}
}
return l;
}You are given an array with jobs load and you are given N workers. The problem is to distribute jobs among workers to minimize the maximum total workload per worker. Example of such job loads partition:
10 20 30 40 | 50 60 | 70 | 80 | 90
Solution
#include <bits/stdc++.h>
using namespace std;
class FairWorkload {
public:
int workerForLoad(int maxLoad, vector <int>& folders) {
int nworkers = 1;
int load = 0;
for (int f : folders) {
if (load + f <= maxLoad)
load += f;
else {
++nworkers;
load = f;
}
}
return nworkers;
}
int getMostWork(vector <int> folders, int workers) {
int l = *max_element(folders.begin(), folders.end());
int r = accumulate(folders.begin(), folders.end(), 0);
while (l < r) {
int m = l + (r - l)/2;
if (workerForLoad(m,folders) <= workers)
r = m;
else
l = m+1;
}
return r;
}
};Given array of items cost, you can pick up some items and the total cost of
them should <= S.
You want to buy as many as possible items, but minimize their cost.
The cost is computed as follows: a_i + i * k, where k is the total number of items picked.
Output the maximum number of items you can pick and the minimal cost of them.
Solution
#include <bits/stdc++.h>
using namespace std;
vector<int> c;
typedef long long lint;
vector<lint> temp;
lint minCost(lint k) {
copy(c.begin(), c.end(), temp.begin());
for (lint i = 0; i < temp.size(); ++i)
temp[i] += (i+1LL)*k;
sort(temp.begin(), temp.end());
return accumulate(temp.begin(), temp.begin() + k, 0LL);
}
lint binSearch(lint S) {
lint l = 0;
lint r = c.size() + 1;
while (l + 1LL < r) {
lint m = l + (r - l)/2LL;
if (minCost(m) <= S)
l = m;
else
r = m;
}
return l;
}
int main(int, char**) {
int n, S;
cin >> n >> S;
c.resize(n);
temp.resize(n);
for (int i = 0; i < n; ++i)
cin >> c[i];
lint k = binSearch(S);
cout << k << " " << minCost(k) << "\n";
return 0;
}Sweep line solution
#include <bits/stdc++.h>
using namespace std;
class UnionOfIntervals {
public:
int nthElement(vector <int> lowerBound, vector <int> upperBound, int n) {
vector< pair<int, int> > events;
for (int i = 0; i < lowerBound.size(); ++i) {
events.push_back( make_pair(lowerBound[i], 1) );
events.push_back( make_pair(upperBound[i]+1, -1) );
}
sort(events.begin(), events.end());
long long h = 1;
auto cur = events.front();
auto prev = cur;
for (int i = 1; i < events.size(); ++i) {
prev = cur;
cur = events[i];
long long d = h * (1LL*cur.first - prev.first);
if (n < d) {
return prev.first + n/h;
} else {
n -= d;
}
h += cur.second;
}
return -1;
}
};If you want to practice ternary search and writing binary search from scratch. The problem is to find a value x in an array which consists of up and down parts. lc
Find in montain array solution
int peakIndexInMountainArray(MountainArray& A) {
int l = 0, r = A.length() - 1;
while (r - l >= 3) {
int m1 = l + (r - l)/3;
int m2 = r - (r - l)/3;
if (A.get(m1) < A.get(m2)) l = m1;
else if (A.get(m1) > A.get(m2)) r = m2;
else if (A.get(m1) == A.get(m2)) { l = m1; r = m2; }
}
int res = A.get(l);
int ires = l+1;
while (l <= r) {
if (A.get(l) > res) {
res = A.get(l);
ires = l;
}
++l;
}
return ires;
}
int findInMountainArray(int x, MountainArray &A) {
int ipeak = peakIndexInMountainArray(A);
// to practice, lets write it twice
{
int l = 0, r = ipeak;
while (l < r) {
int m = l + (r-l)/2;
if (x <= A.get(m))
r = m;
else
l = m + 1;
}
if (A.get(l) == x)
return l;
}
{
int l = ipeak + 1, r = A.length()-1;
while (l < r) {
int m = l + (r-l)/2;
if (x >= A.get(m))
r = m;
else
l = m + 1;
}
if (A.get(l) == x)
return l;
}
return -1;
}