The idea is to generate all possible solutions to the problem using brute force, and then select the best solution or count the number of solutions, depending on the problem.
// Generating subsets
void search(int k)
{
if (k == n) // process subset
else
{
search(k+1);
subset.push_back(k);
search(k+1);
subset.pop_back();
}
}
// Generating subsets - Iterative (using bitmanipulation)
for (int i = 0; i < (1<<n); ++i)
{
int x = i, pos = 0;
while (x)
{
if (x&1) take(pos);
pos++;
x >>= 1;
}
// process permutation
}
// Generating Permutations
void search()
{
if (permutation.size() == n) // Process permutation
else
{
for (int i = 0; i < n; ++i)
{
if (chosen[i]) continue;
chosen[i] = true;
permutation.push_back(i);
search();
chosen[i] = false;
permutation.pop_back();
}
}
}
// Generating Permutations Iterative (using next_permutation)
vector<int> permutation(n);
for (int i = 0; i < n; ++i) permutation[i] = i+1;
do
{
// Process permutation
} while(next_permutation(permutation.begin(), permutation.end()));
/*
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
*/
/*
1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
1 2 5 4 3
1 3 2 4 5
1 3 2 5 4
1 3 4 2 5
1 3 4 5 2
1 3 5 2 4
1 3 5 4 2
1 4 2 3 5
1 4 2 5 3
1 4 3 2 5
1 4 3 5 2
1 4 5 2 3
1 4 5 3 2
1 5 2 3 4
1 5 2 4 3
1 5 3 2 4
1 5 3 4 2
1 5 4 2 3
1 5 4 3 2
...
*/
// std implementation of next_permutation
bool nextPermutation(std::string &s, int n)
{
// Find the largest index `i` such that `s[i-1]` is less than `s[i]`
int i = n-1;
while (s[i-1] >= s[i])
{
// if `i` is the first index of the string, we are already at the last
// possible permutation (string is sorted in reverse order)
if (--i == 0) {
return false;
}
}
// If we reach here, substring `s[i…n-1]` is sorted in reverse order.
// Find the highest index `j` to the right of index `i` such that `s[j] > s[i-1]`.
int j = n-1;
while (j > i && s[j] <= s[i-1]) {
j--;
}
// swap character at index `i-1` with index `j`
std::swap(s[i-1], s[j]);
// Reverse substring `s[i…n-1]`and return true
std::reverse (s.begin() + i, s.end());
return true;
}Smart Complete Search
// N queens problem
void search(int y)
{
if (y == n) { found++; return; }
for (int x = 0; x < n; ++x)
{
if (col[x] || diag1[x+y] || diag2[x-y+n-1]) continue;
col[x] = diag1[x+y] = diag2[x-y+n-1] = true;
search(y+1);
col[x] = diag1[x+y] = diag2[x-y+n-1] = false;
}
}
/* Let q(n) be ans for n.
There is no known way to efficiently calculate larger values of q(n).
The current record is q(27) = 234907967154122528 */We can often optimize backtracking by pruning the search tree. The idea is to add ”intelligence” to the algorithm so that it will notice as soon as possible if a partial solution cannot be extended to a complete solution.
Let us consider the problem of calculating the number of paths in an n x n grid from upper-left corner to lower-right corner such that the path visits each square exactly once.
- Optimization 1 (Simple backtracking) Running time 783 seconds, 76 billion Recursive calls
- Optimization 2 (If path reaches lowest right square before it has visited all other squares of the grid, it is clear that it will not be possible to complete the solution. Running time 119 seconds, 20 billion Recursive calls
- Optimization 3 (If path touches the wall it can either go left or right in that split two-part case one part will get unvisited) Running time 1.8 seconds, 221 million Recursive calls
- Optimization 4 (Idea of previous optimization can be genralized: if path cannot continue forward but can turn either left or right, the grid splits into two pat that both contain unvisited squares) Running time 0.6 seconds, 69 million Recursive calls
Optimzation made it over 1000 times faster now
Meet in the middle is a technique where the search space is divided into two parts of about equal size. A separate search is performed for both of the parts, and finally the results of the searches are combined.
/** Here naive solution was to get all possible subsets through bitmanipulation 2^(2n) for the cases where popcount is n get the sum.
However total time complexity of 2^2n is 2^30 will give TLE.
Solution use meet in middle approach, divide the array in two part [0, n/2 - 1] [n/2, n-1]
Now, find all subset which will be 2*2^n i.e. 2^16 which is within limit. Grouping those subsets in terms of how many elements taken.
Now do a loop on how much to take from left and get its possible sums and do a lower bound on right possibilities.
*/
class Solution {
public:
int minimumDifference(vector<int>& nums) {
int totalSum = accumulate(nums.begin(), nums.end(), 0), n = nums.size();
function<vector<vector<int>>(int, int)> findAllSubsets = [&](int l, int r) -> vector<vector<int>> {
int len = r - l + 1;
vector<vector<int>> res(len + 1);
for (int i = 0; i < (1 << len); ++i) {
int sum = 0;
for (int j = 0; j < len; ++j) {
if (i&(1<<j)) sum += nums[l + j];
}
res[__builtin_popcount(i)].push_back(sum);
}
return res;
};
auto left = findAllSubsets(0, n/2 - 1);
auto right = findAllSubsets(n/2, n - 1);
int res = INT_MAX;
for (int takeLeft = 0; takeLeft <= n/2; ++takeLeft) {
int takeRight = n/2 - takeLeft;
auto rightPossibleSums = right[takeRight];
sort(rightPossibleSums.begin(), rightPossibleSums.end());
for (auto leftPossibileSum: left[takeLeft]) {
int needSumFromRight = totalSum/2 - leftPossibileSum;
auto it = lower_bound(rightPossibleSums.begin(), rightPossibleSums.end(), needSumFromRight);
if (it != rightPossibleSums.end()) {
int first = leftPossibileSum + *it;
int second = totalSum - first;
res = min(res, abs(first - second));
}
}
}
return res;
}
};This makes the complexity O(2^(n/2)) which is also O(root 2^n)
// Simple style
int l = 0, r = n-1;
while (l <= r)
{
int mid = l + (r-l)/2;
if (arr[mid] == x) return true;
if (arr[mid] > x) r = mid-1;
else l = mid+1;
}
return false;
// Constraint-bound style
int l = 0, r = n-1;
while (l < r)
{
int mid = l + (r-l)/2;
if (check(mid)) l = mid+1;
else r = mid;
}
return l;
/* Jump-based style
Idea is to make jumps and slow the speed when we get closer to the target
element. Search goes from left to right, and initial jump length is n/2.
At each step, the jump length is halved. After the jump either the target
element has been found or we know that it does not appear in the array. */
int j = 0;
for (int i = n/2; i >= 1; i /= 2)
{
while (i+j < n && arr[i+j] <= x) // run atmost twice
j += i;
}
return (arr[j] == x);Consider that there's a monotonically increasing function f(x) with f(0) some negative value we need to find some value n for which f(n) will be the first non negative number of the function.
Naive approach is linearly searching till we get number greater than 0, it will take O(n)
Other approach is using Unbounded Binary Search. The idea is to proceed with f(0) then f(1) f(2) f(4) f(8) f(16) ... till f(x) every other is ''''''''''''''''''''''x2 of previous. Now f(x) is first non negative in the above exponentiated series. Now we need to apply binary search from O(x/2) to O(x) x/2 is previous term of the series. This will give a time complexity of O(logn)
Following STL functions revolve around binary search (assumption array is sorted):
- lower_bound: first array element whose value is at least x
- upper_bound: first array element whose value is larger than x
- equal_range: returns both above pointers
auto a = lower_bound(array, array+n, x);
auto b = upper_bound(array, array+n, x);
cout << b-a << "\n";
auto r = equal_range(array, array+n, x);
cout << r.second-r.first << "\n";
// Both are equivalentint n, k; cin >> n >> k;
vector<int> arr(n);
for (auto &x : arr) cin >> x;
while (k--)
{
int x; cin >> x;
int l = 0, r = n-1;
bool found = false;
while (l <= r)
{
int mid = l + (r-l)/2;
if (arr[mid] == x) { found = true; break; }
if (arr[mid] > x) r = mid-1;
else l = mid+1;
}
if (found) cout << "YES\n";
else cout << "NO\n";
}int n, k; cin >> n >> k;
vector<int> arr(n);
for (auto &x : arr) cin >> x;
while (k--) // k queries of how many numbers > x in arr
{
int x; cin >> x;
int l = 0, r = n, res = 0;
while (l < r)
{
int mid = l + (r-l)/2;
if (arr[mid] <= x) l = mid+1, res = mid+1;
else r = mid;
}
cout << res << '\n';
}int n, k; cin >> n >> k;
vector<int> arr(n);
for (auto &x : arr) cin >> x;
while (k--) // k queries of how many numbers atleast x in arr
{
int x; cin >> x;
int l = 0, r = n, res = n+1;
while (l < r)
{
int mid = l + (r-l)/2;
if (arr[mid] >= x) r = mid, res = mid+1;
else l = mid+1;
}
cout << res << '\n';
}int n; cin >> n;
vector<int> arr(n);
for (auto &x : arr) cin >> x;
sort(arr.begin(), arr.end());
auto cnt = [&](int x)
{
int l = 0, r = n, res = 0;
while (l < r)
{
int mid = l + (r-l)/2;
if (arr[mid] > x) r = mid;
else l = mid+1, res = mid+1;
}
return res;
};
int k; cin >> k; // Given k queries find count of numbers b/w [L,R] in arr
while (k--)
{
int L, R; cin >> L >> R;
cout << (cnt(R) - cnt(L-1)) << ' ';
}
cout << '\n';int w, h, n; cin >> w >> h >> n;
auto check = [&](int x) { return ((x/w) * (x/h) >= n); };
int l = 0, r = 1;
while (!check(r)) r *= 2;
while (l+1 < r)
{
int mid = l + (r-l)/2;
if (!check(mid)) l = mid;
else r = mid;
}
cout << r << '\n';const double EPS = 1e-6;
int n, k; cin >> n >> k;
vector<int> arr(n);
for (auto &x : arr) cin >> x;
double l = 0, r = 1e9;
while (l + EPS < r)
{
double mid = (l + r)/2;
int cnt = 0;
for (const int x : arr) cnt += x/mid;
if (cnt < k) r = mid;
else l = mid;
}
cout << setprecision(6) << fixed << l << '\n';int n, x, y; cin >> n >> x >> y;
auto check = [&](int v)
{
v -= min(x, y);
if (v < 0) return (n == 0);
int copies = (n-1) - max(0LL, v/x) - max(0LL, v/y);
return (copies <= 0);
};
int l = 0, r = 1;
while (!check(r)) r *= 2;
while (l+1 < r)
{
int mid = (l + r)/2;
if (check(mid)) r = mid;
else l = mid;
}
cout << r << '\n';Searching takes O(1), Terminologies - Hashing, Hashfunction, Hashtable
Hashfunction requirements - Uniformly distributed, Easy to compute, minimize collision.
- Division Method: h(k) = k mod n where n is size of hashtable.
- Folding Method: divide in group of 2 and add like 123456 = 12+34+56 = 102 ignore 1 map it to 02
- Mid Square Method: 125 square is 15625 taking mid 56 (If non even digits then append zero at begining)
- MAD (Multiplication Addition & Division): h(k) = (a.k + b) % n
- Multiplication Method: (kA % 1)*n where A is golden ratio constant 0.618, 0 < A < 1
Closed Hashing (Open Addressing) - We don't utilize any thing extra then hash table everything is still mapped in it unlike linked list like ADT
Open Hashing
- Chaining: Using linked list like chain to store collisions.
Closed Hashing H(i) = (h(k) + f(i)) % n
- Linear Probing: f(n) = i
- Quadratic Probing: f(n) = i^2
We go for H(0) first if collision H(1) and so on.
The main problem with linear probing is clustering, many consecutive elements form groups and it starts taking time to find a free slot or to search an element.
Modulo n where n is there in good hash functions so that collision reduces.
https://www.youtube.com/watch?v=Y2AUhxoQ-OQ
Given p, q, r, s, t, u we want to find x
p_e^-x + q_sin(x) + r_cos(x) + s_tan(x) + t*x2 + u = 0
#include<bits/stdc++.h>
using namespace std;
int p, q, r, s, t, u;
#define EPS 1e-7
double f(double x) { return p*exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*x*x + u; }
// Bisection method
double bisection()
{
double l = 0, r = 1;
while (l + EPS < r)
{
double mid = (l + r)/2;
if (f(l) * f(mid) <= 0) r = mid;
else l = mid;
}
return (l + r)/2;
}
int main()
{
while (cin >> p >> q >> r >> s >> t >> u)
{
// Here f is a non-increasing function [0,1]
// So if signs are same then no solution
if (f(0) * f(1) > 0) cout << "No solution\n";
else cout << fixed << setprecision(4) << bisection() << '\n';
}
return 0;
}
// More efficient
double secant()
{
if (f(0) == 0) return 0;
for (double x0 = 0, x1 = 1; ;)
{
double d = f(x1)*(x1-x0) / (f(x1)-f(x0));
if (fabs(d) < EPS) return x1;
x0 = x1;
x1 = x1 - d;
}
}
// Most efficient
double fd(double x) // derrivative of f(x)
{
return -p*exp(-x) + q*cos(x) - r*sin(x) + s/(cos(x)*cos(x)) + 2*t*x;
}
double newton()
{
if (f(0) == 0) return 0;
for (double x = 0.5; ;)
{
double x1 = x - f(x)/fd(x);
if (fabs(x1-x) < EPS) return x;
x = x1;
}
}Ternary Search is also there which is same as binary search except instead of dividing in 2 parts we divide it in 3 parts.
Binary search is better than ternary search because
T(n) = T(n/2) + 2 [In Binary Search]
T(n) = T(n/3) + 4 [In Ternary Search]
in binary search:
Ternary search can find value for a bell shaped curve (unimodal function)
- Given array containing n+1 numbers of range: 1 to n (inclusive). There's 1 duplicate find it.
/* bruteforce (n^2) -> sorting (nlogn) -> hashing (requires space)
To do in O(1) space we want to store hashing info to the array itself.
Given range 1 to n and there are n+1 numbers we can maybe make a number
negative.
We can also get summation sm - n(n+1)/2 */
for (const int x : nums)
{
if (nums[abs(x)-1] < 0) return abs(x);
nums[abs(x)-1] *= -1;
}
/* If we are not allowed to modify the array, cycle detection
extending upon previous idea only [1, 2, 3, 4, 2] 1 points to ind 1, 2 to ind 2
1 -> 2 -> 3 -> 4 -> 2
| |
----------
cycle exists means thats the duplicate, using floyd cycle detection algo */
int slow = nums[0], fast = nums[nums[0]];
while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; }
fast = 0;
while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }
return slow;- Now more than 1 elements can occur twice others once. Find all such duplicate numbers
// Above idea only
vector<int> res;
for (const int x : nums)
{
if (nums[abs(x)-1] < 0)
res.push_back(abs(x));
else
nums[abs(x)-1] *= -1;
}
return res;
/* Extending above cycle detection idea. Instead of keeping visited
we are kinda caching it with cycling swaps. */
vector<int> res;
for (int i = 0; i < nums.size(); ++i)
{
while (nums[i] != i+1 && nums[i] != nums[nums[i]-1])
swap(nums[i], nums[nums[i]-1]); // swaping makes code O(N) time
}
for (int i = 0; i < nums.size(); ++i)
if (nums[i] != i+1) res.push_back(nums[i]);
return res;- Find one duplicate in sorted array, with [0, n] numbers (no number in between is missing)
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (arr[mid] == mid + 1) l = mid+1;
else
{
if (mid > 0 && arr[mid] == arr[mid-1]) return mid;
r = mid-1;
}
}int findPeakElement(vector<int> &nums)
{
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (nums[mid] > nums[mid + 1]) r = mid;
else l = mid + 1;
}
return l;
}int Solution::sqrt(int A)
{
if (A == 0) return 0;
if (A == 1 || A == 2 || A == 3) return 1;
int l = 0, r = A, ans = -1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (mid <= A / mid) l = mid + 1, ans = mid;
else r = mid;
}
return ans;
}class Solution
{
public:
int lower_bound(vector<int> &nums, int target)
{
int l = 0, r = nums.size() - 1;
if (nums[r] < target) return r + 1;
while (l < r)
{
int mid = l + (r - l) / 2;
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
return l;
}
vector<int> searchRange(vector<int> &nums, int target)
{
if (nums.size() == 0)
return {-1, -1};
int idx1 = lower_bound(nums, target);
int idx2 = lower_bound(nums, target + 1) - 1;
if (idx1 < nums.size() && nums[idx1] == target) return {idx1, idx2};
else return {-1, -1};
}
};/* If we look at middle, either all left side is sorted or right one is.
We can check that by checking first and last element of the partition */
int search(vector<int> &nums, int target)
{
int l = 0, r = nums.size() - 1;
while (l <= r)
{
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
// If there can be duplicates then add this cond.
// Eg: [3 1 2 3 3 3 3]
if (nums[l] == nums[mid] && nums[r] == nums[mid]) ++l, --r;
else if (nums[l] <= nums[mid])
{
if (nums[l] <= target && nums[mid] >= target) r = mid - 1;
else l = mid + 1;
}
else
{
if (nums[mid] <= target && nums[r] >= target) l = mid + 1;
else r = mid - 1;
}
}
return -1;
}// O(N) seat and O(logN) leave
int totalSeats;
set<int> locations;
ExamRoom(int N): totalSeats(N) { }
void leave(int p) { locations.erase(p); }
int seat() {
int posToUse = 0;
if (!locations.empty()) {
int optimalDistance = *locations.begin();
for (auto i = locations.begin(), j = next(locations.begin()); j != locations.end(); ++i, ++j) {
int distance = (*j - *i) / 2;
if (distance > optimalDistance)
optimalDistance = distance, posToUse = *i + distance;
}
int lastDistance = totalSeats - *prev(locations.end()) - 1;
if (lastDistance > optimalDistance)
optimalDistance = lastDistance, posToUse = totalSeats - 1;
}
locations.insert(posToUse);
return posToUse;
}
// O(logN) seat and O(logN) leave
int totalSeats;
set<int> locations;
// This set stores the future possibilities, idea is when we place a student there are
// two new possibilities, left or right that we create. pair stores [min_dist, -point]
// Pick one with highest distance and lowest index.
set<pair<int, int>, greater<pair<int, int>>> possibilities;
// Given two locations first & second, add candidate in the middle.
void addCandidate(int first, int second) {
int nextIndex = (first + second) / 2;
if (nextIndex != first)
possibilities.insert({min(abs(first - nextIndex), abs(second - nextIndex)), -nextIndex});
}
// Given two locations first & second, add candidate in the middle.
void deleteCandidate(int first, int second)
{
int nextIndex = (first + second) / 2;
if (nextIndex != first)
possibilities.erase({min(abs(first - nextIndex), abs(second - nextIndex)), -nextIndex});
}
ExamRoom(int N): totalSeats(N) { }
int seat() {
if (locations.empty()) {
locations.insert(0);
possibilities.insert({totalSeats-1, -(totalSeats-1)});
return 0;
}
// Take the best possibility, and place the student there.
// After taking the possbility, it cannot be used in future.
auto [minDistance, point] = *possibilities.begin();
point *= -1;
possibilities.erase(possibilities.begin());
// Taken choice, divides the vacant seats in two parts add them as possibility.
auto upperBoundLocation = locations.upper_bound(point);
if (upperBoundLocation != locations.end()) addCandidate(point, *upperBoundLocation);
if (upperBoundLocation != locations.begin()) addCandidate(point, *prev(upperBoundLocation));
locations.insert(point);
return point;
}
void leave(int p) {
locations.erase(p);
if (locations.empty()) {
possibilities.clear();
return;
}
// If a student leaves, it removes old small possibilities that were in left and right side.
// Instead a new bigger possibility comes in that place.
int nextIndex = -1, prevIndex = -1;
auto upperBoundLocation = locations.upper_bound(p);
if (upperBoundLocation != locations.end()) {
nextIndex = *upperBoundLocation;
deleteCandidate(nextIndex, p);
}
if (upperBoundLocation != locations.begin()) {
prevIndex = *prev(upperBoundLocation);
deleteCandidate(prevIndex, p);
}
// If initially there were two students one left now new set of possibilities exist at left & right
// side of that remaining student.
if (locations.size() == 1)
{
possibilities.clear();
int ind = *locations.begin();
if (ind != 0) possibilities.insert({ind, 0});
if (ind != totalSeats-1) possibilities.insert({totalSeats - 1 - ind, -(totalSeats-1)});
return;
}
// Need three cases 1) extreme left, 2) extreme right, and 3) middle.
if (p == 0) possibilities.insert({*locations.begin(), 0});
else if (p == totalSeats-1) possibilities.insert({totalSeats - 1 - *locations.rbegin(), -(totalSeats-1)});
else if (nextIndex >= 0 && prevIndex >= 0) addCandidate(prevIndex, nextIndex);
}int findMin(vector<int> &nums)
{
int l = 0, r = nums.size() - 1;
while (l < r)
{
if (nums[l] < nums[r])
return nums[l];
int mid = l + (r - l) / 2;
if (nums[mid] > nums[r]) l = mid + 1;
else r = mid;
// In case of equal instead of else, these 2 lines:
else if (nums[mid] < nums[l]) r = mid, l++;
else r--;
}
return nums[l];
}/* Binary search from min to max element of the matrix
upper bound works on sorted array only it tells how many
elements are lesser then or equal to specified Toh we check
mid se kam kitne elements he humeshaa
[1, 3, 5][2, 6, 9][3, 6, 9]
l = 1 r = 9 mid = 5
cur = 3 + 1 + 1 = 5
l = 1 r = 5 mid = 3
cur = 2 + 1 + 1 = 1
l = 4 r = 5 mid = 4
cur = 2 + 1 + 1 = 4
l = 5, r = 5 = ans 5(n*m+1)/2 is 5 which signifies upperbound
must be 5 for median but if matrix is like [[1, 1, 3, 3, 3, 3]]
our check for upperbound of 3 will not be (m*n+1)/2 although
it is clearly the median. But it clear if cur is greater then
count then our answer must be from l to mid and reverse in vice versa. */
int Solution::findMedian(vector<vector<int>> &A)
{
int l = INT_MAX, r = INT_MIN;
for (auto x : A)
for (int i : x)
l = min(l, i), r = max(r, i);
while (l < r)
{
int mid = l + (r - l) / 2;
int places = 0;
for (auto x : A)
places += upper_bound(x.begin(), x.end(), mid) - x.begin();
if (places < ((A.size() * A[0].size()) + 1) / 2)
l = mid + 1;
else
r = mid;
}
return l;
}
/* Suppose there's a very big array which cannot be stored as
one but only as 100 different arrays in sorted order each.
find the median of it as one collective array. The answer is to
treat it like a matrix and then simply do it. */// We can merge both lists using merge sort merge in O(n + m) time and then
// find the median. Can be done in O(1) space since we only care about finding median.
// Use two pointer, both initialized at zero and keep incrementing for smaller value
// until we reach middle position. Time: O(n + m) Space: O(1)
// Using binary search, idea is we find a point in smallest (or equal) array. Such that
// left part before that point and in larger array we can also find a pos (mathematically)
// such that right part after pos combine and form the middle part that will give median.
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
int l = 0, r = nums1.size();
while (l <= r) {
int mid = l + (r-l)/2;
// Find the partition of the larger array such that the sum of elements on
// left side of the partition in both arrays is half of the total elements.
int pos = ((nums1.size() + nums2.size() + 1) / 2) - mid;
int left1 = (mid > 0) ? nums1[mid - 1] : INT_MIN;
int right1 = (mid < nums1.size()) ? nums1[mid] : INT_MAX;
int left2 = (pos > 0) ? nums2[pos - 1] : INT_MIN;
int right2 = (pos < nums2.size()) ? nums2[pos] : INT_MAX;
// Verify if partition is valid by verifying if the largest number on the
// left side is smaller than the smallest number on the right side.
if (left1 <= right2 && left2 <= right1) {
return ((nums1.size() + nums2.size())&1) ?
max(left1, left2) : (double)(max(left1, left2) + min(right1, right2)) / 2;
}
else if (left1 > right2) r = mid - 1;
else l = mid + 1;
}
/*
Example for [1, 2, 3] - [1, 2, 5, 6]
l: 0, r: 4 mid: 1, pos: 3 l1: 1, r1: 2, l2: 5, r2: 6 X
l: 2, r: 4 mid: 3, pos: 1 l1: 3, r1: ∞, l2: 1, r2: 2 X
l: 2, r: 2 mid: 2, pos: 2 l1: 2, r1: 3, l2: 2, r2: 5
*/
return 0;
}/* Given boards and we have 3 painters: 100 200 300 400 500 | 600 700 | 800 900
This way each painter would have to: 1500 | 1300 | 1700 so variance is less
Way like calculating total paint and then dividing by k and trying to match
each partition as close to it could not evaluate all possibilities systematically
and thus do not always produce the correct solution. */
int partition(vector<int> &arr, int &k, int cur = 0, int cnt = 0)
{
if (cnt > k) return INT_MAX;
if (cur == arr.size())
return (cnt == k ? 0 : INT_MAX);
int sm = 0, res = INT_MAX;
for (int i = cur; i < arr.size(); ++i)
{
sm += arr[i];
res = min(res, max(sm, partition(arr, k, i+1, cnt+1)));
}
return res;
}
// It's O(K N^2) after memoization
// Binary Search Approach O(N log(sum of arr))
/* example - [1, 2, 3, 4, 5, 6, 7, 8, 9]
9-------45
low high
low is when there are n painters. high is when there is 1 painter
find mid = 27 find what mid corresponds to 1+2+3+4+5+6 and 7+8+9 this way array partitions
such that parts sum is less then mid. (2 parts)
6------2------1
low mid high
apply binary search on low and mid */
#define ll long long
bool isPossible(int painters, vector<int> &boards, int val)
{
ll count = 1, sum = val, i = 0;
while (i < boards.size())
{
if (sum - boards[i] < 0)
sum = val, count++;
else
sum -= boards[i++];
if (count > painters)
return false;
}
return true;
}
int Solution::paint(int A, int B, vector<int> &C)
{
ll l = 0, r = accumulate(C.begin(), C.end(), 0);
while (l < r)
{
int mid = l + (r - l) / 2;
if (isPossible(A, C, mid))
r = mid;
else
l = mid + 1;
}
return (l * B) % 10000003;
}double minmaxGasDist(vector<int> &stations, int k)
{
const double EPS = 1e-6;
auto check = [&](double x)
{
int cnt = 0;
for (int i = 1; i < stations.size(); ++i)
{
cnt += ceil((double)(stations[i] - stations[i-1]) / x) - 1;
if (cnt > k) return false;
}
return (cnt <= k);
};
double l = 0, r = EPS;
while (!check(r)) r *= 2;
while (l + EPS < r)
{
double mid = (l + r)/2;
if (check(mid)) r = mid;
else l = mid;
}
return r;
}int minimizedMaximum(int n, vector<int>& quantities) {
function<bool(int)> check = [&](int x) -> bool {
int cnt = 0;
for (int quantity: quantities)
cnt += ceil((double)quantity / x);
return cnt <= n;
};
int l = 1, r = *max_element(quantities.begin(), quantities.end());
while (l < r) {
int mid = l + (r-l)/2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}- Maximum Median: https://codeforces.com/contest/1201/submission/76923324
- Mafia: In a game in one round there is 1 moderator and rest n-1 people are player. Given an array of n people signifying times they want to be player. Tell minimum number of games they must play to fulfil that condition of atleast playing ai times. Solution: https://codeforces.com/contest/348/submission/76647058
- Multiplication Table - Easy binary search, initially our search space l = 1, r = n*m signifies our answer can be anything between 1 to n*m we are searching over value. For every mid we find count of items by iterating over row and finding <= mid count Solution: https://codeforces.com/contest/448/submission/74697633
- Hamburgers - Given a string denoting recipe of hamburger B means bun S means Sausage and C means cheese in order L to R. We already have nb ns nc amount already and can purchase addition at cost pb ps pc. What is maximum hamburger we can make given we have r amount. Solution: n[i] + x = cur * cnt[i], here cnt is cnt of that item required and x is additional item we want. We want to make cur amount of hamburger and want to see if it's possible. x = (cur*cnt[i] - n[i]) * p[i] will give additional cost we have to spend. Take care of case when that item is not at all reqd (cnt[i] = 0) and difference is negative. Finally also take care of binary search range, you cant make r 1e18 otherwise calculation will give ll overflow. https://codeforces.com/contest/371/submission/74009612
- Present - Given 3 integers n, m, w and an array of n numbers denoting height of ith plant. We can choose a subsegment of length w and increase height by 1 it will require one operation (-1 of m) find maximal (minimum height) across array we can get. Solution: Apply binary search on value (x means we can form that maximal minimum height) Now check if it's possible. This part is main, reqd holds how much operation that element required and cur is carry over operation from previous subsegment. Pure greedy strategy. https://codeforces.com/contest/460/submission/76685479
- Renting Bikes - Given n, m, a : denoting n peoples m bikes available for renting and a (shared money they have) An array b denotes personal money ith person has. Another array p represents price of bike. What minimum sum of personal money will they have to spend in total to let as many schoolchildren ride bikes as possible? Solution: Greedy binary search type of problem. Check if we can give x people bikes (sort bike based on price in asc while people in desc based on personal money) Idea is for x person to have bike xth richest person must be able to afford it (that's why such sorting) then simple greedy check function. https://codeforces.com/contest/363/submission/76699115
- One-Dimensional Battle Ships - Given a 1 x n matrix where Alice placed k ships each of width a, there must be a gap of atleast 1 within each ship. Given m queries which bob will ask and Alice will tell if that place is a hit or miss, Alice always cheats and keep telling bob it's a miss find the first point at which Bob can tell Alice is lying. Solution: Binary search over the point which is our optimal answer point and check if it's optimal by using a fill like approach of simple dp. https://codeforces.com/contest/567/submission/76719058
- Memory for Arrays - Really a nice problem, Given two arrays a and b of size n and m respectively. Array a denotes free space which needs to be allocated by task in array b. Array b is in bit (so 3 means it require 8 space) If there are two processes of 2, 2 (means require 8-8 space) one block of 16 can be used there. Find maximum task we can finish. Solution: Create a allocation table with rows 0, 1, 2.. means 2^0 can fit how many in given situation then we can apply greedy in reverse manner keeping track of used space (multiplying it by 2) https://codeforces.com/contest/309/submission/76757279
- Degenerate Matrix - Solution involve finding a point x (using binary search) such that a +- x, b +- x, c +- x, d +- x denotes new matrix which should give determinant zero and d should be minimal. Now in the code we return true if det = 0 but for > 0 and < 0 we mark a variable true that's because simple det=0 will detect peak point we want to if x gives true then x-1 also give true in that case our condition will hold https://codeforces.com/contest/549/submission/76795248
- R2D2 and Droid Army - Solution involves binary search over optimal length using maximum window search technique using deque in linear time over each of 5 columns to see if it's possible to pick such length. https://codeforces.com/contest/514/submission/76804227
- New Year Snowmen - Binary Search over pair_count and maximize it. Sort our array in ascending order and inside check function distribute numbers (taken linearly) from array to mid x 3 ans matrix in column major form such that mat[i][0] < mat[i][1] < mat[i][2] is satisfied for all i. Call check function last time before printing values since some false check might have changed ans values. https://codeforces.com/contest/140/submission/76955210
- K-Dominant Character - Binary search to minimize optimal subarray length, now the problem becomes given a length x find if all string subarrays of that length has anything in common. Maintain a table storing frequency of characters for window ending at i (of length x) In the end we just need to check for each char if all of them are > 1 if none of 26 chars hold that that means there's nothing common. https://codeforces.com/contest/888/submission/76990330
- Road to Cinema - Binary search over volume (from minVal-1 to maxVal+1 because while(l+1 < r) searches from (l, r) exclusive) We want to see if we can make it with minimum volume fuel tank and then later pick the one corresponding to minimum price for that volume. Our check function sees adjacent distance. If dist > x i.e. distance is greater than available fuel we cannot reach otherwise min(x, dist-x) denotes minimum kilometers accelerated mode we used. So in the end checking it with time we have. https://codeforces.com/contest/729/submission/77025244
- Energy Exchange - Binary search over the final equalized values that we can make then check it by greedily iterating over desc order sorted array and performing operations. https://codeforces.com/contest/68/submission/77031113
- Three Base Stations - Binary search over the optimal value of d and try to minimize it, in check greedily place the tower right after (+ d) of an uncovered area. Do keep in mind that in
while (i < arr.size() && arr[i] < end)Writing arr[i] <= end would have given WA because of weird floting point precision thing in c++ so check = condition in next line using abs and EPS logic. https://codeforces.com/contest/51/submission/77035869 - Frodo and Pillows - https://codeforces.com/contest/760/submission/77058869
- String Game - https://codeforces.com/contest/779/submission/77066382
- Success Rate - Interesting problem, new x is k*p same with y, new y = k*q. Applying binary search on k (on anything else will not lead to monotonicity) x' = p*k = x + succ i.e. succ = p*k - x simmilarly y' = q*k = y + succ + unsucc i.e. unsucc = q*k - y - succ https://codeforces.com/contest/807/submission/77076898
- Motorack's Birthday
/* Apply ternary search on values then replace every -1 with that
value and find corresponding adjacent element diff (we have to
minimize this) this function is bell shaped. */
int solve(vector<int> &arr, int x)
{
int ans = 0;
for (int i = 1; i < arr.size(); ++i)
{
int p = (arr[i-1] == -1) ? x : arr[i-1];
int q = (arr[i] == -1) ? x : arr[i];
ans = max(ans, abs(p-q));
}
return ans;
}
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> arr(n);
for (auto &x : arr) cin >> x;
int l = 0, r = 1e9;
while (l+3 <= r)
{
int a = l+(r-l)/3, b = r-(r-l)/3;
if (solve(arr, a) > solve(arr, b)) l = a;
else r = b;
}
int ans = solve(arr, l), pt = l;
for (int i = l+1; i <= r; ++i)
{
int cur = solve(arr, i);
if (cur < ans) ans = cur, pt = i;
}
cout << ans << " " << pt << '\n';
}
return 0;
}- Mixing Water - Given 3 values in each test case h, c, t. You can put hot cold hot cold order to minimize abs diff between final tmp and t.
// Apply ternary search to minimize the function
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t;
while (t--)
{
double h, c, d; cin >> h >> c >> d;
auto func = [&](double mid)
{
double q = (mid*h + mid*c + h) / (2*mid + 1);
if (mid == 0) return fabs(q-d);
double p = (mid*h + mid*c) / (2*mid);
return min(fabs(p-d), fabs(q-d));
};
int l = 0, r = 1e13;
while (l+1000 <= r)
{
int a = l + (r-l)/3, b = r - (r-l)/3;
if (func(a) > func(b)) l = a;
else r = b;
}
double ans = func(l);
int pt = l;
for (int i = l+1; i <= r; ++i)
{
double cur = func(i);
if (cur < ans) ans = cur, pt = i;
}
double q = (pt*h + pt*c + h) / (2*pt + 1);
if (pt == 0) { cout << 2*pt+1 << "\n"; continue; }
double p = (pt*h + pt*c) / (2*pt);
if (fabs(p-d) < fabs(q-d)) cout << 2*pt << '\n';
else cout << 2*pt+1 << '\n';
}
return 0;
}