mesanu's blog

Codeforces Round 898 (Div. 4)
By mesanu, history, 3 years 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 (92)
| Write comment?
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

My first unrating contest :)

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Where is SlavicG ?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This contest is gonna be fun!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

First unrated contest for me !!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My First Unrated Round

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Specialist here I come!!!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hopefully my last rated div4 :O

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Finally First unrated contest

Spoiler
→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it -31 Vote: I do not like it

flamestorm > MikeMirzayanov :)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

is it rated?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

average div4 round

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Cool problem set.

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

WTF IS WRONG WITH PROBLEM F?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

please explain F

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Nice contest! I really enjoy it

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Please try to hack this Problem F

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

In queueueueueueueueueueueue!!!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Oh I missed the Div.4 again:(

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My first cf contest!!! For a freshman.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Kendrick Round

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

YAY! I'M CYAN

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    it may be only a coincidence.

    → Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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