The final array will be the form of either $$$1010101...$$$ or $$$0101010...$$$

$$$x^1 + x^2 + x^3 + ... + x^{n - 1} \lt x^n$$$ $$$\forall$$$ $$$x \ge 2$$$

Case $$$x = 1$$$: we will calculate the cost for both $$$101010...$$$ and $$$010101...$$$. Then minimum of this cost will be the answer.

Case $$$x \ge 2$$$: For other value of $$$x$$$, it will always optimal not to change the value of $$$a_n$$$. if $$$a_n = 1$$$ then the final array will be $$$.....0101$$$ and if $$$a_n = 0$$$ then the final array will be $$$.....1010$$$

#include<bits/stdc++.h>
using namespace std;
#define mod         998244353
#define int long long
int power(int x,int y){int res=1;x=x%mod;while(y>0){if(y&1) res=(res*x)%mod;y=y>>1;x=(x*x) % mod;}return res;}
void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int i=0;i<n;i++)
    cin>>v[i];
    if(k==1){
        int c1=0,c2=0;
        int x=0;
        for(int i=0;i<n;i++){
            c1+=(v[i]!=x);
            x^=1;
            c2+=(v[i]!=x);
        }
        cout<<min(c1,c2)<<endl;
    }  
    else{
        int cost=0;
        int x=v[n-1];
        for(int i=n-1;i>=0;i--){
            if(v[i]!=x)
            cost=(cost+power(k,i+1))%mod;
            x^=1;
        }
        cout<<cost<<endl;
    }
}
int32_t main()
{
    int _=1;
    cin>>_;
    while(_--)
    solve();
    return 0;
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

Let $$$dp_g$$$ be the number of valid subsequences formed using a subset of the elements processed so far, such that their cumulative GCD is exactly $$$G$$$. "Valid" here means that at no point during the construction of these subsequences did the GCD drop to 1.

#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
#include "../../debug.h"
#else
#define debug(...)
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double

const ld eps = 1e-12;

template <typename T>
T inverse(T a, T m) {
	T u = 0, v = 1;
	while (a != 0) {
		T t = m / a;
		m -= t * a; swap(a, m);
		u -= t * v; swap(u, v);
	}
	assert(m == 1);
	return u;
}

template <typename T>
class Modular {
public:
	using Type = typename decay<decltype(T::value)>::type;

	constexpr Modular() : value() {}
	template <typename U>
	Modular(const U& x) {
		value = normalize(x);
	}

	template <typename U>
	static Type normalize(const U& x) {
		Type v;
		if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
		else v = static_cast<Type>(x % mod());
		if (v < 0) v += mod();
		return v;
	}

	const Type& operator()() const { return value; }
	template <typename U>
	explicit operator U() const { return static_cast<U>(value); }
	constexpr static Type mod() { return T::value; }

	Modular& operator+=(const Modular& other) { value += other.value; value -= (value >= mod()) * mod(); return *this; }
	Modular& operator-=(const Modular& other) { value -= other.value; value += (value < 0) * mod(); return *this; }
	template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
	template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
	Modular& operator++() { return *this += 1; }
	Modular& operator--() { return *this -= 1; }
	Modular operator++(int) { Modular result(*this); *this += 1; return result; }
	Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
	Modular operator-() const { return Modular(-value); }

	template <typename U = T>
	typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type & operator*=(const Modular& rhs) {
		value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
		return *this;
	}
	template <typename U = T>
	typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type & operator*=(const Modular& rhs) {
		int64_t q = int64_t(static_cast<long double>(value) * rhs.value / mod());
		value = normalize(value * rhs.value - q * mod());
		return *this;
	}
	template <typename U = T>
	typename enable_if < !is_integral<typename Modular<U>::Type>::value, Modular >::type & operator*=(const Modular& rhs) {
		value = normalize(value * rhs.value);
		return *this;
	}

	Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

	friend const Type& abs(const Modular& x) { return x.value; }

	template <typename U>
	friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

	template <typename U>
	friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

	template <typename V, typename U>
	friend V& operator>>(V& stream, Modular<U>& number);

private:
	Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
	assert(b >= 0);
	Modular<T> x = a, res = 1;
	U p = b;
	while (p > 0) {
		if (p & 1) res *= x;
		x *= x;
		p >>= 1;
	}
	return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
	return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
	return to_string(number());
}

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
	return stream << number();
}

// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
	typename common_type<typename Modular<T>::Type, int64_t>::type x;
	stream >> x;
	number.value = Modular<T>::normalize(x);
	return stream;
}

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<ll> divisors[10001];

void solve() {
	ll n; cin >> n;
	vector<ll> a(n);
	for (auto &pos : a)cin >> pos;
	vector<Mint> dp(10001, Mint(0));
	vector<Mint> change(10001, Mint(0));
	Mint tot = 0;
	auto sum = dp;
	for (ll i = 0; i < n; i++) {
		Mint curTot = tot;
		ll val = a[i];
		ll len = divisors[val].size();
		for (ll j = len - 1; j >= 1; j--) {

			ll cur = divisors[val][j];
			Mint changed = sum[cur] + ((j == len - 1) ? Mint(1) : Mint(0));
			for (auto pos : divisors[cur]) {
				if (pos != cur && pos != 1) {
					change[pos] -= sum[cur] ;
					change[pos] -= change[cur];
					tot += sum[cur];
					tot += change[cur];
				}
			}
			change[cur] += changed;
			tot -= sum[cur];
		}
		tot -= dp[1];
		dp[1] += tot;
		sum[1] += tot;
		curTot += tot;
		if (val == 1) {
			dp[1] ++;
			curTot ++;
		}
		for (auto pos : divisors[val]) {
			dp[pos] += change[pos];
			for (auto posi : divisors[pos]) {
				sum[posi] += change[pos];
			}
			curTot += change[pos];
			change[pos] = 0;
		}
		tot = curTot;

	}
	cout << dp[1] << endl;
}




int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("F:\\cp_sublime\\input.txt", "r", stdin);
	freopen("F:\\cp_sublime\\output.txt", "w", stdout);
	freopen("F:\\cp_sublime\\debug.txt", "w", stderr);
#endif
	for (ll i = 1; i <= 10000; i++) {
		for (ll j = i; j <= 10000; j += i) {
			divisors[j].emplace_back(i);
		}
	}
	int tt = 1;
	cin >> tt;
	while (tt--)
		solve();
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

It is difficult to count arrays where the median is exactly $$$x$$$ directly. Instead, it is much easier to count arrays where the median is at least $$$v$$$. Let this count be $$$f(v)$$$. The answer to the problem is simply:

