Записи в блоге

Hint

Solution

Code - aryansanghi

//Written By Aryan Sanghi

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int main()
{
    ll t;
    cin>>t;

    while(t--)
    {
        ll l1, b1, l2, b2, l3, b3;
        cin>>l1>>b1>>l2>>b2>>l3>>b3;

        if(l1+l2+l3 == b1 && b1==b2 && b2==b3) cout<<"YES\n";
        else if(l2+l3 == l1 && b2==b3 && b1+b2==l1) cout<<"YES\n";
        else if(b1+b2+b3 == l1 && l1==l2 && l2==l3) cout<<"YES\n";
        else if(b2+b3 == b1 && l2==l3 && l1+l2==b1) cout<<"YES\n";
        else cout<<"NO\n";
    }
}

Code - harshith_04

#include <iostream>
using namespace std;
 
int main(){
    int t;
    cin >> t;
    
    int l1, b1, l2, b2, l3, b3;
    
    auto check = [&] () {
        if (l1 == l2 && l2 == l3) return (l1 == b1 + b2 + b3 || (b1 == b2 + b3 && 2*l1 == b1));
        if (l2 == l3) return (b2 + b3 == b1 && b1 == l2 + l1);
        return false;
    };
    
    while(t--) {
        cin >> l1 >> b1 >> l2 >> b2 >> l3 >> b3;
        if(check()) cout << "YES\n";
        else {
            swap(l1, b1); swap(l2, b2); swap(l3, b3);
            if(check()) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    
    return 0;
}

Hint 1

Hint 2

Solution

Code - harshith_04

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    
    int n, s, ans = 0, dxi, dyi, xi, yi;
    while(t--) {
        cin >> n >> s;
        
        for (int i = 0; i < n; i++) {
            cin >> dxi >> dyi >> xi >> yi;
            if (dxi == dyi) ans += (xi == yi);
            else ans += (xi + yi == s);
        }
        
        cout << ans << '\n';
        ans = 0;
    }
    return 0;
}

Hint

Solution

Code - harshith_04

#include <iostream>
#include <cstdint>
#include <cassert>
#include <vector>

using namespace std;

#define i64 int64_t

void solve() {
    i64 n, sum;
    cin >> n >> sum;

    if(sum < n || sum > n * (n + 1) / 2) {
        cout << "-1\n";
        return;
    }

    i64 k = sum - n;

    vector<i64> ans;
    i64 curr = 0, nsum = 0;

    for(i64 i = n - 1; i >= 0; --i) {
        if(curr == k) break;
        if(curr + i <= k) {
            curr += i;
            ans.push_back(i + 1);
            nsum += i + 1;
        }
    }

    i64 ct = ans.size();
    for(i64 i = 0; i < n - ct; ++i) ans.push_back(1);

    nsum += (n - ct);
    
    assert(nsum == sum);

    if(n == sum) {
        cout << "1\n";
        for(i64 i = 1; i < n; i++) cout << i << ' ' << i + 1 << '\n';
        return;
    }

    vector<bool> vis(n + 1, 1);
    cout << ans[0] << '\n';
    vis[ans[0]] = 0;

    for(i64 i = 1; i <= n; i++) {
        cout << ans[i - 1] << ' ' << ans[i] << '\n';
        vis[ans[i - 1]] = 0, vis[ans[i]] = 0;

        if(ans[i] == 1) {
            i64 prev = 1;
            for(i64 j = 2; j <= n; ++j) {
                if(vis[j]) {
                    cout << prev << ' ' << j << '\n';
                    prev = j;
                }
            }
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    i64 t;
    cin >> t;

    while(t--) solve();
    return 0;
}

Hint

Solution

Code - aryansanghi

//Written By Aryan Sanghi
 
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
const int mod=1e9+7;
 
int modpower(int a, int b)
{
    int r=1;
    
    a=a%mod;
    while(b>0)
    {
        if(b%2==1)
        {
            r*=a;
            r%=mod;
        }
        
        b=b/2;
        a*=a;
        a%=mod;
        
    }
    
    return r;
}
 
 
int32_t main(){
    int t;
    cin>>t;
 
    while(t--){
        int a, b, k;
        cin>>a>>b>>k;
        
        int n=1, m=1;
        
        n*=a-1;
        n%=mod;
        n*=k;
        n%=mod;
        n+=1;
        n%=mod;
        
        m*=b-1;
        m%=mod;
        m*=k;
        m%=mod;
        for(int i=0;i<a;i++){
            m*=(n-i+mod)%mod;
            m%=mod;
            m*=modpower((a-i+mod)%mod, mod-2)%mod;
            m%=mod;
        }
        m+=1;
        m%=mod;
        
        cout<<n<<" "<<m<<"\n";
    }
}

Code - Starsilk

#include <bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long inv[100001];
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T;
	long long i,a,b,k,d,ans;
	inv[1]=1;
	for(i=2;i<=100000;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(cin>>T;T>0;T--)
	{
		cin>>a>>b>>k;
		d=k*a-k+1;
		ans=k;
		for(i=1;i<=a;i++)ans=ans*((d-i+1)%mod)%mod*inv[i]%mod;
		cout<<d%mod<<' '<<(ans*b-ans+1+mod)%mod<<'\n';
	}
	return 0;
}

Hint 1

Hint 2

Solution

Observe the following(Let $$$1$$$ car shift lanes at a time):

It is always optimal to shift the car at the back of a lane before shifting cars in front of it.
The optimal condition is that in every iteration, the car shifts from the back of the lane with max cars to the back of the lane with minimum cars.
If $$$(\text{cars in the max lane} - \text{cars in min lane}) \lt = K$$$, then it is not optimal to shift any cars as it will only increase the angriness.
It doesn't matter when a car switches lane; it can switch at any time and the optimal answer remains the same.

For a value $$$v$$$, let

$$$def(v)$$$ be number of cars required such that each lane has atleast $$$v$$$ cars, i.e. $$$def(v)=\sum_{i=1}^N max(0, v-a[i]))$$$
$$$defs(v)$$$ be number of lanes with less than $$$v$$$ cars initially, i.e. $$$defs(v)=\sum_{i=1}^N (v-a[i] \gt 0)$$$.
$$$exc(v)$$$ be number of cars to remove such that each lanes has atmost $$$v$$$ cars, i.e. $$$exc(v)=\sum_{i=1}^N max(0, a[i]-v)$$$
$$$excs(v)$$$ be number of lanes with more than $$$v$$$ cars initially, i.e. $$$excs=\sum_{i=1}^N (a[i]-v \gt 0)$$$

Using binary search, find the maximum value of $$$v$$$ for which $$$exc(v+k) \gt def(v)$$$. This $$$v$$$ denotes the minimum value that the array will have after cars have switched lanes optimally, and the maximum value of the array will be $$$v+k$$$ if $$$exc(v+k)=def(v)$$$ and $$$v+k+1$$$ if $$$exc(v+k) \gt def(v)$$$.

Final sorted array $$$A'$$$ after optimal lane switches will have values between $$$v+1$$$ and $$$v+k-1$$$ remain the same as array $$$A$$$. Of the first $$$defs(v)$$$ elements, last $$$max(0, exc(v)-def(v)-excs(v))$$$ values will be $$$v+1$$$ and remaining values will be $$$v$$$. Of the last $$$excs(v)$$$ elements, last $$$min(excs(v), exc(v)-def(v))$$$ values will be $$$v+k+1$$$ and remaining elements will be $$$v+k$$$. Find minimum angriness after optimal lane switches using array $$$A'$$$ and calculating number of cars that have switched lanes. Time complexity is $$$O(n \log \max(A_i))$$$

Special thanks to picramide for the initial problem idea, which I misheard and it turned into this problem.

Code - aryansanghi

//Written By Aryan Sanghi

#include<bits/stdc++.h>

using namespace std;

#define ll long long int
#define rep(i, n) for(ll i = 0; i < n;i++)

int main()
{
    ll t;
    cin>>t;

    while(t--)
    {
        ll n, k;
        cin>>n>>k;

        vector<ll> a(n, 0);
        ll suma=0;
        rep(i, n) cin>>a[i], suma+=a[i];

        sort(a.begin(), a.end());

        ll l=a[0], r=(suma+n-1)/n + 1;

        while(r-l>1){
            ll mid=(l+r)/2;
            
            ll req=0, exc=0;
            rep(i, n) req+=max<ll>(0, mid-a[i]), exc+=max<ll>(0, a[i]-mid-k);

            if(req>exc) r=mid;
            else l=mid;
        }

        ll req=0, exc=0, reqs=0, excs=0, ans=0;
        rep(i, n){
            if(a[i]<=l) reqs++, req+=l-a[i], a[i]=l;
            if(a[i]>=l+k+1) excs++, exc+=a[i]-l-k, a[i]=l+k;
        }
        exc -= req;
        rep(i, min<ll>(excs, exc)) a[n - 1 - i]++;
        exc -= excs;
        rep(i, exc) a[i]++, req++;
        ans += req * k;
        for(int i = 0; i < n; ++i) ans += (a[i] * (a[i] + 1)) / 2;
        // rep(i, n) cout << a[i] << " ";
        // cout << "\n";
        cout << ans <<"\n";
    }
}

Code - ugly2333

//��
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 1111111;
const LL inf = 1e18;
int n,k,a[N];
LL s[N];
int main(){
	int T,i,l,r,h;
	LL x,y,z,o,p,t;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		for(i=1;i<=n;i++)
			scanf("%d",a+i);
		sort(a+1,a+n+1);
		for(i=1;i<=n;i++)
			s[i]=s[i-1]+a[i];
		z=inf,o=-1;
		l=0,r=N;
		while(l<=r){
			h=l+r>>1;
			i=lower_bound(a+1,a+n+1,h)-a-1;
			x=(LL)i*h-s[i];
			i=lower_bound(a+1,a+n+1,h+k)-a-1;
			y=(s[n]-s[i])-(LL)(n-i)*(h+k);
			if(z>max(x,y))
				z=max(x,y),o=h;
			if(x<y)
				l=h+1;
			else
				r=h-1;
		}
		//cout<<z<<' '<<o<<endl;
		p=z*k;
		t=0;
		for(i=1;i<=n;i++){
			x=min(max((LL)a[i],o),o+k);
			p+=(LL)x*(x+1)/2;
			t+=x-a[i];
		}
		if(t>0)
			p-=(o+k)*t;
		if(t<0)
			p+=(o+1)*-t;
		printf("%lld\n",p);
	}
	return 0;
}

Hint 1

Hint 2

Solution

In a graph $$$G$$$, two vertices $$$v_1$$$ and $$$v_2$$$ are said to be of type1 if they are not adjacent and have the same open neighborhood, i.e., $$$v_1v_2 \not\in E(G)$$$ and $$$N_G(v_1)=N_G(v_2)$$$.

In a graph $$$G$$$, two vertices $$$v_1$$$ and $$$v_2$$$ are said to be of type2 if they are adjacent and have the same closed neighborhood, i.e., $$$v_1v_2 \in E(G)$$$ and $$$N_G[v_1]=N_G[v_2]$$$.

An equivalence class is defined as the set of vertices of the same type. Here, note that if two vertices of type1 are present, then both vertices can't correspond to independent sets as we can merge them to a larger independent set and denote it by a single vertex. Similarly, if two vertices of type2 are present, then both can't correspond to cliques as we can merge them to a larger clique and denote it by a single vertex.

Proof:

Graph is superb $$$\rightarrow$$$ Every type1 pair has atleast one vertex correspond to a clique and every type2 pair has atleast one vertex correspond to an independent set(We'll prove contrapositive).

Assume there exists a type1 pair $$$v_1v_2$$$ that has both vertices corresponding to an independent set. Let their vertex set be $$$V_1$$$ and $$$V_2$$$. Consider the set $$$V=V_1 \cup V_2$$$ and a new vertex $$$v$$$ that has the same neighborhood as $$$v_1(or v_2)$$$. Each vertex in the set $$$V$$$ satisfies all of the $$$4$$$ conditions given, as if vertices in set $$$V_1$$$ were connected to a vertex, so is every vertex in the set $$$V_2$$$ and vice versa. Hence, we can merge both $$$v_1$$$ and $$$v_2$$$ into a single vertex $$$v$$$ and still satisfy the conditions, making the graph not superb as it doesn't have minimum order. Same reasoning goes for a type2 pair.

Every type1 pair has atleast one vertex correspond to a clique and every type2 pair has atleast one vertex correspond to an independent set $$$\rightarrow$$$ Graph is superb.

Consider a graph $$$G({v_i}, E)$$$. Let its fun graph be $$$G'({V_i}, E')$$$. Observe that if two vertices $$$V_i$$$ and $$$V_j$$$ have different neighborhoods (excluding each other), then we can't have any fun graph $$$G2'$$$ in which a vertex $$$K$$$ contains some non-zero vertices of $$$V_i$$$ and some non-zero vertices of $$$V_j$$$. This is because if that happens, then it means all vertices in set $$$K$$$ have the same neighborhood, excluding each other, meaning that $$$V_i$$$ and $$$V_j$$$ have the same neighborhood, excluding each other, a contradiction. For the same reasons, if two vertices have the same neighborhood, excluding each other, they have to be either a type1 or type2 pair for there to exist another fun graph $$$G2'$$$ in which a vertex $$$K$$$ contains some non-zero vertices from both sets. Suppose every type1 pair has at least one vertex corresponding to a clique, and every type2 pair has at least one vertex corresponding to an independent set. In that case, there can't be any fun graph $$$G2'$$$ in which a vertex K contains some non-zero vertices from two sets of $$$G'$$$ as set $$$K$$$ has either all vertices in it connected or none of them connected. So, in $$$G2'$$$, each vertex $$$K$$$ corresponds to a subset of vertices of $$$G'$$$, implying that it has at least as many vertices as $$$G'$$$. So, $$$G'$$$ is of minimum cardinality and so is superb. \end{enumerate}

So, for this problem, a vertex is assigned $$$0$$$ if it is assigned an independent set and a vertex is assigned $$$1$$$ if it is assigned a clique. Consider two vertices $$$a$$$ and $$$b$$$. If both are type1, then we can denote it by $$$a \lor b$$$(both can't be I.S.) and if both are type2, we can denote it by $$$\lnot a \lor \lnot b$$$(Both can't be cliques). We can make a $$$2$$$-sat equation using this. If the $$$2$$$-sat has a solution, then the graph is a superb graph. Else, it is not. Expected complexity is $$$O(n^3)$$$

Code - picramide

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

bool twoSAT(vector<vector<int>> &adj, vector<vector<int>> &adj_rev, vector<bool> &assignment) {
    int n = adj.size();
    vector<int> order;
    vector<bool> used(n, false);

    function<void(int)> dfs1 = [&](int v) {
        used[v] = true;

        for(auto u : adj[v]) 
            if(!used[u])
                dfs1(u);

        order.push_back(v);
    };

    vector<int> comp(n, -1);

    function<void(int, int)> dfs2 = [&](int v, int color) {
        comp[v] = color;

        for(auto u : adj_rev[v]) 
            if(comp[u] == -1)
                dfs2(u, color);
    };

    for(int i = 0; i < n; ++i) 
        if(!used[i])
            dfs1(i);

    used.assign(n, false);

    for(int i = 0, j = 0; i < n; ++i) {
        int v = order[n - i - 1];
        if(comp[v] == -1)
            dfs2(v, j++);
    }

    assignment.assign(n / 2, false);
    for(int i = 0; i < n; i += 2) {
        if(comp[i] == comp[i + 1]) 
            return false; 
        assignment[i / 2] = comp[i] > comp[i + 1];
    }
    return true;
}

void solve() {
    int n, k; cin >> n >> k;

    vector<vector<int>> adj(2*n), adj_rev(2*n);

    auto add_or = [&](int a, bool nega, int b, bool negb) {
        a = (2*a) + nega;
        b = (2*b) + negb;
        adj[a^1].push_back(b);
        adj[b^1].push_back(a);
        adj_rev[b].push_back(a^1);
        adj_rev[a].push_back(b^1);
    };

    function<void(int, vector<vector<int>>&)> process = [&n, &add_or](int m, vector<vector<int>> &adj) {
        map<vector<int>, vector<int>> mp;

        for(int i = 0; i < n; ++i) {
            auto temp = adj[i];
            temp.push_back(i);
            sort(temp.begin(), temp.end());

            mp[temp].push_back(i);
        }

        for(auto [x, y] : mp) {
            for(int i = 0; i < y.size(); ++i) {
                for(int j = i + 1; j < y.size(); ++j) {
                    add_or(y[i], 1, y[j], 1);
                }
            }
        }

        mp.clear();

        for(int i = 0; i < n; ++i) {
            sort(adj[i].begin(), adj[i].end());
            mp[adj[i]].push_back(i);
        }

        for(auto [x, y] : mp) {
            for(int i = 0; i < y.size(); ++i) {
                for(int j = i + 1; j < y.size(); ++j) {
                    add_or(y[i], 0, y[j], 0);
                }
            }
        }
    };

    for(int i = 0; i < k; ++i) {
        int m; cin >> m;
        vector<vector<int>> adj(n);

        for(int j = 0; j < m; ++j) {
            int x, y; cin >> x >> y;
            x--; y--;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }

        process(m, adj);
    }

    vector<bool> assignment(n, false);
    cout << ((twoSAT(adj, adj_rev, assignment)) ? "Yes" : "No");
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int _TC = 0; cin >> _TC;
    for(int _ct = 1; _ct <= _TC; ++_ct) {
        solve(); cout << endl;
    }
}

Bonus problem

Hint 1

Hint 2

Hint 3

Solution

Code - aryansanghi

//Written By Aryan Sanghi
 
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long int
#define rep(i, n) for(ll i = 0; i < n;i++)
#define pb push_back

vector<vector<ll> > v;
 
bool EulerCycle(ll k)
{
    ll odd = 0, n=v.size();
    rep(i, n) if(v[i].size() % 2) odd++;
    
    
    if(odd == 0) return true;// G has all even degree vertices, so it has Euler Cycle
 
    rep(i, n)
    rep(j, v[i].size())
    if(v[v[i][j]].size()%2==v[i].size()%2){
        // cout<<i+1<<" "<<v[i][j]+1<<"\n";
        return false;
    }
 
    if(k>=2) return true;// L^2(G) has all even degree vertices, so it has Euler Cycle
 
    return false;
}
 
int LongestTrailingPath(ll n, ll p){
    if(v[n].size()>2) return 0;
    rep(i, v[n].size()) if(v[n][i]!=p) return 1+LongestTrailingPath(v[n][i], n);
}
 
void MarkVisited(ll n, vector<ll> &visited, vector<vector<ll> > &adj){
    visited[n]=1;
    rep(i, adj[n].size()){
        if(!visited[adj[n][i]]){
            MarkVisited(adj[n][i], visited, adj);
        }
    }
}
 
bool EulerPath(ll k){
    ll oddv[2], temp=0, n=v.size();
    rep(i, n) if(v[i].size()%2) oddv[temp++]=i;
    ll l[2]={LongestTrailingPath(oddv[0], -1), LongestTrailingPath(oddv[1], -1)};
    if(l[0]>l[1]) swap(l[0], l[1]), swap(oddv[0], oddv[1]);
    if(l[0]>=k) return true; // shortest longest trailing path is longer than k
    if(l[0]>0) return false; // shortest longest trailing path is non zero and less than k
    if(l[1]==1 && v[oddv[0]].size()==3 && v[oddv[1]][0] == oddv[0] && k==1) return true; // odd[0] and odd[1] are connected with one one have degree 1 and other having degree 3
    if(find(v[oddv[0]].begin(), v[oddv[0]].end(), oddv[1]) != v[oddv[0]].end()) return false; // odd[0] and odd[1] are adjacent
    if(k==1 || k>=3) return false; // Special cases left, and k=1, k>=4 don't satisfy it
 
    vector<vector<ll> > tempv(v);
    vector<ll> vis(v.size(), 0), noniso;
 
    rep(i, n){
        if(find(tempv[i].begin(), tempv[i].end(), oddv[0]) != tempv[i].end()) tempv[i].erase(find(tempv[i].begin(), tempv[i].end(), oddv[0]));
        if(find(tempv[i].begin(), tempv[i].end(), oddv[1]) != tempv[i].end()) tempv[i].erase(find(tempv[i].begin(), tempv[i].end(), oddv[1]));
        if(tempv[i].size()>0 && i!=oddv[0] && i!=oddv[1]) noniso.pb(i);
    }
 
    MarkVisited(noniso[0], vis, tempv);
    rep(i, noniso.size()){
        if(!vis[noniso[i]]) return false; // After removing odd degree vertices, there is more than one component
    }
 
    ll cntedge=0;
    rep(i, noniso.size()){
        int temp=0;
        if(find(v[noniso[i]].begin(), v[noniso[i]].end(), oddv[0]) != v[noniso[i]].end()) cntedge++, temp++;
        if(find(v[noniso[i]].begin(), v[noniso[i]].end(), oddv[1]) != v[noniso[i]].end()) cntedge++, temp++;
 
        if(temp && v[noniso[i]].size() > 2) return false; // Vertex connected to odd vertex has degree exactly 2
    }
    if(cntedge>2) return false; // More than 2 edges are connected to odd degree vertices from the component
 
    return true; // Special case, k=2 is always satisfied
}
 
void solve(){
    ll n, m, k;
    cin>>n>>m>>k;
 
    v.clear();
    v.resize(n);
 
    rep(i, m){
        ll x, y;
        cin>>x>>y;
        v[x-1].pb(y-1);
        v[y-1].pb(x-1);
    }
 
    if(EulerCycle(k)){
        cout<<"YES\n";
        return;
    }
    if(EulerPath(k)){
        cout<<"YES\n";
        return;
    }
    cout<<"NO\n";
}
 
int main()
{
    ll t;
    cin>>t;
 
    while(t--)
    {
        solve();
    }
}

Code - ugly2333

//��
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 222222;
int n,m,k,a[N],b[N],d[N],r[N][2];
vector<int> v[N],c;
LL solve1(){
	int i;
	LL s=0;
	for(i=1;i<=m;i++)
		s+=d[a[i]]%2!=d[b[i]]%2;
	return s;
}
LL solve2(){
	int i;
	LL s=0;
	for(i=1;i<=n;i++)
		s+=(LL)r[i][0]*r[i][1];
	return s;
}
LL solve3(){
	int i,o;
	LL s=0;
	for(i=1;i<=n;i++)
		s+=(LL)r[i][0]*r[i][1]*(d[i]-2);
	for(i=1;i<=m;i++){
		o=(d[a[i]]+d[b[i]])%2;
		s+=(LL)(r[a[i]][0]-(d[b[i]]%2==0))*(r[b[i]][o^1]-(d[a[i]]%2==(o^1)))+(LL)(r[a[i]][1]-(d[b[i]]%2==1))*(r[b[i]][o]-(d[a[i]]%2==o));
	}
	return s;
}
int dfs(int u,int fa=0){
	if(d[u]>=3)
		return 0;
	if(d[u]==1)
		return N;
	int i,x,r=N;
	for(i=0;i<v[u].size();i++){
		x=v[u][i];
		if(x!=fa)
			r=min(r,dfs(x,u)+1);
	}
	return r;
}
int main(){
	int T,i,f;
	LL s,t;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);
		for(i=1;i<=m;i++)
			scanf("%d%d",a+i,b+i);
		for(i=1;i<=m;i++)
			d[a[i]]++,d[b[i]]++;
		for(i=1;i<=m;i++)
			r[a[i]][d[b[i]]%2]++,r[b[i]][d[a[i]]%2]++;
		for(i=1;i<=m;i++)
			v[a[i]].push_back(b[i]),v[b[i]].push_back(a[i]);
		if(k==1)
			f=solve1()<=2;
		if(k==2)
			f=solve2()<=2;
		if(k==3)
			f=solve3()<=2;
		if(k>3){
			s=solve2();
			if(s==0)
				f=1;
			if(s>=4)
				f=0;
			if(s==2){
				t=solve3();
				if(t==0)
					f=1;
				if(t>=4)
					f=0;
				if(t==2){
					c.clear();
					for(i=1;i<=n;i++)
						if(r[i][0]&&r[i][1])
							c.push_back(i);
					if(c.size()!=2)
						f=0;
					else
						f=k<=min(dfs(c[0]),dfs(c[1]))+1;
				}
			}
		}
		if(f)
			printf("YES\n");
		else
			printf("NO\n");
		for(i=1;i<=n;i++)
			d[i]=0,r[i][0]=0,r[i][1]=0,v[i].clear();
	}
	return 0;
}

