If $$$k$$$ is greater or equal to $$$2$$$ you can always swap adjacent elements.

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int arr[n];
        for(int i = 0;i < n;i++){
            cin>>arr[i];
        }
        if(is_sorted(arr,arr+n) || k > 1){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
    return 0;
}

Good

Mid

Bad

Think of each bit independently.

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int m[n][n];
        int arr[n];
        for(int i = 0;i < n;i++){
            arr[i] = (1<<30) - 1;
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                cin>>m[i][j];
                if(i != j){
                    arr[i] &= m[i][j];
                    arr[j] &= m[i][j];
                }
            }
        }
        bool ok = true;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                if(i != j && (arr[i] | arr[j]) != m[i][j]){
                    ok = false;
                }
            }
        }
        if(!ok){
            cout<<"NO\n";
        }
        else{
            cout<<"YES\n";
            for(int i = 0;i < n;i++){
                cout<<arr[i]<<" ";
            }
            cout<<"\n";
        }
    }
}

Good

Mid

Bad

Think of suffixes.

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int arr[n];
        long long suf[n+1] = {0};
        for(int i = 0;i < n;i++){
            cin>>arr[i];
        }
        for(int i = n-1;i >= 0;i--){
            suf[i] = suf[i+1] + arr[i];
        }
        long long ans = suf[0];
        for(int i = 1;i < n;i++){
            if(suf[i] > 0){
                ans += suf[i];
            }
        }
        cout<<ans<<"\n";
    }
}

Good

Mid

Bad

Try using greedy to construct the answer bit by bit.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
ll T[LIM], P[LIM], n, k;
void solve() {
  rep(i, n) T[i]=P[i];
  ll ans=0;
  for(ll i=60; i>=0; --i) {
    ll sum=0;
    rep(j, n) {
      if(T[j]&(1ll<<i)) continue;
      ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i);
      p+=ans^(p&ans);
      sum+=p-T[j];
      if(sum > k){
          break;
      }
    }
    if(sum>k) continue;
    rep(j, n) {
      if(T[j]&(1ll<<i)) continue;
      ll p=(T[j]/(1ll<<i))*(1ll<<i)+(1ll<<i);
      p+=ans^(p&ans);
      T[j]=p;
    }
    ans+=1ll<<i;
    k-=sum;
  }
  cout << ans << '\n';
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int q;
  cin >> n >> q;
  rep(i, n) cin >> P[i];
  while(q--) {
    cin >> k;
    solve();
  }
} 

Good

Mid

Bad

Try optimizing the greedy approach from $$$O$$$($$$n$$$) to $$$O$$$($$$1$$$).

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7;
ll dpsum[1<<20][20], dpcnt[1<<20], T[LIM];
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  ll n, q;
  cin >> n >> q;
  ll sto=0, sfrom=0;
  rep(i, n) {
    cin >> T[i];
    sto+=(1ll<<20ll)-T[i];
    sfrom+=T[i];
    ++dpcnt[T[i]];
    ll sum=0;
    rep(j, 20) {
      sum+=T[i]&(1ll<<j);
      dpsum[T[i]][j]+=sum;
    }
  }
  rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) dpcnt[j]+=dpcnt[j+(1<<i)];
  rep(i, 20) rep(j, 1<<20) if(!(j&(1<<i))) rep(l, 20) dpsum[j][l]+=dpsum[j+(1<<i)][l];
  while(q--) {
    ll k;
    cin >> k;
    if(k>=sto) {
      k+=sfrom;
      cout << k/n << '\n';
      continue;
    }
    ll ans=0;
    for(ll i=19; i>=0; --i) {
      ll x=(n-dpcnt[ans|(1<<i)])*(1ll<<i);
      x-=dpsum[ans][i]-dpsum[ans|(1<<i)][i];
      if(x<=k) {
        k-=x;
        ans|=1<<i;
      }
    }
    cout << ans << '\n';
  }
}
 

Good

Mid

Bad

