[PYTHON] Codeforces Round # 660 (Div. 2) Bacha Review (8/4)

This time's results

Impressions of this time

I solved three questions this time. The implementation of the C problem was heavy, but I was able to answer it correctly by organizing the policy.

I had already solved the D problem by organizing the implementation, so I would like to continue to be aware of it.

Problem A

$ X $ is represented by the sum of four different positive integers (at least three of which are $ near \ primer $), but ** the minimum $ nearly \ primer $ to represent as much $ x $ as possible. I decided to look for **. $ nearly \ primer $ is a number that can be expressed by multiplying two prime numbers, and $ 6,10,14 $ is the smallest three $ nearly \ primer $. Therefore, if $ x $ is less than $ 30 (= 6 + 10 + 14) $, you cannot construct the four integers in question.

Also, if you select $ 6,10,14 $ when $ x> 30 $, you cannot select $ 6,10,14 $ as another number to select, but this method when $ x = 36,40,44 $ In the case of, you cannot construct the four integers of the subject, but you can also construct the four integers of the subject in the case of $ x = 36,40,44 $ by choosing $ 15 $ instead of $ 14 $.

A.py

for i in range(int(input())):
    n=int(input())
    if n<=30:
        print("NO")
    elif n==36:
        print("YES")
        print("6 10 15 5")
    elif n==40:
        print("YES")
        print("6 10 15 9")
    elif n==44:
        print("YES")
        print("6 10 15 13")
    else:
        print("YES")
        print("6 10 14"+f" {n-30}")

Problem B

To summarize the problem, given $ n $, consider a binary number $ k $, which is a concatenation of each digit of the $ n $ digit decimal number $ x $ in decimal notation, and is of $ k $. It constitutes the smallest $ x $ in maximizing the number $ r $, ignoring the lower $ n $ digits. Also, when converting to binary notation, it is not padded with zeros.

First of all, it is self-evident that $ x $ should be $ 99… 99 $ ** to maximize ** $ r $. However, at this time, $ x $ becomes the maximum. Therefore, you should ** make the lower $ n $ digits of $ k $ to ignore ** as small as possible. Also, since $ 9 $ is in the $ 4 $ digit when expressed in binary, the only way to reduce $ x $ while keeping $ r $ at maximum is to replace $ 9 $ with $ 8 $. Therefore, the digit of $ x $ corresponding to the lower $ n $ digit of the ignored $ k $ should be changed to $ 8 $, and the value of $ n % 4 $ indicates how many digits can be replaced with $ 8 $. I will consider it separately.

From the above, when $ n % 4 = 0 $, the lower $ [\ frac {n} {4}] $ digit of $ x $ is changed to $ 8 $, and when $ n % 4 \ neq 0 $, $ The lower $ [\ frac {n} {4}] + 1 $ digit of x $ can be $ 8 $, and the code looks like this:

B.py

for _ in range(int(input())):
    n=int(input())
    l=n//4 if n%4==0 else n//4+1
    ans="9"*(n-l)+"8"*(l)
    print(ans)

C problem

First, consider ** a rooted tree with roots in the capital (vertex 1) **. Based on this, the number of people who feel good and those who feel bad is decided so that $ h_i, p_i $ holds at any vertex, but it turns out that it is difficult to decide ** in the dark clouds **. It's also difficult to deal with ** changing moods in the middle of the edge ** (contribution to $ h_i $ goes from +1 to -1). Therefore, in such a case, ** follow the tree from the direction of the roots or the direction of the leaves **. ** BFS is often used in the former case, and DFS ** is often used in the latter case. Also, in this issue, it seemed that ** the number of people who feel good and the number of people who feel bad in the leaves can be uniquely determined **, so I decided to do DFS.

Here, assuming that the ** $ i $ th vertex is a leaf **, and letting the number of people who feel good and bad passing through that vertex be $ c and d $, respectively, the people who pass through that vertex will pass through that vertex. Since only people who live in that city, $ cd = h \ _i, c + d = p \ _i $ holds. When this is transformed into an expression, $ c = \ frac {p_i + h_i} {2}, d = \ frac {p_i-h_i} {2} $, and if both $ c and d $ are 0 and integers, the subject is Meet.

Next, assuming that the ** $ i $ th vertex is not a leaf **, ** DFS searches in order from the vertex closest to the leaf **, so each vertex included in the subtree rooted at that vertex We already know how many people feel good and bad at passing through. Here, ** If you return a pair of good and bad people who pass through each vertex with the DFS recursive function **, it will pass through the $ i $ th vertex, but at the $ i $ th vertex You can find the number of good and bad people who do not live first, and set them as $ x and y $, respectively.

At this time, if the number of good and bad people passing through the $ i $ th apex is $ c and d $, respectively, then $ cd = h \ _i, c + d = p \ _i + x + y $ Holds. When this is transformed into an expression, it becomes $ c = \ frac {p_i + x + y + h_i} {2}, d = \ frac {p_i + x + y-h_i} {2} $. Also, in addition to $ c and d $ being both 0 and an integer, ** a person who feels sick once does not feel better **, so $ c <x $ may be satisfied. No way.

You can find a lever answer that checks all vertices by performing DFS, paying attention to the leaf and non-leaf cases. Also, if there are vertices that do not hold, the recursive function returns a pair of (-1, -1).