Solution

Let $$$s_i$$$ be the maximum number such that array $$$[a_1, a_2, ...a_i-1, s_i, a_i+1, .., a_n]$$$ is valid.

Lemma 1: There exists at most one index $$$i$$$ such that $$$a_i \ge s_i$$$.

Proof 1: Assume there exist two indices $$$i$$$ and $$$j$$$ such that $$$a_i \ge s_i$$$ and $$$a_j \ge s_j$$$, say $$$i \lt j$$$.

$$$a_j \ge s_j \gt = j-1 + a_1 + a_2 + ... + a_{j-1} \Rightarrow a_j \ge j-1 + \sum_{k = 1}^{j-1} a_k \Lleftarrow \text{Eq}_1$$$

For an index $$$i \lt j$$$, $$$a_i \ge s_i$$$ when $$$a_j \ge s_j \Rightarrow$$$

$$$a[i] \ge a[j] - (j-i) + 1 \Lleftarrow \text{Eq}_2$$$

$$$\text{Eq}_1$$$ and $$$\text{Eq}_2 \Rightarrow$$$

$$$a_j + a_i \ge j-1 - (j-i) + 1 + a_j + \sum_{k = 1}^{j-1} a_k \Rightarrow a_i \ge i + \sum_{k = 1}^{j-1} a_k$$$

