Omg sponsored div2 round!

It will be interesting if Mike and the team can share how they prepare a contest.

1. How each problem was created(Idea)?
2. Problem statement
3. How testers helped?
4. How they decided problem difficulty?
5. If any other challenges they have faced

So we can understand your efforts and hard work to conduct a contest.

can i expect constructive algo problem? as it was sponsored by constructor institution

As a tester, I thought the problems were nice, and I recommend participating in this round!

As a tester, I hope my enjoyment when testing the round would be indicative of your enjoyments when participating in it.

orz tibinyte testing round !!!

Hope to become cyan!

Hoping to reach specialist this time.

Hope to become specialist before arrival of Joyboy

Hope to be constructive(as this round)

As a tester, I really enjoyed this round! Everyone should participate!

I say a full constructive and a happy specialist for me. gl everyone!

As a participant i recommend all of you to participate.

As a tester, good luck! (And give me contribution)

Based on the score distribution, I think this round would be speedforces.

Hiha, this round is going to be fun! >_<

hoping to become pupil again

As a tester, problems is excellent and cute :>

This Constructor Institute, it's the former "Schaffhausen Institute of Technology", right? Is it going to obtain (or maybe already has) accreditation any time soon? I also wonder what's the connection with Constructor University Bremen... They seem to share the logotype.

As a tester, ris noitubirtnoc em evig esaelp

Round Clashing with Leetcode Round

hope i can ac C problem ：）

Thanks,Constructor Institute.

Hope I can be a master.

5 problems? I think it will be hard.

Hoping to become pupil this contest

preparing for permutation problems :) DYK? A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

It's good to see that cf is finally improving on their problem statements.

For me, this was the coolest contest I've been to in the last couple months. Namely in the fact that the tasks mostly do not require knowledge of complex algorithms, all the solutions are quite short. Thank you! And a question. in E2 n = 1e6 to prevent bitset O(n^2/64) solutions?

I'm fed up with these constructor algo problems.

A: If a[i]<=a[i+1], then 0 <= max(0, a[i+1]-1) and a[i]-1 <= a[i+1]-1 <= max(0, a[i+1]-1), therefore max(0, a[i]-1) <= max(0, a[i+1]-1), then a[i]<=a[i+1] holds after any times of operation. If a[i]>a[i+1], we need to perform a[i] operations to make a[i]=a[i+1]=0. So the answer is max(a[i]) where a[i]>a[i+1].

B: If n==1 there's no solution, let's assume n>=2. Let t be the number of occurences of 1 in a[i]. If t==0, then we can let a[1]+=n-1 and a[i]-=1 (2<=i<=n). Let's assume t>=1. Then sum(i: a[i]==1)(b[i] — a[i]) >= t because b[i] is positive integer and b[i]!=1, so b[i]>=2. Therefore, sum(i: a[i]!=1)(b[i]-a[i]) <= -t --> sum(i: a[i]!=1)(a[i]-b[i]) >= t --> sum(i: a[i]!=1)(a[i]-1) >= t. So if sum(i: a[i]!=1)(a[i]-1) < t, there's no solution. Otherwise, we can construct a solution: First turn 1 into 2, then we reduce the maximum element in a by 1 for t times. If there's some a[i] remain unchanged, then a[i]>1, then we can reduce them by 1 and add them to any occurence of 2.

C: For any 1<=i<=n-1, let's find the maximum value it can become by binary search. Assume the value we are checking is T. Then we need T-a[i] operations on i-th element. If a[i+1]>=T-1 then we are done. Otherwise, we need T-1-a[i+1] additional operations on (i+1)-th element, Then check if a[i+2]>=T-2. We repeat this process until we find some j such that a[i+j]>=T-j, or we have used more than k operations. Then we can solve the problem in O(n^2*log(k)).

D: We can solve the problem by D&C (Divide and Conquer). Assume we need to find the index of maximum element on [L, R]. If L==R then the answer is L. If L+1==R, we can do query(L, R) and the answer of query is 1 if p[L] is the maximum (0 otherwise). In general cases, we choose M close to (L+R)/2 and solve (L, M) and (M+1, R) recursively, assume their answer be x, y. Then we only need to find if p[x]<p[y]. Let's do query(x, y) and query(x, y-1), the difference of answer of the queries means "there are how many i such that x<=i<=y-1 and p[i]>p[y]". If p[x]<p[y], then we have p[i]<=p[x]<p[y] for x<=i<=M and p[i]<p[y] for M+1<=i<=y, so the difference will be 0. Otherwise we have p[x]>p[y], so the difference will be at least 1. Then we can solve the problem. The cost of queries will be not greater than 2*n^2 for the top layer, 4*(n/2)^2 = n^2 for the second top layer, 8*(n/4)^2 = n^2/2 for the third top layer and so on. So the total cost is not greater than n^2*(2+1+(1/2)+(1/4)+...)=4*n^2.

