mesanu's blog

Codeforces Round 898 (Div. 4)
By mesanu, history, 15 months ago, In English

Hello Codeforces!

flamestorm, MikeMirzayanov and I want to invite you to Codeforces Round 898 (Div. 4).

It starts on Sep/21/2023 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

  • 5-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behaviour. To qualify as a trusted participant of the fourth division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to the testers: Gheal, Phantom_Performer, KrowSavcik, haochenkang, sandry24, BucketPotato, Vladosiya, NintsiChkhaidze, erekle, Dominater069, MADE_IN_HEAVEN, Qualified.

We suggest reading all of the problems and hope you will find them interesting!

Good Luck!

UPD: Editorial is out!

  • Vote: I like it
  • +200
  • Vote: I do not like it

Comments Comments (97)
| Write comment?
»
15 months ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So hapy for the round. I did't participate in a rated round for a long time.:)

P.S. I am not racist

→ Reply
»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

My first unrating contest :)

→ Reply
»
15 months ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it -49 Vote: I do not like it

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 ``)

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Because we will get too many dumb specialists

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Theyre too hard i think there should be more div1 contests for new people, it's really dumb how there's only 2 every month...

    → Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Where is SlavicG ?

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest is gonna be fun!

→ Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

First unrated contest for me !!

→ Reply
»
15 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My First Unrated Round

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Specialist here I come!!!

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully my last rated div4 :O

→ Reply
»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Finally First unrated contest

Spoiler
→ Reply
»
15 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it -31 Vote: I do not like it

flamestorm > MikeMirzayanov :)

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is it rated?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +7 Vote: I do not like it

average div4 round

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool problem set.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WTF IS WRONG WITH PROBLEM F?

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I see nothing wrong with F. Time wise, it took me much longer to solve G.

                   problem: A  B  C  D  E  F  G  H
  num_minutes_to_solve: 6  2 10  3  5 26 63 28
    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :((((((

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same. But I stuck at problem E. Did anyone give some advises for solving binary search problems like this? I am too dumb to ensure the edge condition. Would I use mid = (l+r)/2 or(l+r+1)/2? give answer as l? or r? or mid? all gives me a lot trouble.

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The edge conditions also confused me a lot. You can actually use recursive functions to write the binary search algorithms just like building a segment tree ,which means you don't need to worry about the vague conditions any more.

      int solve(int l,int r) //The answer exactly belongs to [l,r]
{
	if (l==r)
		return l;
	
	const int mid=(l+r+1)/2;
	if (check(mid))
	    return solve(mid,r);
	return solve(l,mid-1);
}

      We replace the variable mid into (l+r+1)/2 instead of (l+r)/2 because it always satisfies mid<=r and l<=mid-1. If mid is a valid answer then the interval would be shrunk into [mid,r]. Of course, if mid is an invalid answer we can just throw it out, so we choose solve(l,mid-1) instead of solve(l,mid). Details are very clear if you write the algorithm like this.

      → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      C#, but should be almost exactly the same in C++

       static long BinSearch(Predicate<long> IsInRightPart, long l, long r, bool firstYes = true)
        {
            while (l < r)
                (l, r) = firstYes
                    ? (IsInRightPart((l + r) / 2)
                        ? (l, (l + r) / 2)
                        : ((l + r) / 2 + 1, r))
                    : (IsInRightPart((l + r + 1) / 2)
                        ? (l, (l + r + 1) / 2 - 1)
                        : ((l + r + 1) / 2, r));
            return l;
        }
      → Reply
»
15 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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';
}

}

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    (not verified with code but just based on code review): The raw tmp value range is [0,n] and then adjusted to [0,n-1]. When tmp is 0, gap should be 0 instead. To fix, do not adjust tmp, but compute gap with:

      gap = mid * tmp - (tmp == 0 ? 0 : dp[tmp-1]);
    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please explain F

→ Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it 

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 ?

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    penalty is total of time you need to get AC all problems. If you haven't AC a problem (except WA on test 1), then 10 minutes is added to your penalty when you AC that problem.

    → Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Imagine the character 'B' will divide $$$s$$$ into some parts of consecutive 'A'. Then the answer is just the total 'A' in $$$s$$$ minus the minimum number of 'A' among all these parts.

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    zackscott286 already explained what the code does. To get there, note that we can get rid of any sequence of 'A' as long as there is a 'B' next to it, but that a single 'B' can only be used to eliminate either the sequence to its left or the one to its right. As the number of 'A' sequences is one more than the number of 'B', one of the 'A' sequences needs to stay, and we can always ensure that we only keep the shortest. The maybe somewhat surprising part of this is that this still works if this shortest sequence is empty, i.e. if the string starts or ends with 'B' or contains a substring 'BB'.

    → Reply
»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 =|

→ Reply
»
15 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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!

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

Please explain some one...

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, it is confusing. But you can choose subsegment of length 1 if a[i] <= k

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeahh I also had a chat with them on this. They didn't mentioned anything about subarray of size 1.

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There's no such $$$i$$$, so, no such constraint too. If $$$r=l+1$$$, we have to ensure $$$h_l$$$ is divisible by $$$h_r$$$. If $$$r=l$$$, there's nothing we have to ensure. You can also find such case in the 3rd example

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Please red the blog https://mirror.codeforces.com/blog/entry/120638.

    → Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Nice contest! I really enjoy it

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Please try to hack this Problem F

→ Reply
»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it +5 Vote: I do not like it

In queueueueueueueueueueueue!!!

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh I missed the Div.4 again:(

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My first cf contest!!! For a freshman.

→ Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Kendrick Round

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

YAY! I'M CYAN

→ Reply
»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it may be only a coincidence.

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Another coincidence with Luogu Monthly Contest... Hope that the authors can check their problems in Chinese websites (such as Luogu) before the round in the future.

    → Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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!

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :/

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Bro was trying to avoid plagiasm check, but got caught anyways :)

    → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please find any exception for my source code for G? I think my code is correct but it gets wrong on test 2. My submission: 246793693.

→ Reply