Proving greedy approaches [Invariance+Extremal Principle]
Problem: 1 https://codeforces.com/contest/1579/problem/D
Coming up with optimal solution is ez, proving it is hard. Here goes my proof. </br>
Case 1: If S = sum of all elements, and S/2 <= max. element. We can show that max #operations is (S-max. element). </br>
Argue by showing that max element can pair with max S-max. element. Rest all can be paired fullest. We can’t do better!! </br>
Case 2: If S/2 > max. element we show that we can follow a process as goes below: </br>
Choose a max element from the set, and reduce it by any(random other) element from the set till it is not maximum. </br> Then change max element and continue. </br>
Let any configuration be (S,max. ele). We only change when max. (max. ele-t) >= a[x], the new configuration is (S-2t,a[x]). </br>
Invariance is: S/2 > max. ele, in the new configuration, (S-2t)/2 = (S/2-t) > max. ele-t >= a[x], hence (S-2t,a[x]) maintains invariance. </br>
Only thing remaining to see is that with such a invariance condition, we can always get an operation. Hence a[x] goes to 0. </br>
Ans = S/2
A more intuitive proof for case 2. Assume that sum of the remaining element is more than the maximum element. We claim that we can always bring down the sum of the remaining element down to the maximum element and then we are done(trivial!). Only configuration which can’t be reduced is [0,0,0,0,0,x], we can’t bring it down to max means x>max. which is not possible
Problem-2 https://www.codechef.com/problems/SWAPGAME
Consider two elements a and b. a and b will only add to the value if their order gets swapped.
Problem-3 https://codeforces.com/contest/540/problem/E
Use PBDS/Fenwick Tree + Coordinate Compression
cin >> n;
vector<pair<int,int>> A;
vector<int> v;
for(int i=0;i<n;i++){
int a,b;
cin >> a >> b;
A.eb(mp(a,b));
v.eb(a);
v.eb(b);
}
sort(all(v));
v.erase(unique(all(v)),v.end()); // remove the duplicate elements
map<int,int> coor;
for(int i=0;i<sz(v);i++) coor[v[i]] = i;
vector<int> perm(sz(v));
iota(all(perm),0);
for(int i=0;i<n;i++){
int coor_x = coor[A[i].fi], coor_y = coor[A[i].se];
int tmp = perm[coor_x];
perm[coor_x] = perm[coor_y];
perm[coor_y] = tmp;
}
ll ans=0;
for(int i=0;i<sz(v);i++) ans += abs((ll) v[perm[i]]- (ll) v[i])-abs((ll) perm[i]-(ll)i);
ordered_set os;
for(int i=sz(v)-1;i>=0;i--){
ans += os.order_of_key(perm[i]);
os.insert(perm[i]);
}
cout << ans << endl;
Problem 4: https://codeforces.com/contest/1593/problem/C
Idea: <li> Claim: If there is a set of mice with their distances from hole sum to R and R < n. We can save all those mices. <li> Greedily to maximize m (#mice), we choose to reduce each distances in a sorted fashion hence selecting from end makes sense. <li> Proof: If R >= n then, <li> We can’t save all mice. Why? Let say we saved m-1 mice in time q. So position of cat = q & position of mth mice= R-q. R >=n so, R-q >= n-q. R-q+q >=n. Mice will be chased. <li> Consider R < n. Consider leftmost mice be positioned at l. So, R < n => R-(n-l) < l. So when all the other cats reaches the hole, cat is still behind leftmost mice. So can be saved.
Invariance in the problem: Sum of distances of mice.
Problem 5:
In a round robin tournament, what is the maximum number of wins player ranked k can have?
Claim 1: In a greedy way let every player ranked i>k loses vs every player j
Claim 2: No of wins left for top j<=k teams to disribute maintaining the condition= C(K,2). Kth player should win floor(C(K,2)/K) games among them.
https://codeforces.com/contest/1608/problem/C [Good greedy based problem]
Idea 2: Graph Based. Standard trick: if A[i]->[A[i+1],A[i+2],….] for all i, consider only the edges with consecutive
Problem 6:
https://codeforces.com/contest/1615/problem/C
Idea: Whenever there is some weird process going on, think about the bipartite-ness, if btw consecutive operations some structure remains intact. Then greedily solve for the varying part.
Problem 7:
https://codeforces.com/contest/1845/problem/D
Observations:
- At the point where you freeze the rating point K. After that some —-, +-..+., —–, ++.
- Simulate the process, it dips to K at some point(possibly no!).
- Consider the first and last such occurrence. say l,r
- It is as good as removing segment [l,r].
- So the Optimal answer is Total Sum - Sum of some subarray!
- Can we minimize the subarray? What is the value of K?
- K = pref[l-1].
- After r, it cannot go below K. If it goes there is some prefix r…N which is negative. So [l,r] is not the minimum subarray!
Problem 8:
https://codeforces.com/contest/1705/problem/D
Observations:
- Operation: Toggle x[i] if x[i-1] !=y[i+1] corresponds to x[i] -> x[i] ^ x[i-1] ^ x[i+1]
- Consider : {x1, x2, x3, x4, x5, x6, x7} and the transformed array : {x1 ^ x2, x2 ^ x3, x3 ^ x4, … so on}. Bijection exists under the transformation.!
- Toggle corresponds to swap’ing adjacent elements in the transformed array.
- So just compare the transformed array. (classical)
Intuition:
- Check an example pattern: 000000100000110111101111001010101001001001111001
- How does the pattern transform?
- 00000011000000011000
- 001111111000000011000
- 001 -> 011
- 100 -> 110
- 01s and 10s are invariants. (Spotting the invariance is the key)
- Every 01 gets mapped in sorted fashion between initial and final string!
Problem 9:
https://codeforces.com/problemset/problem/1852/B
Main Idea: If the constraint is such that (a + b > 0) count matters and ab != 0. Then a transformation exists to preserve this constraints. Ex. -2 -3 -3 -3 5 5 5 5. You can flatten this array to have only distinct integers. Why it works because it only matters the order of two absolute values and signs. Preserve the sign!, As for absolute values, if you flatten, the order of the values remain same!.
Once you have this next idea is simple is to attack the problem extremally.
Problem 10:
https://codeforces.com/problemset/problem/1704/D
Given a complicated process, try to find out some invariances. Think about prefix sums in this cases. Solution will be easy to find once you find out the invariances. Also for this problem it is good to think in terms of center of mass. Each operations moves a particle one to he left and one to the right so that the center of mass remains same.
Fun blogs around invariance : https://codeforcesc.com/blog/entry/130338
Few things to try in invariance under sorting problems:
- Check for inversion count, parity, odd / even etc.
- What happens if there is a duplicate element?
- Transform to prefix sum, difference arrays.
- Number of times things changes, parity.
https://brilliant.org/wiki/invariant-principle-definition/