Important matters this time

C.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 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
#define CANT MP(ll(-1),ll(-1))

pair<ll,ll> dfs(vector<ll> &p,vector<ll> &h,vector<bool> &seen,vector<vector<ll>> &graph,ll v) {
    seen[v] = true;
    bool f=false;
    //Good bad pair
    pair<ll,ll> x(0,0);
    for (auto ne:graph[v]) { 
        if(seen[ne])continue;
        f=true;
        pair<ll,ll> y=dfs(p,h,seen,graph,ne);
        if(y==CANT)return CANT;
        x.F+=y.F;x.S+=y.S;
    }
    //cout<< x.F << " " << x.S << " " << v << endl;
    if(f){
        if(abs(p[v]+x.F+x.S)%2!=abs(h[v])%2){
            //cout<<-1<<endl;
            return CANT;
        }else{
            ll c=(p[v]+x.F+x.S+h[v])/2;ll d=(p[v]+x.F+x.S-h[v])/2;
            if(c<0 or d<0 or c<x.F){
                //cout<<-2<<endl;
                return CANT;
            }else{
                return MP(c,d);
            }
        }
    }else{
        if(abs(p[v]%2)!=abs(h[v]%2)){
            //cout<<-3<<endl;
            return CANT;
        }else{
            ll c=(p[v]+h[v])/2;ll d=(p[v]-h[v])/2;
            if(c<0 or d<0){
                //cout<<-4<<endl;
                return CANT;
            }else{
                return MP(c,d);
            }
        }
    }
}

signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    REP(_,t){
        ll n,m;cin>>n>>m;
        vector<bool> seen(n,false);
        vector<vector<ll>> graph(n);
        vector<ll> p(n);REP(i,n)cin>>p[i];
        vector<ll> h(n);REP(i,n)cin>>h[i];
        REP(i,n-1){
            ll x,y;cin>>x>>y;
            graph[x-1].PB(y-1);
            graph[y-1].PB(x-1);
        }
        pair<ll,ll> z=dfs(p,h,seen,graph,0);
        if(z==CANT){
            cout<<"NO"<<endl;
        }else{
            cout<<"YES"<<endl;
        }
    }
}

D problem

Because I had little time left, I was impatient and had a rough policy. I don't want to worry too much about the remaining time.

During the contest, I thought I would greedily choose a large number, but ** if the order is relevant, consider a directed graph ** to improve the outlook.

In this problem, when selecting $ i $ and performing an operation, $ a [i] $ is added to $ a [b [i]] $ as well as $ ans $, but $ a [i] $ is If it is negative, you can operate in the order of $ b [i] \ rightarrow i $ rather than $ i \ rightarrow b [i] $. On the contrary, if $ a [i] $ is positive, you can operate with $ i \ rightarrow b [i] $.

I thought about it and greedily tried to choose from a large number of positive numbers, but ** each $ a [i] $ is not optimal as the value can change **. However, conversely, you can choose $ a [i] $ whose value does not change **. Therefore, if we consider a directed graph with each number as a weighted vertex, the value does not change for ** vertices with 0 edges coming from other vertices ** (vertices with 0 degree, source point). Hmm.

Therefore, consider a directed graph assuming that $ b [i] $ received by input indicates the tip of an edge, and make the following judgment from the source point ($ \ because $ ** Because it is a directed non-cycle graph, the source point is always Exists **). When $ a [i] \ geqq 0 $, ** the weights of other vertices can be increased **, so insert a [i] into f and connect to the $ i $ th vertex. Add $ a [i] $ to the weights. When $ a [i] <0 $, ** the weights of other vertices cannot be increased **, so just insert a [i] into s. In addition, ** the degree of the vertex that has been judged is reduced by one **, and the one whose degree is 0 is used as a candidate for a new vertex to be considered. Since it is a directed cycle graph, you can check any vertex with the above. Also, the sum of the updated values of a [i] is the maximum value of $ ans $, and the order of operations is ascending order before s because the vertices inserted in f increase the weight. The vertices inserted in s` reduce the weight, so you can do it in reverse order.

D.py

from collections import deque
ans=0
n=int(input())
a=list(map(int,input().split()))
b=[i-1 if i!=-1 else -1 for i in list(map(int,input().split()))]
flow=[0]*n
graph=[[] for i in range(n)]
for i in range(n):
    if b[i]!=-1:
        flow[b[i]]+=1
        graph[i].append(b[i])
check=[a[i] for i in range(n)]
ver=deque()
lv=0
for i in range(n):
    if flow[i]==0:
        ver.append(i)
        lv+=1
f,s=[],[]
while lv:
    #print(ver)
    for i in range(lv):
        x=ver.popleft()
        lv-=1
        if check[x]>=0:
            f.append(x)
            for j in graph[x]:
                flow[j]-=1
                check[j]+=check[x]
                if flow[j]==0:
                    ver.append(j)
                    lv+=1
        else:
            s.append(x)
            for j in graph[x]:
                flow[j]-=1
                if flow[j]==0:
                    ver.append(j)
                    lv+=1
#print(check)
print(sum(check))
print(" ".join(map(lambda x:str(x+1),f+s[::-1])))

After the E problem

I will skip this time