AtCoder Regular Contest 103

It have been a long time since my last post. Lets begin.

Problem C

Solution: First, we see that for every value on an odd spot should be all equal, and the same applies for even spot. Secondly, we need fulfill the requirement that exactly two numbers need to appear. Therefore, we can conclude that we need to change every number on odd spot and even spot to the ones that appear the most frequently if they are not equal, otherwise we need to figure out the largest and second largest of each one and take maximum.

Code:

#include <bits/stdc++.h>
using namespace std;
int n;
map<int,int>mp1,mp2;
vector<int> v;


tuple<int,int,int> fd_mx(map<int,int> mp){
    vector<int> tmp;
    int val = 0;
    int mx = 0;
    for(auto it : mp){
        if(mx < it.second){
            mx = it.second;
            val = it.first;
        }
        tmp.emplace_back(it.second);
    }
    sort(tmp.begin(),tmp.end(),[=](int x,int y){return x > y;});
    int f = tmp[0];
    int s = 0;
    if(tmp.size() > 1) s = tmp[1];

    return tuple<int,int,int>(val,f,s);
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    v.resize(n + 1);
    for(int i = 1; i <= n; i++) cin>>v[i];
    for(int i = 1; i <= n; i++){
        if(i & 1) mp1[v[i]]++;
        else mp2[v[i]]++;
    }
    int ans = n;
    auto re1 = fd_mx(mp1);
    auto re2 = fd_mx(mp2);
    if(get<0>(re1) != get<0>(re2)) ans -= get<1>(re1) + get<1>(re2);
    else ans -= max(get<1>(re1),get<1>(re2)) + max(get<2>(re1), get<2>(re2));
    cout<<ans<<endl;
    return 0;
}

Problem D

Solution: To be continued…..

Problem E

Solution:  If $s_i = \mathrm{1}$, then it means that we have to be able to separate a connected component with size equals to $\mathrm{i}$. Therefore, we can create a new edge extends out. Otherwise, we can simply keep adding edges in the same spot, thus preventing any separation of a connected component with such size. We only have to do for half of the entire tree because the rest with size $\mathrm{n – i}$ can be simply procured when separating the ones with size $\mathrm{i}$. So, the rest of the nodes can be simply added to the last visited node.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
char s[N];
int main()
{
    scanf("%s",s+1);
    int n=(int)strlen(s+1);
    if(s[n]=='1'||s[1]=='0'||s[n-1]=='0'){
        printf("-1\n");
        return 0;
    }
    int now = 2;
    while(now<=n-now){
        if(s[now]!=s[n-now]) {
            printf("-1\n");
            return 0;
        }
        now++;
    }
    int root=2,num=1;
    now=2;
    printf("2 1\n");
    while(now<=n-now){
        if(s[now]=='1'){
            printf("%d %d\n",++now,root);
            root=now;
        }else{
            printf("%d %d\n",++now,root);
        }
        num++;
    }
    for(int i=num+1;i<n;i++){
        printf("%d %d\n",root,++now);
    }

}

Problem F

Solution: First, we see that all nodes have different $\mathrm{D_i}$. So, this can lead to two thoughts. First, we can think of sorting all nodes and either construct the tree from bottom to top or from top to bottom. In addition, it is easy to recognize the fact that the node with smallest $\mathrm{D}$ would be the root, while the node with the largest would be a leaf. The second thought we can think of is the relationship between two connected node. Lets assume node $\mathrm{i}$ is connected to $\mathrm{j}$, and the latter one is a son of the previous one. Then, it is not hard to conclude that $\mathrm{D_i} = \mathrm{D_j} – \mathrm{n} + \mathrm{2} \times \mathrm{size(j)}$, where the size is the number of nodes in the subtree of $\mathrm{j}$. Going back to the first thought, we can now think of a construction method from bottom to top. If we have a node, we can use the aforementioned formula to ascertain its father. If it could not find one, then we cannot construct the tree. Finally, we need to check any points. Because the formula above could have constructed a tree with $\mathrm{D’_i} = \mathrm{D_i} + \mathrm{c}$, where $\mathrm{D’}$ is the constructed solution and $\mathrm{D_i}$ is the actual solution.

Code:

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

int n;
vector<pair<ll,int>> v;
vector<int> fa,siz;
vector<vector<int>> G;
ll tot;
void dfs(int u,int par,ll d){
    tot += d;
    for(int v : G[u]){
        if(v == par) continue;
        dfs(v,u,d + 1);
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n;
    v.resize(n + 1);
    fa.resize(n + 1);
    siz.resize(n + 1);
    G.resize(n + 1);
    fill(fa.begin(),fa.end(),0);
    fill(siz.begin(),siz.end(),1);
    for(int i = 1; i <= n; i++) {
        cin>>v[i].first;
        v[i].second = i;
    }
    sort(v.begin() + 1,v.end(),[](auto x,auto y){ return x.first > y.first;});
    for(int i = 1; i < n; i++){
        ll d = v[i].first;
        int sz = siz[v[i].second];
        ll d_nxt = d - n + 2 * sz;
        int lo = i + 1, hi = n;
        int ans_pos = 0;
        while(lo <= hi){
            int mid = lo + hi >> 1;
            if(v[mid].first > d_nxt){
                lo = mid + 1;
            }
            else if(v[mid].first < d_nxt){
                hi = mid - 1;
            }
            else {
                ans_pos = mid;
                break;
            }
        }
        if(ans_pos == 0){
            cout<<-1<<endl;
            exit(0);
        }
        int u = v[i].second;
        int f = v[ans_pos].second;
        fa[u] = f;
        G[f].emplace_back(u);
        G[u].emplace_back(f);
        siz[f] += siz[u];
    }
    dfs(v[n].second,0,0);
    if(tot != v[n].first){
        cout<<-1<<endl;
        exit(0);
    }
    for(int i = 1; i < n; i++){
        cout<<v[i].second<<" "<<fa[v[i].second]<<endl;
    }

    return 0;
}