Educational Codeforces Round 94 Bacha Review (9/3)

This time's results

スクリーンショット 2020-09-04 9.30.57.png

Impressions of this time

The time has melted infinitely because I spent a lot of time on the B problem. As a reflection of problem B, I have just tried to solve it analytically. ** I think that I could solve it if I intuitively performed the greedy method **, so I regret it.

Problem A

Do you alternate 01 when you first see it? I thought that, but I felt it was troublesome because the position would shift. Therefore, I thought that it would be good if all the characters were the same so as not to depend on the position **. At this time, the condition in question shows that ** every string contains $ s [n] $ **. Therefore, if you create a string by connecting $ n $ of this character, the character corresponding to $ s [n] $ will be equal to any string. So this is the answer.

A.py


for _ in range(int(input())):
    n=int(input())
    s=input()
    print(n*s[n-1])

Problem B

As you can see in the impression, it can be solved by ** normal greedy algorithm **.

Keep in mind that it is best to choose from the lightest ones to choose as many as possible. Also, $ s \ leqq w $ (otherwise swap the value). First, select ** what you take away **, but depending on the combination, it may be better to save heavy ones, so I am only $ i (0 \ leqq i \ leqq cnts) $ lighter ones. Suppose you choose. Also, at this time, it is necessary to satisfy $ i \ times s \ leqq p $. Below this, the number of heavier ones you can choose is $ min (\ frac {p-i \ times s} {w}, cntw) $. Also, since it is easy to find out how many of each thing is left, ** your followers should be greedily selected in order from the lightest one **. Therefore, the number of things that can be stolen when $ i $ is set is calculated by $ O (1) $, and it is possible to write a sufficiently fast program.

B.py