since $$$i \lt j \Rightarrow$$$

$$$a_i \ge i + a_1 + a_2 + .... + a_i + ... + a_{j-1} \Rightarrow 0 \ge i + a_1 + ... + a_{i-1} + .... + a_j$$$

$$$\text{Contradiction!!}$$$

Lemma 2: If $$$a_i \le s_i$$$ $$$\forall$$$ $$$i \in [1, n]$$$, $$$a$$$ is valid.

Proof 2: Backwards induction — let's divide it into two cases.

Case 1. $$$a_i \lt s_i$$$ $$$\forall$$$ $$$i \in [1, n]$$$. Let $$$j \gt 0$$$ be the smallest index such that $$$a_j \gt 0$$$ and say $$$j$$$-th index car overtakes the one ahead $$$i.e.,$$$

$$$0 ... a_{j-1}, a_j, a_{j+1} ... a_n \Rightarrow 0 ... a_j-1, a_{j-1}, a_{j+1} ... a_n$$$ $$$0 ... s_{j-1}, s_j, s_{j+1} ... s_n \Rightarrow 0 ... s_j-1, \ge s_{j-1} + a_j, s_{j+1} ... s_n$$$

For all $$$i \lt j-1$$$ and $$$i \gt j$$$, $$$a_i \lt s_i$$$ holds as they were unaffected, why?
At index $$$j-1$$$ since $$$a_j \lt s_j \Rightarrow a[j]-1 \lt s[j]-1$$$ holds.
At index $$$j$$$ since $$$a_{j-1} \lt s_{j-1} \Rightarrow a_{j-1} \lt s_{j-1} + a_j$$$ holds.