How to calculate $$$f(v)$$$ For the median to be $$$\ge v$$$, at least half of the elements in the array (specifically $$$\lceil n/2 \rceil$$$ or more) must be greater than or equal to $$$v$$$. Count of valid numbers $$$\ge v$$$ is: $$$A = y - v + 1.$$$ Count of valid numbers $$$ \lt v$$$ is: $$$B = v - 1.$$$ We iterate $$$k$$$ from $$$\lceil n/2 \rceil$$$ to $$$n$$$ (the number of "large" elements). For each $$$k$$$, we choose which positions are large and fill the rest with small numbers:

The time complexity is $$$O(n)$$$ per test case to compute the sum.

#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
#include "../../debug.h"
#else
#define debug(...)
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double

const ld eps = 1e-12;


template <typename T>
T inverse(T a, T m) {
    T u = 0, v = 1;
    while (a != 0) {
        T t = m / a;
        m -= t * a; swap(a, m);
        u -= t * v; swap(u, v);
    }
    assert(m == 1);
    return u;
}

template <typename T>
class Modular {
public:
    using Type = typename decay<decltype(T::value)>::type;

    constexpr Modular() : value() {}
    template <typename U>
    Modular(const U& x) {
        value = normalize(x);
    }

    template <typename U>
    static Type normalize(const U& x) {
        Type v;
        if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
        else v = static_cast<Type>(x % mod());
        if (v < 0) v += mod();
        return v;
    }

    const Type& operator()() const { return value; }
    template <typename U>
    explicit operator U() const { return static_cast<U>(value); }
    constexpr static Type mod() { return T::value; }

    Modular& operator+=(const Modular& other) { value += other.value; value -= (value >= mod()) * mod(); return *this; }
    Modular& operator-=(const Modular& other) { value -= other.value; value += (value < 0) * mod(); return *this; }
    template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
    template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
    Modular& operator++() { return *this += 1; }
    Modular& operator--() { return *this -= 1; }
    Modular operator++(int) { Modular result(*this); *this += 1; return result; }
    Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
    Modular operator-() const { return Modular(-value); }

    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type & operator*=(const Modular& rhs) {
        value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
        return *this;
    }
    template <typename U = T>
    typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type & operator*=(const Modular& rhs) {
        int64_t q = int64_t(static_cast<long double>(value) * rhs.value / mod());
        value = normalize(value * rhs.value - q * mod());
        return *this;
    }
    template <typename U = T>
    typename enable_if < !is_integral<typename Modular<U>::Type>::value, Modular >::type & operator*=(const Modular& rhs) {
        value = normalize(value * rhs.value);
        return *this;
    }

    Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

    friend const Type& abs(const Modular& x) { return x.value; }

    template <typename U>
    friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

    template <typename U>
    friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

    template <typename V, typename U>
    friend V& operator>>(V& stream, Modular<U>& number);

private:
    Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
    assert(b >= 0);
    Modular<T> x = a, res = 1;
    U p = b;
    while (p > 0) {
        if (p & 1) res *= x;
        x *= x;
        p >>= 1;
    }
    return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
    return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
    return to_string(number());
}

// U == std::ostream? but done this way because of fastoutput
template <typename U, typename T>
U& operator<<(U& stream, const Modular<T>& number) {
    return stream << number();
}

// U == std::istream? but done this way because of fastinput
template <typename U, typename T>
U& operator>>(U& stream, Modular<T>& number) {
    typename common_type<typename Modular<T>::Type, int64_t>::type x;
    stream >> x;
    number.value = Modular<T>::normalize(x);
    return stream;
}

// using ModType = int;

// struct VarMod { static ModType value; };
// ModType VarMod::value;
// ModType& md = VarMod::value;
// using Mint = Modular<VarMod>;

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

vector<Mint> fact(1, 1);
vector<Mint> inv_fact(1, 1);

Mint C(int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    while ((int) fact.size() < n + 1) {
        fact.push_back(fact.back() * (int) fact.size());
        inv_fact.push_back(1 / fact.back());
    }
    return fact[n] * inv_fact[k] * inv_fact[n - k];
}


void solve() {

    ll n , x, y; cin >> n >> x >> y;
    ll half = (n + 1) >> 1;
    auto get = [&](ll val)->Mint{
        Mint ans = 0;
        ll can = y - val + 1;
        can = max(can, 0ll);
        Mint val1 = power(Mint(can), half);
        Mint val2 = power(Mint(val - 1), half - 1);
        Mint other = 1;
        if (val != 1) other = Mint(1) / Mint(val - 1);
        for (ll i = half; i <= n; i++) {
            if (i == n)
                ans += C(n, i) * val1;
            else
                ans += C(n, i) * val1 * val2;
            val1 *= can;
            val2 *=other;
            // if (val != 1) val2 /= Mint(val - 1);
        } return ans;
    };

    cout << (get(x) - get(x + 1)) << '\n';
}




int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("F:\\cp_sublime\\input.txt", "r", stdin);
    freopen("F:\\cp_sublime\\output.txt", "w", stdout);
    freopen("F:\\cp_sublime\\debug.txt", "w", stderr);
#endif
    int tt = 1;
    cin >> tt;
    while (tt--)
        solve();
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

Let the hidden permutation be $$$p$$$ of size $$$n$$$. Our strategy will be choosing $$$k=2$$$ always and we will have an element $$$idx$$$, which will store the index of the suffix maximum element of the hidden permutation. Initially $$$idx=n$$$.

We will start querying backwards from index $$$i=n-1$$$ For each query we will ask for $$$i$$$ and $$$idx$$$, let's say judges response is $$$v$$$. There are two possible outcomes:
1. $$$v \gt 0$$$: This means $$$p_i \lt p_{idx}$$$, and the interactor has explicitly revealed that $$$p_i = v$$$.
2. $$$v = 0$$$: This means $$$p_i \gt p_{idx}$$$. Since $$$p_{idx}$$$ was the maximum of the suffix to the right, $$$p_i$$$ becomes the new maximum of the current suffix $$$p[i \dots n]$$$. We update $$$idx = i$$$. We do not know the value of $$$p_i$$$ yet, so we mark this position as "unknown".
Now we will be repeating this till $$$i = 1$$$. So we used $$$n - 1$$$ queries and also found some numbers in the permutation.

Now the main observation here is after this the remaining unknown elements in the permutation will be in decreasing order. It is because, since these numbers are unfounded that means no number on the right of any of these numbers(say $$$x$$$) in the permutation is bigger than $$$x$$$ otherwise we would have found the $$$x$$$ while querying with the bigger number.

