Hello Codeforces!

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

It starts on 21.09.2023 17:35 (Московское время).

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!

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

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

P.S. I am not racist

My first unrating contest :)

Mine too

me too

mine too

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

Kvaradona

my profile picture says it all :)

Kvara orz!

## Why?

basis instead of being held every two months?Because we will get too many dumb specialists

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

this will be my first contest on this platform (unless im too lazy)

Where is SlavicG ?

In the backrooms.

He entered university this year

![ ]()

Alt + 128514

Lol so true!!

Next Saturday (23 Sept) is my

Algorithmsexam xDThis contest is gonna be fun!

When it gonna be exactly

all the best !

First unrated contest for me !!

38th rated contest for me :/

What are my chances? 0-don't even try 1-maybe you will solve just one 2-averege 3-i belive in you 4-all the way to the top

Its div4, i think you have great chances, idk you, but at least 2

Good Luck! Ill pick 3 cause i believe in you

Thanks. Good luck to you too!

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

Thanks for this round

I will be happy to participate in this round

Best Wishes

My First Unrated Round

Congratulations it's a great feeling:)

Same lol, sad it had to be one of my best performing rounds yet.

how long will the contest last after the start time?

2 hours and 30 minutesSpecialist here I come!!!

Hopefully my last rated div4 :O

good luck

first time participating in an unrated div 4 round!!! TT

Wishing for another enjoyable Div.4 round!:)Hope to get +300 this round

Div. 4 >>>>> all rounds

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

I only want 70 points:)

flamestorm > MikeMirzayanov :)

Genshin，Startup！

is it rated?

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.bro I was joking

Wuwu,i want rating TTTT ,thankuu

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

Going to participate in the contest after 2 years long break.

Hope, This will be a good one

My second round on this website and the first rated. In the first one I solved 2 tasks in the first hour and then 0 in the next four hours... I hope this one will go better.

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

Div 4 without SlavicG .....

I don't like ICPC...But this is the only chance making my rating higher

average div4 round

Very Excited!! I have solved 5 of them so far!

P.S. I am a newbie

me too i have solved 5 questions so far

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

This contest was quite nice... Can't wait for the next :) Codeforces Round 898 (Div. 4)

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

WTF IS WRONG WITH PROBLEM F?

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

Nice round.

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

same, was top 20 once, now 800th

bro how did you got the algorithm for D. I am not able to do it.I did first 3 and C been pretty average to me like its algo is repetitive.

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.

hey how did you do D.

you can use this trick:

always write your code as

here 2 thing to consider. 1st: lets say you want to binary search on a to b.condition is true for a but not for b i.e TTTTT...FFFFF then answer will be r. and for FFFF...TTTT answer is l. 2nd: in the "if condition" will there be < or <=. It will depend on problem like lets say we want largest number <=x in that case we cant take equality. otherwise in the base case l will exceed x. same logic can be used if we need number >x

}

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.

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.

Thanks to all of you!

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

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

}

i did exactly same but don't know why it's not working

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

Thanks, your reply did a lot of help for me!

How to solve G?

please explain F

You can use two pointers method.

My submission

You can solve this by using sliding window or two pointers approach.

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

A and B were pretty easy. C is just slightly above average and the code is repetitive. and I didn't able to 4th one. I got some math but it is throwing me an error in the first case itself but it solved almost 7 cases in it. Can anyone help me how to do it.

Create a array that will contain only the index of every

B.Now, iterate over the array using two pointers. If difference between two points exceed

(consecutive cells) simply add one to the answer and move your starting pointer.kPlease explain F

Basically you will have to determine the maximum length of subarray of array

such that sum of every element in that subarray does not exceeda.kHowever the the catch is, the subarray you are creating from

, those indices must also form a valid subarray ofa. And subarrays ofhis constructed following the condition:h`hi is divisible by h(i+1)`

.So, for the following test case,

subarrays of

are:h`4 4 2`

and`4 1`

. Notice that every element is divisible by the next element.One optimal subarray of

will bea`3 2 4`

since sum 9 is less than 12. And the length will be the answer.`2 4 1`

is also a subarray that has a sum lower than 12. But it does not overlap in any subarray of. Therefore this subarray is not optimal.hThank you .i also tried to implement the sliding window solution but i overcomplicated the idea or messed with the approach. This was my code and it always for 2nd testcase.

great contest!

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 ?

use long long ($$$1 \leq a_i \leq 10^9$$$) 224508834

Thanks

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

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.

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

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.

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'.

Thanks, clear now.

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.

You are right!

Yes, I solved H using this idea

WHY ARE YOU SCREAMING ????

They're excited about the cake! (I would be too.)

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

Thank you for this great contest! I'm so happy that I solved 3 problems in 30 minutes

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!

how did you fix the high bound?, I tried a lot of things still couldn't do it

The key here is just to make sure it won't be overflow between

`long long`

and`int`

.In your submission with

`end=2e14`

then`mid`

will be`1e14`

, in function`isPossible`

variable`w`

may become`2e19`

(overflow for`long long`

) because`n`

can be max`2e5`

.thanks a lot!

