There are only two possible ways to arrange rectangles into a square if possible.

The only cases possible to arrange rectangles into a square are:

1. All three rectangles are put side by side, i.e. $$$l_1=l_2=l_3=b_1+b_2+b_3$$$ or $$$b_1=b_2=b_3=l_1+l_2+l_3$$$.
2. Rectangles $$$2$$$ and $$$3$$$ are side by side with rectangle $$$1$$$ above it, i.e. $$$l_1+l_2=l_1+l_3=b_1=b_2+b_3$$$ or $$$b_1+b_2=b_1+b_3=l_1=l_2+l_3$$$.

Check both these cases, and if either is true, output YES, otherwise NO. Complexity is $$$O(1)$$$ per test.

//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";
    }
}

#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;
}

What happens to the balls that collide with an edge, eventually?

How does a collision between two balls affect the outcome?

Observations

• Any ball on the diagonals of the square that is shot towards a pocket will be potted on a free table.
• Any ball that collides with an edge will be in a $$$4$$$-periodic path colliding with the $$$4$$$ edges forever on a free table.
• The collisions are elastic, so if two balls collide, they exchange their directions.
• $$$\bigstar$$$ Neither collisions affect the effective number of balls traversing towards a pocket.

Therefore, the answer is the number of balls initially on the diagonals of the square and shot towards the pockets.

Hope you liked the figures; a lot of effort went into them.

#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;
}

What are bounds on $$$m$$$ for a given $$$n$$$ to have a divine tree? And how does the tree look for the lower bound and the upper bound?

The $$$\text{min}$$$ and $$$\text{max}$$$ value of $$$m$$$ for a divine tree to exist are $$$n$$$ and $$$\frac{n \cdot (n + 1)}{2}$$$ respectively.

$$$\text{POC:}$$$ Any $$$m \in [\text{min}, \text{max}]$$$ can be achieved similar to exhaustive subset sum with redraws enabled.

Let $$$p = m - n$$$, $$$\text{cur} = 0$$$, $$$\text{ans}$$$ = [ ]. Now, we need to select a multiset of $$$n$$$ non-negative integers that sum to $$$p$$$.

$$$\text{Greedy:}$$$ Loop $$$j$$$ from $$$n - 1$$$ to $$$0$$$, if $$$\text{cur} + i \le p$$$: $$$\text{cur}$$$ += $$$i,$$$ $$$\text{ans.push_back}(i + 1)$$$

If $$$\text{ans.back}()$$$ is not $$$1$$$ add a $$$1$$$, why?

$$$\text{Construction:}$$$ The tree can always be simple path, why?

1. Tree is rooted at $$$\text{ans}[0]$$$. Let's store $$$\text{vis}[0:n - 1] = \text{false}$$$ to keep track if a node is visited or not.
2. Loop $$$i$$$ from $$$1$$$ to $$$\text{size(ans)}$$$ and add edge between $$$\text{ans}[i-1]$$$ to $$$\text{ans}[i]$$$ and mark all of them $$$\text{true}$$$ in $$$\text{vis}$$$.
3. Take all un-visited in the array $$$\text{unvis}$$$ and add an edge from $$$1$$$ to $$$\text{unvis}[0]$$$.
4. Loop $$$i$$$ from $$$1$$$ to $$$\text{size(unvis)}$$$ and add an edge from $$$\text{unvis}[i-1]$$$ to $$$\text{unvis}[i]$$$.

The divine tree which is a simple path looks like $$$\text{ans}[0] \leftrightarrow$$$ . . . $$$\leftrightarrow 1 \leftrightarrow \text{unvis}[0] \leftrightarrow$$$ . . . $$$\leftrightarrow \text{unvis.back}()$$$.

#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;
}

Use pigeonhole principle to get minimum $$$n$$$ and then minimum $$$m$$$.