So if we have stored the unfounded elements, by iterating the permutation from left we can assign the unfounded numbers in decreasing order in the missing positions of the permutation.

Thus using $$$n-1$$$ queries we can find the permutation. This can be done in O(n) or O(nlogn) depending upon the implementation.

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
using namespace std;
using namespace __gnu_pbds;
#define itsiftikar02     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
int ask(int l,int r){
    int in;
    cout<<"? 2 "<<l+1<<" "<<r+1<<endl;
    cout.flush();
    cin>>in;
    return in;
}
void solve()
{
    int n;
    cin>>n;
    vector<int>ans(n);
    set<int>st;
    int idx=n-1;
    
    for(int i=0;i<n;i++)
    st.insert(i+1);
    
    for(int i=n-2;i>=0;i--){
        int in=ask(i,idx);
        if(in){
            st.erase(in);
            ans[i]=in;
        }
        else
        idx=i;
    }
    
    idx=n;
    for(int i=n-1;i>=0;i--){
        if(!ans[i]){
            ans[i]=(*st.begin());
            st.erase(*st.begin());
        }
    }
    cout<<"!";
    for(auto x:ans)
    cout<<" "<<x;
    cout<<endl;
    cout.flush();
}
int32_t main()
{
    itsiftikar02;
    int _=1;
    while(_--)
    solve();
    return 0;
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

Mathematical Expression:

First, consider any person $$$a$$$ who lives at position $$$x$$$ on the coordinate line and has a budget $$$y$$$. Our goal is to determine how many people $$$a$$$ can invite such that the total travel cost does not exceed $$$y$$$.

A direct way to solve the equation for every possible $$$X$$$ (meeting point or pivot) takes $$$O(n)$$$ per query, resulting in $$$O(n^2)$$$ overall — which is too slow.

To improve this, we use the following optimized strategy:

We binary search on the answer — i.e., on the maximum number of people (say $$$m$$$) that person $$$a$$$ can invite. For a fixed number $$$m$$$, we must check whether it is feasible.

To check feasibility, we try selecting: $$$r$$$ participants from the left side of $$$x$$$, $$$m - r$$$ participants from the right side of $$$x$$$. For any chosen $$$r$$$, we compute the total travel cost and verify whether it stays within $$$y$$$. Since $$$r$$$ ranges from $$$0$$$ to $$$m$$$, we can again apply binary search on $$$r$$$ to efficiently find the best configuration. Thus, both searches combined significantly reduce the complexity from $$$O(n^2)$$$ to a much faster solution.

$$$\therefore$$$ The complexity of each query is $$$O(\log^2 n)$$$ and the overall complexity of the algorithm is $$$O(n \cdot \log^2 n)$$$ per test case.

Proof: We apply binary search on $$$r$$$ — but why? Because the cost function is unimodal.

The cost function is defined as:

Where $$$j$$$ is the index of $$$x$$$ in the position array $$$p$$$.

Define the forward difference:

$$$D(r) = \text{cost}(r+1) - \text{cost}(r)$$$ After simplification: $$$D(r) = 2x - S(r)$$$ Where $$$S(r) = x_{i-(r+1)} + x_{i+m-r-1}$$$ Since the array is sorted, we have: $$$S(r+1) \le S(r)$$$ Thus $$$D(r)$$$ is non-decreasing: $$$D(r+1) \ge D(r)$$$ Therefore, the cost function is unimodal, and binary search on $$$r$$$ is applicable.

#include<bits/stdc++.h>
using namespace std; 
#define fr(i,s,n)      for(ll i=s;i<n;i++)
#define read(a)        for(auto &e:a) cin>>e;
typedef long long            ll;
void solve(){
    ll n; cin>>n;
    vector<ll> x(n),b(n); read(x); read(b);
    vector<ll> pref(n);
    pref[0]=x[0];
    fr(i,1,n) pref[i]=pref[i-1]+x[i];
    auto range_sum=[&](int l,int r)->ll{
        if(l>r) return 0;
        return pref[r]-(l?pref[l-1]:0);
    };
    auto split_cost=[&](int p,int m,int left)->ll{
        if(left<0) return 1e18;
        ll t=x[p];
        int leftL=p-left,leftR=p-1;
        int rightl=p,rightR=p+(m-left)-1;
        if(leftL<0 || rightR>=n) return 1e18;
        ll suml=range_sum(leftL,leftR);
        ll sumr=range_sum(rightl,rightR);
        ll costL=t*left-suml;
        ll costR=sumr-t*(m-left);
        return costL+costR;
    };
    auto min_cost=[&](int p,int m)->ll{// m is the length
        ll l=max(0ll,m-(n-p));
        ll r=min(m,p);
        if(l>r) return 1e18;
        // range for left-side element
        while(l<r){
            int mid=(l+r)>>1;
            ll cost1=split_cost(p,m,mid);
            ll cost2=split_cost(p,m,mid+1);
            if(cost2<cost1) l=mid+1;
            else r=mid;
        }
        return split_cost(p,m,l);
    };
    auto max_count=[&](int p,ll budget)->ll{
        ll low=1,high=n,ans=1;
        ll t=x[p];
        while(low<=high){
            ll mid=(low+high)>>1;
            if(min_cost(p,mid)<=budget){
                ans=mid;
                low=mid+1;
            }
            else high=mid-1;
        }
        return ans;
    };
    fr(i,0,n){
        cout<<max_count(i,b[i])-1<<" ";
    }

}   

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    cin>>t;
    fr(i,0,t){
        solve();
        cout<<endl;
    }
    return 0;
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

If two vertices have equal distance vectors, they will also have equal hash values. We can compute the hash of the distance vector for every vertex using rerooting.

Choose any root, compute the hash for the root, and then propagate the DP values across edges when rerooting the tree.
This allows us to obtain the hash for all vertices in linear time. After obtaining the hash values we can easily calculate the power of each vertex.

Consider any simple path between vertices $$$u$$$ and $$$v$$$.
Suppose a particular distance vector $$$D$$$ appears multiple times on this path.

Claim: A distance vector can appear on a tree path at most $$$2$$$ times.

Therefore, for any path, the frequency of any distance vector is $$$0$$$, $$$1$$$, or $$$2$$$.

Since a distance vector can appear at most twice, the contribution of its power cancels out if it appears two times.
Thus the power of the path is simply:

To compute the xor of path we can use binary lifting.

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
 
#define ll long long

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll uid(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 

const int N = 2, MX = 1e5 + 1;
using Hash = array<int, N>;
const Hash M = {1000000007, 998244353};
const Hash B = {uid(1000001, M[0] - 1), uid(1000001, M[1] - 1)};
Hash pwr[MX];
 
Hash shift(Hash a, int p) {
    for (int i = 0; i < N; i++) {
        a[i] = (1ll * a[i] * pwr[p][i]) % M[i];
    }
    return a;
}
Hash add(Hash a, Hash b) {
    Hash res;
    for (int i = 0; i < N; i++) {
        res[i] = a[i] + b[i];
        if (res[i] > M[i]) res[i] -= M[i];
    }
    return res;
}
Hash sub(Hash a, Hash b) {
    Hash res;
    for (int i = 0; i < N; i++) {
        res[i] = a[i] - b[i];
        if (res[i] < 0) res[i] += M[i];
    }
    return res;
}
 
 
void solve() {
    int n; cin >> n;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        --u, --v;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    int timer = 0;
    vector<int> tin(n), tout(n);
    int LG = ceil(log2(n));
    vector<vector<int>> UP(n, vector<int>(LG + 1));
    vector<Hash> dp(n), up(n);
    auto dfs = [&] (auto dfs, int v, int p) -> void {
        tin[v] = timer++;
        UP[v][0] = p;
        for (int i = 1; i <= LG; i++) 
            UP[v][i] = UP[UP[v][i - 1]][i - 1];

        for (int i = 0; i < N; i++) dp[v][i] = 1;
        for (auto &[u, w] : adj[v]) if (u ^ p) {
            dfs(dfs, u, v);
            dp[v] = add(dp[v], shift(dp[u], w));
        }
        tout[v] = timer++;
    }; dfs(dfs, 0, 0);
    
    up[0] = dp[0];
    auto dfs_ = [&] (auto dfs, int v, int p, int w) -> void {
        if (v ^ p) {
            Hash t = sub(up[p], shift(dp[v], w));
            up[v] = add(dp[v], shift(t, w));
        } 
        for (auto &[u, w] : adj[v]) if (u ^ p) dfs(dfs, u, v, w);
    }; dfs_(dfs_, 0, 0, 0);
 
    auto is_ancestor = [&](int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    };
    auto lca = [&](int u, int v) {
        if (is_ancestor(u, v))
            return u;
        if (is_ancestor(v, u))
            return v;
        for (int i = LG; i >= 0; i--) {
            if (!is_ancestor(UP[u][i], v))
                u = UP[u][i];
        }
        return UP[u][0];
    };
    vector<int> order(n);
    iota(order.begin(), order.end(), 0ll);
    sort(order.begin(), order.end(), [&] (const int &i, const int &j) {
        return up[i] < up[j];
    });
    vector<int> a(n), pre(n);
    for (int i = 0; i < n; i++) {
        int j = i;
        while (j < n && up[order[i]] == up[order[j]]) j++;
        for (int k = i; k < j; k++) a[order[k]] = j - i;
        i = j - 1;
    }
    auto dfs_last = [&] (auto dfs, int v, int p) -> void {
        pre[v] = pre[p] ^ a[v];
        for (auto &[u, w] : adj[v]) if (u != p) {
            dfs(dfs, u, v);
        }
    }; dfs_last(dfs_last, 0, 0);
    auto query = [&] (int v, int u) {
        int _lca = lca(u, v);
        return pre[v] ^ pre[u] ^ a[_lca];
    };
    int q; cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        --x, --y;
        cout << query(x, y) << "\n";
    }
}
 
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _TEST = 1;
    cin>>_TEST;
    for (int i = 0; i < N; i++) pwr[0][i] = 1;
    for (int i = 1; i < MX; i++) 
        for (int j = 0; j < N; j++)
            pwr[i][j] = 1ll * pwr[i - 1][j] * B[j] % M[j];
    
    for(int _ = 1; _ <= _TEST; _++) {
        solve();
    }
        
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

Trivial case: If $$$n \lt k$$$, then the modulo operation never happens and we can choose $$$b$$$ to be infinitely large, so the answer will be $$$-1$$$.

Now, The problem can be divided into two different sections:

i) Finding the maximum number of balls possible at time $$$n$$$