for _ in range(int(input())):
    p,f=map(int,input().split())
    cnts,cntw=map(int,input().split())
    s,w=map(int,input().split())
    if s>w:
        s,w=w,s
        cnts,cntw=cntw,cnts
    ans=0
    for i in range(cnts+1):
        if i*s>p:break
        ans_sub=0
        nows=cnts-i
        ans_sub+=i
        #s is selected
        rest1=p-i*s
        #w
        noww=cntw-min(rest1//w,cntw)
        ans_sub+=min(rest1//w,cntw)
        #Next person
        #s
        ans_sub+=min(f//s,nows)
        rest2=f-min(f//s,nows)*s
        #w
        ans_sub+=min(noww,rest2//w)
        ans=max(ans,ans_sub)
    print(ans)

C problem

Since $ s $ is given, ** $ w $ will be restored **. Here, when $ s \ _i = 1 $, $ w $ is restored on the condition that either $ w \ _ {ix} = 1 $ or $ w \ _ {i + x} = 1 $ holds. Since it is difficult, $ w $ from the condition that both $ w \ _ {ix} = 1 $ and $ w \ _ {i + x} = 1 $ hold when ** $ s \ _ i = 0 $ ** I decided to restore.

Also, although part of $ w $ is not restored by this method, all the part that has not been restored so as to satisfy the condition ** $ s \ _i = 1 $ is set to 1 **. From the above, we were able to restore $ w $, but we do not know if it can actually be transformed from $ w $ to $ s $, so we need to confirm whether it can be transformed at the end.

C.py


for _ in range(int(input())):
    s=list(map(int,input()))
    x=int(input())
    n=len(s)
    w=[1]*n
    for i in range(n):
        if s[i]==0:
            if i-x>=0:
                w[i-x]=0
            if i+x<n:
                w[i+x]=0
    t=[1]*n
    for i in range(n):
        g=0
        if i-x>=0:
            if w[i-x]==1:
                g+=1
        if i+x<n:
            if w[i+x]==1:
                g+=1
        if g>0:
            t[i]=1
        else:
            t[i]=0
    if s==t:
        print("".join(map(str,w)))
    else:
        print(-1)

D problem

I became impatient with MLE, but I was relieved to finish solving it in time. ** I have devised such things as converting pair <ll, ll> to ll and changing ll to ʻint` **.

I felt that this problem was not so difficult to consider and was a little troublesome to implement.

Look for $ i, j, k, l $ such that $ a \ _i = a \ _k $ and $ a \ _j = a \ _l $ hold under $ i <j <k <l $. At this time, I noticed that ** $ (a \ _ i, a \ _ j) = (a \ _ k, a \ _l) $ holds **. Also, since $ n $ has at most 3000 ways, all pairs of $ _ {3000} C_2 $ can be generated. Also, the same set is put together by map. In other words, let's assume that $ m $ is a map object, key is a pair of two elements, and value is a vector, and the pair of indexes that are the two elements is included.

Under this, $ (a \ _i, a \ _j) = (a \ _ k, a \ _l) $ must be ** $ a \ _ j <a \ _k $ **. Therefore, for each pair of two elements, use upper_bound to find the number that satisfies this. However, it takes a linear time to know the index if you use the distance function, so ** implement a binary search by yourself and return the index **. For the implementation of binary search, I referred to my this article.

D.cc


//Debugging options:-fsanitize=undefined,address

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

//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef int 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 4000 //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

//MLE

signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    REP(_,t){
        ll n;cin>>n;
        vector<ll> a(n);
        REP(i,n)cin>>a[i];
        //Managed by each value
        map<ll,vector<ll>> m;
        REP(i,n){
            FOR(j,i+1,n-1){
                m[a[i]*MOD+a[j]].PB(i*MOD+j);
            }
        }
        long long ans=0;
        FORA(i,m){
            //Binary search
            ll m=SIZE(i.S);
            REP(j,m-1){
                ll l,r;l=j+1;r=m-1;
                if(i.S[j]%MOD<ll(i.S[l]/MOD)){
                    ans+=(m-j-1);
                    continue;
                }
                if(i.S[j]%MOD>=ll(i.S[r]/MOD)){
                    continue;
                }
                while(l+1<r){
                    ll k=l+(r-l)/2;
                    if(ll(i.S[k]/MOD)>i.S[j]%MOD){
                        r=k;
                    }else{
                        l=k;
                    }
                }
                ans+=(m-r);
            }
        }
        cout<<ans<<endl;
    }
}

E problem

Recursion is easily MLE with PyPy, why ... Anyway, ** I will write recursion in C ++ **.

Perform the following two operations.

(1) An operation that selects a certain section and reduces the number included in that section by one (however, there is at least one of each)

② Select one number and set the number to 0.

Consider the minimum number of operations when performing these operations and emptying all the sequences. The operation of ② can be easily obtained by simply calculating the number of operations for the length of the section. On the other hand, the operation of ① is a little complicated as follows.

For operation (1), it is best to select the section as long as possible. I won't prove it this time, but I feel that the pattern ** that you only have to select the whole when you select a section and perform an operation ** appears frequently (this time, you can reduce the number of operations by narrowing the section. I thought it wasn't intuitive, so I proceeded with this policy. ** It should be valid **, but ...).

In addition, when performing the operation of ①, perform the operation at the minimum of the section, not ** 1 at a time **. In addition, there is an element that becomes 0 after the operation, and the entire section cannot be operated as it is from the operation condition of ** ① **, so ** Find the minimum number of operations for each section divided by DFS * *.

So, considering the DFS implementation:

(1) When the length of the given interval $ x $ is 1.

The number of elements included in the interval $ x $ (number of operations in ①) and $ min $ in 1 (number of operations in ②) are taken and returned.

(2) When the length of the given interval $ x $ is greater than 1.

The length of the interval is $ l $, the minimum number among the numbers included in the interval is $ m $, the return value is $ ret = 0 $, and the vector that substitutes the divided intervals is $ nex = $ { }will do.

Below this, we will look at $ x [i] $ with $ i = $ 0 ~ $ l $ -1, but when $ x [i]! = M $, we can substitute it for nex. Also, when $ i = l $ -1, the interval is fixed, so call dfs with nex as the interval and add the return value to ret. When $ x [i] = m $, if $ nex $ is not empty, the interval is fixed, so call dfs with $ nex $ as the interval and add the return value to ret. At this time, leave $ nex $ empty for the next interval.

You can find the solution just by performing the above DFS. Also, if DFS is not perfected, problems of this magnitude will be a problem, so I would like to devote myself to it.

E.cc


//Debugging options:-fsanitize=undefined,address

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

//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef int 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

ll dfs(vector<ll>& x){
    ll l=SIZE(x);
    //If 0
    if(l==1)return min(1,x[0]);
    ll m=*min_element(ALL(x));
    ll ret=m;
    vector<ll> nex;
    REP(i,l){
        if(x[i]!=0){
            nex.PB(x[i]-m);
            if(i==l-1)ret+=dfs(nex);
        }else{
            if(SIZE(nex)){
                ret+=dfs(nex);
                nex.clear();
            }
        }
    }
    return min(ret,l);
}

signed main(){
    ll n;cin>>n;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    cout<<dfs(a)<<endl;
}

After the F problem

I will skip this time

Recommended Posts

Educational Codeforces Round 93 Bacha Review (8/17)
Educational Codeforces Round 94 Bacha Review (9/3)
Educational Codeforces Round 91 Bacha Review (7/28)
Educational Codeforces Round 88 Bacha Review (8/4)
Educational Codeforces Round 86 Bacha Review (9/17)
Educational Codeforces Round 89 Bacha Review (9/8)
Educational Codeforces Round 92 Bacha Review (7/30)
Educational Codeforces Round 90 Bacha Review (8/19)
Codeforces Round # 658 (Div. 2) Bacha Review (7/29)
Codeforces Round # 654 (Div. 2) Bacha Review (8/18)
Codeforces Round # 594 (Div. 2) Bacha Review (10/29)
Codeforces Round # 609 (Div. 2) Bacha Review (10/8)
Codeforces Round # 597 (Div. 2) Bacha Review (10/27)
Codeforces Round # 666 (Div. 2) Bacha Review (9/2)
Codeforces Round # 651 (Div. 2) Bacha Review (8/20)
Codeforces Round # 659 (Div. 2) Bacha Review (8/5)
Codeforces Round # 610 (Div. 2) Bacha Review (10/5)
Codeforces Round # 479 (Div. 3) Bacha Review (9/25)
Codeforces Round # 603 (Div. 2) Bacha Review (10/15)
Codeforces Round # 600 (Div. 2) Bacha Review (10/21)
Codeforces Round # 481 (Div. 3) Bacha Review (9/24)
Codeforces Round # 639 (Div. 2) Bacha Review (9/4)
Codeforces Round # 612 (Div. 2) Bacha Review (10/2)
Codeforces Round # 521 (Div. 3) Bacha Review (10/9)
Codeforces Round # 652 (Div. 2) Bacha Review (8/24)
Codeforces Round # 673 (Div. 2) Bacha Review (10/22)
Codeforces Round # 606 (Div. 3) Bacha Review (10/13)
Codeforces Round # 613 (Div. 2) Bacha Review (10/1)
Codeforces Round # 665 (Div. 2) Bacha Review (8/23)
Codeforces Round # 592 (Div. 2) Bacha Review (11/03)
Codeforces Round # 662 (Div. 2) Bacha Review (8/8)
Codeforces Round # 618 (Div. 2) Bacha Review (9/26)
Codeforces Round # 648 (Div. 2) Bacha Review (9/5)
Codeforces Round # 676 (Div. 2) Bacha Review (10/31)
Codeforces Round # 675 (Div. 2) Bacha Review (10/30)
Codeforces Round # 486 (Div. 3) Bacha Review (9/23)
Codeforces Round # 671 (Div. 2) Bacha Review (9/22)
Codeforces Round # 669 (Div. 2) Bacha Review (9/9)
Codeforces Round # 672 (Div. 2) Bacha Review (10/16)
Codeforces Round # 638 (Div. 2) Bacha Review (9/16)
Codeforces Round # 663 (Div. 2) Bacha Review (8/13)
Codeforces Round # 668 (Div. 2) Bacha Review (9/7)
Codeforces Round # 663 (Div. 2) Bacha Review (8/16)
Codeforces Round # 609 (Div. 2) Bacha Review (10/6)
Codeforces Round # 645 (Div. 2) Bacha Review (9/10)
Codeforces Round # 664 (Div. 2) Bacha Review (8/13)
Codeforces Round # 660 (Div. 2) Bacha Review (8/4)
Educational Codeforces Round 87
Codeforces Round # 643 (Div. 2) Review
Codeforces Round # 679 (Div. 2) Review (10/25)
Codeforces Round # 657 (Div. 2) Review
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
DP100 Question Bacha Review 1 ~ 10 (8 / 26,27)
Codeforces Educational Codeforces Round 101 C. Building a Fence Manage scope YES/NO
Codeforces Round # 626 B. Count Subrectangles
Codeforces Round # 609 (Div. 2) (up to B)