How to approach C problem anyone??

Could anyone please tell me how my E1 question didn't pass the test 7?

E2，seems to be bad. why 1e6.

hint for E2?

Anyone who had wa7 on e1, how did you deal with it?

i wish all cf problem statements are like this contest. even though I did badly in it.

Any idea for E1? I thought of a dfs approach, in which I visited every node and counted the total number of nodes in it's subtree. Then according to the number of immediate children to the node, I tried dividing the total number of nodes in the subtree into two groups such that both the groups have roughly the same number of nodes.

I kept getting wrong answer on test case 7 for some reason I don't understand. Can anyone provide some insight to it please?

It is interesting, that transition from E1 to E2 looks like a super standard problem that everyone should know how to solve, yet so much struggle to do so. (Note, personally idk how to solve E2).

Just wanna know how many people got WA on problem D because of making query with l = r LOL.

WA on 6th pretest in C anyone?

Submission: 217341446

Who decided E1 was a good problem on 5th position?

just asking to confirm if it is just with me or happening with u also? Did the first question took more than 5 minutes to load for u all?

Most balanced contest ever!

Cool problems, thanks. :)

wasted 30 minutes on C because I did not read the constraints carefully

Had high hopes from this contest, but got stuck at A:(

Please help me what went with my logic/code ; It keeps failing on pre-test 2. I am not able to find a test case, where this fails. If you could provide me with one, I can word out the error myself. Thanks!

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define ll long long

void solve(){

    ll n;
    cin>> n;

    vector<ll> v(n);

    for(ll i=0;i<n;i++){
        cin>>v[i];
    }

    if(is_sorted(all(v))){
            cout<<0<<endl;
            return;
    }

    ll index = max_element(all(v)) - v.begin();
    if(index!=n-1){
        cout<<*max_element(all(v))<<endl;
        return;
    }
    else{
        ll index=INT_MIN;
        for(ll i=n-1;i>=1;i--){
            if(v[i]<v[i-1]){
                index=i;
                break;
            }
        }
        cout<<*max_element(v.begin(),v.begin()+index)<<endl;
    }   
}

int main(){  

	ll t;
	cin>>t;

	while(t--){
		solve();
	}

    return 0;

}

Hints for B?

please help in C

C was a good problem E1 also. I solved it with DFS+SUBSET SUM Dp

Is it possible to solve C without binary search? My idea is to check each subarray and find the maximum value achievable, but was not able to implement it in $$$O(n ^ 2)$$$.

well，E1 is easier than D and it can easily AC,but E2's score is lower than D,it makes A+B+C+D+E1 > A+B+C+E1+E2 . you know , AC E2 is more and more and more harder than AC D.

Is it good?

Could anyone tell me why my E1 code returns the wrong answer on test #13?

my E2 solution without bitsets fits in half of TL, can anyone hack? 217346719

A question to anybody who solved C: this problem is about BS on the answer. How do you understand a problem requires being approached in this way? Is there a particular signature or something which makes you think in this direction? Is it the constraints? The fact that the operation was mentioned to be performed no more than k times? Does it ut just comes with experience and/or by solving similar problems(if yes please suggest some)? Any good insight is appreciated.

can someone tell me why i got FST on E1? 217343471
my approach: I calculated the subtree size for each node. then for every node, stored the subtree sizes of its child nodes in an array. then did a dp to partition the array in 2 sets such that the difference of their sum is minimized. and then added their product with answer.

upd: got ac after making the graph directed :')

Does 11k+ submission of B justified ??

After getting FST on problem D, I dropped from rank 3 to rank ~200. I am not surprised because in each recursion I ask three queries (r-l)*(r-l). If my code did not pass the pretests, I would come up with the solution.

And I think the score division in problem E is not suitable.

Sorry for my bad English!

Could anyone help me out with C Submission

I hope rating changes will update before i get to sleep.