If $$$a=b$$$ we need $$$0$$$ steps.

If $$$a$$$ can be divided by $$$b$$$, we only need $$$1$$$ step, which is to multiply $$$b$$$ by $$$\frac{a}{b}$$$. Same for the case when $$$b$$$ can be divided by $$$a$$$.

Otherwise, we need at most $$$2$$$ steps. As both $$$a$$$ and $$$b$$$ are positive integers, we can first multiply $$$a$$$ by $$$b$$$ and then multiply $$$b$$$ by the original value of $$$a$$$. Both number will be equal to $$$a\times b$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int solve(){
    int a,b;
    cin >> a >> b;
    if(a == b) return 0;
    if(a % b == 0 || b % a == 0) return 1;
    return 2;
}
 
int main(){
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while(TC --){
        cout << solve() << '\n';
    }
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

The number of cakes collected from an oven depends only on the last time Maple visits it. Therefore, in the optimal strategy, she should visit distinct ovens in the last $$$\min(m,n)$$$ seconds.

Let's think in reverse: suppose we fix an order $$$p_1,\dots,p_n$$$ of the ovens. Then at second $$$m$$$ we visit oven $$$p_1$$$, at second $$$m-1$$$ we visit oven $$$p_2$$$, and so on. For the $$$i$$$-th oven in this order, we collect $$$a_{p_i}\cdot \max(0, m-i+1)$$$ cakes.

To maximize the total number of cakes collected, ovens with larger $$$a_i$$$ should be visited later (i.e., assigned larger multipliers). Thus we sort $$$a$$$ in non-increasing order first.

The final answer is $$$\sum_{i=1}^n a_i \cdot \max(0, m-i+1)$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
 
void solve(){
    int n,t;
    cin >> n >> t;
    ll ans = 0;
    vector <int> a(n);
    for(int i = 0;i < n;i ++) cin >> a[i];
    sort(a.begin(),a.begin() + n,greater <int>());
    for(int i = 0;i < n;i ++) ans += 1ll * a[i] * max(0,t - i);
    cout << ans << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while(TC --){
        solve();
    }
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

You can backtrack from the final state.

Denote the state $$$(a,b)$$$ that indicates Chocola has $$$a$$$ cakes and Vanilla has $$$b$$$ cakes.

After one operation of type $$$1$$$, Vanilla's number of cakes will definitely be at least half of the total, and similarly for operation $$$2$$$. If $$$0 \lt a \lt 2^{k}$$$, then $$$2^{k} \lt b \lt 2^{k+1}$$$, meaning the previous operation must have been type $$$1$$$. Similarly, if $$$0 \lt b \lt 2^{k}$$$, the previous operation must have been type $$$2$$$.

Therefore, you can backtrack from the final state $$$(x,2^{k+1}-x)$$$, until it reaches the initial state $$$(2^k,2^k)$$$.

Now let's analyze how many steps we need to do during the process.

For the state $$$(a, b)$$$, where $$$a, b \neq 0$$$, assume $$$a = i \cdot 2^{p_a}$$$ and $$$b = j \cdot 2^{p_b}$$$, $$$i$$$ and $$$j$$$ are positive odd integers.

Since $$$a + b = 2^{k+1}$$$, it must be true that $$$ 0 \le p_a = p_b \le k$$$ , and after one operation $$$1$$$ or $$$2$$$, both $$$p_a$$$ and $$$p_b$$$ decrease by exactly $$$1$$$.

Therefore, the whole process takes at most $$$k$$$ steps, so we solve the problem with $$$O(tk)$$$ time complexity.

#include <bits/stdc++.h> 
using namespace std;
int main(){
    int t; cin>>t;
    while(t--){
        long long k,x,kk; cin>>k>>x; kk=1ll<<k;
        if (!x||x==kk*2) {cout<<"-1\n"; continue;}
        long long y=kk*2-x;
        vector<int> ans; ans.clear();
        while(x!=kk){
            if (x>y) ans.push_back(2),x-=y,y*=2;
            else ans.push_back(1),y-=x,x*=2;
        }
        cout<<ans.size()<<"\n";
        while(!ans.empty()) cout<<ans.back()<<' ',ans.pop_back();
        cout<<"\n";
    }
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

For array $$$b$$$, we can prove that $$$f(b)\neq g(b)$$$ if and only if there exist indexes $$$1\le i \lt j \lt k\le m$$$ which satisfy $$$b_i \gt b_j \gt b_k$$$.

Since $$$a$$$ is a permutation, all elements in $$$b$$$ should be distinct. $$$g(b)$$$ is equal to the number of inversions in $$$b$$$. When there exists some index $$$i$$$ that satisfies $$$a_i \gt a_{i+1} \gt a_{i+2}$$$, we can reduce the number of inversions by $$$3$$$ by applying operation $$$2$$$, allowing $$$f(b)$$$ to become less than $$$g(b)$$$. This is the only case where you can reduce more than $$$1$$$ inversion with one operation.

If there exist indexes $$$1\le i \lt j \lt k\le m$$$ which satisfy $$$b_i \gt b_j \gt b_k$$$, we can first choose indexes $$$i,k$$$, then move all elements greater than $$$b_i$$$ to the right of $$$b_k$$$ and move all elements less than $$$b_k$$$ to the left of $$$b_i$$$ by swapping adjacent numbers (applying the first operation). Now all elements $$$b_p$$$ between $$$b_i,b_k$$$ satisfy $$$b_i \gt b_p \gt b_k$$$. We then swap them to the left of $$$b_i$$$ until there is only one element $$$b_j$$$ left. Now $$$b_i \gt b_j \gt b_k$$$ and they are adjacent, and we can apply operation $$$2$$$ on the current index of $$$b_i$$$.

If we only apply operation $$$1$$$ on indexes $$$i$$$ which satisfy $$$b_i \gt b_{i+1}$$$, there will never exist any index $$$i$$$ satisfying $$$b_i \gt b_{i+1} \gt b_{i+2}$$$ in $$$b$$$ during the process. If we apply an operation $$$1$$$ on some index $$$i$$$ where $$$b_i \lt b_{i+1}$$$, the number of inversions will be increased by $$$1$$$ instead of decreased by $$$1$$$, which makes it impossible to reach $$$f(b) \lt g(b)$$$ with one operation $$$2$$$, even if it decreases the number of inversions by $$$3$$$. Therefore, in this case $$$f(b)=g(b)$$$.

For each element $$$a_i$$$, we define:

• $$$l_i$$$: the maximum index $$$ \lt i$$$ such that $$$a_{l_i} \gt a_i$$$,
• $$$r_i$$$: the minimum index $$$ \gt i$$$ such that $$$a_{r_i} \lt a_i$$$.

Then the answer to a query $$$[l, r]$$$ is $$$\texttt{NO}$$$ if and only if some segment $$$[l_i, r_i]$$$ lies fully inside $$$[l, r]$$$.

To answer multiple queries, you can preprocess the smallest $$$r$$$ for every $$$l$$$ such that the answers for all $$$[l,x](x\ge r)$$$ should be $$$\texttt{NO}$$$.

The time complexity is $$$O(n)$$$ if you find $$$l_i,r_i$$$ with the Monotonic Stack trick. $$$O(n\log n)$$$ solutions can also pass.

#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
 
    vector<int> mxl(n + 1), mir(n + 1);
    for (int i = 1; i <= n; i++)
    {
        mxl[i] = i - 1;
        while (mxl[i] > 0 && a[mxl[i]] < a[i])
            mxl[i] = mxl[mxl[i]];
    }
    for (int i = n; i >= 1; i--)
    {
        mir[i] = i + 1;
        while (mir[i] <= n && a[mir[i]] > a[i])
            mir[i] = mir[mir[i]];
    }
    vector<int> L(n + 1, 0);
    for (int i = 2; i < n; i++)
    {
        if (mxl[i] > 0 && mir[i] <= n)
        {
            L[mir[i]] = max(L[mir[i]], mxl[i]);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        L[i] = max(L[i], L[i - 1]);
    }
 
    for (int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        if (l <= L[r])
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

We can first find out that the maximum possible answer is the minimum depth among all leaves $$$d=\min{dep_u}$$$, as the LCS can't be greater than the minimum length of all names.

We consider a special case first where all leaves have the same depth. If we want to achieve the maximum answer $$$d$$$, the names of all leaves should be exactly the same. Which means, for any two vertices with the same depth, their labels has to be the same.

For each depth $$$i$$$, we group all vertices with depth $$$i$$$ together as the $$$i$$$-th group (suppose root has depth $$$1$$$). For each group, all vertices in the group should have the same label. Let the size of groups $$$1,\cdots,d$$$ be $$$c_1,\cdots,c_d$$$. Now the problem can be considered as a knapsack problem, where you have $$$d$$$ items with weight $$$c_1,\cdots,c_d$$$. We need to find out whether you can take several numbers from $$$c$$$ that have a sum equal to $$$k$$$. This can be solved in $$$O(n^2)$$$.

If the maximum answer $$$d$$$ is not achievable, we can show that you can always achieve $$$d-1$$$. For each group from the first to the $$$d$$$-th, we assign an arbitrary label $$$0$$$ or $$$1$$$ which still has at least $$$c_i$$$ numbers remaining to all vertices in the group. As all leaves have the same depth, $$$c_d$$$ should be the maximum element in the array, so you are always able to select a label for groups $$$1$$$ to $$$d-1$$$. Then arbitrarily distribute the remaining labels among vertices in the last groups (which are leaves).

Now consider the general case where not all leaves have the same depth. If we want to achieve answer $$$=d$$$, we need to select $$$d$$$ groups. For each leaf vertex $$$v$$$, there should exist a vertex in the $$$d$$$-th group which is an ancestor of $$$v$$$. And for every $$$2\le i\le d$$$, for each vertex $$$v$$$ in the $$$i$$$-th group, there should exist a vertex in the $$$i-1$$$-th group which is an ancestor of $$$v$$$. All vertices in the same group should have the same label. Suppose the $$$i$$$-th group has label $$$l_i$$$, then we can achieve $$$\text{LCS}=l_1l_2\ldots l_d$$$ which has length $$$d$$$.

We can still group all vertices with depth $$$1\le i\le d$$$ together as the $$$i$$$-th group. For all vertices with depth $$$ \gt d$$$, we can set their label arbitrarily. We can view them as items with weight $$$1$$$ in the knapsack problem.

And we can show this is the optimal way to select $$$d$$$ groups. If some vertex $$$u$$$ with depth $$$\le d$$$ is not selected, there must be some vertices selected in some group in the subtree of $$$u$$$, because the path from the root to $$$u$$$ consists of fewer than $$$d$$$ vertices. If the smallest group index that some vertex in the subtree of $$$u$$$ belongs to is $$$i$$$, we can instead let $$$u$$$ be inside the $$$i$$$-th group, and then the labels of all vertices in the subtree of $$$u$$$ that were previously in group $$$i$$$ can be selected arbitrarily. If we consider the knapsack problem, we have reduced some $$$c_i$$$ by $$$x$$$ and added $$$x$$$ items with weight $$$1$$$. All achievable values still remain achievable, while some previously unachievable values become achievable.

The time complexity is $$$O(n^2)$$$, the bottleneck is knapsack.

// n^2/w
#include <bits/stdc++.h>
using namespace std;
int solve() {
    int n, k;
    cin >> n >> k;
    vector<int> fa(n, -1), dep(n, 0);
    vector<int> noson(n, 1), cnt(n + 1);
    cnt[0]++;
    for (int i = 1; i < n; i++) {
        cin >> fa[i], fa[i]--;
        dep[i] = dep[fa[i]] + 1;
        cnt[dep[i]]++;
        noson[fa[i]] = 0;
    }
    int mxdep = 1e9;
    for (int i = 0; i < n; i++)
        if (noson[i]) mxdep = min(mxdep, dep[i]);
 
    int sum = 0;
 
    vector<int> dp(n + 1);
    dp[0] = 1;
    for (int i = 0; i <= mxdep; i++) {
        for (int j = sum; j >= 0; j--) dp[j + cnt[i]] |= dp[j];
        sum += cnt[i];
    }
    if (sum <= k || sum <= n - k) return mxdep + 1;
    for (int i = 0; i <= sum; i++)
        if (dp[i]) {
            if (i <= k && sum - i <= n - k) return mxdep + 1;
        }
    return mxdep;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) cout << solve() << "\n";
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

We focus on optimizing the knapsack problem. In the knapsack problem we only need to know $$$f_i=0/1$$$ which means whether you can achieve sum $$$i$$$, so we can optimize the knapsack with bitset. The time complexity is $$$O(\frac{n^2}{\omega})$$$ which is enough to pass E2.

But actually we can do better. For the knapsack problem, it has at most $$$n$$$ items, and the sum of weights of all items is also at most $$$n$$$. We can do a sqrt decomposition trick here.

• For items with weight $$$\ge\sqrt{n}$$$, there are at most $$$\sqrt{n}$$$ such items.
• For items with weight $$$ \lt \sqrt{n}$$$, we count the number of items for each different weight. If there are $$$c_w$$$ items for weight $$$w$$$, we decompose $$$x$$$ into $$$c_w=2^0+2^1+\cdots+2^k+y$$$ where $$$k$$$ is the largest integer satisfying $$$2^0+2^1+\ldots+2^k\le c_w$$$. Then we create new items with weights $$$2^0\cdot w,2^1\cdot w,\ldots,2^k\cdot w,y\cdot w$$$. The set of new items is the same as $$$c_w$$$ items with weight $$$w$$$ if we only consider the different sum of weights the set of items can achieve. Now we only have $$$\sum_{w=1}^{\sqrt{n}}\log(c_w)=\sqrt{n}$$$ items.

The total time complexity is $$$O(\sqrt{n}\cdot n+\sqrt{n}\cdot n)=O(n\sqrt{n})$$$.

And this can also be optimized with bitset, leading to an $$$O(\frac{n\sqrt{n}}{\omega})$$$ solution.

// nsqrtn/w
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
template <int maxn>
int solve(int n, int k) {
    if (maxn <= n) {
        return solve<min(N, maxn * 2)>(n, k);
    }
    bitset<maxn> dp;
    vector<int> fa(n, -1), dep(n, 0);
    vector<int> noson(n, 1), cnt(n + 1);
    cnt[0]++;
    for (int i = 1; i < n; i++) {
        cin >> fa[i], fa[i]--;
        dep[i] = dep[fa[i]] + 1;
        cnt[dep[i]]++;
        noson[fa[i]] = 0;
    }
    dp.reset();
    dp[0] = 1;
    int mxdep = 1e9;
    for (int i = 0; i < n; i++)
        if (noson[i]) mxdep = min(mxdep, dep[i]);
 
    int sum = 0;
    vector<int> all(cnt.begin(), cnt.begin() + mxdep + 1);
    sort(all.begin(), all.end());
    vector<int> v;
    for (int i = 0; i < (int)all.size(); i++) {
        int j = i;
        while (j + 1 < (int)all.size() && all[i] == all[j + 1]) j++;
        int t = j - i + 1;
        for (int z = 1; z <= t; z *= 2) {
            v.push_back(z * all[i]);
            t -= z;
        }
        if (t > 0) v.push_back(t * all[i]);
        i = j;
    }
    dp[0] = 1;
    for (auto val : v) {
        sum += val;
        dp |= (dp << val);
    }
    if (sum <= k || sum <= n - k) return mxdep + 1;
    for (int i = 0; i <= sum; i++)
        if (dp[i]) {
            if (i <= k && sum - i <= n - k) return mxdep + 1;
        }
    return mxdep;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, k;
        cin >> n >> k;
        cout << solve<1>(n, k) << "\n";
    }
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

Let’s define $$$b_i$$$ as the position of the $$$i$$$-th slider decreased by $$$i$$$. Every operation on the sliders can be interpreted as a modification of the array $$$b$$$.

• If we increase the position of slider $$$i$$$, then $$$b_i$$$ increases. At the same time, every suffix element $$$b_{i+1}, b_{i+2}, \dots, b_n$$$ gets updated to $$$b_j := \max(b_j, b_i)$$$.

• If we decrease the position of slider $$$i$$$, then $$$b_i$$$ decreases. At the same time, every prefix element $$$b_1, b_2, \dots, b_{i-1}$$$ gets updated to $$$b_j := \min(b_j, b_i)$$$.

Since the array $$$b$$$ always remains non-decreasing, we can reinterpret operations as follows:

• Every operation simultaneously applies a $$$\min$$$ operation to all elements on the left, and a $$$\max$$$ operation to all elements on the right.

For a fixed slider $$$b_i$$$, the effect of each operation on the slider should be one of the following:

1. $$$b_i := \max(b_i, x)$$$
2. $$$b_i := \min(b_i, x)$$$
3. $$$b_i := x$$$ (assignment)

Our task is to compute the sum of final values of $$$b_i$$$ after all possible sequences of operations.

We sort all operations by their parameter $$$x$$$. If multiple operations share the same $$$x$$$, we give them a consistent order and then assume all $$$x$$$ are distinct in the following part of the editorial.

We first suppose that the position of the slider is changed at least once. Suppose the final value for slider $$$i$$$ is $$$b_e$$$, let’s consider which operation sets $$$b_i = b_e$$$ at the very end.

At this point, we no longer care about the exact value of $$$b_i$$$ during the process — only whether it is less than, equal to, or greater than $$$b_e$$$.

All operations of type $$$\max$$$ with $$$x \lt b_e$$$ and type $$$\min$$$ with $$$x \gt b_e$$$ are irrelevant. We can insert them anywhere after deciding the order of other operations without affecting the result. We won't consider these operations in the following parts of the editorial.

All assignment operations $$$b_i := x$$$ can be reinterpreted:

• If $$$x \lt b_e$$$, treat it as $$$b_i := \min(b_i, x)$$$.
• If $$$x \gt b_e$$$, treat it as $$$b_i := \max(b_i, x)$$$.

The last operation, that makes $$$b_i = b_e$$$ must be the one with parameter $$$x = b_e$$$.

• If this operation is assignment, then all other operations can appear in any order.

• If this operation is $$$\max$$$ type, then immediately before it we must have $$$b_i \lt b_e$$$.

• • Either the last preceding valid operation is some $$$\min$$$ type operation making $$$b_i \lt b_e$$$;
• • Or no other effective operation occurs, and the initial value of $$$b_i$$$ was already smaller than $$$b_e$$$.

• If this operation is $$$\min$$$ type operation, it is symmetric: either the last preceding valid operation is a $$$\max$$$ type operation, or the initial value of $$$b_i$$$ was already larger than $$$b_e$$$.

Finally, don’t forget the case where a slider is never touched, where it simply keeps its initial value.

For each of the $$$n$$$ sliders, we need to check contributions over all $$$m$$$ operations. The overall time complexity is $$$O(nm)$$$.

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
long long a[5000],ans[5000],tt[5001],inv[5001];
struct apos{
	long long id;
	long long x;
	friend bool operator<(apos a,apos b){
		return a.x<b.x;
	}
}ap[5000];
int main(){
	ios::sync_with_stdio(false),cin.tie(0);
	int T,flag;
	long long n,m,p,q,x,i,j,cl,cr;
	tt[0]=1;
	for(i=1;i<=5000;i++)tt[i]=tt[i-1]*i%mod;
	inv[1]=1;
	for(i=2;i<=5000;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	for(cin>>T;T>0;T--)
	{
		cin>>n>>m>>p;
		for(i=0;i<n;i++)
		{
			cin>>a[i];
			a[i]-=i;
		}
		for(i=0;i<p;i++)
		{
			cin>>ap[i].id>>ap[i].x;
			ap[i].id--;
			ap[i].x-=ap[i].id;
		}
		sort(ap,ap+p);
		for(i=0;i<n;i++)
		{
			flag=0;
			for(j=0;j<p;j++)
			{
				if(ap[j].id<=i&&ap[j].x>=a[i])flag=1;
				if(ap[j].id>=i&&ap[j].x<a[i])flag=1;
			}
			if(!flag)
			{
				ans[i]=a[i]+i;
				continue;
			}
			ans[i]=0;
			cl=0;
			cr=0;
			for(j=0;j<p;j++)
			{
				if(ap[j].id<=i)cr++;
			}
			for(j=0;j<p;j++)
			{
				if(ap[j].id<=i)cr--;
				if(ap[j].id==i)ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1])%mod;
				if(ap[j].id<i)
				{
					if(cl==0&&cr==0&&a[i]<=ap[j].x)ans[i]=(ans[i]+ap[j].x+i)%mod;
					else ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1]%mod*inv[cl+cr]%mod*cl)%mod;
				}
				if(ap[j].id>i)
				{
					if(cl==0&&cr==0&&a[i]>ap[j].x)ans[i]=(ans[i]+ap[j].x+i)%mod;
					else ans[i]=(ans[i]+(ap[j].x+i)*inv[cl+cr+1]%mod*inv[cl+cr]%mod*cr)%mod;
				}
				if(ap[j].id>=i)cl++;
			}
		}
		for(int x = 0;x < n;x ++)
		{
			cout<<ans[x]*tt[p]%mod<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

Thanks to EvenImage for his significant contribution to this solution.

#include<bits/stdc++.h> 
using namespace std;
const int N=81;
int a[N][N];
vector<pair<int,int>> e;
void add(int x,int y){
    e.push_back({x,y});
}
void make_matrix(int n){
    for(int i=2;i<n;++i) a[i][i]=1;
    a[n][1]=1;
    for(auto [x,y]:e) a[x][y]=-1;
}
int main(){
    int _; scanf("%d",&_); //cin>>_;
    int max_bit=15;
    while(_--){
        memset(a,0,sizeof(a)); e.clear();
        int n=1;
        for(int i=0;i<max_bit;++i){
            add(n,n+1); add(n+1,n+2); add(n+2,n+3); add(n+3,n+4);
            add(n+1,n+3); add(n+2,n+4);
            n+=4;
        }
        int x,bit_1=1,bit_2=4; scanf("%d",&x); ++n;
        for(int i=0;i<max_bit;++i){
            if (x%3==1) add(bit_1,n),add(n,n+1),++n;
            if (x%3==2) add(bit_2,n),add(n,n+1),++n;
            bit_1+=4; bit_2+=4; x/=3;
        }
        make_matrix(n);
        cout << n <<'\n';
        for (int r = 1; r <= n; r++) {
            for (int c = 1; c <= n; c++) {
                printf("%d ",a[r][c]);
            }
            cout << '\n';
        }
    }
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

In Solution 2, the first two steps remain consistent with G1, but we need a better method to find a suitable $$$A_{m−1}$$$ such that the length of the final sequence is less than or equal to $$$50$$$. Randomly searching for $$$A_{m−1}$$$ within the range $$$[1, n-1]$$$ may result in TLE.

We noticed that if $$$A_{m−1}$$$ and $$$A_m$$$ are two adjacent fibonacci numbers, the sequence will converge rapidly (with a length within $$$40$$$). Although not all $$$A_m=n$$$ are fibonacci numbers, we can still draw inspiration from this.

We attempt to decompose $$$n$$$ as $$$n=a \cdot \operatorname{fib}(i)+b \cdot \operatorname{fib}(i-1), a,b \ge 0$$$, where $$$\operatorname{fib}(i)$$$ denotes the $$$i$$$-th fibonacci number.

Then, we set $$$A_{m-1}=a \cdot \operatorname{fib}(i-1)+b \cdot \operatorname{fib}(i-2)$$$

By iterating further, we obtain $$$A_{m-2}=a \cdot \operatorname{fib}(i-2)+b \cdot \operatorname{fib}(i-3)$$$, $$$\dots$$$

The purpose of this is to make the iteration process rapidly decrease the value in the initial steps, similar to the fibonacci sequence. Intuitively, the larger the $$$i$$$ chosen, the higher the probability of finding a legal $$$A_{m-1}$$$.

The author did not provide a rigorous mathematical proof for this, but using a verification program which found a legal $$$A_{m-1}$$$ for all $$$A_m=n \in [2,10^7]$$$ within one minute. Therefore, it is feasible to prove the correctness of this approach within the data range during the contest.

#include<bits/stdc++.h>
using namespace std;
int fl[1005],inf=1e9,cnt;
int work(int x,int y){
    int ans=0,tmp;
    while(y&&ans<=50){
        ++ans; tmp=y;
        if (x>y) y=x-y; else y=y-x;
        x=tmp;
    }
    if (x>1) return inf;
    return ans;
}
void gen(int x,int y){
    //printf("%d\n",work(x,y));
    vector<int> seq; seq.clear(); seq.push_back(x); seq.push_back(y);
    int tmp;
    while(!(x==2&&y==1)){
        tmp=y;
        if (x>y) y=x-y; else y=y-x;//x=tmp;
        x=tmp; 
        seq.push_back(y);
    }
    int ans[55][55]={0};
    int pre=seq.back(),n=1; seq.pop_back(); ans[1][1]=1;
    while(!seq.empty()){
        ++n;
        if (seq.back()>pre) ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=-1;
        else ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=1;
        pre=seq.back(); seq.pop_back();
    }
    printf("%d\n",n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",ans[i][j]);
        }
        printf("\n");
    }
}
typedef long long ll;
ll fib[55]={1,1};
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1; y=0; return a;
	}
	ll d=exgcd(b,a%b,y,x);
	y-=(a/b)*x;
	return d;
}
map<int,int> mp;
int main(){
    for(int i=2;i<=50;++i) fib[i]=fib[i-1]+fib[i-2];
    int _; cin>>_;
    while(_--){
        int n; cin>>n;
        if (n==0) {printf("1\n0\n"); continue;}
        if (n==1) {printf("1\n1\n"); continue;}
        if (n<=10){
            gen(n,n-1); continue;
        }
        if (mp[n]) {gen(n,mp[n]); continue;}
        int noww=0;
        while(fib[noww]<n) ++noww;
        int now=noww;
        while(now>=3){
            ll a=fib[now-1],b=fib[now-2],x,y,c=n;
            ll d=exgcd(a,b,x,y);
            x*=c,y*=c;
            //find x,y
            x=(x%b+b)%b;  y=(c-a*x)/b; if (y<0) {--now; continue;}
            int s=inf,o;
            while(y>=0){
                o=fib[now-2]*x+fib[now-3]*y;
                s=work(n,o);
                if (s>50) {x+=b,y-=a; continue;}
                else break;
            }
            if (s>50) {--now; continue;}
            else{
                gen(n,o); mp[n]=o; break;
            }
        }
        //
    }
    return 0;
}

We note that for the fibonacci sequence, $$$\lim_{x \to \infty} \frac{\operatorname{fib}(x-1)}{\operatorname{fib}(x)} = \frac{\sqrt 5 -1}{2}$$$, which suggests that searching for $$$A_{m-1}$$$ around $$$\frac{\sqrt 5 -1}{2}n$$$ might be a promising approach.

In fact, directly enumerating $$$A_{m-1}$$$ starting from $$$\frac{\sqrt 5 -1}{2}n$$$ and trying each one is a efficient method. The author also verified through a verification program that for all $$$A_m=n \in [2,10^7]$$$, a legal $$$A_{m-1}$$$ was found within one minute. Thus, it is feasible to prove the correctness of this approach within the data range during the contest.

Considering that the time limit for this problem is relatively loose (5s), most attempts to search for $$$A_{m-1}$$$ around $$$\frac{\sqrt 5 -1}{2}n$$$ may be able to pass.

#include<bits/stdc++.h>
using namespace std;
int fl[1005],inf=1e9,cnt;
int work(int x,int y){
    int ans=0,tmp;
    while(y&&ans<=50){
        ++ans; tmp=y;
        if (x>y) y=x-y; else y=y-x;
        x=tmp;
    }
    if (x>1) return inf;
    return ans;
}
void gen(int x,int y){
    //printf("%d\n",work(x,y));
    vector<int> seq; seq.clear(); seq.push_back(x); seq.push_back(y);
    int tmp;
    while(!(x==2&&y==1)){
        tmp=y;
        if (x>y) y=x-y; else y=y-x;//x=tmp;
        x=tmp; 
        seq.push_back(y);
    }
    int ans[55][55]={0};
    int pre=seq.back(),n=1; seq.pop_back(); ans[1][1]=1;
    while(!seq.empty()){
        ++n;
        if (seq.back()>pre) ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=-1;
        else ans[n][n]=1,ans[n][n-1]=1,ans[n-1][n]=1;
        pre=seq.back(); seq.pop_back();
    }
    printf("%d\n",n);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            printf("%d ",ans[i][j]);
        }
        printf("\n");
    }
}
map<int,int> mp;
int main(){
    int _; cin>>_;
    while(_--){
        int n; cin>>n;
        if (n==0) {printf("1\n0\n"); continue;}
        if (n==1) {printf("1\n1\n"); continue;}
        if (mp[n]) {gen(n,mp[n]); continue;}
        double s=(sqrt(5)-1.0)/2.0;
        int st=s*n,l=max(1,st),r=n-1;
        //int l=1,r=n-1;
        int nowy,nows=50;
        if (n%2==0){
            if (l%2==0) ++l;
            for(int y=l;y<=r;y+=2){
                int tmp=work(n,y);
                if (tmp<=nows) {gen(n,y); mp[n]=y; break;}
            }
        }
        else{
            for(int y=l;y<=r;++y){
                int tmp=work(n,y);
                if (tmp<=nows) {gen(n,y); mp[n]=y; break;}
            }
        }
    }
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem:

For convenience, we mark the targets point and the points on the initial segment with $$$A(0,0),B(1,0),C(p,q)$$$.

The problem asks us to do at most $$$\left\lceil 2|AC|\right\rceil$$$ moves. This constraint is actually not quite usual. We can first show that the theoretical lower bound should be $$$x=\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1$$$. We can show we can't get less moves by following: If we have already constructed the final structure, then $$$AC$$$ and $$$BC$$$ should be connected with a path, and we can find a path from $$$A$$$ to $$$C$$$ and a path from $$$B$$$ to $$$C$$$ that don't intersect (except at point $$$C$$$), otherwise the structure can't be built with non-degenerate triangles.

And we have to alternate progressing through two paths every time we construct a triangle, otherwise we must draw a line longer than $$$1$$$. The last triangle will cover both paths, so the number of steps will be decreased by one. The optimal path is two straight segments (which is not always possible).

Case 1.1: We first try some simple strategies. Two triangles can form a parallelogram, so we can connect $$$AC$$$, choose a point $$$D$$$ on $$$AC$$$ which makes $$$|AD|=\frac{|AC|}{\lceil|AC|\rceil}$$$, which is always in range $$$[0.5,1]$$$ when $$$|AC|\ge 1$$$. And from $$$\triangle ADB$$$ we can construct a parallelogram. We draw a line passing $$$D$$$ that is parallel to $$$AB$$$, a line passing $$$B$$$ that is parallel to $$$AC$$$, and they intersect at $$$E$$$. Then we pile up the same parallelogram structure until we reach $$$C$$$. This always works when $$$30^\circ\le\angle CAB\le60^\circ$$$.

Proof: We first prove that all segments have length between $$$0.5$$$ and $$$1$$$. Because we stack the same parallelogram structure, all segments have length equal to $$$AB,BD$$$ or $$$AD$$$. $$$AB$$$ and $$$AD$$$ already meet the requirement. When $$$30^\circ\le\angle CAB\le60^\circ$$$, the length of $$$BD$$$ is at least $$$0.5$$$ as the distance between two parallel lines is at least $$$0.5$$$, and at most $$$1$$$ as $$$AB=1$$$ and $$$\angle CAB$$$ is never the largest angle in $$$\triangle DAB$$$. We can calculate that the number of moves we used is $$$2\left\lceil |AC|\right\rceil-1\le\left\lceil 2|AC|\right\rceil$$$ which matches the requirement (for the last parallelogram we only need one triangle).

Case 1.2: We can change the way we construct parallelograms (with sides $$$AB,BC$$$) and this method always works when $$$30^\circ\le\angle CBx\le60^\circ$$$. The number of moves is $$$\left\lceil2|BC|\right\rceil\le \left\lceil 2|AC|\right\rceil$$$. This case is actually necessary, which will be explained in the following part.

Case 2: If $$$\angle CAB \lt \angle CBx \lt 30^\circ$$$. We first build a point $$$D$$$ which makes $$$AD=1$$$ and $$$\angle DAB=30^\circ$$$ and construct $$$\triangle DAB$$$.

We can show that the constraint is actually easier to meet in this situation, because when $$$\angle CAB \lt \angle CBx \lt 30^\circ$$$, $$$|BC| \lt |AC|-0.5$$$. With this, $$$\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1=\left\lceil 2|AC|\right\rceil-1$$$ always holds, allowing us one extra move.

Then we draw a line passing $$$D$$$ parallel to $$$BC$$$. We can show that if $$$\angle DAB=30^\circ$$$ and $$$0\le \angle CAB\le 30^\circ$$$, the distance from $$$D$$$ to line $$$BC$$$ is at least $$$0.5$$$. So all segments with ends on different lines will have length $$$\ge 0.5$$$.

Then we select a point $$$E$$$ on $$$BC$$$, which makes $$$DE=1$$$. We can show that $$$\sqrt{3}-1\le |BE|\le 1$$$ based on some calculations in this case. Then we do a similar parallelogram construction process to $$$C$$$. The total number of moves is $$$2\left\lceil |CE|\right\rceil+2$$$.

There are still two cases here to analyze to prove the number of steps fulfills our requirement. We write $$$|BC|=a+b$$$ where $$$a$$$ is the integer part of $$$|BC|$$$, then we analyze cases about $$$b$$$.

• Case 2.1: When $$$b\ge\sqrt{3}-1$$$ or $$$b=0$$$, we can show that $$$2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$, and $$$\left\lceil |AC|\right\rceil=\left\lceil |BC|\right\rceil+1$$$ if $$$|AC|\ge 2$$$. The number of steps is $$$2\left\lceil |EC|\right\rceil+2\le 2\left\lceil |BC|\right\rceil+2=2\left\lceil |AC|\right\rceil$$$.

• Case 2.2: When $$$0 \lt b \lt \sqrt{3}-1$$$, we can show that $$$\left\lceil |EC|\right\rceil=\left\lceil |BC|\right\rceil-1$$$. The number of steps equals to $$$2+2\left\lceil |CE|\right\rceil=2\left\lceil |BC|\right\rceil\le \left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$.

Be careful with small cases where $$$|BC|$$$ is too short, which may make $$$|DF|=|EG| \lt 0.5$$$.

Note that there are some cases where $$$\angle CBx \gt 30^\circ$$$ and $$$\angle CAB \lt 30^\circ$$$, where Case 2 strategy doesn't work. So case 1.2 is required.

Case 3: If $$$\angle CBx \gt \angle CAB \gt 60^\circ$$$. We first build a point $$$D$$$ which makes $$$AD=1$$$ and $$$\angle DAB=60^\circ$$$ and construct $$$\triangle DAB$$$. We write $$$|AC|=a+b$$$ where $$$a$$$ is integer, then we analyze two cases about $$$b$$$.

Case 3.1: When $$$b \gt 0.5$$$ or $$$b=0$$$, $$$2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$. We begin a same parallelogram construction as Case 1 where the sides of parallelogram are $$$BC,BD$$$. We can show that $$$30^\circ\le\angle CBD\le60^\circ$$$. So it is possible to pile up to $$$C$$$ from $$$BD$$$ in $$$2\left\lceil |BC|\right\rceil-1$$$ moves. And in total we need $$$2\left\lceil |BC|\right\rceil\le2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$ moves.

Case 3.2: When $$$0 \lt b\le 0.5$$$, $$$2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil+1$$$. We instead connect $$$CD$$$ and construct parallelogram with sides $$$DC,DB$$$. We can show that $$$120^\circ\le\angle CDB\le150^\circ$$$ so we can still do the parallelogram construction. When $$$|AC|\ge \sqrt{3}$$$, $$$\left\lceil |CD|\right\rceil=\left\lceil |AC||\right\rceil-1$$$, making the number of moves $$$2\left\lceil |CD|\right\rceil+1=2\left\lceil |AC|\right\rceil-1=\left\lceil 2|AC|\right\rceil$$$.

Actually case 1.1 is not required, because it is impossible to construct a testcase where $$$\angle CAB \lt 60^\circ, \angle CBx \gt 60^\circ,0 \lt b\le 0.5$$$ and Case 3.2 fails.

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db pi = acos(-1.0);
const int N = 1000005;

inline int sgn(db x){
    if(x < 1e-13 && x > -1e-13) return 0;
    if(x > 0) return 1;
    return -1;
}

struct point{
    db x,y;
    point (db _x = 0.0,db _y = 0.0) : x(_x), y(_y) {}
};
point operator + (const point &p1,const point &p2){
	return point(p1.x + p2.x,p1.y + p2.y);
}
point operator - (const point &p1,const point &p2){
	return point(p1.x - p2.x,p1.y - p2.y);
}
point operator * (db x,const point &p){
	return point(x * p.x,x * p.y);
} 
bool operator == (point x,point y){
	return sgn(x.x - y.x) == 0 && sgn(x.y - y.y) == 0;
}

inline db dot(point p1,point p2){
    return p1.x * p2.x + p1.y * p2.y;
}

inline db det(point p1,point p2){
	return p1.x * p2.y - p2.x * p1.y;
}

inline db len(point p){
    return sqrtl(1.0 * p.x * p.x + 1.0 * p.y * p.y);
}

point project_point(point x,point ya,point yb){
	point v = yb - ya;
	return ya + (dot(v,x - ya) / dot(v,v)) * v;
}

db distp(point x,point ya,point yb){
	return fabs(det(ya - x,yb - x)) / len(yb - ya);
}

point line_circle_intersec_point(point o,point la,point lb){
	db dis = distp(o,la,lb),l;
	point pj = project_point(o,la,lb);
	l = sqrt(1.0 - dis * dis);
	point ret = pj + (l / len(lb - la)) * (lb - la);
	return ret;
}

tuple <int,int,int> ans[N];
point p[N],target;
int step;

bool check(int n){
    set <pair <int,int> > st;
    st.insert({1,2});
    if(n > step) return 0;
    db eps_len = 1e-8,eps_dis = 1e-4;
    int fl = 0;
    for(int i = 1;i <= n;i ++){
        auto [u,v,w] = ans[i];
        if(u > v) swap(u,v);
        if(st.find({u,v}) == st.end()) return 0;
        if(len(p[u] - p[w]) < 0.5 - eps_len || len(p[u] - p[w]) > 1.0 + eps_len) return 0;
        if(len(p[v] - p[w]) < 0.5 - eps_len || len(p[v] - p[w]) > 1.0 + eps_len) return 0;
        st.insert({u,w}); st.insert({v,w});
        if(len(p[w] - target) <= eps_dis) fl = 1;
    }
    return 1;
}

int solve1a(){
    point dir = target - p[1];
    int split = ceil(len(dir) - 1e-9);
    int c = 2;
    for(int i = 1;i < split;i ++){
        ++ c; p[c] = p[1] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        // construct one parallelogram
    }
    ++ c; p[c] = target;
    ans[c - 2] = {c - 2,c - 1,c};
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve1b(){
    point dir = target - p[2];
    int split = ceil(len(dir) - 1e-9);
    int c = 2;
    for(int i = 1;i <= split;i ++){
        ++ c; p[c] = p[1] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve2(){
    p[3] = point(sqrt(3.0) / 2,0.5);
    p[4] = line_circle_intersec_point(p[3],p[2],target);
    if(len(p[4] - p[2]) > 1)
        p[4] = p[2] + (1.0 / len(target - p[2])) * (target - p[2]);
    ans[1] = {1,2,3};
    ans[2] = {2,3,4};
    point dir = target - p[4];
    int split = ceil(len(dir) - 1e-9);
    int c = 4;
    for(int i = 1;i <= split;i ++){
        ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[4] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve3a(){
    p[3] = point(0.5,sqrt(3.0) / 2);
    ans[1] = {1,2,3};
    point dir = target - p[2];
    int split = ceil(len(dir) - 1e-9);
    int c = 3;
    for(int i = 1;i < split;i ++){
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    ++ c; p[c] = target;
    ans[c - 2] = {c - 2,c - 1,c};
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve3b(){
    p[3] = point(0.5,sqrt(3.0) / 2);
    ans[1] = {1,2,3};
    point dir = target - p[3];
    int split = ceil(len(dir) - 1e-9);
    int c = 3;
    for(int i = 1;i <= split;i ++){
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve(){
    if(int res = solve1a()) return res;
    if(int res = solve1b()) return res;
    if(int res = solve2()) return res;
    if(int res = solve3a()) return res;
    if(int res = solve3b()) return res;
    return 0;
}

int main(){
    int TC; scanf("%d",&TC);
    p[1] = point(0,0);
    p[2] = point(1,0);
    while(TC --){
        int tx,ty;
        scanf("%d %d %d",&tx,&ty,&step);
        step = ceil(2.0 * sqrt(1.0 * tx * tx + 1.0 * ty * ty));
        target = point(tx,ty);
        int n = solve();
        assert(n > 0);
        printf("%d\n",n);
        for(int i = 1;i <= n;i ++){
            auto [u,v,w] = ans[i];
            printf("%d %d %.12lf %.12lf\n",u,v,p[w].x,p[w].y);
        }
    }
    return 0;
}

• Amazing problem:
• Good problem:
• Average problem:
• Bad problem:
• Horrible problem: