monthly leetcode contest let's gooooo!!! hope the statements are clear to everyone (so that we can ak faster)

My first unrating contest :)

As a tester, today K77 will score a goal. P.S problems are very nice.

Why?

• Why isn't Division 4 prepared on a weekly or bi-weekly
  basis instead of being held every two months?

class vote:
    votes=0
    def __init__(self,state="up"):
        if state=="up":
            votes+=1
        else:
            votes-=1
upvote_me = int(input())
for i in range(upvote_me):
    obj = vote(state="up")

print(vote.votes) 

upvote pls ``)

Where is SlavicG ?

This contest is gonna be fun!

First unrated contest for me !!

its been ages since the last time problem ratings were updated. :feelsoldman:

My First Unrated Round

Specialist here I come!!!

Hopefully my last rated div4 :O

Finally First unrated contest

Spoiler

:P

Bro really I was waiting for this day to participate in my first Div 4. contest and I can not register because of one rating point

flamestorm > MikeMirzayanov :)

is it rated?

i am going to participate despite having chemistry exam tomorrow, sorry to mr Ratherford, Bohr, Thomson, Schrodinger, Higenberg and 69 others :)

Why aren't there more div4s i think once per month is too rare, we are noob we need more div4

Good luck to everyone, I hope I can get specialist this round!

average div4 round

Cool problem set.

Wow, that contest was amazing!!! I really hope that with such contests, I'll become green...

balanced problems and clear statements, this is defintion of a perfect contest!! thanks to the authors

Loved the Kendrick Lamar references throughout the contest! The authors have good taste in music

WTF IS WRONG WITH PROBLEM F?

bruh imagine doing 5 problems in 18 minutes and being like top 50 or even better and then taking 2 hours for the sixth one, i don't understand what happened to my brain :((((((

why is this code wrong for E? plz give me some advice. thx in advance.

include <bits/stdc++.h>

using namespace std;

long long num[200001]; long long dp[200001];

int main(void) { ios::sync_with_stdio(0); cin.tie(0);

int t;
cin >> t;
for(int i=0; i<t; i++)
{
    int n, x;
    cin >> n >> x;
    for(int j=0; j<n; j++)
       cin >> num[j];
    sort(num, num+n);
    dp[0] = num[0];
    for(int j=1; j<n; j++)
       dp[j] = dp[j-1] + num[j];
    long long st = 0, en = 4000000001;

    while(st+1 < en)
    {
       long long mid = (st+en)/2;
       long long tmp = lower_bound(num, num+n, mid) - num;
       if(tmp == n)
         tmp--;
       long long gap = mid*(tmp+1) - dp[tmp];
       if(gap > x)
         en = mid;
       else
         st = mid;
    }
    cout << st << '\n';
}

}

please explain F

Duuuudeeee if I had like 1 minute, I would've solved the last problem yikes

include<iostream> 
#include<bits/stdc++.h> 
using namespace std; 
int possible(vector<int> v,int mid){
    int n = v.size(); 
    int  wdth = 0; 
    for(int i=0;i<n;i++){
        if(v[i]<mid){
            wdth = wdth + (mid-v[i]); 
        }
        else{
            continue; 
        }
    }
    return wdth; 
}
int main(){
    int t; 
    cin>>t; 
    while(t--){
        int n; 
        cin>>n; 
        int w; 
        cin>>w; 
        vector<int> v; 
        for(int i=0;i<n;i++){
            int x; 
            cin>>x; 
            v.push_back(x); 
        }
        int low = 1; 
        int high = w + accumulate(v.begin(),v.end(),0); 
       int  ans = -1; 
        // binary search on heights 
        while(low<=high){
           int mid = low + (high-low)/2; 
            if(possible(v,mid)<=w){
                low = mid + 1;
                int cnt = mid; 
                ans = max(cnt,ans);
            }
            else{
                high = mid - 1; 
            }
        }
        cout<<ans<<endl; 
    }
}

i applied checked width for every height from lower to upper bound and applied binary search on heights it passed 3 test cases whats the problem ?

Why showing penalty currently in the standings? I didn't do wrong submissions?

pwild can you please explain this beautiful solution of yours for G?

MY INTUTION FOR THE LAST ONE IS. ONLY ONCE CYCLE EXISTS IN THE GRAPH IF IT DOES. FIND WHERE THE PERSON RUNNING CAN ENTER IT. THEN SEE WHO CAN REACH IT FIRST. IF THE PERSON RUNNING CAN REACH IT FIRST ITS A YES OR ELSE A NO. AM I RIGHT? I COULD NOT DO IT COZ I WENT TO EAT A CAKE.

When you've spent a whole hour coming up with a solution for H when there are 1 to n*(n-1) edges, and only after the solution was found do you notice that there are only 1 to n edges =|

Problem E is nice, came up with binary search fast but spent lots of time fixing the high bound, lesson learned for me.

Problem G is so nice, with short and clear statement, like it the best in this contest!

Thank you guys for the contest!

For problem F: Given, (l≤i<r). Here, How l and r can be same? That means (l==r)?

Please explain some one...

Can someone help me find issue in F? I am not finding any case where it is failing. TIA https://mirror.codeforces.com/contest/1873/submission/224511926

Does problem F, test 2, test case 1: n = 2, k = 15, a = {9, 6}, h = {1, 3} exists a contiguous subarray satisfies the condition that each i (l <= i < r), h_i is divisible by h_(i+1)? The expected answer is 1, but there is no h_i is divisible by h_(i+1), so I think there is no contiguous subarray satisfies the condition. Please explain.

For Problem E how are we supposed to fix the upper bound while using binary search

I never thought upper bounds could be an issue. I assumed taking high bound as LLONG_MAX-1 should suffice always

I was surprised by my friend's submission in problem E. He used greedy that I couldn't think it was possible LOL. His submission: 224456152

Nice contest! I really enjoy it

Were some of the problems in the contest inspired by Kendrick lamar?

Please try to hack this Problem F

Some of the problem names reference Kendrick's songs, right?

In queueueueueueueueueueueue!!!

Oh I missed the Div.4 again:(

My first cf contest!!! For a freshman.

Kendrick Round

YAY! I'M CYAN

However, H is https://www.luogu.com.cn/problem/P8943

You can also watch the video editorials I made on the problems E , F, G and H

Enjoy watching and let me know what you think about them!

I'm sorry for using ideone.com

Supposedly, out of the five that I solved, it's showing (that Solution B) of mine coincides with a couple of people, in a hurry while submitting I accidentally used ideone.com with public display settings, Sorry for that

Proof: https://drive.google.com/file/d/17RVpgMSCirhaVRcfAAACe9_cnKEhVPLd/view?usp=sharing

Sorry :/