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
didn't know there are people living in tajikistan
didn't know Indian people can write.....
Ouch! I know Tajikistan is shit but can't express in cool edgy way.
P.S : I am not Racist.
My first unrating contest :)
Mine too
me 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...
Where is SlavicG ?
In the backrooms.
He entered university this year
![ ]()
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
Congratulations it's a great feeling:)
Specialist here I come!!!
Hopefully my last rated div4 :O
Finally First unrated contest
: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?
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
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?
I see nothing wrong with F. Time wise, it took me much longer to solve G.
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. 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.
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.
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);
}
(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:
please explain F
You can use two pointers method.
My submission
Duuuudeeee if I had like 1 minute, I would've solved the last problem yikes
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
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'.
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 =|
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...
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
Please red the blog https://codeforces.net/blog/entry/120638.
Can someone help me find issue in F? I am not finding any case where it is failing. TIA https://codeforces.net/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 -
No comments
Please read the blog https://codeforces.net/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 maximumlong
value.@f20190909 Your submission 224516751 with additional check
if (w > x) return false;
worked here 224521160.@LaughingBuddha Your submission 224509345 with additional check
if (W < 0LL) return false;
worked here 224521345.Thanks bro, This should have popped up in my mind.
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
done
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
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.
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 :/
Bro was trying to avoid plagiasm check, but got caught anyways :)
well in the third problem "Target Practice" the output is wrong.
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.