Codeforces Round 943 (Div. 3)

In this competition, I just got three Accepted.
Competition Address

A. Maximize?

The meaning of the question is to find maximum of gcd(x,y)+y when gives you x.
My solution is to have a linear search. Enough to pass this question.

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main()
{
    int T;
    cin>>T;
    while(T--){
        int x;
        cin>>x;
        int ans = 0;
        int temp = 0;
        for(int i=1;i<x;i++){
            if(gcd(i,x)+i>ans){
                temp = i;
                ans = gcd(i,x)+i;
            }
        }
        cout<<temp<<endl;
    }
    return 0;
}

But the real answer is x-1,it need some mathematical derivations。

B. Prefiquence

Give you two 01 strings named a and b, find the max length of prefix of a which is a subsequence of b.
I worte a Binary search and passed it.

#include<bits/stdc++.h>
using namespace std;
string a,b;

bool check(int len){
    if(len>b.size()) return false;
    string temp = "";
    for(int i=0;i<len;i++){
        temp+=a[i];
    }
    int k=0;
    for(int j=0;j<b.size();j++){
        if(k>=temp.size()) break;
        if(b[j]==temp[k]){
            k++;
        }
    }
    if(k==temp.size()) return true;
    return false;
}
int main()
{
    int T;
    cin>>T;
    while(T--){
        int lena,lenb;
        cin>>lena>>lenb;
        
        cin>>a>>b;
        string temp="";
        int ans=0;
        int l=0,r=lena;
        while(l<=r){
            int mid = (l+r)/2;
            if(check(mid)){
                ans = mid;
                l = mid+1;
            }
            else r = mid-1;
        }
        cout<<r<<endl;
    }

    return 0;
}

But last night I must have something wrong in my head. It obviously didn’t need a binary search. The better solution is to use two iterators and linear search.
The better code is below.

#include<bits/stdc++.h>
using namespace std;
string a,b;
int main()
{
    int T;
    cin>>T;
    while(T--){
        int lena,lenb;
        cin>>lena>>lenb;
        
        cin>>a>>b;
        int i=0,j=0;
        while(i<lena&&j<lenb){
            if(a[i]==b[j]){
                i++;
            }
            j++;
        }
        cout<<i<<endl;
    }

    return 0;
}

C. Assembly via Remainders

An array: x₁,x₂,…,x_n, find any array a₁,a₂,a₃,…,a_n, that a_i%a_i-1 = x_i, i : 2~n.

Solution: take a number that is bigger than any number in x array, the number is a₁, and next is a₁+x₂…
Notice that 1 <= x_i <= 500, you can just take 501 as the first number.

#include<bits/stdc++.h>
using namespace std;
int x[550];
int main()
{
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        int mi=0;
        for(int i=2;i<=n;i++){
            cin>>x[i];
            mi = max(x[i],mi);
        }
        x[1]=mi+1;
        for(int i=2;i<=n;i++){
            x[i]=x[i-1]+x[i];
        }
        for(int i=1;i<=n;i++){
            cout<<x[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

D. Permutation Game

A permutation of length 𝑛 is an array consisting of 𝑛 distinct integers from 1 to 𝑛 in arbitrary order.

Two people, Bodya and Sasha, play the game which has k turns. Both of them are trying to win. Each turn, they get score in their current position. They can decide to move from x to p_x or stay in current position.

Of course you will get the first position of them.

The key of the solution is that you move from x to p_x,it’s acturally a circle. What we need to do is to traverse this circle once. ans = max (ans,sum_i + (k-i)a_{pos_i}).

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll score(vector<int>&p,vector<int>&a,int pos,int k){
    ll sum = 0;
    ll ans = 0;
    vector<bool> vis(p.size());
    while(!vis[pos]&&k>0){
        vis[pos]=true;
        ans = max(ans,sum+1LL*k*a[pos]);
        sum+=a[pos];
        pos=p[pos];
        k--;
    }
    return ans;
}
int main()
{
    int T;
    cin>>T;
    while(T--){
        int n,k,pb,ps;
        cin>>n>>k>>pb>>ps;
        vector<int> p(n),a(n);
        for(auto &pi:p){
            cin>>pi;
            pi-=1;
        }
        for(auto &ai:a){
            cin>>ai;
        }
        ll Bodya=score(p,a,pb-1,k);
        ll Sasha=score(p,a,ps-1,k);
		cout<<(Bodya>Sasha?"Bodya\n":Bodya<Sasha?"Sasha\n":"Draw\n");
    }
    return 0;
}

E. Cells Arrangement

A n*n grid, find n cells that maximize Manhattan distances between any pair of the cells.
Official solutions:

Can you generalize the pattern? We put 𝑛−2 cells on the main diagonal. Then put two cells at (𝑛−1,𝑛) and (𝑛,𝑛).
But why does it work? Interesting fact, that in such way we generate all possible Manhattan distances.
Odd distances are generated between cells from the main diagonal and (𝑛−1,𝑛).
Even distances are generated between cells from the main diagonal and (𝑛,𝑛).

#include<iostream>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n-2;i++){
			cout<<i<<' '<<i<<"\n";
		}
		cout<<n-1<<' '<<n<<"\n"<<n<<' '<<n<<"\n";
	}
}