1 minute late editorial?

:)))) Too fast

E was such a good problem, great problemset. im so mad i didnt get C earlier though

very interesting problems!!

The goddamn C...

so fast :O

anyway, good songs :D

Thank you so much for the great contest! I loved the problems!

Is it just me or was this Div 2, little too difficult?

To solve the third problem [2018A cards partition], can we use the binary search?

if yes then how to implement the checker function that this size of deck is possible or not

How much practice do i need i was stuck at B completely.

E1，O(n * sqrt(n) * log^2(n)) got a TLE......sad

How to implement E.

today's contest just ruined my day (though contest was good)... My submission on C 283251847 is the biggest blunder i had done till now... if i did not tried the binary search && just run a loop my code would be accepted && I might be Cyan today...

when i firstly start to solve this C.. i go for nlogn approach... then make the function 'f' .. but i did not notice function is literally O(1) .. so I could run a O(n) loop...

when i find this 1 minute after contest, I realize this CP is not for me...

(apologies for my poor english)..

The intervals in the editorial of F should be $$$[i - a_i + 1, i + a_i - 1]$$$?

An alternative solution for Speedbreaker (Div2D):

There are 4 cases:

1. $$$a_0 < n$$$ and $$$a_{n-1} < n$$$: no solution is possible.
2. $$$a_0 \geq n$$$ and $$$a_{n-1} < n$$$: This means that $$$a_0$$$ must be the last element that is conquered. We now check how many solutions exist in the interval $$$[1, n-1]$$$.
3. $$$a_0 < n$$$ and $$$a_{n-1} \geq n$$$: Similar to second case.
4. $$$a_0 \geq n$$$ and $$$a_{n-1} \geq n$$$: We now want to check if $$$a_0$$$ and $$$a_{n-1}$$$ are valid solutions. $$$a_0$$$ is a valid solution only if we can conquer every city going from left to right. To check if $$$a_0$$$ is a valid solution, create a segment tree $$$b$$$ with $$$b_i = a_i - i$$$. Now do a query on the range $$$[0, n-1]$$$. $$$a_0$$$ is a valid starting city if and only if the result of the query $$$\geq 1$$$. For checking if $$$a_{n-1}$$$ is a valid starting city, do something similar. After that, count the number solutions in the range $$$[1, n-2]$$$.

Submission: 283247155

Wasn't div2 E a lot easier for its position?

C was tooo gorgeous... Gave it the attempt of my life on Codeforces... Learnt a lot, it was like an adventure... Thank you contest×codeforces

For div2 E i used ternary search on depth...and got wrong answer on test 3.i can not find any wrong case.can anyone hep me 283252293? update: may be this problem can't be solve using ternary search. i got a case

woah too fast (:

Felt like DIV2B was harder than DIV2C :)

Oh wow, my solution to F is completely different. The canonical strategy that I use for an array with a marked interval of possible starting cities is to always go to the city with the shortest deadline and break ties by going left. It seems that the resulting dp is very different (and in particular I don't need to use any division)

Obligatory "thanks mr Radewoosh" comment.

div1E is https://mirror.codeforces.com/blog/entry/61331

Why this code is a incorrect !! My intuition was first find maximum element across the array and then if n is even — n/2 and if n is odd — ((n+1)/2)?!

int main() {
    int t;
    cin >> t; 
    while (t--){
        int n;
        cin>>n;
        vector<int>arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        int max_value= *max_element(arr.begin(),arr.end());
        if(n==3){
            cout<<arr[0]+((n+1)/2)<<endl;
        }
        if(n%2==0){
            cout<<(n/2)+max_value<<endl;
        }
        else if (n!=3){
            cout<<((n+1)/2)+max_value<<endl;
        }
    }
 
    return 0;
}

It's shocking that so many people in Div1 solved problem C.

can someone please tell me what's wrong with this soln for Div2-B? it gave WA on pretest 9

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin>>t;

    while(t--){
        int n,q;
        cin>>n>>q;
        vector<int> v(n);
        vector<long long> queries(q);

        for(auto &x:v) cin>>x;
        for(auto &x:queries) cin>>x;

        map<long long,int> mp;

        for(int i=0; i<n; i++){
            long long cnt = 0;  // number of segments this point is part of

            if(i==0 || i==n-1) cnt += n-1;
            else{
                cnt += (n-1+(i*(n-1-i)));
            }

            if(mp.find(cnt)!=mp.end()) mp[cnt]++;
            else mp[cnt]=1;
        }

        for(int i=0; i<n-1; i++){    // considering the points that lie on the axis apart from the ones in the array
            long long cnt = (i+1)*(n-1-i);

            if((v[i+1]-v[i]-1)>0){
                if(mp.find(cnt)!=mp.end()) mp[cnt]+=(v[i+1]-v[i]-1);
                else mp[cnt]=(v[i+1]-v[i]-1);
            }

        }

        for(int i=0; i<q; i++){
            if(mp.find(queries[i])!=mp.end()) cout<<mp[queries[i]]<<" ";
            else cout<<0<<" ";
        }
        cout<<endl;


    }

    return 0;
}

