• Horrible contest
• Bad contest
• Average contest
• Good contest
• Epic contest

• Impossible contest
• Hard contest
• Average contest
• Simple contest
• Trivial contest

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Epic problem
• Did not solve

Which index is always ugly?

Consider the lower bound of the answer.

Observe that index $$$n$$$ is always ugly, so the answer is at least $$$1$$$.

It remains to show that this lower bound is achievable.

Set $$$p_1\gets n$$$ so that for each $$$i$$$, $$$\max(p_1,p_2,\cdots,p_i)=n$$$. As a result, the only ugly index is $$$n$$$.

By StayAlone.

#include <bits/stdc++.h>
using namespace std;
int n, a[505];
 
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == n) swap(a[1], a[i]);
    }
    for(int i = 1; i <= n; i++) printf("%d ", a[i]); puts("");
}
 
int main() {
    int T;
    cin >> T;
    for (; T--; ) solve();
    return 0;
}

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Epic problem
• Did not solve

Consider the prime decomposition of the given $$$n$$$.

$$$n$$$ has at most $$$1$$$ prime divisor not smaller than $$$\sqrt n$$$.

Let $$$n=\prod p_i^{\alpha_i}$$$ be the prime factorization of $$$n$$$. Hence, if $$$n$$$ is a divisor of $$$k^n$$$, each $$$p_i$$$ must be a divisor of $$$k^n$$$ and then $$$k$$$.

Under constraints above, the minimum valid number is $$$k=\prod p_i$$$. Due to $$$\alpha_i\le n$$$, each $$$p_i^{\alpha_i}$$$ will be a divisor of $$$p_i^n$$$, so $$$n$$$ is a divisor of $$$k^n$$$.

Thus, we only need to find $$$\prod p_i$$$. Because $$$n$$$ has at most $$$1$$$ prime divisor not smaller than $$$\sqrt n$$$, we only need to check the prime numbers smaller than $$$\sqrt n$$$, and the remaining part is $$$1$$$ or the only prime divisor bigger than $$$\sqrt n$$$.

So we solve the problem in $$$\mathcal O(\sqrt n)$$$.

By Leftist_G.

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int tc;
int n;
vector <int> pr;
bool vis[N];
void init(int n = 31623){
	for(int i = 2; i <= n; i++){
		if(!vis[i]) pr.push_back(i);
		for(auto j: pr){
			if(i * j > n) break;
			vis[i * j]=1;
			if(i % j == 0) break;
		}
	}
}
void solve(){
	cin>>n;
	int ans = 1;
	for(auto i: pr){
		if(n % i == 0){
			ans *= i;
			while(n % i == 0) n /= i;
		}
	}
	ans *= n;
	cout << ans << '\n';
}
int main(){
	ios::sync_with_stdio(false);
	init();
	cin >> tc;
	while(tc--) solve();
}

By StayAlone.

import sys
import math

def read_int():
    return int(sys.stdin.readline().strip())

def solve():
    n = read_int()
    ans = 1
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ans *= i
            while n % i == 0:
                n //= i
    print(ans * n)

T = read_int()
for _ in range(T):
    solve()

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Epic problem
• Did not solve

For an array $$$a_i$$$, only the last occurrence of each element matters. Therefore, the problem reduces to the case where all elements in one array are distinct.

Think the process in reverse.

Also, throughout the whole process, only the last occurrence of each element matters, so we may determine the order by working backwards.

Fix an order (in reverse). For each array in this order, we iterate through its elements. If an element is already contained in $$$Q$$$, ignore it. Otherwise, append it to the end of $$$Q$$$.

Thus, at each step, we choose the array that is lexicographically smallest among the remaining ones. Then, for the remaining arrays, we only keep the elements that are not contained in $$$Q$$$. Comparing two arrays takes $$$\mathcal O(\min{|a_i|, |a_j|})$$$, we can solve the problem with total time complexity $$$\mathcal O(n^2+n\sum l_i)$$$.

By StayAlone.

#include <bits/stdc++.h>
#define rep1(i, l, r) for (int i = l; i <= int(r); ++i)
using namespace std;
const int MAXN = 1e6 + 10, inf = ~0U >> 2;
int n, vis[MAXN], chg[8010]; vector <int> a[8010];
 
void init(vector <int> &now) {
    for (auto &v : now) cin >> v, vis[v] = 0;
    reverse(begin(now), end(now));
    vector <int> nw;
    for (auto v : now) if (!vis[v]) nw.emplace_back(v), vis[v] = 1;
    for (auto v : nw) vis[v] = 0;
    now = nw;
}
 
