Topics
A = {H1, H2, H3,…,HN-1,HN}.
void solve(vector<int> &H){
H.eb(0);
int n = sz(H);
stack<int> s;
s.push(H[0]);
int i=0;
while(i<n){
if(s.empty() or H[s.top()]<=H[i]) s.push(i++);
else{
int y = s.top();
s.pop();
int height = H[y];
int width = s.empty() ? i : i-s.top()-1;
ans = max(ans, height*width);
}
}
}
Take max and min and increase that. Check the distance between two consecutive points. Observe the interval eg. https://codeforces.com/contest/1695/submission/164965524
https://www.geeksforgeeks.org/job-sequencing-problem/ (Nice. nlogn solution using Max Heap)
Problem : Given a matrix whose elements are taken as a combination from a array i.e M[i][j] = a[i] op a[j]. How do you find max sum taking m elements from the matrix?
Solution Idea: Lets fix, min pair sum in the final list i.e a[i] + a[j] and maximize over it using Binary Search s.t total such element >= m (monotonic function). So now we got mid <= a[i] + a[j] for all i,j present in the optimal list. Observe (mid + 1) cannot deliver >= m elements. So we should take all elements greater than (m+1) and fill the remaining with pair sum = mid. Why does this work?
With pair sum = mid, observe [p1, p2, p3, p4, ….. pH] where H>=m elements. With pair sum = mid + 1, observe [q1, q2, q3, ….qJ] where J < m elements.
Also set Q is suffix of set P. So all extra elements cannot be mid + 1, as max sum element is J. But we can greedily say there are (m-J) elements with pair_sum = mid from the set P.
Given any array [a[1], a[2], a[3], a[4], ….a[N]], an element val and a given range [l…r]. What is the frequency of val in [l..r]?
Ans : Create a array of vectors g[val] -> vector
Ans : lower_bound (r+1) - lower_bound (l)
For type = pair<int, pair<int,int»
vector
UB = upper_bound(all(a), mp(target, mp(INF, INF)));
LB = lower_bound(all(a), mp(target, mp(-INF, -INF)));
Problems: - https://codeforces.com/problemset/problem/1852/A (Ntaris’s set, Nice Idea with backward simulation)
For problems, where there are multiple linear graphs with varying slope and your result is a sum of all such graphs, say ans = g1(x) + g2(x) + … + gm(x). If you need to iterate across n points and find the value of the function at n points, brute force approach is calculate for each point, value of each function, so total complexity is O(n*m).
You can optimize this by observing that ans[i] has correlation with ans[i-1] in terms of how slopes changes. In general if the functions are perfectly linear, you could store m_total = m_1 + m_2 + m_3 + m_4 … m_N. In each iteration i you can just increase the value by m_total.
Now if the slopes for each of g_i changes at some point, mark the “inflection” points and how the slope changes. When you are at the inflection point change the value accordingly. In general to achieve this store two maps:
Ex. https://atcoder.jp/contests/abc268/tasks/abc268_e
Some problems become more tractable if you just change the origin, or perform a linear transformation.
Ex. https://codeforces.com/contest/1909/problem/D
For problems where you need to replace a segment of an array with its median, it is sometimes good to transform the array into boolean form. Consider any element x. If at last you need x in the array then all elements less than x are sort of equivalent and all elements more than x are equivalent. Also after transforming the array into 0s and 1s (elements >= x), array can be further compressed. 010 can be compressed to 0 without affecting 0, 1 count. So finally what remains is a snake pattern 0101010101 which is irreducible.
https://www.codechef.com/problems/OPME
Idea is to sort the array, then consider only the inequality x1 + x2 > x3 in the sorted array.
https://www.codechef.com/problems/CNTTRIANGLE https://codeforces.com/contest/1991/problem/F
In some problems you have to achieve a sum of S, from the set of permutations [1,2,…..N].
To solve such problems, consider the prefix sums,
[1+2+3+….+x] where x is the least number such that sum (1…x) > S. Sum cannot exceed by more than equal to x.
So sum(1...x) - S
is less than x. Just remove a number y = sum(1...x) - S
to achieve S. Hence you can always achieve S if S <= C(n+1,2).
https://www.codechef.com/problems/STACKED
Given a graph problem on average path sum, you can assume the average is x and reduce the problem.
Example: https://atcoder.jp/contests/abc324/tasks/abc324_f