Hey there Codeforces!
flamestorm and I are glad to invite you to our first-ever Codeforces round, Codeforces Round 742 (Div. 2), which will be held on Sep/05/2021 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.
Special shoutouts to:
adedalic, for his fantastic coordination and translation of the round!
MikeMirzayanov, for creating the amazing Codeforces and Polygon platforms!
dorijanlendvaj, awoo, YouKn0wWho, PurpleCrayon, phattd, ijxjdjd, stefdasca, tenth, Aaeria, Eyed, kalki411, Shinchan01, BRCode, namanbansal013, Urvuk3, mudkip, richy6, and tdpencil for testing the round, catching any mistakes and providing lots of valuable feedback! We tried to get a large range of testers with different coding experiences so that everybody enjoys the round.
stefdasca once again, for creating video editorials which will be available after the contest!
saarang, not because he contributed anything to the round, but because he would annoy me for months if I didn't mention him here.
And you, the user, for
upvoting this blog and giving me contributionparticipating in this contest!
You will have 2 hours to work on (and solve!) 6 problems. At most one of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round! You are highly encouraged to read all the problems ;).
UPD: The score distribution is 500 — 1000 — 1500 — 1750 — 2250 — 2750.
Good luck, and see you on the scoreboard!
UPD: Editorial is out!
UPD: Congrats to the winners!
Div. 2 (the only 5 contestants to solve the whole set!):
Div. 1 + 2:
We hope you enjoyed the round. See you soon!
As a tester, I like the tags of this announcement just like the problems.
He is asking for upvotes here
And you for downvotes.
How did you know that ?
And he deserves it
^-^
Can you like...shut the fuck up? Your comments are trash and you're just spamming. You're not even related to the contest, and yet your comments make up more than 10% of the comment section. Stop trying so hard to get contribution, you don't deserve it.
Ok
everybody can write as many comments as he wants
Stop spamming pls
You must be fun at parties.
aha
Really excited for this one!
not because he contributed anything to the round, but because he would annoy me for months if I didn't mention him here
Lol
Join saarang's official fan club here: https://codeforces.net/ratings/organization/29233
saarang orz
saarang orz
saarang orz
who is saarang
Some unknown user who got viral
if they are unknown, then why do they have a fan club?
surang fan club rise up !
ScarletS you had one job!
omk
flamestorm orz ScarletS orz saarang orz
As a tester, did you know that if you don't upvote an 'as a tester' comment you will get negative delta? I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Last time I trusted a word of tester, I ended up with -70 :(
He never said that upvoting 'as a tester' comment will get you positive delta :(
Black magic is only option left for me to become CM :\
As a tester, I agree with you :)
Me having to get up at 12:35 am (midnight) till 2:35 am because of bad time zone differences.
Try to change your want ,if that works .
Edit: Lol ,he edited his comment so that my comment doesn't make any sense ,and ironically i edited my comment to bring back the sense
Excuse me well I am a she and your comment is a bit rude. I am from Australia so please try to be in my shoes.
...
She never wanted anyone to do anything about it.
So many downvotes ,that's why i generally shitpost with fake ids
I didn't say you shouldn't have written a comment, actually nobody can say that. Just try to respect others.
.
Must be tough giving contests while being upside down :D
I know that this will be a high quality round.
upvoting this blog and giving me contributionAuthors and testers always asking for contribution, reminds me of mr ditkovich from spiderman 2 who always used to ask for rent. https://youtu.be/usIJYbv_gXwUnban from server
What's your server ScarletS?
It's more like saarang's fan club
Man, are you like banned in everywhere ((
sounds like rotavirus but indian
If rotavirus ever gets unbanned, he gonna open his account with 78459043758349025798034334053 pings
But rotavirus is a good person.
rotavirus contests used to be awesome
Will somebody please tell me who was rotavirus and why she/he was banned!?
He was someone very known in the CF community. He got banned for racism.
She*
By the way, who is saarang? @saarang
Pupil missed the large range of testers. Sad life :(
time to upsolve this
As a participant, I hope this would be a great contest with 6/6 wonderful problems
My contribution is dropping!!!! https://www.youtube.com/watch?v=L0Z3XyVKmZw&list=RDMML0Z3XyVKmZw&start_radio=1
We all deserve low contribution because of the importance of
high rating ...
Don't you see that high-rated people have higher contribution? When your rating is high enough,people will start to give you likes. So dude,don't care about contribution. Care about how to get high rating.
I can't agree with you more , I'm trying to improve my programming ability , and this link is my best friend's music , i want to make it more visible but I post it in last contest's blog and get 50 downvote...
Dude, why are you posting music in a contest blog? No doubt you will get many downvotes. You should post it in your own blog.
Of course because I want to get more viewed
So that is why you get low contribution! You post the wrong thing at the wrong place at the wrong time.
It's actually pretty good ngl, but don't advertise non CP/non programming related stuff on CF pls. Hope your friend becomes the next mozzart ig?
OK I see , thank you!
Is my rating high enough to get high contribution? No
Good luck for everyone!
As a Newbie, I am gonna take ScarletS 's graph as a motivation
yeah sure ,i have a few graphs too for some extra motivation Kerim.K netman
Has there ever been a tester that criticized a contest(before the round)?
As a tester, I enjoyed being in the same team as ScarletS in hashcode this year!
He loves his team name
Indeed, I love to hate it :)
As their teammate, I confirm that BRCode and me enjoyed
naming the teambeing in the same team as ScarletS in hashcode this year!I will become Pupil after 3 days. This is so exhilarating...
Don't be so sure. Saying from experience
LOL! I show your rating graph. It's nearly the same as mine.
Exactly, At one moment you are expecting pupil the next moment you get -126.
`
Correction:
You may get WA.
It's so frustrating not knowing you have to apply brackets.
Though my compiler was giving warnings
I can't play on Sunday night, so have mercy on me. Only 6 points short.
As a participant, the day the contest starts is my 15th birthday, so I hope I could get a high ranking as my birthday present :)
I predict that you will drop in rating by atleast 50 points.
BTW Happy Birthday in advance! 😍 😘
Thanks :)
drop?)
Doesn't look like a typo :(
happy birthday！
I believe it's past midnight in China now, so happy birthday! I hope you enjoy our contest and get the present you wanted ;)
Thanks very much :)
Looks like a good birthday contest :P
Yeah :D
Ready to become newbie again
same
支持此比赛！
20 Social credits have been removed from your account! The CCP didn't ask for your opinion.
English: Support this competition!
I have a question. I am a Chinese middle school student. But I started school on Monday morning, and I couldn’t participate in the Sunday night game. Because of the time difference, it only started after ten o'clock in the evening, and I needed to sleep. But what should I do if I want to participate in the competition?
skip school day and participate
True
hhh just don't care about them
As the official video editorialist of the round, subscribe to my channel
I really hope to solve problem C, but it might be too difficult
You are specialist and can't solve c ??
that's okay, not every C is easy at his lvl
Yes, and it sometimes depends on the amount of problems. If there are at least 7, C is likely to be solvable. If there is 5, then it might be difficult
Yep
you are 600 with 300 problems solved???
I didn't make a new account like you
You are specialist and can't solve c ??Yes.
I am CM but I can't solve c and i can solve E!!So s**t round!!!
:)
Sir kindly once have a look at it. These idiots are downvoting my contribution. My only intention was to stop such things and make Codeforces a healthy place in whatever way I can.
I feel disheartened to see these things going around us and sharing with all of you what I came across recently. I was trying to solve this B problem and after devoting 1 hour approx I decided to log out my account as I didn't get it logic. I searched on the youtube the problem name just to check if anyone is not posting solutions during the contest like the way people post video solutions during codechef long challenges.
It did not used to happen earlier but recently it started happen and I came this issue several times but I just moved on then. This time I could not resist myself from not sharing this, that these kind of folks are trying to ruin the whole environment of the community by doing such cheap acts just to get views and subscribers.
Kindly take actions regarding the same. This needs to be stopped.
Sharing the blog link and the youtube channel link. Please do have a look. https://techtogether.live/codeforces-round-742-mexor-mixup-solution/ https://www.youtube.com/watch?v=XlHgagQjUIc
Bro just chill, these peeps would go nowhere, and more importantly these peeps would majorly effect greens and lower blues... So, work hard go way beyond their ability and you are rocking and moreover many blogs have already been posted and many people at top level know about this and would definitely do something... Till then, just scratch your brain and enjoy!
looking fwd to this chinese round .. will surely become rated this time :} Also i wanna congratulate all chinese people for their nation's outstanding performance in paralympics , love from north korea
How do you know that it is a Chinese round? From the author's profile it reads that he is from Ireland
And from the name, it looks like he is Indian.
All set to become newbie again. Here we go again.
I'm gonna do good in this contest.
There might be a game theory problem, guessed from the alice and bob tag :)
what the hack is MEX and link is no opening too
You can ask questions in contest page in the questions about problems.
BTW MEX is the smallest non negative integer not present in the array. FOr example if the array is {1,2,3} the MEX is 0. Where as when the array is {0,2,3,4} MEX is 1
Sorry about that, it's a bug on the platform. The link is https://en.wikipedia.org/wiki/Mex_(mathematics) .
digitforces
Great Problems. Specially Problem E.
Why is it so special to you?
Because, It was a proper DS problem.
so i had to lose around 400 points because i didn't know x^b==a and (x^b)==a aren't the same (-_-) if you know you know
Same mistake :/
Good contest! But I think that there is so many math problems, like B,C ans D :(
Now I have a chance to improve my math skills.
learned a lot about xor today
I know that I am dumb but daaaamn question C is tough.
nice contest, thank you ScarletS
I spent 45 mins cause curr_xor^b is different from ((curr_xor)^(b)) (-_-)
i dont get it....how is it different...can u please share any resources?
Its not different , its just that:
When you do (a^b == c) the compiler actually does a^ (b==c) because of the precedence of operators. so (a)^(b) == c is basically (a^b) == c which is the correct version
If I fail system tests I'm going to kill my self and it's your fault, I'm finally getting to CM !!!
I think the difficulty ranking is:
A<B<E<D<C<F.
So true
orz
Overwhelmed by sadness
Please speak English.
What's the solution for E?
Segment tree where for each node we store the total number of good subarrays, the lengths of the longest prefix that is good and the longest suffix that is good, and the first value and the last value of the interval
Came up with the solution for E after a glance but it seemed that my brain is "voidily" than any black holes in the whole universe for C and D.
Nice contest, finally a Div.2 B with normal difficulty.
Here are the today's video editorials
If my F passes, it will be my first time reaching Master :D
But I think my F solution can fail, it looks too simple. It is only bipartite matching.
I came up with the same idea when I saw problem F, but I don't know how to proof its correctness and I don't think the solution is right......
So why is it correct......it seems that the solution passed the system test.
During the contest, I tried to construct a counterexample to my approach by I could not. Probably I should have submitted my solution earlier.
The proof of correctness is explained in the editorial.
But my D failed systests, so I guess no Masters for me :/
How to solve problem C ?
note that if you build 2 numbers:
number from odd positions = x
number from even positions = y
then, those numbers are correctly computed during the process. so the answer will be: (x + 1) * (y + 1) — 2. (because those cases for each number are disjoint)
Let poss(x) = number of ordered pairs (a,b) such that 0 <= a,b <= 9 and a + b = x. You should with some casework or bruteforce. Also let dp[i][j][k] be the number of ways to fix the ith digit to the last digit with carry j for i-2 and carry k for i-1.
We can make the recurrence dp[i][j][k] = dp[i+1][k][0]*poss(s[i] + j*10) + dp[i+1][k][1]*poss(s[i] + j*10- 1), and with it, the answer will be dp[0][0][0]-2.
I applied bitmasks to calculate for which positions get a carry and which do not.
I think maybe problem E is too easy for a div2E.
Problem C is a good idea!
ScarletS I am sorry to say that, but the problems C and D are of very questionable quality, as for my taste. I even know some people (from post-contest discussions) who would ask you to stop creating problems (in a very cf-toxic manner). Instead, I want to ask you to keep going. I believe in you, and hope that your next contest will be better!
The only toxic things here are the problems.
Funny that you say that, because IMO C is one of the most genius easy problems I have seen in a while.
Same for D. Only some observation in D and an easy DP in C.
Well, there will always be some unhappy people. For example, I don't like digit-related problems in general, so my opinion is clearly biased. What I was saying is "don't take all comments personally, even if they come from div 1 users"
Can anyone tell me what's wrong with my code, problem C. I used brute force approach
You should take one test, output pairs you've found, compare them to given solution in problem statement and look into your logic — why they don't match. It's called debugging, this is part of problem solving you should get used to.
I think it was probably the worst round I've ever in.
swap(C,E)
I dont think so
Problem C is quite easy if you come with the key observation.
that's a big if
solved A,B under 30 mins and failed to implement C for 1 and a half an hour :(
Should've seen E first, spent 1 hour implementing D.
I solved $$$B$$$ in $$$19$$$ minutes, $$$C$$$ in $$$1$$$ hour and $$$13$$$ minutes, and $$$E$$$ in $$$16$$$ minutes. I'm still shocked :)
Where is the interactive problem?
The announcement says that at most one of the problems will be interactive :)
There will be at most five hundred interactive problems in every existing CF contest.
"At most 1" is actually really good clue to understand that there won't be many interactive problems.
They did say at most one
Test case 5 killed me in D :(
Why already system testing, but I still have B on "Pretests passed"?
Last 10 minutes brought 200 + Successful submissions on both D and E , amazing.
ready to be specialist again :(
Ready to be expert for the first time:))
When solving problem B, spent too much time thinking that $$$a$$$ was supposed to be the smallest non-present number in the array among those that are positive and got the whole contest derailed because of this. After a long debugging session wondered why [1, 10001] was not a correct answer for the a=2, b=10000 testcase and then checked the problem statement again.
Now I wonder what was the purpose of the a >= 1 constraint in the first place? The problem would be still solvable if $$$a$$$ was allowed to be 0. It's entirely my fault, but reading comprehension played a major role here and if this was the contest authors' intention, then they surely achieved their goal.
Missed an AC in E by 3 minutes , Sad life :(
Same here.
I enjoyed this contest.
Thank you for the nice problems.
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
@below oh i must have missed it when I read it thanks
Actually no. I think it's better to read Codeforces instructions to avoid downvotes
thx
I didn't like C and D, but F was pretty nice.
C: just another standard digit dp problem.
E: just another standard segment tree problem.
Downvoted.
AliceForces!
Bobforces too :)
Can someone check why my submission for problem D failed? I just did the carrying one by one starting from the rightmost digit of $$$s$$$.
One of the best problem sets in recent times. Thanks ScarletS and flamestorm for the contest! :)
I think I have wrote a wrong F but it passed !
Compare submission 127972613 with submission 127978516 , I think that I only change the left and right when a 'X' has 4 '.' neighbors .
I think I can be Up Hacked.
Problem C is beautiful. I love it.
A: U->D D->U L,R unchanged B: Preprocess the exclusive OR of 0~n-1 and judge with m
Please update problem ratings.
We don't have any control over that
Hi regarding Question C of this round (742) ,the test case number 3 where input of n is 8 ,the output is given as 7 whereas it should be 9 . What I mean is that to make 8 according to question we have following pairs : (`1 ,7),(7 ,1) ,(2 ,6),(6 ,2)(4 ,4),(5,3),(3 ,5) ,(8 ,0),(0,8).This adds to total of 9 .Can anyone tell if its right . Here is the question link : **https://codeforces.net/contest/1567/problems** Thank you for your time .
Notice that the statement asks for the number of ordered pairs of positive integers, so $$$(0,8)$$$ and $$$(8,0)$$$ don't count, as $$$0$$$ is not positive.