Do mod $$$2$$$ in all coordinates and see how many different types of points you have in the end.

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int sx,sy;
        cin>>sx>>sy;
        int x[n],y[n];
        set<int>p[2];
        for(int i = 0;i < n;i++){
            cin>>x[i]>>y[i];
            p[(x[i] % 2) ^ (y[i] % 2)].insert(i+1);
        }
        int v = (sx % 2) ^ (sy % 2);
        if(p[v].size() >= p[v^1].size()){
            cout<<"First"<<endl;
            v ^= 1;
            for(int i = 0;i < n;i++){
                if(i % 2 == 0){
                    int j;
                    if(!p[v].empty()){
                        j = (*p[v].begin());
                        p[v].erase(j);
                    }
                    else{
                        j = (*p[v^1].begin());
                        p[v^1].erase(j);
                    }
                    cout<<j<<endl;
                }
                else{
                    int j;
                    cin>>j;
                    if(p[0].count(j)){
                        p[0].erase(j);
                    }
                    else{
                        p[1].erase(j);
                    }
                }
            }
        }
        else{
            cout<<"Second"<<endl;
            for(int i = 0;i < n;i++){
                if(i % 2 == 1){
                    int j;
                    if(!p[v].empty()){
                        j = (*p[v].begin());
                        p[v].erase(j);
                    }
                    else{
                        j = (*p[v^1].begin());
                        p[v^1].erase(j);
                    }
                    cout<<j<<endl;
                }
                else{
                    int j;
                    cin>>j;
                    if(p[0].count(j)){
                        p[0].erase(j);
                    }
                    else{
                        p[1].erase(j);
                    }
                }
            }
        }
    }
}

Good

Mid

Bad

Use binary search the answer and 2-sat.

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
vector<vector<ll> >adj,rev;
vector<ll>order;
vector<ll>vis,comp;
ll c;
ll cur;
ll val(ll idx,bool v){
    return cur + (2 * idx + v);
}
void dfs1(ll idx){
    vis[idx] = true;
    for(auto x:adj[idx]){
        if(!vis[x]){
            dfs1(x);
        }
    }
    order.pb(idx);
}
void dfs2(ll idx){
    comp[idx] = c;
    for(auto x:rev[idx]){
        if(!comp[x]){
            dfs2(x);
        }
    }
}
void build(ll s,ll e,ll idx){
    if(s == e){
        adj[idx].pb(val(s,0));
        rev[val(s,0)].pb(idx);
        return;
    }
    ll mid = (s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);
    adj[idx].pb(idx*2);
    adj[idx].pb(idx*2+1);
    rev[idx*2].pb(idx);
    rev[idx*2+1].pb(idx);
}
void update(ll s,ll e,ll qs,ll qe,ll idx,ll k){
    if(qs <= s && e <= qe){
        adj[val(k,1)].pb(idx);
        rev[idx].pb(val(k,1));
        return;
    }
    if(s > qe || qs > e){
        return;
    }
    ll mid = (s+e)/2;
    update(s,mid,qs,qe,idx*2,k);
    update(mid+1,e,qs,qe,idx*2+1,k);
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m;
        ll u[m],v[m];
        f(i,0,m){
            cin>>u[i]>>v[i];
        }
        ll l = 1,r = n;
        ll ans = 1;
        cur = 4*n;
        while(l <= r){
            ll mid = (l+r)/2;
            order.clear();
            vis.assign(6*n+5,0);
            comp.assign(6*n+5,0);
            adj.assign(6*n+5,vector<ll>());
            rev.assign(6*n+5,vector<ll>());
            f(i,0,m){
                adj[val(u[i],0)].pb(val(v[i],1));
                adj[val(v[i],0)].pb(val(u[i],1));
                rev[val(u[i],1)].pb(val(v[i],0));
                rev[val(v[i],1)].pb(val(u[i],0));
            }
            build(1,n,1);
            f(k,1,n+1){
                ll l = max(1,k - mid + 1),r = k-1;
                update(1,n,l,r,1,k);
                l = k+1;
                r = min(n,k + mid - 1);
                update(1,n,l,r,1,k);
            }
            bool ok = true;
            c = 1;
            f(i,1,n+1){
                if(!vis[val(i,0)]){
                    dfs1(val(i,0));
                }
                if(!vis[val(i,1)]){
                    dfs1(val(i,1));
                }
            }
            reverse(order.begin(),order.end());
            for(auto x:order){
                if(!comp[x]){
                    dfs2(x);
                    c++;
                }
            }
            f(i,1,n+1){
                ok &= comp[val(i,0)] != comp[val(i,1)];
            }
            if(ok){
                l = mid + 1;
                ans = max(ans,mid);
            }
            else{
                r = mid - 1;
            }
        }
        cout<<ans<<"\n";
    }
}