At every second, we multiply the current number of balls by $$$2$$$, and at every second $$$t$$$ such that $$$k$$$ divides $$$t$$$, the number of balls $$$x$$$ becomes $$$x \bmod c$$$. We know repeated periodic modulo in such operations is equivalent to taking modulo only once at the end. Hence, we can find the final position $$$m$$$ such that $$$m \bmod k = 0$$$ and $$$m \le n$$$ (i.e., $$$m = n - n \bmod k$$$).

Since the operations after $$$m$$$ are constant and are not altered by the modulo operation, we can calculate the maximum number of balls we can achieve at $$$n$$$ by maximizing the number of balls at $$$m$$$. Initially, we start with $$$b$$$ balls $$$(b \ge 0)$$$, and each second, the number of balls doubles. So the expression that we need to maximize is $$$b \cdot 2^{m} \bmod c$$$. Let $$$\gcd(2^{m}, c)$$$ be $$$g$$$. Then we know the results of this expression are multiples of $$$g$$$. So the results are: $$$0, g, 2g, 3g, \ldots$$$

Therefore, the maximum value that we can achieve for the expression would be the last multiple of $$$g$$$ that is less than $$$c$$$. Since $$$g$$$ divides $$$c$$$, this maximum value is $$$c - g$$$. Hence the maximum number of balls that we can achieve at $$$m$$$ is $$$c - g$$$. Now we need to multiply $$$c - g$$$ by $$$2^{n - m}$$$ modulo $$$998244353$$$ to get the maximum balls at $$$n$$$ modulo $$$998244353$$$.

ii) Find the minimum $$$b$$$ that achieves this maximum.

Now that we know the maximum number of balls we can achieve is $$$c - g$$$ at $$$m$$$. So the new equation to find $$$b$$$ is: $$$(b \cdot 2^{m} \equiv c - g) \bmod c$$$ $$$\Rightarrow (b \cdot 2^{m} \equiv -g) \bmod c$$$

Now, since $$$g$$$ divides both sides of the equivalence as well as the modulo, $$$\Rightarrow (b \cdot 2^{m} / g \equiv -g / g) \bmod (c / g)$$$

Let $$$2^{m} / g$$$ and $$$c / g$$$ be $$$x$$$ and $$$y$$$ respectively. (We know $$$g$$$ divides both $$$2^{m}$$$ and $$$c$$$.) $$$\Rightarrow (b \cdot x \equiv -1) \bmod y$$$ $$$\Rightarrow (b \equiv -x^{-1}) \bmod y$$$ (the inverse $$$x^{-1} \bmod y$$$ exists because $$$\gcd(x, y) = 1$$$)

