Then change max element and continue.
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
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;
Idea:
Invariance in the problem: Sum of distances of mice.
In a round robin tournament, what is the maximum number of wins player ranked k can have?
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
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.
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!
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!
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.
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.