Good

Mid

Bad

Assume that cells $$$i-1$$$, $$$i$$$, and $$$i+1$$$ are covered in water. What happens if you remove water from cell $$$i$$$?

The water at position $$$i$$$ is replaced as both cells $$$i-1$$$ and $$$i+1$$$ have water in them.

Read the hints.

If there are 3 consecutive empty cells $$$i-1$$$, $$$i$$$, $$$i+1$$$, we can place water in cells $$$i-1$$$ and $$$i+1$$$ and then move water from cell $$$i$$$ to all other cells. If there are no such cells, we have to place water on every empty cell.

So if we find substring ''...'' in the array, the answer is $$$2$$$, otherwise the answer is the number of empty cells.

Time and memory complexities are $$$O(N)$$$.

Solve the problem if it is required that each cell is filled with water, or next to at least $$$1$$$ cell that is filled with water.

Check if only digits $$$1$$$ can remain. The situation is similar for checking if only digits $$$2$$$ or only digits $$$3$$$ can remain.

Try to find something that stays the same after each operation.

Look at the parity of the numbers.

The parity of each number changes after an operation. That means that if $$$2$$$ numbers have the same parity, they will always have the same parity. If they had different parity, their parities stay different.

Read the hints.

If the parity of $$$b$$$ and $$$c$$$ is not the same, then it is impossible for only digits $$$1$$$ to remain on the board, as it would require $$$b = c = 0$$$. Otherwise, the following construction will leave only digits $$$1$$$ on the board.

First remove digits $$$2$$$ and $$$3$$$ and write digit $$$1$$$ while $$$b>0$$$ and $$$c>0$$$. If $$$b=c$$$, then we are done. Otherwise, without loss of generality assume $$$b>c$$$. That means that after the operations $$$c=0$$$ and $$$b$$$ is even (Because $$$b$$$ and $$$c$$$ are the same parity). Now we perform the following $$$2$$$ operations $$$\frac{b}{2}$$$ times to get only digits $$$1$$$ left. Remove digits $$$1$$$ and $$$2$$$ and add digit $$$3$$$. After that remove digits $$$2$$$ and $$$3$$$ and add digit $$$1$$$. An effective change of these $$$2$$$ operations is the reduction of $$$b$$$ by $$$2$$$.

Time and memory complexities are $$$O(1)$$$.

Come up with a problem that uses a similar idea and try to solve it. A lot of beginner problems use a similar idea.

Solve the problem if all of the characters on vertices are 'U'.

We can run DFS from the root. Using it we can calculate the number of edges that we have to traverse to get to every edge. Just output the smallest value among all the leaves.

Modify the DFS such that it takes into account that traversing some edges does not require an operation.

Add weights to the edges.

Read the hints.

We will make edges from a vertex to its children. The weight of that edge will be $$$1$$$ unless one of the following holds:

• The weight of an edge between a vertex and its left child will be $$$0$$$ if the letter written on that vertex is 'L'.

• The weight of an edge between a vertex and its right child will be $$$0$$$ if the letter written on that vertex is 'R'.

Now we run a modified DFS to find the distance of each vertex from the root, but with weighted edges. We output the minimal value among all the leaves.