If each column is of size $$$n=k(a-1)+1$$$, by pigeonhole principle, it will have at least $$$a$$$ elements with the same value. Let those elements appear positions $$$p_1 \lt p_2 \lt ... \lt p_a$$$($$$p_i$$$ is the row number where the element occurs) and let the value be $$$v$$$. Consider the tuple $$$(v, p_1,p_2,...,p_a)$$$. If the same tuple appears $$$b$$$ times, we are done as we obtain an $$$a*b$$$ submatrix with all elements of same value. The number of possible values of the tuple is $$$k\times\,^nC_a$$$. So, there should be atleast $$$m=(b-1)k\times\,^nC_a+1$$$ columns for there to be $$$b$$$ repetitions by pigeonhole principle.

//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";
    }
}

#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;
}

Use binary search to find minimum number of cars in a lane after optimal number lane shifts.

Adjust cars afterwards such that minimum number of cars remains same as found in binary search, but angriness is minimized.

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

1. It is always optimal to shift the car at the back of a lane before shifting cars in front of it.
2. 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.
3. 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.
4. 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

1. $$$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]))$$$
2. $$$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)$$$.
3. $$$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)$$$
4. $$$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.

//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";
    }
}

//��
#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;
}

If two vertices have same open neighborhood in some graph $$$G_i$$$, atleast one of them has to correpond to a clique in every $$$G_i, H_i$$$ pair.

If two vertices have same closed neighborhood in some graph $$$G_i$$$, atleast one of them has to correpond to an independent set in every $$$G_i, H_i$$$ pair.

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)$$$

#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;
    }
}

When is a graph a superb graph of itself?

If $$$G$$$ has an Euler cycle, what can we say about $$$L^k(G), k\geq1$$$

If $$$L(G)$$$ has Euler path, how to determine if $$$L^k(G), k\geq2$$$ has an Euler path?

If $$$L(G)$$$ doesn't Euler tour, but $$$L^2(G)$$$ does, what can we say about structure of $$$G$$$? Can there exist another graph $$$H$$$ such that $$$L(H)=G$$$?

Following are the cases where Euler tour is possible:

For the case of Euler cycle-

1. If $$$G$$$ has an Euler cycle, then $$$L(G)$$$ always has an Euler cycle.

2. If after removing the two odd-degree vertices of $$$G$$$, the remaining graph is fully disconnected(i.e. the odd-degree vertices form a vertex cover), then $$$L^2(G)$$$ has an Euler cycle.

For the case of Euler path-

1. If $$$G$$$ doesn't have an Euler tour but $$$L(G)$$$ does, then there is no graph $$$H$$$ such that $$$G=L^2(H)$$$, and any of the graph $$$L^{-k}(H), k\geq0$$$ has an Euler tour. So, we only need to consider cases where $$$G$$$ has an Euler tour, $$$L(G)$$$ doesn't, but $$$L^2(G)$$$ does, or where both $$$G$$$ and $$$L(G)$$$ have Euler tour.

2. If $$$G$$$ has an Euler path, $$$L(G)$$$ doesn't, but $$$L^2(G)$$$ does, then $$$G$$$ has exactly two odd-degree vertices $$$v_1$$$ and $$$v_2$$$. Additionally, graph obtained after removing $$$v_1$$$ and $$$v_2$$$ from $$$G$$$(i.e. $$$G\backslash$$${$$$v_1,v_2$$$}) consists of exactly one connected component with more than one vertex, and the rest are isolated vertices. Additionally, each connected component/isolated vertex in $$$G\backslash$$${$$$v_1,v_2$$$} has exactly two edges connecting them to $$$v_1$$$, $$$v_2$$$ in $$$G$$$. Here, $$$L^k(G), k\geq3$$$ won't have Euler tour.

3. If $$$G$$$ has an Euler tour and $$$L(G)$$$ also has an Euler tour, find the smallest trailing path of $$$G$$$(trailing path means a path where the degree of all vertices is either $$$1$$$ or $$$2$$$. There will be only $$$2$$$ of them as $$$G$$$ has an Euler tour) and return its length, and that will be the answer as the length of a trailing path decreases by $$$1$$$ from $$$G$$$ to $$$L(G)$$$.

All of this can be checked in initial graph itself in $$$O(n+m)$$$ time.

//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();
    }
}

//��
#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;
}

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$$$.

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

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

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

$$$\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.,$$$

• 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]$$$.

#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;
}

#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";
    }
}

If $$$a$$$ is valid, also determine the index of the first overtaker, if multiple are possible, return any one of them.