Case 2. Now, for an index $$$j$$$ if $$$a_j = s_j \Rightarrow$$$ we choose the index $$$k \gt j$$$ such that $$$a_k \gt 0$$$; if there's no such $$$k$$$, we choose $$$j$$$. Condition holds similarly, why?

$$$\text{Solution}$$$

def check(arr, i):
    cnt = 0, s = sum(arr[:i - 1]) + i  
    for j in range(i + 1, n):
        if arr[j] <= cnt:  cnt += 1 
        else:  s += arr[j] - cnt↵
    return arr[i] <= s↵

Let $$$p = [0, a_1, a_1 + a_2, a_1 + a_2 + a_3, .... ]$$$ and say an index $$$i$$$ is critical $$$\Leftrightarrow$$$ $$$i + p[i] \lt a_i$$$.

Lemma 3: It is sufficient to check the greatest critical index $$$i.e.,$$$ if $$$i_1, i_2, ..., i_k$$$ are critical, $$$check(a, i_k)$$$ would be enough to determine whether $$$a$$$ is valid or not.

Proof 3: Trivial, if $$$i_k$$$ performs $$$a_{i_k}$$$ overtakes successfully $$$\Rightarrow$$$ overtakes at indices $$$i \lt i_k$$$ will be nullified by $$$a_{i_k}$$$