When calculating the sum, if we exit the loop just after it exceeds

`x`

, then, we don't have to worry about the high bound.(In your case it is in method

`check`

, for the variable`cnt`

. If we add`if (cnt > x) return false;`

, it would have probably worked, even with the maximum long value as the high bound.)Nice tip, thank you!

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

Please explain some one...

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

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

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

I just ignored the note,, actually by reading the statement i was oversure that l must less than r.

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

I read it,,but not satisfied

I think C and D should be swapped. C was harder question.I did not observe C, somehow I escaped with some implementation but costed me so much time.

One of the best and most Balanced Div 4 i saw there was so happy to take part in it

Can someone help me find issue in F? I am not finding any case where it is failing. TIA https://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.

Yess Exactly, I asked them in the chat while contest about subarray of size 1 and they gave me below reply -

SpoilerNo comments

Please read the blog https://codeforces.com/blog/entry/120638.

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 did same and got 5 WAs. This will result in integer overflow.

If we break the loop just after it exceeds

`x`

, then, it works even if we set the higher bound to the maximum`long`

value.@f20190909 Your submission 224516751 with additional check

`if (w > x) return false;`

worked here 224521160.@Itadori_yuji_007 Your submission 224509345 with additional check

`if (W < 0LL) return false;`

worked here 224521345.Thanks bro, This should have popped up in my mind.

thanks a lot!

I wonder why I have rank 6900 with 5 problems while there are people with 4 problems and rank 6000 or even higher. Should It be the one with more problems has higher rank and only if there is a tie the time penalty plays a role?

Please explain, this Is weird

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

W Kendrick Lamar Problem Setters

Nice contest! I really enjoy it

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

Can someone please explain what is wrong with my approach for problem F void solve() { ll n, k; cin >> n >> k;

}

Please try to hack this Problem F

done

Test case?

Why cf tracker, carrot etc etc chrome extension is not working after div 4??

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

Hey , it was my first contest on codeforces , I am trying to understand which contest is rated and unrated , as the paragraph suggests that the contest was rated for everyone who was having a ranking less than 1400 but in my profile it shows under the contests section that it was an unrated one ? what am i missing out? is there any rule that first 5 contests would be unrated aur so?

Codeforces contests can be rated or unrated, but it's not based on your rating or the number of contests you've participated in. Check the official contest details for the specific contest's rating status. There's no rule that the first 5 contests are unrated, each contest is individually rated or unrated by the organizers.

Ohh... in this post it is written that "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" that why i am like confused i remember that in the contest details it was written that the contest is a rated one , do the rankings come after a day or wot?

Yea it takes few hours to get updated

Fine!!! Thanks for the clarification

In queueueueueueueueueueueue!!!

Problem E and F are really amazing problems

Oh I missed the Div.4 again:(

Hello All,

I am new to this platform. I recently participated in Codeforce round 898 div-4. But still ratings isn't updated yet. Open hacking phase is already completed.

Can anyone tell me what's the procedure or is this contest unrated ?

Can any one tell me about which time ratings of this round will come (Codeforces Round 898 Div 4)

My first cf contest!!! For a freshman.

I solved Problem B when the contest was running! and it was accepted. But now it's showing time limit is exceeded. Why?

This may go into infinite loop!Kendrick Round

YAY! I'M CYAN

## The most painful thing is when you solve around 6 problems on Codeforces,

gaining, let's say, +100, and then the last problem gets removed after the testing phase.

## It really hurts:(

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

it may be only a coincidence.

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.

very nice binary search problem

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 was doing questions in random order. I had written a rough pseudocode on ideon.com of 1863D problem latest Codeforces Round 898 (Div. 4) for writing code later and unfortunately it was in public mode. I don't know man someone took my idea and submitted the solution before me by translating the pseudocode into actual code. Apologies for this unintentional action. I will make sure this won't happen again.

Thanks

hey i have got an mail telling that my solution 221323129 coincided with other people .but i dont have any solution with that code. how do i even check it?

Astagfirullah, Your submission page looks terrible. This cannot be coincidence!

what does that even mean bro ??

Hi can anyone give me edge case for problem H been confused for a long time whats the issue with my code . Thanks in advance !!

Submission = 224828768

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

Bro, how do you code in 6 different languages : python, c#, ruby, java, go, c++.. Thats just insane ! :o

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

I want to clarify that the similarity between my solution (224380982) for problem 1873C and the solution by Anonymous_P (224476541) was purely coincidental and occurred due to the unintentional public access of my code on onecompiler.com (which I had no idea about). My submission, under the username redder02, was made at 20:37, while Anonymous_P's submission was at 22:07, clearly indicating that my code was posted well before theirs. I take the rules seriously and request you to consider this timeframe in your evaluation.

Okay so got a message from system that my solution got coincided with the solution of some other person whom I do not know at all My solution: https://codeforces.com/contest/1873/submission/224426160

The other one: https://codeforces.com/contest/1873/submission/224487303

The only thing seems similar in the codes is the logic that is checking the conditions updating the variable neither do I use any platform where my solution can get leaked nor do I know the other person. It was just a pure coincidence since the solution was simple. Kindly review it.