[PYTHON] Codeforces Round # 600 (Div. 2) Bacha Review (10/21)

This time's results

Impressions of this time

Bacha's review has not caught up because I prepared for today's graduation announcement just before. I want to be a person who can balance graduation research and competition professionals.

Also, I will not upsolve because the review is not catching up. I will do my best from tomorrow.

Problem A

I won't go into the details of the problem, but consider equalizing $ a $ and $ b $ in a single operation.

Here, with ** paraphrasing the problem ** and taking the unequal continuous parts of $ a $ and $ b $, ① when the number of parts is two or more ② the number of parts is one NO should be output when the difference in the part is not equal or the difference in the part is $ b \ _i-a \ _i \ <0 $), and YES should be output in other cases.

The unequal contiguous part of $ a $ and $ b $ can be easily extracted by using the ** groupby function to determine if $ b \ _i-a \ _i = 0 $ **. Also, it is not difficult to judge ① and ② as long as this continuous part can be extracted.

A.py

from itertools import groupby
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    c=[a[i]-b[i] for i in range(n)]
    d=[[i,list(j)] for i,j in groupby(c,key=lambda x:x==0) if i==False]
    if len(d)>=2:
        print("NO")
    elif len(d)==0:
        print("YES")
    else:
        l=len(d[0][1])
        for i in range(l):
            if d[0][1][i]!=d[0][1][0]:
                print("NO")
                break
        else:
            if d[0][1][i]>0:
                print("NO")
            else:
                print("YES")

Problem B

If you do not sort out the problem, it will be almost $ O (n ^ 2) $, so implement it carefully. Also, this time we don't have to think about the maximum or minimum days, so we just do a ** honest simulation **.

Also, there are some conditions, so make sure to ** write them out **. Please forgive me though the expression is slightly different from the question sentence. If the following does not hold for each input / output information, it holds as a day.

① When only one of + and-(+) appears ② When +,-(+) appears more than once ③ When-appears before +

At this time, in order to avoid the case where the condition (2) appears more than once, if it holds as a ** day, it is immediately decided that the day holds. This explanation is not easy to understand, so the implementation is explained below.

$ s: $ A set of people who have already come $ b: $ A set of people who haven't returned yet $ now: $ Index of the given I / O information you are looking at (less than $ n $) $ ans: $ Last index of input / output information given for a day

If you prepare the above four, you can just make the following ** cases **.

(1) When $ a [now] > 0 $ [1] When $ a [now] $ is included in $ s $ Since + appears twice, ② is not satisfied. Outputs -1. [2] When not included Add $ a [now] $ to both $ s $ and $ b $.

(2) When $ a [now] \ <0 $ [1] When $ -a [now] $ is not included in $ b $ Since-is appearing first or +,-is already appearing, neither ② nor ③ is satisfied. Outputs -1. [2] When included Exclude $ -a [now] $ from $ b $.

Also, if ** $ b $ is empty, it holds as a day **, so clear all the contents of $ s $ and add $ now $ to $ ans $.

If $ b $ is not empty after performing the above case classification in order with arbitrary input / output information, ① is not satisfied. In this case, -1 is output.

Also, since the output is ** the length when the input / output information is divided **, $ ans [i] -ans [i-1] $ should be output in ascending order of $ i $.