Hence, we can calculate $$$b$$$ by solving $$$(-x^{-1}) \bmod y$$$.

Time complexity: $$$O(\log n)$$$

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define sz(x) ((int)(x).size())
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll uid(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 


#define int long long
const int N = 1e6 + 10;
const int M = 998244353;

int bpow(int x, int p, int mod) {
    int res = 1;
    while(p) {
        if(p & 1) res = (res * x) % mod;
        x = (x * x) % mod;
        p >>= 1;
    }
    return res;
}

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

int inv(int x, int mod) {
    x %= mod;
    int a, b;
    assert(gcd(x, mod, a, b) == 1);
    return (a % mod + mod) % mod;
}

void Determinist() {
    int n, k, c; cin >> n >> k >> c;
    if(n < k) {
        cout << "-1\n";
        return;
    }
    int pw = bpow(2, n - n % k, c);
    int g = __gcd(pw, c);
    int ans = c - g;
    int npw = pw / g;
    int nc = c / g;
    int b = (nc - inv(npw, nc)) % nc;
    cout << (ans * bpow(2, n % k, M)) % M << ' ' << b << '\n';
}
int32_t main() {
    ios_base ::sync_with_stdio(0); 
    cin.tie(0);               
    cout.tie(0);

    int t = 1;
    cin >> t;
    while(t--) {
        Determinist();
    }
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

Increasing the height of $$$a_i$$$ to $$$k$$$: Since each building height can incremented if and only if the previous one has at least the required height, we have to apply operations on the continuous subarray starting $$$j+1$$$ to $$$i$$$ and we are taking $$$j$$$ as a hinge.

For this to work, considering the arithmetic series we must have $$$a_i = k, a_{i-1} = k - X, a_{i-2} = k-2 \cdot X$$$ so on.

Hence, $$$a_j \ge k - (i-j)X$$$ must be satisfied.

rearranging the inequality we get this: $$$a_j - j \cdot X \ge k - i \cdot X$$$

Let $$$B_j = a_j - j \cdot X$$$. We need to find the rightmost index $$$j \lt i$$$ such that $$$B_j \ge k - i \cdot X$$$. This index $$$j$$$ represents the point where the existing building heights are already sufficient to support the new height $$$k$$$ at $$$i$$$.

Data Structure: Use a Segment Tree with Lazy Propagation to handle:

1. Range Assignment (Type 1)

2. Range Addition (Type 2)

3. Querying Sum of $$$a$$$ (for cost calculation)

4. Querying Maximum of $$$B$$$ (to find index $$$j$$$)

Query 3 Algorithm:

1. Check if current $$$a_i \gt k$$$. If so, print -1 (we can only increase heights).

2. Check if current $$$a_i = k$$$. If so, print 0.

3. Perform a binary search on the Segment Tree (or walk the tree) to find the largest index $$$j \lt i$$$ where $$$B_j \ge k - i \cdot X$$$.

4. The new heights in the range $$$[j+1, i]$$$ will form an Arithmetic Progression ending at $$$k$$$ with common difference $$$X$$$.

5. Answer: (Sum of required AP) $$$-$$$ (Current Sum of $$$a[j+1 \dots i]$$$).

Complexity: $$$O(Q \log N)$$$

#include <bits/stdc++.h>
#include <climits>

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...)
#endif

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ld long double
#define endl '\n'

const ld eps = 1e-12;

ll no_operation = LLONG_MAX;
ll x;
struct Node {
	ll l = -1, r = -1;
	ll sum = 0;
	ll operation = no_operation;
	bool type = false;
	ll maxi = LLONG_MIN;
	Node(ll val, ll idx) {
		// debug(x);
		l = idx, r = idx;
		sum = val;
		maxi = val - l * x;
	}
	Node() {

	}
	void apply(ll op) {
		type = false;
		operation = op;
		sum = (r - l + 1) * op;
		maxi = op - l * x;
	}
	void apply1(ll op) {
		if (operation != no_operation) {
			operation += op;
		} else if (operation == no_operation) {
			operation = op;
			type = true;
		}
		sum += (r - l + 1) * op;

		maxi += op;
	}
};

struct Stree {
	vector<Node> segtree;
	vector<ll> arr;
	void init(ll n, vector<ll> A) {
		arr = A;
		segtree.resize(4 * (n + 1));
	}

	Node merge(const Node &left, const Node &right) {
		if (left.l == -1)return right;
		if (right.l == -1)return left;
		Node cur;
		cur.l = left.l;
		cur.r = right.r;
		cur.maxi = max(left.maxi, right.maxi);
		cur.sum = right.sum + left.sum;
		return cur;
	}

	void propagate(ll tl, ll tr, ll node) {
		if (tl >= tr)return;
		if (segtree[node].operation != no_operation) {
			ll op = segtree[node].operation;
			if (!segtree[node].type) {

				segtree[2 * node].apply(op);
				segtree[2 * node + 1].apply(op);
			} else {
				segtree[2 * node].apply1(op);
				segtree[2 * node + 1].apply1(op);
			}
		}
		segtree[node].operation = no_operation;
	}

	void build(ll l, ll r, ll node) {
		if (l > r) return;
		if (l == r) {
			segtree[node] = Node(arr[l], l);
			return;
		}
		ll mid = (l + r) >> 1;
		build(l, mid, 2 * node);
		build(mid + 1, r, 2 * node + 1);
		segtree[node] = merge(segtree[2 * node], segtree[2 * node + 1]);
	}

	Node query(ll l, ll r, ll tl, ll tr, ll node) {
		propagate(tl, tr, node);
		if (l > r || tl > tr || tl > r || tr < l) return Node();

		if (tl >= l && tr <= r) {
			return segtree[node];
		}

		ll mid = (tl + tr) >> 1;
		return merge(query(l, r, tl, mid, 2 * node) ,
		             query(l, r, mid + 1, tr, 2 * node + 1));
	}


	ll Query(ll idx, ll val, ll tl, ll tr, ll node)
	{
		propagate(tl, tr, node);
		if (tl > tr || segtree[node].maxi < val || tl >= idx)return -1;
		if (tl == tr)return tl;
		ll mid = (tl + tr) >> 1;
		ll right = Query(idx, val, mid + 1, tr, 2 * node + 1);
		if (right != -1)return right;
		return Query(idx, val, tl, mid,	2 * node);
	}


	void update(ll l, ll r, bool type, ll value, ll tl, ll tr, ll node) {
		propagate(tl, tr, node);
		ll mid = (tl + tr) >> 1;
		if (tl > tr || tr < l || tl > r || l > r) return;

		if (tl >= l && tr <= r) {
			// we apply update
			if (!type)
				segtree[node].apply(value);
			else segtree[node].apply1(value);
			return;
		}
		update(l, r, type, value, tl, mid, 2 * node);
		update(l, r, type, value, mid + 1, tr, 2 * node + 1);

		segtree[node] = merge(segtree[2 * node], segtree[2 * node + 1]);
	}


	void update(ll l, ll val, ll tl, ll tr, ll node) {
		propagate(tl, tr, node);
		ll mid = (tl + tr) >> 1;
		if (tl > tr || tr < l || tl > l) return;

		if (tl == l && tr == l) {
			segtree[node] = Node(val, l);
			return;
		}
		update(l, val, tl, mid, 2 * node);
		update(l, val, mid + 1, tr, 2 * node + 1);

		segtree[node] = merge(segtree[2 * node], segtree[2 * node + 1]);
	}
};


void solve() {
	ll n, q; cin >> n >> q >> x;
	vector<ll> a(n + 1);
	vector<ll> arr(n + 1, 0);
	for (ll i = 1; i <= n; i++)cin >> a[i];
	Stree just;
	just.init(n + 1, a);
	just.build(1, n, 1);
	while (q--) {
		ll type; cin >> type;
		if (type == 1 || type == 2) {
			ll l, r ; cin >> l >> r;
			ll val ; cin >> val;
			just.update(l, r, (type == 2), val, 1, n, 1);
		} else {
			ll i , k; cin >> i >> k;



			ll cur = just.query(i, i, 1, n, 1).sum;
			if (k < cur) {
				cout << -1 << endl;
				continue;
			}
			if (k == cur) {
				cout << 0 << endl;
				continue;
			}



			auto ck1 = [&](ll mid)->ll{
				ll looking = mid - i * x ;
				ll idx = just.Query(i, looking, 1, n, 1);
				if (idx != -1) {

					ll su = just.query(idx + 1, i, 1, n, 1).sum;
					ll len = i - idx;
					ll sum = (2 * mid + (len - 1) * (-x)) * len;
					sum >>= 1;
					return sum - su;
				} return -1;
			};
			cout << ck1(k) << endl;
		}
	}
}




int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("F:\\cp_sublime\\input.txt", "r", stdin);
	freopen("F:\\cp_sublime\\output.txt", "w", stdout);
	freopen("F:\\cp_sublime\\debug.txt", "w", stderr);
#endif
	int tt = 1;
	cin >> tt;
	while (tt--)
		solve();
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

We build subsequences one by one, always making each subsequence as lexicographically small as possible. For each subsequence, we repeatedly pick its next character using a greedy rule: Among all letters 'a' to 'z', pick the smallest letter whose next unused occurrence at position $$$pos$$$ still allows us to complete the remaining $$$rem$$$ characters of this subsequence. This is possible iff the number of unused characters in the $$$s_{pos .. n−1}$$$ is $$$ \ge rem$$$. If that letter is feasible, we choose it; otherwise we try the next letter.

After choosing the subsequence $$$t$$$, we need to remove the occurrence of all the letters of that subsequence from the string so that we don't choose the same letters again. Now it is always optimal to remove the last occurrence of the letter from the original string. i.e, if we want to remove $$$t_i$$$ then it is always optimal to remove the last occurrence of $$$t_i$$$ from the original string such that it comes before $$$t_{i+1}$$$

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

struct FenwickTree {
    int n;
    vector<int> bit;
    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }
    FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }
    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }
    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};
 