My O(n^5) solution (with small constant) passed F1. However it's hard to optimize to O(n^4) or better (Because I solved d1B by a suboptimal solution, which mislead my thinking of F1)

EDIT: you can actually do this in $$$O(n)$$$: 283287968. Same idea, but using path counting instead of the first PIE step.

For F you don't really have to think about paths at all, inclusion-exclusion on the arrays is enough (submission 283272424, ignore the unused variable).

Idea one: it's always sufficient to take the "working" interval first.

Idea two: to count the number of arrays of length $$$k$$$ with elements in $$$[1,n]$$$ and every index works, one only needs to make sure the endpoints work. You can just lower bound the elements for a count of

Now iterate over $$$k$$$. Count the above and consider how to count extensions to arrays of length $$$n$$$ that do not break any of the elements that were supposed to work. You can do this with PIE; to get extensions of length $$$i$$$ get extensions of length $$$i-1$$$ and extend them on either side, then subtract out extensions of length $$$i-2$$$ where you can take the next two elements in either order. (see my solution for the push dp)

Now you have

Idea three. the PIE to finish is by subtracting out

for each $$$a$$$ with a working interval larger than $$$k$$$. If you know the size of the working interval, you can count this.

too fast!!

D is a tremendous problem

Good contest, I explained the entire process of how to do D (div 2) and GPT-o1-mini still couldn't solve it.

In case anyone is wondering, I have written a code with the exact same logic and it is AC. You can check it out on my submissions.

Good news is, despite several attempt and demand of direct conversion of logic to code without adding its own logic, it could not produce a code which solved even TC 1.

This implies GPT-o1 really isn't something we should worry about for now for div 2 and above. Not only can it not think critically, it cannot even follow basic logical instructions.

Can someone tell me why I got WA on Test Case 9?

283223987

Can anyone tell me which test case will be wrong in this solution of Problem C 283238912 ? Can anyone give me the tc where binary function won't be monotonic??

I have a quite different solution for Div2 E. I think it’s quite enriching and gives some insights about an alternate way of thinking hence i will try to present it here. Let’s try to calculate the cost for some fixed final depth(say d) of all the leaves. What do we need to do to make the depth of all the leaves equal to d? Try to think of it before looking up the spoiler below.

Do the two cases hint you something, how are they related. Do they seem quite similar?

We define two arrays:

1) less[d] : it represents the cost of case 2 for depth d. More formally for some depth d, it represents the cost of removing all leaves with depth less than d to a point where the left tree has no leaf with depth less than d

2) more[d] : cost of case 1 for choosen depth = d(define formally in a similar way)

How do we calculate these for all possible d(0 <= d <= n)

Now the cost for a final depth of d = less[d] + more[d]. Hence take minimum across all the values

You can view my solution for implementation details here : 283261930

