[PYTHON] Codeforces Round # 479 (Div. 3) Bacha Review (9/25)

This time's results

Impressions of this time

The E problem was an implementation game, but I regret it because I continued to bug it ** by forcibly implementing it without imagining the final form of implementation. It was good to switch to the F problem on the way, but it is not a good idea to drop the implementation even though the policy is completely correct, so I will repeatedly train with Kodofo's bacha.

Problem A

It's just a matter of thinking of a number as a string and ** simulating it honestly **. I was a little lost because there aren't many problems like this.

A.py

n,k=input().split()
n=[int(i) for i in n]
k=int(k)
for i in range(k):
    if n[-1]==0:
        n=n[:-1]
    else:
        n[-1]-=1
print("".join(map(str,n)))

Problem B

I had a little trouble understanding the meaning of the problem statement, but I just need to count how many of each of the two consecutive characters (hereinafter simply referred to as a character string) are. In other words, if the dictionary $ check [i]: = $ (there are several combinations of indexes whose character strings are $ i $), there are $ n-1 $ combinations of indexes, so all of them should be $ check $. You can record it. After saving in the dictionary, the one with the largest combination of indexes should be output, and the elements in the dictionary are sorted in reverse order and the first one is the solution.

B.py

n=int(input())
s=input()
check=dict()
for i in range(n-1):
    t=s[i:i+2]
    if t in check:
        check[t]+=1
    else:
        check[t]=1
c=list(check.items())
c.sort(key=lambda x:x[1],reverse=True)
print(c[0][0])

C problem

It's $ x \ in [1,10 ^ 9] $, so you should ** pay attention to the corner case ** (I noticed that I issued 1WA, attention ...).

If $ x $ can take any integer, then when the sequence $ a $ is sorted in ascending order, $ a \ _0, a \ _1, a \ _2,…, a \ _ {k-1} \ leqq x Just take $ x $, which is $ and $ x <a \ _k $. Also, since they are arranged in ascending order, you can take $ x $, which is $ a \ _ {k-1} \ leqq x <a \ k $. Also, ** $ x = a \ _ {k-1} $ should be set **, but if $ a {k-1} = a \ _k $, the condition is not satisfied, so -1 is output. I will.

Also, when $ k = 0, n $, one of ** $ a \ _ {k-1} $ and $ a \ _k $ does not exist **, so it is necessary to separate the cases. When $ k = n $, $ a \ _ {max} $ is at most $ 10 ^ 9 $, so $ x = 10 ^ 9 $. On the other hand, when $ k = 0 $, it is $ x \ geqq 1 $ when $ a \ _0 = 1 $, so the condition is not satisfied. In other cases, $ a \ _0-1 $ will satisfy the condition. (1WA made a mistake when $ k = n $ ...)

C.py

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
if k==0:
    if a[0]==1:
        print(-1)
    else:
        print(a[0]-1)
elif k==n:
    print(a[-1])
else:
    if a[k-1]==a[k]:
        print(-1)
    else:
        print(a[k-1])

D problem

I thought it was unexpectedly difficult, but it was a D problem level problem.

(In the following policy, I thought that -1 would be output if it does not exist halfway, so I proceeded with the consideration, so there are some redundant points, but please do not worry.) (I misread it, but the problem of the person who misread it If you make ** It seems that you can make a problem at the level of the first half of green **.)

$ x $ can only be divided by 3 or multiplied by 2. Also, for example, in the case of $ 4,6 $, it cannot be created by operation, but ** input is always satisfied ** (even if you think that it may not exist and solve the problem, you can solve it after all. However, the implementation will be slightly reduced).

First of all, paying attention to the operation of "divide by 3" among the operations, if the multiple of 3 still remains when dividing by 3 and it is no longer a multiple of 3, the subject is not satisfied. In other words, from the operation of dividing by 3, we can see that if each is a multiple of $ 3 ^ i $, we should operate from the one with the largest ** $ 3 ^ i $ **. Also, from the operation of multiplying by 2, you can also see that you should operate from the smallest ** $ 2 ^ i $ **.

Therefore, find out how many times $ a \ _i $ can be divided by $ 2,3 $ as $ x \ _i, y \ _i $, starting with ** $ x \ _i $ being smaller and $ y \ _i $ being larger. Process ** in order (✳︎). If you process in this order, you can always sort in the order that satisfies the subject under the conditions of this problem, and output in that order.

(✳︎)… If it doesn't exist, consider GCD here, but it's not necessary here.

D.py

from math import gcd
def gce(x):
    ret=x[0]
    for i in x:
        ret=gcd(ret,i)
    return ret