Special thanks to Proelectro444 for the formal proof.

$$$\looparrowright$$$ Alternate Solution: $$$O(n \cdot log n)$$$ data structure optimized $$$check(a, i_k)$$$ $$$\forall$$$ $$$k \in [1, n]$$$.

Code O(n) - harshith_04

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
int64_t n, a[N], p[N + 1];

void solve() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];

    for(int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i - 1];

    int cti = n - 1;
    for(int i = n - 1; i >= 0; --i) {
        if(i + p[i] < a[i]) {
            cti = i;
            break;
        }
    }

    int cnt = 0;
    int64_t s_i = p[cti] + cti;

    for (int j = cti + 1; j < n; ++j) {
        if (a[j] <= cnt) ++cnt;
        else s_i += a[j] - cnt;
    }

    if (s_i < a[cti]) cout << "No\n";
    else cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int t; cin >> t;

    while(t--) solve();
    return 0;
}

Code O(n*logn) - IceKnight1093

#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct FT {
    vector<ll> s;
    FT(int n) : s(n) {}
    void update(int pos, ll dif) { // a[pos] += dif↵
        for (; pos < size(s); pos |= pos + 1) s[pos] += dif;
    }
    ll query(int pos) { // sum of values in [0, pos)
        ll res = 0;
        for (; pos > 0; pos &= pos - 1) res += s[pos-1];
        return res;
    }
};

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    map<vector<int>, bool> cache;
    auto brute = [&] (const auto &self, auto v) -> bool {
        if (ranges::max(v) == 0) return true;
        if (cache.find(v) != cache.end()) return cache[v];
 
        for (int i = 1; i < v.size(); ++i) {
            if (v[i] > 0) {
                auto w = v;
                --w[i];
                swap(w[i], w[i-1]);
                bool res = self(self, w);
 
                if (res) return cache[v] = true;
            }
        }
        return cache[v] = false;
    };

    auto solve = [&] (auto v) {
        int n = size(v);

        vector<int> b(n);
        Tree<array<int, 2>> cur;
        for (int i = 0; i < n; ++i) {
            if (v[i] == 0) b[i] = i;
            else {
                // v[i]-th largest element↵
                if (cur.size() >= v[i]) {
                    int want = cur.size() - v[i];
                    auto [val, _] = *cur.find_by_order(want);
                    b[i] = val;
                }
                else b[i] = -1;
            }
            cur.insert({b[i], i});
        }

        vector deactivate(n+1, vector<int>());
        for (int i = 0; i < n; ++i)
            if (b[i] >= 0) deactivate[b[i]].push_back(i);
        
        ll pref = 0;
        for (int i = 0; i < n; ++i) pref += v[i] + 1;

        FT fen(n);
        ll suf = 0;
        for (int i = n-1; i >= 0; --i) {
            pref -= v[i] + 1;
            
            ranges::reverse(deactivate[i]);
            for (int x : deactivate[i]) {
                if (v[x]) {
                    int sub = fen.query(x+1) - fen.query(i+1);
                    sub = x - i - sub;
                    suf -= v[x] - sub;
                    fen.update(x, -1);
                }
                suf -= fen.query(n) - fen.query(x);
            }
            ll have = pref + suf;
            if (v[i] > have) return false;
            if (v[i] > 0) {
                suf += v[i];
                fen.update(i, 1);
            }
        }
        return true;
    };

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector a(n, 0);
        for (int &x : a) cin >> x;
        
        if (solve(a)) cout << "Yes\n";
        else cout << "No\n";
    }
}

Bonus for those who haven't seen the Solution