Div2E, can solve using bfs.
iterate level-by-level, each level we can compute the number of nodes not removed.
when a node is a leaf node, need to remove from leaf to it’s parent recursively.

what is the "x" in the tutorila of problem C

Here's a "troll" way to solve F in linear time.

As with some other approaches to this problem, we want to answer the following question: given $$$n$$$ and a width $$$w$$$, compute the sum over all $$$n-w+1$$$ intervals of width $$$w$$$ of the number of ways to pick numbers outside that interval so that all cities in that interval are good, given that the numbers inside that interval are already chosen to make it possible. Now observe, either through a bijective argument or by printing the results from a slower solution, that this quantity only depends on $$$n-w$$$, i.e. it is the sequence $$$1$$$, $$$2$$$, $$$7$$$, $$$34$$$, $$$209$$$, $$$\dots$$$ found in column 1 of the samples. Finally, observe that this is OEIS A002720 which provides a recurrence that computes these numbers in linear time. The rest is straightforward.

$$$O(n)$$$ Algorithm for D1F: https://mirror.codeforces.com/contest/2018/submission/283298613.

Thank you for sharing polygon materials! For future setters, can we normalize this?

Very nice problems!

Could someone explain the problem div2D for me, as I couldn't understand the editorial.

For problem D(div2) can someone explain this line from the editorial — "At some time t, consider the minimal interval [l,r] that contains all the cities with ai≤t(let's call it "the minimal interval at time t"). If this interval has length >t, the answer is 0."

Can anyone explain C?

It's my birthday and I get -180 as a gift :p sadge

Can the editorial writers consider providing some useful thinking process to reach the solution instead of a formal proof of correctness which I don't think is very useful for most readers of the editorials ?

At least, for Div2 A B C D , make it simple and intelligible and actually useful for PROBLEM-SOLVING.

For example, I find editorial for problem C very challenging to follow and honestly not very useful. I Solved this problem before reading the editorial with a very different thinking.

I suggest that the editorial writer for such problems not to be red coder but maybe expert level, or a red coder who has some teaching background.

Great contest,was able to solve A-B-C,got the idea of E in the contest but didn't know how to find lca of two node in logn time(though i know that binary lifting is used),after the contest i learned Lca using binary lifting.Basically i calculated distance of root from every node.Let say we fix the level of all the leaf nodes in the tree,total number of edge that u have to remove is nothing but ((n-1)-total number of unique edge that all the node on the particular level pass through)).To calculate the total number of unique edge on a particular level,i iterated through all the node in that level using queue,and added (distance of that node from root-distance of lowest common ancestor of previous node and current node from root).Answer is lowest operation on all the level.

how 2F?

can anyone help me understand D?

:O I see a lot of geometry dash songs in the problem statements

in problem E can we solve it ternary search? if no why?

can you please include the actual solutions themselves

can anyone provide me the dp solution for 1st problem ...did it using greedy but not getting right solution using dp...2019A Max Plus Size

For 2018B-Speedbreaker, I have another solution which seems simpler. Consider [1,n] first, we observe that if max(a[1],a[n])<n, then there isn't a valid starting point because 1st or nth must be the last city visited. If a[1]==n, we know that if we start in [2,n], then 1st is the last city and we can only consider cities [2,n]. This implies we can first check whether 1st is a valid starting point or not, and then decrease the question size by one. When considering [l,r] and a[l]>=r-l+1 (we want set l to l+1), l is valid starting point if and only if a[l]>=1, a[l+1]>=2, a[l+3]>=3,...,a[r]>=r-l+1, which is equivalent to a[x]-x>=1-l for any x in [l,r], which can be maintained using Sparse Table. Similar condition for r when we want set r to r-1. This leads to a O(n log n) solution.

Could anyone please explain me how to prove this part of C solution: "the maximum number of cards of some type (x ) is ≤m/s"

I saw a lot of solutions for problem Div1D. Max Plus Min Plus Size that use DP + Segment tree. Can someone explain those please?