void solve() {
    int n, k; cin >> n >> k;
    string s; cin >> s;
 
    vector<set<int>> at(26);
    for (int i = 0; i < n; i++) {
        at[s[i] - 'a'].insert(i);
    }
    vector<int> ans;
    FenwickTree bit(n);
    for (int i = 0; i < n; i++) bit.add(i, 1);
    int rem = k, start = 0;
    for(int q = 0; q<n/k; q++){
        start = -1;
        rem = k;
        vector<int> v;
        for (int j = 0; j < k; j++) {
            for (int i = 0; i < 26; i++) {
                auto it = at[i].upper_bound(start);
                if (it == at[i].end()) continue;
                int sum = bit.sum(n - 1 - *it);
                if (sum>=rem) {
                    ans.push_back(*it);
                    start = *it;
                    v.push_back(i);
                    rem--;
                    break;
                }
            }
        }
        reverse(v.begin(),v.end());
        int p = n+1;
        for(auto i:v){
            auto it = prev(at[i].lower_bound(p));
            p = *it;
            bit.add(n - 1 - *it, -1);
            at[i].erase(it);
        }
    }
    for (int &e : ans) cout << s[e];
    cout << "\n";
}
int32_t main() {
#ifndef ONLINE_JUDGE
    freopen("Error.txt", "w", stderr);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0); 
    int _TEST = 1;
    cin>>_TEST;

    for(int i=1; i<=_TEST; i++) {
        solve();
    }   
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

Consider $$$0$$$ means one step going right and $$$1$$$ means going one step up. Now $$$001$$$ means going two steps right followed by one step up and $$$110$$$ means going two steps up followed by one step right. If you start from any position both $$$001$$$ and $$$110$$$ will take you to the same position iff $$$F_1 + F_2 = F_3$$$ where $$$F_i$$$ = the amount of distance covered in the $$$i^{th}$$$ step. We can clearly see the Fibonacci sequence here.

Now if we consider we are at $$$(0, 0)$$$ then after $$$n$$$ steps our position will be in the line: $$$x + y = \sum_{i=1}^{n}F_i$$$.

We can proof that:

Total possible position = $$$F_{n+2} - 1$$$. Two string which results in different positions are not equivalent. So the maximum possible size of a set of such strings where no two strings in the set are equivalent is F[n + 2] — 1

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

#define int long long