void change(vector <int> &now) {
    if (now.size() == 1 && now[0] == inf) return;
    vector <int> nw;
    for (auto v : now) if (!vis[v]) nw.emplace_back(v);
    now = nw;
}
 
void solve() {
    cin >> n;
    rep1(i, 1, n) {
	int _;
	cin >> _;
        a[i].resize(_); init(a[i]); chg[i] = 0;
    }
    rep1(i, 1, n) {
    	int id = 1;
    	rep1(j, 1, n) if (!chg[j] && a[j] < a[id]) id = j;
    	auto &now = a[id];
        for (auto v : now) printf("%d ", v), vis[v] = 1;
        now = vector <int> {inf}; chg[id] = 1;
        rep1(j, 1, n) if (!chg[j]) change(a[j]);
    } puts("");
}
 
int main() {
	int T;
	cin >> T;
    for (; T--; ) solve();
    return 0;
}

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Epic problem
• Did not solve

Simons's goal of minimizing operations means that the remaining array should be as long as possible.

Which element is absolutely impossible to remove?

The position of the maximum value cannot be removed, and we can see that splitting the array from the maximum value will result in two independent parts.

Consider the Cartesian tree of the given permutation.

It's noticed that the maximum number of each number cannot be moved, and either the left side or the right side will be removed completely, so we can solve both sides separately.

The maximum number of both sides cannot be removed, either. Accordingly, they became the same problem with smaller scale.

Build the Cartesian tree for the sequence. It's easy to see that any path from the root corresponds to a way to keep the maximum number on one side and delete the others.

Calculate the depth of each node $$$d_u$$$, then the answer is $$$n - \max d_u$$$.

The solution could be done in $$$\Theta(n)$$$, and there are also solutions based on Dynamic Programming (DP) for time complexity $$$\tilde O(n)$$$.

By yanghanyv.

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int t,n,a[N],del[N],stk[N],top,ans;
void init(){
	for(int i=1;i<=n;i++){
		del[i]=0;
	}
	ans=n;
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		init();
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		top=0;
		for(int i=1;i<=n;i++){
			while(top&&a[stk[top]]<a[i]){
				top--;
			}
			stk[++top]=i;
			del[i]+=i-top;
		}
		top=0;
		for(int i=n;i>=1;i--){
			while(top&&a[stk[top]]<a[i]){
				top--;
			}
			stk[++top]=i;
			del[i]+=n-i+1-top;
		}
		for(int i=1;i<=n;i++){
			ans=min(ans,del[i]);
		}
		printf("%d\n",ans);
	}
	return 0;
}

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Epic problem
• Did not solve

Consider applying Dynamic Programming (DP) to solve the problem. What may the state be?

Assign a unique way to operate $$$s$$$ to $$$t$$$ for every different $$$s$$$.

For any $$$[l_i, r_i]$$$ you chose, consider the border of $$$t_{[l_i, r_i]}$$$. A border of an array $$$a[1 \sim n]$$$ means the subarray $$$a[1,l]$$$ such that $$$a[1,l] = a[n - l + 1,n]$$$.

Let's apply Dynamic Programming to the problem.

Assume $$$dp_i$$$ represents the different arrays $$$s[1:i]$$$ can generate $$$t[1:i]$$$.

to update $$$dp_{i + 1}$$$, consider the last subarray in the decomposition $$$dp_{[a, i + 1]}$$$. To ensure no duplicate counting, $$$dp_{[a, i + 1]}$$$ can't have a border. Which is to say, for any $$$s$$$ which could be operated to $$$t$$$, it could be realized by decomposing $$$s$$$ into subarrays without a border and reversing them.

Why can the solution above calculate the answer correctly?

To check if any $$$dp_{[l, r]}$$$ has a border, we need to apply the KMP algorithm (starting from $$$t_{1 \sim n}$$$)for $$$n$$$ times, whose time complexity is $$$O(n^2)$$$. The dp progress also takes $$$O(n^2)$$$ time. So the total time complexity is $$$O(n^2)$$$.

By Leftist_G.