Time and memory complexities are $$$O(N)$$$.

Solve the problem if after reaching a leaf, Keksic can teleport to any other leaf that he chooses and then needs to get back to the root, or report that it is impossible for him to complete such a travel.

Let $$$m$$$ be the biggest value in the array. Calculate array $$$x$$$ such that $$$x_i$$$ ($$$1 \le i \le m$$$) is the number of triples which have $$$\gcd$$$ of $$$i$$$. Then the answer is the sum of $$$i \cdot x_i$$$ over all $$$i$$$ ($$$1 \le i \le m$$$).

Value of $$$\lfloor \frac{m}{1} \rfloor + \lfloor \frac{m}{2} \rfloor + \lfloor \frac{m}{3} \rfloor + \ldots + \lfloor \frac{m}{m} \rfloor$$$ is around $$$m log m$$$.

We calculate $$$x_i$$$ from $$$x_m$$$ to $$$x_1$$$. For some $$$i$$$, we can first calculate the number of triples that have a value of function $$$f$$$ that is an integer multiple of $$$i$$$, and then from it subtract $$$x_{2i}, x_{3i}, x_{4i} \ldots$$$. Because of the previous hint, the subtractions will be quite fast.

Now the question is how to calculate the number of triples that have a value of function $$$f$$$ that is an integer multiple of $$$i$$$.

Numbers up to $$$100\,000$$$ can have at most $$$128$$$ divisors.

As the order in which numbers are given does not matter, we can sort the array. Now for each number $$$d$$$ ($$$1 \le d \le M$$$) store indices of all numbers that are divisible by $$$d$$$ in an array of vectors. Now we will for each number $$$d$$$ ($$$1 \le d \le m$$$) count the number of triples.

To find the number of triples that have a gcd value that is an integer multiple of $$$d$$$, we can do the following. We go over the index of the number that will be value $$$b$$$ in the function. We can utilize the vectors we calculated in the previous step for that. Say that the current index is $$$i$$$. Then for value $$$c$$$ we can pick any number with an index larger than $$$i$$$ as the array is sorted. For value $$$a$$$, we can pick any of the numbers divisible by $$$d$$$ with an index less than $$$i$$$, the number of which we can get from the vector. By multiplying those $$$2$$$ numbers we get the number of triples that have $$$a_i$$$ as their middle value.

As numbers can have up to $$$128$$$ divisors, the step above is quite fast.

Total time complexity is $$$O(m log m + n log n + 128 \cdot n)$$$. Total memory complexity is $$$O(m + 128 \cdot n)$$$.

Solve the problem if $$$f(a,b,c) = \gcd (a,c)$$$.

Try to simplify graph $$$H$$$.

Look at strongly connected components of $$$G$$$, and what happens with them.

Use dp to find the answer.

The main observation is what $$$H$$$ looks like. All the strongly connected components (SCC) in $$$G$$$ will become fully connected subgraphs in $$$H$$$. Secondly, take any two vertices $$$a$$$ and $$$b$$$ such that $$$a$$$ and $$$b$$$ are not in the same SCC. We can let $$$S_a$$$ be a set of vertices that are in the same SCC as $$$a$$$ ($$$a$$$ included). Similarly, $$$S_b$$$ is a set of vertices that are in the same SCC as $$$b$$$. If there is an edge going from $$$a$$$ to $$$b$$$, then for any two vertices $$$x$$$ and $$$y$$$ such that $$$x$$$ belongs to $$$S_a$$$ and $$$y$$$ belongs to $$$S_b$$$, there is an edge going from $$$x$$$ to $$$y$$$. Both of the previously stated facts about the graph can be proven by induction.

Now, let's say that there is the longest path that goes through at least one vertex of an SCC. Then that path goes through all the vertices in the SCC, due to all vertices in SCC being connected to the same vertices outside the SCC and due to the fact that SCC is a complete subgraph.