using Matrix = array<array<int, 2>, 2>;
const int MOD = 998244353;
Matrix mul(Matrix a, Matrix b) {
    Matrix res = {{{0, 0}, {0, 0}}};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                res[i][j] += a[i][k] * b[k][j];
                res[i][j] %= MOD;
            }
        }
    }
    return res;
}
void solve() {
    int n; cin >> n;
    Matrix base = {{{1, 0}, {0, 1}}};
    Matrix m = {{{1, 1}, {1, 0}}};
    n += 3;
    for (; n > 0; n /= 2, m = mul(m, m)) {
        if (n & 1) base = mul(base, m);
    }
    int ans = base[0][1] - 1;
    if (ans < 0) ans += MOD;
    cout << ans << "\n";
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _TEST = 1;
    cin>>_TEST;
    for(int _ = 1; _ <= _TEST; _++) {
        solve();
    }
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

Corner positions contribute to one row and one column.

Moving a stone from corner position to any non-corner border position in the same row will not change the sum in the row but will change the sum by one in the column.

After Ash's move Gary will pick the same stone and placed it in any non-corner position. Then he will pick a stone from a corner position and move to a row or column such that it will maintain the sum. Gary can do this till there are stones on the corners. if $$$a_{11} + a_{1n} + a_{m1} + a_{nm} \ge$$$ sum of non borders elements then Gary will win otherwise Ash will win

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

#define int long long

void solve() {
    int n, m; cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (auto &v : a) for (int &e : v) cin >> e;
    int alice = 0;
    int bob = a[0][0] + a[0][m - 1] + a[n - 1][0] + a[n - 1][m - 1];
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) 
        if (i != 0 && i != n - 1 && j != 0 && j != m - 1) 
            alice += a[i][j];

    if (alice > bob) cout << "Ash\n";
    else cout << "Gary\n";
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _TEST = 1;
    cin>>_TEST;
    for(int _ = 1; _ <= _TEST; _++) {
        solve();
    }
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

It is optimal to form cycle only with size 3. To form a cycle of size 3 by adding an edge will require two extra edges. So one edges will consume two other edges. So we can add at most $$$\lfloor\frac{2n-1}{2}\rfloor$$$ edges

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
void solve() {
    int n; cin >> n; 
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
    }
    cout << (n - 1 >> 1) << "\n";
 
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int _TEST = 1;
    cin>>_TEST;
    for(int _ = 1; _ <= _TEST; _++) {
        solve();
    }    
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst

Let’s represent the array $$$a$$$ as a Directed Graph with vertices $$$1 \ldots n$$$ and edges $$$i \rightarrow a_i$$$.

If $$$a_i \le n$$$, the edge points to another vertex in the graph

Else, the edge points to outside of the graph, thus imposing no restrictions.

We can observe that for a good array, the graph has two types of edges $$$(i, a_i)$$$:

i) $$$a_i \ge i$$$: The indegree (number of edges incident on a vertex) of $$$i$$$ can take any non-negative value.

ii) $$$a_i \lt i$$$: The indegree of $$$i$$$ has to be zero.

So let’s divide the elements $$$i$$$ into two sets :

i) Good ($$$G$$$): $$$a_i \ge i$$$

ii) Bad ($$$B$$$): $$$a_i \lt i$$$ and $$$a_i \in G$$$

Now we can frame the solution as:

We chose a subset of indices $$$G \in {1, 2, \ldots, n}$$$. Let $$$|G| = k$$$.

For $$$i \in G$$$: $$$a_i \ge i$$$ must hold.

For $$$i \in B$$$: $$$a_i \in G$$$ and $$$a_i \lt i$$$.

Let’s pursue a DP approach. Let $$$dp_{i, j}$$$ be the number of ways to assign the first $$$i$$$ elements to the sets $$$G$$$ and $$$B$$$ such that $$$j$$$ elements belong to $$$G$$$.

Add $$$i^{th}$$$ element to $$$G$$$: $$$dp_{i, j} += dp_{i - 1, j - 1}$$$

Add $$$i^{th}$$$ element to $$$B$$$ by choosing one of the $$$j$$$ elements in $$$G$$$ to anchor it: $$$dp_{i, j} += dp_{i - 1, j} \cdot j$$$

So, $$$dp_{i, j} = dp_{i - 1, j - 1} + dp_{i - 1, j} \cdot j$$$.

However, these transitions would only land us with an $$$O(n^2)$$$ transition that would TLE under our problem constraints.

To optimise $$$dp$$$, we can observe that $$$dp_{i, j}$$$ basically calculates the number of ways to partition a set of $$$i$$$ elements into $$$j$$$ non-empty subsets, which is exactly the definition of Stirling Numbers of the Second Kind.

So finally, the number of ways to distribute $$$n$$$ elements to the sets $$$G$$$ and $$$B$$$ such that $$$k$$$ of them belong to the set $$$G$$$:

We can calculate the $$$n^{th}$$$ row of Stirling Numbers of the Second Kind using NTT efficiently.

Let the indices in $$$G$$$ the sorted order be: $$$j_1, j_2, \ldots j_k$$$. Now we need to assign values to each of these indices.

Let's consider $$$j_k$$$, it can take any value $$$ \gt n$$$ or $$$a_{j_{k}} = j_k$$$. So there are $$$(max(0, m - n) + 1)$$$ ways.

Now for $$$j_{k -1}$$$, it can either take values $$$ \gt n$$$ or from {$$$j_{k-1}, j_k$$$}, hence there are $$$(max(0, m - n) + 2)$$$ ways.

We can generalize the ways for each $$$j_p$$$ ($$$1 \le p \le k$$$) as: $$$(max(0, m - n) + k - p + 1) $$$

Hence, the total number of ways to assign values to each of the indices is:

So the total number of ways to form good arrays is:

Case $$$m \ge n$$$:

Case $$$m \lt n$$$:

All the indices $$$i$$$ such that $$$i \gt m$$$ will have to be part of set $$$B$$$ and will point to one of the $$$k$$$ elements in $$$G$$$. Hence, we can calculate the number of good arrays with size $$$m$$$ and point the rest $$$n-m$$$ elements to one of the $$$k$$$ indices belonging to $$$G$$$. This leads to a multiplier of $$$k^{n-m}$$$.

Overall time complexity: $$$O(nlogn)$$$

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define sz(x) ((int)(x).size())
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll uid(ll l, ll r) {return uniform_int_distribution<ll>(l, r)(rng);} 


const int N = 1e6 + 10;

ll myRand(ll B) {
    return (ull)rng() % B;
}
 
 
ll MOD = 998244353;
struct Mint { // 1000000007  1000000009
    ll x;
 
    Mint() : x(0) {}
    Mint(ll _x) {
        _x %= MOD;
        if (_x < 0) _x += MOD;
        x = _x;
    }
 