#include <bits/stdc++.h>
#define fr1(i, a, b) for (int i = a; i <= b; i++)
#define fr2(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
const int N = 1e5 + 10;
const int mod = 998244353;
int tc;
int n;
int a[N];
int dp[N];
int kmp[N];
void add(int & x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
void solve() {
    cin >> n;
    fr1(i, 1, n) cin >> a[i];
    dp[0] = 1;
    fr1(i, 1, n) dp[i] = 0;
    fr1(i, 1, n) {
        kmp[i] = i + 1;
        int poi = i + 1;
        fr2(j, i - 1, 1) {
            while (a[j] != a[poi - 1] && poi != i + 1) poi = kmp[poi];
            if (a[j] == a[poi - 1]) poi--;
            kmp[j] = poi;
        }
        fr2(j, i, 1) {
            if (kmp[j] == i + 1) add(dp[i], dp[j - 1]);
        }
    }
    cout << dp[n] << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin >> tc;
    while (tc--) solve();
}

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Epic problem
• Did not solve

Consider the case without any "accidents", i.e., when there are no additional restrictions on the reconstructed streets.

Observe the structure of a valid solution and try to construct a kind of "basis".

We can define each basis as a square, and assign its value as follows:

Now, it is easy to see that any subset of the bases forms a valid solution, and conversely, any valid solution can be decomposed into such bases.

Now consider a street that cannot be reconstructed. This implies that the two bases it connects must have the same state — either both are chosen, or both are not chosen. Therefore, we can use a DSU to maintain these constraints. The overall time complexity is $$$\mathcal O(nm\alpha(nm))$$$.

By yanghanyv.

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
const int M=4e5+5;
int t,n,m,fa[M];
ll s[M],ans;
vector<int> w[N],v[N];
void init(){
	for(int i=1;i<=n;i++){
		w[i].clear();
		v[i].clear();
	}
	for(int i=0;i<=(n-1)*(m-1);i++){
		fa[i]=i;
		s[i]=0;
	}
	ans=0;
}
int idx(int x,int y){
	return x>=1&&x<n&&y>=1&&y<m?(x-1)*(m-1)+y:0;
}
int find(int x){
	return fa[x]!=x?fa[x]=find(fa[x]):fa[x];
}
void merge(int a,int b){
	if(find(a)!=find(b)){
		fa[find(a)]=find(b);
	}
}
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		init();
		for(int i=1;i<n;i++){
			w[i].resize(m+1);
			for(int j=1;j<=m;j++){
				scanf("%d",&w[i][j]);
			}
		}
		for(int i=1;i<=n;i++){
			v[i].resize(m);
			for(int j=1;j<m;j++){
				scanf("%d",&v[i][j]);
			}
		}
		for(int i=1;i<n;i++){
			for(int j=1;j<m;j++){
				s[idx(i,j)]=1ll*w[i][j]-1ll*w[i][j+1]+1ll*v[i][j]-1ll*v[i+1][j];
			}
		}
		for(int i=1;i<n;i++){
			scanf("\n");
			for(int j=1;j<=m;j++){
				char p;
				scanf("%c",&p);
				if(p=='0'){
					merge(idx(i,j-1),idx(i,j));
				}
			}
		}
		for(int i=1;i<=n;i++){
			scanf("\n");
			for(int j=1;j<m;j++){
				char q;
				scanf("%c",&q);
				if(q=='0'){
					merge(idx(i-1,j),idx(i,j));
				}
			}
		}
		for(int i=1;i<=(n-1)*(m-1);i++){
			if(find(i)!=i&&find(i)!=find(0)){
				s[find(i)]+=s[i];
			}
		}
		for(int i=1;i<=(n-1)*(m-1);i++){
			if(find(i)==i&&find(i)!=find(0)){
				ans+=max(s[i],0ll);
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

• Horrible problem
• Bad problem
• Average problem
• Good problem
• Epic problem
• Did not solve

The equation has an integral solution if and only if $$$\gcd(i\oplus j,j\oplus k)$$$ is a divisor of $$$n$$$. This is a famous theorem, called Bézout's theorem.

Considering enumerating $$$g=\gcd(i\oplus j,j\oplus k)$$$, then we calculate how many tuples $$$(i,j,k)$$$ can exactly get this $$$g$$$.

Consider Möbius inversion formula. There is a famous equation that $$$[n=1]=\sum\limits_{d|n}\mu (d)$$$, where $$$\mu$$$ is the Möbius function.

Apply Möbius' formula, and try to transform the formula we need to calculate until you have to calculate $$$f(T)$$$ for every $$$T$$$ from $$$1$$$ to $$$2m$$$, where $$$f(T)$$$ is the number of tuples $$$(i,j,k)$$$ such that $$$T$$$ is a divisor of both $$$i\oplus j$$$ and $$$j\oplus k$$$.

Consider enumerating $$$j$$$, $$$d_1T=i\oplus j$$$ and $$$d_2T=j\oplus k$$$. It's easy to see that the number of tuples $$$(j,d_1,d_2)$$$ is equal to the number of tuples $$$(i,j,k)$$$, if we ensure that $$$d_1T\oplus j \le m$$$ and $$$d_2T\oplus j\le m$$$.

Due to the series sum of Harmonic series, it can be accepted to enumerate $$$T$$$ and $$$d_1$$$.

Observation: although a pair of $$$T$$$ and $$$d_1$$$ will process a set of $$$j$$$ such that $$$d_1T\oplus j\le m$$$, these $$$j$$$ will be distributed in $$$\mathcal O(\log m)$$$ intervals.

You can prove the observation by considering the bitmask of $$$m$$$ and $$$d_1T$$$.

The sum of the number of intervals will be $$$\mathcal O(m\ln m\log m)$$$. How about applying a data structure to record the intervals?

After recording, we can enumerate $$$d_2$$$ in the same complexity. It's easy to see we need to find the intersection of some intervals (the number of $$$j$$$ that satisfy both conditions simultaneously). We will make queries on our data structure to complete it.

Trie is a suitable data structure. If you are sensitive to some observations, Fenwick Tree also works.

We will ignore a few corner cases, such as $$$i=j$$$ or $$$j=k$$$, and other corner cases involving $$$0$$$. The contributions of those cases are relatively simple or classical, so we omit them here; Consequently, some summation bounds below are not written with full formal tightness.

We actually want to compute

As usual, enumerate the value of the $$$\gcd$$$. Thus

where $$$p=i\oplus j$$$, $$$q=j\oplus k$$$, and $$$c(p,q)$$$ is the number of tuples $$$(i,j,k)$$$ with those values of $$$p$$$ and $$$q$$$.

Apply Möbius inversion to the condition $$$\gcd(p,q)=d$$$:

where $$$\mu$$$ is the Möbius function.

We now change the summation order and pull $$$d'$$$ outward.

Writing $$$T=dd'$$$ we obtain

The outer sum over $$$T$$$ runs up to $$$2m$$$ because $$$p,q\in[0,2m]$$$.

The inner quantity depends on $$$T$$$ only. Let $$$f(T)$$$ be the number of tuples $$$(i,j,k)$$$ such that $$$T$$$ is a divisor of both $$$i\oplus j$$$ and $$$j\oplus k$$$.

Then the entire sum becomes

Due to the series sum of the Harmonic series, we can enumerate $$$T$$$ and $$$d$$$ in $$$\mathcal O(m\ln m)$$$. Hence, the main task is to compute $$$f(T)$$$ efficiently for all $$$T$$$.

Fix $$$T$$$. We enumerate $$$j$$$ and count the number of pairs $$$(i,k)$$$ such that $$$i\oplus j$$$ and $$$j\oplus k$$$ are multiples of $$$T$$$.

Equivalently, we count the number of pairs $$$(d_1,d_2)$$$ under the enumerated $$$j$$$ such that

with the additional constraints $$$d_1T\oplus j\le m$$$ and $$$d_2T\oplus j\le m$$$ (because $$$(i,k)$$$ must lie in $$$[0,m]$$$).

Equivalently, if we can enumerate $$$d_1,d_2$$$ to get $$$d_1T$$$ and $$$d_2T$$$, we only need to find the number of $$$j$$$ that satisfy both constraints. If we enumerate $$$d_1$$$ to find the set of $$$j$$$ and record it, we can enumerate $$$d_2$$$ similarly, and what we need to calculate is the size of the intersection of the two sets.

Consider enumerating $$$d_1$$$ to get $$$d_1T$$$, due to bitmask theory, the $$$j$$$ such that $$$d_1T\oplus j\le m$$$ will be distributed in $$$\mathcal O(\log m)$$$ intervals.

By using Segment Tree or Fenwick Tree naively, we will solve the problem in $$$\mathcal O(m\ln m\log^2 m)$$$, which is too slow to get accepted in the problem.

By LiHn's observation, actually, we can apply a Trie instead of a Segment Tree to record the intervals, because each interval can be formed by a subtree in the Trie. This will allow us to avoid incurring a logarithmic cost to find intervals in data structures every time.

By Leftist_G's observation, there are only two types of intervals, but one type of intervals has $$$\mathcal O(\log)$$$, and another has $$$\mathcal O(1)$$$. We can avoid using Segment Tree or Fenwick Tree in the former.

By liuhangxin's observation, we can avoid using any data structure. We can naively save the intervals, sort them, and then apply two pointers to calculate the intersection. Note that if we implement the method naively, the complexity will turn to $$$\mathcal O(m\ln m\log m\log\log m)$$$ (although it may be enough to get Accepted). He used a designed order and implmented carefully to ensure his complexity.

All solutions above can solve the problem in $$$\mathcal O(m\ln m\log m)$$$.

Note that some not-so-good solutions may apply __int128 to avoid integer overflow. Don't forget to deal with corner cases.

By LiHn.

#include<bits/stdc++.h>
#define rep1(i, a, b) for(int i = a; i <= b; ++i)
#define rep2(i, a, b) for(int i = a; i >= b; --i)
#define pii pair <int, int>
#define ft first
#define sd second
#define ll long long
#define pb push_back
#define gmax(a, b) a = max(a, b)
#define gmin(a, b) a = min(a, b)
#define all(a) a.begin(), a.end()
#define debug cout << "------------------\n"
const int N = (1 << 21) + 10;
using namespace std;
int tot, ch[N][2], cnt[N], sz[N], fa[N]; ll f[N], sum[N];
int p[N], vis[N], miu[N];
void solve() {
    int n, m; cin >> n >> m;
    // get miu
    rep1(i, 0, tot) ch[i][0] = ch[i][1] = sz[i] = fa[i] = sum[i] = cnt[i] = 0;

    miu[1] = 1;
    tot = 0;
    rep1(i, 2, 2 * m) vis[i] = 0;
    rep1(i, 2, 2 * m) {
        if(!vis[i]) p[++tot] = i, miu[i] = -1;
        for(int j = 1; p[j] * i <= 2 * m && j <= tot; ++j) {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) break;
            miu[i * p[j]] = -miu[i];
        }
    }

    // get trie
    tot = 1;
    rep1(i, 0, m) {
        int nw = 1;
        rep2(j, 19, 0) {
            int &nxt = ch[nw][i >> j & 1];
            if(!nxt) nxt = ++tot, fa[nxt] = nw;
            nw = nxt;
        }
        while(nw) ++sz[nw], nw = fa[nw];
    }

    // get f(T)
    rep1(T, 1, 2 * m) {
        f[T] = 0;
        rep1(d, 1, 2 * m / T) {
            int nw = 1, bg = 0, v = (d * T) ^ m;
            rep2(i, 19, 0) {
                int x = v >> i & 1;
                if(m >> i & 1) {
                    int u = ch[nw][x ^ 1];
                    if(u) ++cnt[u], sum[u] += sz[u];
                }
                if(!ch[nw][x]) {bg = i + 1; break;}
                nw = ch[nw][x];
            }
            ll num = 0;
            if(!bg) ++cnt[nw], ++sum[nw], ++num;
            rep1(i, bg, 19) {
                nw = fa[nw];
                int x = v >> i & 1;
                if(m >> i & 1) {
                    int u = ch[nw][x ^ 1];
                    num += sz[u];
                }
                sum[nw] += num;
            }
        }
        rep1(d, 1, 2 * m / T) {
            int nw = 1, v = (d * T) ^ m;
            ll num = 0;
            rep2(i, 19, 0) {
                int x = v >> i & 1;
                num += cnt[nw];
                if(m >> i & 1) {
                    int u = ch[nw][x ^ 1];
                    if(u) f[T] += sum[u] + 1ll * num * sz[u];
                }
                nw = ch[nw][x];
                if(!nw) break;
            }
            if(nw) f[T] += sum[nw] + 1ll * num * sz[nw];
        }
        rep1(d, 1, 2 * m / T) {
            int nw = 1, bg = 0, v = (d * T) ^ m;
            rep2(i, 19, 0) {
                int x = v >> i & 1;
                int u = ch[nw][x ^ 1];
                cnt[nw] = sum[nw] = cnt[u] = sum[u] = 0;
                nw = ch[nw][x];
            }
            if(nw) cnt[nw] = sum[nw] = 0;
        }
    }

    ll ans = 0;
    rep1(d, 1, 2 * m) {
        if(n % d) continue;
        rep1(j, 1, 2 * m / d) {
            ans += miu[j] * f[j * d];
        }
    }

    // get i == j or j == k
    rep1(g, 1, 2 * m) {
        if(n % g) continue;
        int nw = 1, v = g ^ m;
        rep2(i, 19, 0) {
            int x = v >> i & 1;
            if(m >> i & 1) {
                int u = ch[nw][x ^ 1];
                ans += 2 * sz[u];
            }
            nw = ch[nw][x]; if(!nw) break;
        }
        if(nw) ans += 2;
    }

    cout << ans << '\n';
}
int main() {
    int T = 1; cin >> T;
    while(T--) solve();
    return 0;
}