Now we can construct the graph $$$H'$$$. Each of the SCCs from $$$H$$$ will be a vertex in $$$H'$$$. The number on the vertex will be equal to the sum of all numbers on the vertices of the SCC that it was constructed from. Edges between two new vertexes will be added if there is an edge between their original SCCs. The edge will have a weight equal to the size of the SCC that it is going into. An additional vertex will be added at index $$$0$$$ and an edge will be made between it and all other vertices with $$$0$$$ ingoing edges. Weight will be determined based on the size of the SCC of the vertex that the edge is going into.

Due to the previous observations, the answer for the $$$H'$$$ will be the same as the answer for the $$$H$$$. However, notice that $$$H'$$$ is a DAG. That means that the answer for it can be computed using DP after topological ordering.

Total time and memory complexity is $$$O(n)$$$.

We will define the value of the path as the biggest value of a vertex on the path. Among the values of all the longest paths, find the median one. It is guaranteed that there are at most $$$10^{18}$$$ longest paths starting from each node. (So basically, you can ignore overflow in the number of paths) The rest of the constraints are the same.

Solve the problem for $$$q=1$$$.

We can just simulate the process. Each operation removes at least half of the elements, meaning that we will perform at most $$$log n$$$ operations.

Solve the problem if each $$$l_i = 1$$$. So basically, solve the problem for each prefix.

Keep values that are in the array after $$$1$$$, $$$2$$$, $$$3$$$, $$$\cdots$$$, $$$log n$$$ operations. Let's call those array's layers. Layer $$$0$$$ is an array after $$$0$$$ operations, layer $$$1$$$ after $$$1$$$ operation, and so on. When we add a value to the end of the layer, only $$$1$$$ number that was previously local extreme (local minimum or maximum, depending on layer) might unbecome local extreme if the new value becomes local extreme. So we can just propagate this update to all layers.

Try to simulate the process of updating described in hint $$$4$$$. Also, notice that if the array is longer than $$$3$$$, we can handle prefix and suffix updates separately.

Read the hints.

Now we will precompute and store the array after each operation on the entire permutation. We will call those array layers.

We can now solve queries in $$$O(log n)$$$.

If a query involves a small number of elements, we can just brute force it. Otherwise, we do the following:

Now let's define our queries a bit differently. We are given some array $$$x$$$, which will be a subarray of some layer, and $$$2$$$ values, $$$a$$$ and $$$b$$$. We will get array $$$y$$$ by appending $$$a$$$ to the start of $$$x$$$ and appending $$$b$$$ to the end of $$$x$$$. We are interested in the value of $$$f$$$($$$y$$$). It is easy to see that all queries involving $$$3$$$ or more elements can be converted into the modified query.

If $$$|y|$$$ is small, we can just brute force it. Otherwise, we can transform it into a query on the next layer in constant time, or in $$$O(log n)$$$.

Now, the first thing to notice is that all elements in $$$x$$$ that are neither first nor last will be deleted only if they were deleted when we performed operations on the whole permutation. That means that they will represent some interval on the next layer, let's call it $$$z$$$. (That interval can be found either with binary search or in $$$O(1)$$$ with precomputation) It holds that $$$ |z| $$$ is around half of $$$|x|$$$. Now, notice that among $$$a$$$ and the first element of $$$x$$$, there has to be at least one deletion. The same goes for the last element of $$$x$$$ and $$$b$$$.

So now we have transformed the query onto the next level in $$$O(1)$$$, or $$$O(log n)$$$. As we will do at most $$$O(log n)$$$ such transformations, the complexity of a single query is either $$$O(log n)$$$ or $$$O(log^2 n)$$$ depending on the way we find the next interval, both of which should be fast enough to pass.

Total time complexity: $$$O(n + q log n)$$$ or $$$O(n + q log^2 n)$$$. Total memory complexity: $$$O(n+q)$$$

Imagine that you already decided for each layer which indices will be on it. Come up with a generator that will uniformly randomly pick one permutation that satisfies those conditions.