(It's a long explanation, but I only think about the conditions ** ① to ③ and what is necessary as a variable **.)

B.py

n=int(input())
a=list(map(int,input().split()))
#People who have already come
s=set()
#Those who have to get rid of now
b=set()
#Until what day
now=0
#Array of answers
ans=[]
while now<n:
    if a[now]>0:
        if a[now] in s:
            print(-1)
            exit()
        else:
            s.add(a[now])
            b.add(a[now])
    else:
        if -a[now] not in b:
            print(-1)
            exit()
        else:
            b.remove(-a[now])
    if len(b)==0:
        ans.append(now+1)
        s=set()
    now+=1
if len(b)!=0:
    print(-1)
    exit()
for i in range(len(ans)-1,0,-1):
    ans[i]-=ans[i-1]
print(len(ans))
print(" ".join(map(str,ans)))

C problem

** I was confused by the problem setting **, but if you think calmly, it is a problem with many obvious parts.

Consider choosing a $ k $ piece. At this time, it is best to select ** $ k $ pieces ** from the smallest. Furthermore, when selecting $ k $ pieces, it is best to ** select $ m $ pieces in descending order of sweetness ** on each day. Therefore, if you think about $ m = 2 $, it will be as shown in the figure below. (The double-headed arrow represents $ m $, the circled part is the day when each confectionery is selected, and the part displayed in red is the change.)

Considering the movement of the interval of the length of ** $ m $ ** in the above figure, by increasing $ k $, the increment of the total sweetness becomes the index ** with the remainder of ** $ m $. (** Paraphrase with a high degree of abstraction! **). In other words, the remainder of dividing the index (0-indexed) by $ m $ is included in $ k $ of the indexes that are $ (k-1) \% \ m $. Also, this can be easily calculated by taking the cumulative sum of the remainders for each index. Furthermore, since the cumulative sum is the increment, you can find the answer for any $ k $ by taking the cumulative sum at the end.

(✳︎)… Incremental is the cumulative sum of each remainder during the virtual console, so I thought that I would be able to get the subscripts here.

C.py

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
tod=[[] for i in range(k)]
for i in range(n):
    tod[i%k].append(a[i])
from itertools import accumulate
for i in range(k):
    tod[i]=list(accumulate(tod[i]))
ans=[]
now=0
for i in range(n):
    now+=tod[i%k][i//k]
    ans.append(now)
print(" ".join(map(str,ans)))

D problem

It may be my favorite problem with UnionFind.

It's easy to see what to do, so I'll do my best to implement it well.

When $ (l, r) $ is connected, $ (l, l + 1) $, $ (l, l + 2) $… $ (l, r-1) $ are also connected, that is, * * All nodes with numbers in $ [l, r] $ must be in the same connected component **. Since sample 1 is easy to understand, considering this case, it will be as follows.

1-2-5-7
3-4-6-8
9
10
11-12

At this time, $ (1,7) $ is connected, so the nodes with the numbers included in $ [1,7] $ must be the same connected component. That is, the first and second connected components must be the same connected component, and the answer is 1.

1-2-3-4-5-6-7-8
9
10
11-12

Therefore, first perform Union Find to divide into connected components. Also, after performing Union Find, you need to stick the connected components together a minimum number of times to satisfy the subject. Here, if $ l $ and $ r $ are connected, all the nodes included in $ [l, r] $ are connected, so only the node with the smallest and largest ** number of the connected component is saved. You can do it **.

Therefore, according to UnionFind, if $ l \ _i $ is the minimum value and $ r \ _i $ is the maximum value for the $ i $ th connected component, then $ [l \ _1, r \ _1], [l \ _2, You can get the interval r \ _2],…. [L \ _ k, r_k] $.

If you arrange these sections in ascending order of ** $ l $ ** (✳︎), when ** $ hashi > l \ _i $ holds by setting the right end of the section that should have the same connected component as $ hashi $. $ [l \ _i, r \ _i] $ must be the same connected component **, and at this time, it is updated as $ hash = max (hashi, r \ _i) $.

On the contrary, in the case of $ hashi \ <l \ _i $, ** there is no need to update and the subject is satisfied **, so if you save the number of original connected components contained in that connected component in $ now $ , $ Now-1 $ is the minimum number of edges needed to create that connected component. (At the same time, we also update the values of $ hashi $ and $ now $ for the next connected component we want to examine.)

Therefore, if the minimum number of edges to be added is $ ans $, the answer can be obtained by checking in any interval and adding $ now-1 $ to $ ans $. You just have to output it.

(✳︎)… When considering merging sections, it is common to sort by the left or right edge **

D.cc

//Debugging options:-fsanitize=undefined,address

//Compiler optimization
#pragma GCC optimize("Ofast")

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

//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of endings)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair

//Below, the disjoint sets and the tree represent the same thing.
class UnionFind{
public:
    vector<ll> parent; //parent[i]Is the parent of i
    vector<ll> siz; //An array representing the size of the disjoint sets(Initialize with 1)
    map<ll,set<ll>> group; //Manage by set(key:Set representative element, value:Array of elements of the set)
    ll n; //Element count

    //constructor
    UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){ 
        //Initialize as the root of all elements is itself
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //Get the root of the tree to which the data x belongs(Also performs path compression)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//Since the value of the assignment expression is the value of the assigned variable, the route can be compressed.
    }

    //Merge x and y trees
    void unite(ll x,ll y){
        ll rx=root(x);//root of x
        ll ry=root(y);//root of y
        if(rx==ry) return;//When in the same tree
        //Merge small set into large set(Merged from ry to rx)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;//When x and y are not in the same tree, attach y root ry to x root rx
    }

    //Determine if the tree to which x and y belong is the same
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    //Get the size of the disjoint sets of x
    ll size(ll x){
        return siz[root(x)];
    }

    //Group each disjoint set
    void grouping(){
        //Perform path compression first
        REP(i,n)root(i);
        //Manage with map(Use default build)
        REP(i,n)group[parent[i]].insert(i);
    }

    //Delete the disjoint sets and initialize
    void clear(){
        REP(i,n){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};

signed main(){
    //Output specification of decimal digits
    //cout<<fixed<<setprecision(10);
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    UnionFind uf(n);
    REP(i,m){
        ll u,v;cin>>u>>v;
        uf.unite(u-1,v-1);
    }
    uf.grouping();
    vector<pair<ll,ll>> segments;
    FORA(i,uf.group){
        segments.PB(MP(*i.S.begin(),*--i.S.end()));
    }
    sort(ALL(segments));
    ll hashi=segments[0].S;
    ll now=1;
    ll ans=0;
    FOR(i,1,SIZE(segments)-1){
        if(hashi<segments[i].F){
            ans+=(now-1);
            now=1;
            hashi=segments[i].S;
        }else{
            hashi=max(hashi,segments[i].S);
            now++;
        }
    }
    ans+=(now-1);
    cout<<ans<<endl;
}

After the E problem

I will skip this time.