I might be retarded but once you get the arrays a and b for Div2E/Div1C as mentioned in the editorial, how do you calculate the count of intervals overlapping each 1<=i<=n, at least without using max segment tree with range update or something stupid. I saw a lot of answers using prefix sum and Shayan's video editorial also mentioned prefix sum, but I'm absolutely not able to understand what we are accomplishing with prefix sum.

Can someone explain div2D "speedbreaker" problem ? I am not able to understand it solution ?

hello, I am getting wrong answer on test 45, i tried my best but i was unable to find why it is happenning in this Solution, Problem D Name- mouse hunt , in educational round 49,could anyone please help me

What is x in the solution of problem C?

Hi, this is my second account and in this round I was testing my solution to problem A before writing it in my official account and i had no idea that my solution will be skipped if I did this, so can you please accept my solution because as a beginner I was trying hard to solve it and thank you

I have a strict $$$\mathcal{O}(n)$$$ approach to the div1C problem, which uses long-chain partitioning to optimize dynamic programming on trees.

283907902

Can anyone elaborate on Div1.D? I cannot understand the editorial. Thanks in advance!

Problem B is too difficult to understand

For problem Div2E, I understand for all leaves to have depth d, nodes that will be alive need to satisfy below properties:

1. Their depth(ai) >= d
2. Maximum depth of child in the subtree(bi) >= d

But how does it translate to this line in the tutorial: So every node is alive in the interval of depths [ai, bi] ? How do above properties enable us to form an interval of depths [ai, bi] ?

Sorry, for D1B, you say one possible solution is to intersect all $$$[i-a_i+1, i+a_i-1]$$$, but the second sample case fails?

6
5 6 4 1 4 5

$$$[-3, 5]$$$ $$$[-3, 7]$$$ $$$[0, 6]$$$ $$$[4,4]$$$ $$$[2,8]$$$ $$$[2,10]$$$

The intersection is $$$[4,4]$$$ right?

Now I understand why problem D was named speedbreaker.

I have trouble with problem E why order was O(n √n α(n)) ? i think is it O(n √(nlg) α(n))

How to perform the following check (from editorial problem 2018A — Cards Partition) in O(1) time?

'' if you already have x⋅s or more cards at the beginning, you have to check if you can make m a multiple of s. ''

I tried this code for Cards partition problem , it's not working can anyone tell why ?:

void solve() {
    int n , k ; 
    cin >> n >> k ; 
    vint arr(n); 
    inp(arr , n) ;
    int maxi = -1 ; 
    int sum= 0 ;
    ffor(i,0,n){
        if(arr[i] > maxi){
            maxi = arr[i] ; 
        }
        sum += arr[i] ; 
    }
    //cout << sum << endl ;


    int l = 1 , r = n ;
    int ans  = l ; 
    while(l<=r){
        int mid = (l+r)/2 ; 
        if(sum%mid == 0 && sum/mid >= maxi){
            ans= mid ; 
            l  = mid+ 1 ; 
        }
        else if( (sum+k)/mid >= maxi  && ((sum+k)/mid)* mid >= sum ){
            ans= mid ; 
            l = mid+ 1 ;
        }
        else r = mid-1 ; 
       ; 
        //"  "<< mid << " " << l << " " << r << endl;
    }
     cout << ans << endl ;
    
}

I wrote this code for solve this problem if there is/are any question feel free to ask me : ~~~~~~~ import math

def helper(cases): seq_res = [] for case in cases: n, array = case max_value = max(array) length = math.ceil(n / 2)

if n % 2 == 0:
        result = max_value + length
    else:
        odd_position_found = False
        for i in range(n):
            if array[i] == max_value and (i % 2 == 0): 
                odd_position_found = True
                break          
        if odd_position_found:
            result = max_value + length
        else:
            result = max_value + length - 1

    seq_res.append(result)
return seq_res

def solve(): cases = [] for _ in range(int(input())): length = int(input()) take_it = list(map(int, input().split())) cases.append((length, take_it)) result = helper(cases) for res in result: print(res)

def main(): solve()

if name == "__main__": main() ~~~~~~~~