n=int(input())
a=list(map(int,input().split()))
g=gce(a)
a=[i//g for i in a]
b=[]
for i in range(n):
    d=[0,0]
    c=a[i]
    while c%2==0:
        c//=2
        d[0]+=1
    while c%3==0:
        c//=3
        d[1]+=1
    b.append(d)
b.sort(key=lambda x:x[0])
b.sort(reverse=True,key=lambda x:x[1])
ans=[]
for i in range(n):
    ans.append(str((2**b[i][0])*(3**b[i][1])*g))
print(" ".join(ans))

E problem

I wrote it in C ++ because I thought DFS (recursive) was necessary, but I ended up implementing it in BFS. I made a lot of silly mistakes, but as I said, I think it was because I couldn't get an image of the final form of the implementation **.

If you read the problem statement, you will have a policy. It's a bit long, but it just explains that it's a common type of graph with no loops (edges connecting itself) and no multiple edges. What we should ask for in this question is ** how many connected components are made in only one cycle **. Here, we need to capture the characteristics of the cycle before implementing it. The figure is as follows.

Also, I always use UnionFind when finding connected components, but here I decided to use ** BFS to think of connected components that satisfy the subject **. In the above figure, if one point at the time of BFS is decided as the starting point, when tracing from that starting point **, if the degree of each vertex is 2 and finally returns to the starting point, <font color = "red" "> (✳︎) </ font> ** It can be said that the connected components form only one cycle. However, I made a bug even though I only had to implement this, so I thought of an easier implementation method **.

Then I came up with the following implementation. I think it's an implementation that comes to mind when you consider the conditions that are met when the cycle is set.

First, ** select the starting point **. The starting point can be any vertex that has not been searched. Also, in BFS, the starting point is put in a deque, the vertices that are connected to the vertices in the deque and have not been searched are made searched, and then put in the deque and repeated until there are no elements in the deque. .. However, this time ** I want to search in the following order **, so this implementation does not work ($ \ because $ it will proceed in two directions from the start point as it is).

Therefore, after deciding the start point and making it searched, ** the one point (only) connected to the start point is considered to have been searched, and the search is performed in order from that point **. Here, in addition to the deque (d) used in the BFS search, prepare a deque (ʻe) that is stored in the search order. After performing this BFS search, the above cycle is judged. At this time, since the vertex information is held in ʻe in the search order **, "Is the degree of any vertex included in ʻe 2?" And "Arbitrary of ʻe" If you check both ** continuous vertices and whether the start point and end point are connected ** ”, the cycle will be judged.

Also, in the previous BFS, only two of the vertices connected from the start point are searched (at the maximum), and if the order is 2 or more, there may be vertices that have not been searched, so the start point is searched again. Insert it into d and do a BFS to find out the ** remaining vertices contained in this concatenated component **.

From the above, it is possible to judge whether each connected component is a cycle, so the total number is the answer.

(I'm always working hard on the first implementation I came up with, but sometimes I thought it was important to change some of the policies to make the implementation easier **. Not only the power to implement it, but also ** clearer and buggy. I think that it is also the mounting power to think about easy implementation without letting it **, so I will try to acquire both mounting power.)

Postscript (2020/09/25)

The condition for the connected component to be a cycle is written as (✳︎) </ font>, but since this condition is ** equivalent to the degree of any vertex being 2, ** After finding the connected component using UnionFind, all you have to do is make sure that the degree of any vertex in the connected component is 2, which is considerably easier to implement. I didn't have enough thinking power ...

//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 ends)、のどちら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

vector<bool> check;
vector<vector<ll>> tree;


//Organize the implementation and imagine it ...
ll bfs(ll i){
    ll ret=1;
    deque<ll> d;
    deque<ll> e;
    check[i]=true;
    if(SIZE(tree[i])==0)return 0;
    e.PB(i);
    d.PB(tree[i][0]);
    e.PB(tree[i][0]);
    check[tree[i][0]]=true;
    //Suppose it holds
    while(SIZE(d)){
        ll l=SIZE(d);
        REP(_,l){
            ll p=d.front();
            d.pop_front();
            FORA(j,tree[p]){
                if(check[j]==false){
                    check[j]=true;
                    d.PB(j);
                    e.PB(j);
                }
            }
        }
    }
    //FORA(i,e)cout<<i<<" ";
    //cout<<endl;
    for(auto j=e.begin();j!=e.end();j++){
        ll x,y;x=*j;
        if(j==--e.end()){
            y=*e.begin();
        }else{
            //y=*I made it j
            auto k=j;k++;y=*k;
        }
        if(SIZE(tree[x])!=2){
            ret=0;
            break;
        }else{
            if(tree[x][0]==y or tree[x][1]==y){
                continue;
            }else{
                ret=0;
                break;
            }
        }
    }
    d.PB(i);
    while(SIZE(d)){
        ll l=SIZE(d);
        REP(_,l){
            ll p=d.front();
            d.pop_front();
            FORA(j,tree[p]){
                if(check[j]==false){
                    check[j]=true;
                    d.PB(j);
                    e.PB(j);
                }
            }
        }
    }
    return ret;
}

signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    tree=vector<vector<ll>>(n);
    check=vector<bool>(n,false);
    REP(i,m){
        ll u,v;cin>>u>>v;
        tree[u-1].PB(v-1);
        tree[v-1].PB(u-1);
    }
    ll ans=0;
    REP(i,n){
        if(check[i]==false){
            ans+=bfs(i);
        }
    }
    cout<<ans<<endl;
}

//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 ends)、のどちら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,vector<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;//If x and y are not in the same tree, add 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 route compression first
        REP(i,n)root(i);
        //Manage with map(Use default build)
        REP(i,n)group[parent[i]].PB(i);
    }

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


signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    vector<vector<ll>> tree(n);
    UnionFind uf(n);
    REP(i,m){
        ll u,v;cin>>u>>v;
        tree[u-1].PB(v-1);
        tree[v-1].PB(u-1);
        uf.unite(u-1,v-1);
    }
    uf.grouping();
    ll ans=0;
    FORA(i,uf.group){
        ll check=1;
        FORA(j,i.S){
            if(SIZE(tree[j])!=2){
                check=0;
                break;
            }
        }
        ans+=check;
    }
    cout<<ans<<endl;
}

n=int(input())
a=list(map(int,input().split()))
s=dict()
for i in range(n):
    if a[i]-1 in s:
        s[a[i]]=s[a[i]-1]+1
    else:
        s[a[i]]=1
ans=[-1,-1]
for i in s:
    if ans[1]<s[i]:
        ans=[i,s[i]]
ans_=[]
for i in range(n-1,-1,-1):
    if ans[0]==a[i]:
        ans[0]-=1
        ans[1]-=1
        ans_.append(i+1)
        if ans[1]==0:
            break
print(len(ans_))
print(" ".join(map(str,ans_[::-1])))