    Mint& operator += (const Mint &a) {
        x += a.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    Mint& operator -= (const Mint &a) {
        x += MOD - a.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
    Mint& operator *= (const Mint &a) {
        x = (ull)x * a.x % MOD;
        return *this;
    }
    Mint pow(ll pw) const {
        Mint res = 1;
        Mint cur = *this;
        while(pw) {
            if (pw & 1) res *= cur;
            cur *= cur;
            pw >>= 1;
        }
        return res;
    }
    Mint inv() const {
        assert(x != 0);
        ll t = x;
        ll res = 1;
        while(t != 1) {
            ll z = MOD / t;
            res = (ull)res * (MOD - z) % MOD;
            t = MOD - t * z;
        }
        return res;
    }
    Mint& operator /= (const Mint &a) {
        return *this *= a.inv();
    }
    Mint operator + (const Mint &a) const {
        return Mint(*this) += a;
    }
    Mint operator - (const Mint &a) const {
        return Mint(*this) -= a;
    }
    Mint operator * (const Mint &a) const {
        return Mint(*this) *= a;
    }
    Mint operator / (const Mint &a) const {
        return Mint(*this) /= a;
    }
 
    bool sqrt(Mint &res) const {
        if (MOD == 2 || x == 0) {
            res = *this;
            return true;
        }
        if (pow((MOD - 1) / 2) != 1) return false;
        if (MOD % 4 == 3) {
            res = pow((MOD + 1) / 4);
            return true;
        }
        int pw = (MOD - 1) / 2;
        int K = 30;
        while((1 << K) > pw) K--;
        while(true) {
            Mint t = myRand(MOD);
            Mint a = 0, b = 0, c = 1;
            for (int k = K; k >= 0; k--) {
                a = b * b;
                b = b * c * 2;
                c = c * c + a * *this;
                if (((pw >> k) & 1) == 0) continue;
                a = b;
                b = b * t + c;
                c = c * t + a * *this;
            }
            if (b == 0) continue;
            c -= 1;
            c *= Mint() - b.inv();
            if (c * c == *this) {
                res = c;
                return true;
            }
        }
        assert(false);
    }
 
    bool operator == (const Mint &a) const {
        return x == a.x;
    }
    bool operator != (const Mint &a) const {
        return x != a.x;
    }
    bool operator < (const Mint &a) const {
        return x < a.x;
    }
};
struct Factorials {
    vector<Mint> f, fi;
 
    Factorials() : f(), fi() {}
    Factorials(int n) {
        n += 10;
        f = vector<Mint>(n);
        fi = vector<Mint>(n);
        f[0] = 1;
        for (int i = 1; i < n; i++)
            f[i] = f[i - 1] * i;
        fi[n - 1] = f[n - 1].inv();
        for (int i = n - 1; i > 0; i--)
            fi[i - 1] = fi[i] * i;
    }
 
    Mint C(int n, int k) {
        if (k < 0 || k > n) return 0;
        return f[n] * fi[k] * fi[n - k];
    }
};
struct Powers {
    vector<Mint> p, pi;
 
    Powers() : p(), pi() {}
    Powers(int n, Mint x) {
        n += 10;
        if (x == 0) {
            p = vector<Mint>(n);
            p[0] = 1;
        } else {
            p = vector<Mint>(n);
            pi = vector<Mint>(n);
            p[0] = pi[0] = 1;
            Mint xi = x.inv();
            for (int i = 1; i < n; i++) {
                p[i] = p[i - 1] * x;
                pi[i] = pi[i - 1] * xi;
            }
        }
    }
 
    Mint pow(int n) {
        if (n >= 0)
            return p[n];
        else
            return pi[-n];
    }
};
struct Inverses {
    vector<Mint> ii;
 
    Inverses() : ii() {}
    Inverses(int n) {
        n += 10;
        ii = vector<Mint>(n);
        ii[1] = 1;
        for (int x = 2; x < n; x++)
            ii[x] = Mint() - ii[MOD % x] * (MOD / x);
    }
 
    Mint inv(Mint x) {
        assert(x != 0);
        ll t = x.x;
        ll res = 1;
        while(t >= (int)ii.size()) {
            ll z = MOD / t;
            res = (ull)res * (MOD - z) % MOD;
            t = MOD - t * z;
        }
        return ii[t] * res;
    }
};

#define int long long

const long long mod = (119 << 23) + 1, root = 62; // = 998244353
// For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21
// and 483 << 21 (same root). The last two are > 10^9.

long long modpow(long long b, long long e) {
	long long ans = 1;
	for (; e; b = b * b % mod, e /= 2)
		if (e & 1) ans = ans * b % mod;
	return ans;
}
typedef vector<long long> vl;
void ntt(vl &a) {
	int n = sz(a), L = 31 - __builtin_clz(n);
	static vl rt(2, 1);
	for (static int k = 2, s = 2; k < n; k *= 2, s++) {
		rt.resize(n);
		long long z[] = {1, modpow(root, mod >> s)};
		for(int i = k; i < 2 * k; i ++) rt[i] = rt[i / 2] * z[i & 1] % mod;
	}
	vector<int> rev(n);
	for(int i = 0; i < n; i ++) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
	for(int i = 0; i < n; i ++) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) for(int j = 0; j < k; j ++) {
			long long z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j];
			a[i + j + k] = ai - z + (z > ai ? mod : 0);
			ai += (ai + z >= mod ? z - mod : z);
		}
}
vl conv(const vl &a, const vl &b) {
	if (a.empty() || b.empty()) return {};
	int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s),
	    n = 1 << B;
	int inv = modpow(n, mod - 2);
	vl L(a), R(b), out(n);
	L.resize(n), R.resize(n);
	ntt(L), ntt(R);
	for(int i = 0; i < n; i ++)
		out[-i & (n - 1)] = (long long)L[i] * R[i] % mod * inv % mod;
	ntt(out);
	return {out.begin(), out.begin() + s};
}

Factorials ft(N);

void Determinist() {
    int n, m; cin >> n >> m;
    int N = min(n, m);

    vl a(N + 1), b(N + 1);
    for(int i = 0; i <= N; i ++) {
        a[i] = (ft.fi[i] * (i & 1? -1: 1)).x;
        b[i] = (Mint(i).pow(N) * ft.fi[i]).x;
    }
    auto c = conv(a, b); //stirling second kind
    
    Mint ans = 0, ways = 1;
    for(int i = 1; i <= N; i ++) {
        ways *= (max(0ll, m - n) + i);
        ans += ways * c[i] * Mint(i).pow(max(0ll, n - m));
    }
    cout << ans.x << '\n';
}   

int32_t main() {
    ios_base ::sync_with_stdio(0); 
    cin.tie(0);               
    cout.tie(0);

    int t = 1;
    cin >> t;
    while(t--) {
        Determinist();
    }
}

Difficulty
- Excellent
- Good
- Average
- Bad
- Worst
Quality
- Excellent
- Good
- Average
- Bad
- Worst