Hello, Codeforces!
We are glad to invite you to participate in Codeforces Round 949 (Div. 2), which will start on May/31/2024 13:05 (Moscow time). Note the unusual start time of the round. You will be given 6 problems and 2 hours to solve them.
This round will be rated for participants whose rating is below 2100. Participants with higher rating can participate unofficially.
The problems were authored and prepared by sinsop90, yinhee and me.
I would like to thank:
- 244mhq for his wonderful coordination.
- sinsop90 and yinhee for providing problem ideas and discussing the problems with me.
- AFewSuns and crazy_sea for providing a better solution to one of the problems.
- Um_nik for the only LGM testing.
- A_G, antontrygubO_o, StarSilk, CharlieV, rui_er and Andreasyan for red testing.
- FengLing, YuJiahe, CSQ31, small_peter and JWRuixi for orange testing.
- yinhee, QwQwf, lovely-ckj, wsc2008qwq and Jryno1 for purple testing.
- sinsop90, dieselhuang, Edwin__VanCleef, wtc, WRuperD, starrykiller and gdf_yhm for blue testing.
- Ender32k and liangbowen for cyan testing.
- ishaandas1 for the only green testing.
- cyz2010 and cppcppcpp3 for grey testing.
- MikeMirzayanov for the great Codeforces and Polygon platforms.
- Last but not the least,
You
, for participating!
Scoring distribution: $$$500 - 1000 - 1500 - 2000 - 2500 - 3500$$$.
Good luck & Have fun!
UPD: Congratulations to the winners!
Div 2:
Div. 1 + Div. 2:
Editorial and also Simplified Chinese Editorial are out.
As a tester, there are some beautiful ideas in the tasks, and I encourage everyone to participate!
can you tell me how people are selected for testing ?
for this contest, most of the testers are the authors' classmates or friends, and some of the others are well-known competitors in China as well.
Is there any specific reason for the unusual starting time?
Usually the reason is either that the contest is based on an olympiad or some other contest, so to avoid leaking problems the codeforces contest is set in an unusual time. The other reason is simply that this is the best time that fits the authors due to time zone difference or other reasons
Yes, thanks for your understanding. Actually there is a conflict between this round and ours studying plan (we are from the same school). At the same time zltzlt and I are preparing for the Zhongkao, one of the most important exams in our life, so hope participants can understand us.
Good luck on your exams!
I've heard that Zhongkao is very prestigious, just as Gaokao is. I wish you the best of luck, and I hope that you perform really well.
Good luck & high mark in Zhongkao!
Good luck for you too!
To my knowledge, both of you are good enough in competition and can be Baosong(enter without exam) to a very good high school. You don't need to do Zhongkao.
Actually due to the policy, we are still required to get at least 680/810 in the exam, and the school ask as to get a score of 730+. It's not that easy, is it?
Can we stop saying "Zhongkao" and actually speak some English? This is really a bit embarrasing /qd
Zhongkao is shorter than 'ahrghaghrah entrance exam' and everyone knows what it means so it's not an issue
Thanks!
OKay. Thanks a lot for quenching my Curiosity.
How exactly would an unusual round time prevent leaking problems?
That's for mirror rounds, rounds that replicate an actual on-site contest.
As far as I know, it is because Guangdong provincial team training. The author of this round is a member of Guangdong provincial team.
Okay Thanks a lot for replying. May I ask, How long does the training lasts and how do Chinese coders train?
Sorry, I don't know cause i'm not in Guangdong.
Two weeks.
It will be my first contest in Codeforces, and I am looking forward to it!
As a first-time tester and one of the writers, I'm certain that you will have a good experience in this round and learn a lot. Just enjoy yourself:)
As a tester, hope you can enjoy the problems and get a positive rating $$$\Delta$$$!
Meanwhile, good luck to the authors who are about to attend an important examination -- Zhongkao!
As a tester, I like the problem set and hope you enjoy it too!
Still waiting for the Educational Round blog
Codeforces Round 949! One step closer to the milestone Round 950! <3
please change the time of the contest it is in the time of the pray in Egypt and we want to participate
Please delegate it one more hour, Many muslim guys in the middle east won't be able to join because of the prayer of jumaa.
HOPE IN THIS ROUND I'D REACH MY GOAL BEFORE SUMMER BEGUN
GL FOR EVERY PERSON,WHO READING THIS COMMENT
As a Chinese CPer, I'm happy with the start time.
Don't you have any class?
We leave school at 5:30 p.m.
As a tester, I would like to say that the problems are wonderful!
As a tester, I'm zltzlt fan.
As a writer, I'm wsc2008qwq fan.
looking forward to give this round as a cyan :)
As a writer, I am a fan of zltzlt.
As a tester, I am a fan of zltzlt. Good luck in Zhongkao!
Hope the competition topic is more interesting！
Usually the reason is either that the contest is based on an olympiad or some other contest, so to avoid leaking problems the codeforces contest is set in an unusual time. The other reason is simply that this is the best time that fits the authors due to time zone difference or other reasons
As a tester, I think this round will be educational and fun.
I think all the problems are great.
OMG Finally 18:05 round
will be good contest
It would be great if you can delay it by 1 hour, as many middle east contestants will miss it due to a weekly prayer at that time.
Arithmetic Progression in scoring distribution!!!
No because $$$3500-2500\ne2500-2000$$$ :)
Ohhoo, I missed the last one. But, suiitable for the first five. Thank you.
Giving the round to compensate the loss in educational
Fun fact: the setter has solved 4000+ problems on codeforces and 10k+ problems on a Chinese online judge(which provide the remote judge service of codeforces and atcoder). I'm so shocked by his hard work.
I'm curious, how long did he take for the 10k milestone locally? Heck, this is making my 2.5k in ~2 years fall obsolete by a long shot, such a dedication.
Auto comment: topic has been updated by zltzlt (previous revision, new revision, compare).
If I don't solve A B and C then it's gg
Update: I couldn't even do B its over for me
As a PST kid, I somehow managed to wake up for it :)
Wish positive delta in this round!
Will queue issues appear in contest because of EDU 166 system testing?
Will there be delays due to an overlap with yesterday's Educational round's System Testing?
Wish ABC！
orz zltzlt
Tough contest.
This didn't seem like a Div. 2.
It was more like Div. 1.5
Any smart solution for C? Feels like another boring implementation task that I can't care less debugging. Took a huge L today.
263463935
Can you please explain your intuition and solution ?
If there are no set values, just do 1 2 repeated.
If there is some value set then the prefix can be obtained from the first value by halfing. If you get to 1 you double because you cannot half. The suffix is similar.
Now to complete middle parts. Say we are bounded by $$$a$$$ and $$$b$$$. If $$$a > b$$$ then we must half $$$a$$$ in order to get closer to $$$b$$$. If we don't then $$$a$$$ was half of its right neighbour, but that only increases the distance to $$$b$$$ and we still will have to half at some point. We reduced the problem to a smaller instance (from $$$\frac a 2$$$ to $$$b$$$ and one less element). Similarly you can do the same if $$$b > a$$$. There is one issue, if both $$$a$$$ and $$$b$$$ are 1, then this does not work but you can just insert a 2 instead.
In the end you want to check the original problem constraints (you did not get an invalid array). This can be computed as you complete the array.
Mathforces
What the fuck of the C???????????
I used more than an hour to write the code(182 lines) for C,but still didn't AC
isn't that simply find n sequence {a1,a2,...,an} start from x to y where a0 = x, a_{n+1} = y, a[i] = a[i + 1] / 2 or a[i] = a[i — 1] / 2?
yeah, very easy to get the idea, but it just brabra casework and very hard to debug.
not needed that much of case handling. assume the array has this form: [-1, -1, ..., x, -1, -1, -1, ..., y, -1, -1, ...]
The prefix and suffix are kinda the same, start by doing x/2 until you reach 1 then do 2 1 2 1 2 1, In the middle part, start x/2 and y/2 from left and right, divide the bigger one in half each time, once you reach the other side just double check the OKity
I literally missed a case in C and threw like 30 minutes finding the cause of the WA, leaving 5 minutes for D which I figured out a few minutes after the round ended ._.
I feel like I code a large number of droppings :(
How to do prob B ?????
Go through the bits of n, let's say you're at bit x, if the bit is a 0 then check if m >= 2^x — (the number represented by the binary expression before bit x) or if x is not greater than the most significant bit of n then you can also check if m >= (the number represented by the binary expression before bit x).
263459449
As the operation spreads for every second, at time $$$t=m$$$, the value at $$$a_i$$$ will be $$$a_i = a_{i-m}|a_{i-m+1}|...|a_{i+m}$$$.
The above is exactly the bit-wise OR in the range $$$[max(0,n-m), n+m)]$$$.
loved problem B.
Can you explain how you did?
yeah, just notice by writing the operation a couple of times let say 20 and 3 are values of n and m then in the first operation value will be
(19|20|21)and in the second operation the value will be(18|19|20)|(19|20|21)|(20|21|22)--> which is nothing but or of[18,22], so if u write more such iteration u can conclude that the answer isOR of range(max(0,n-m),n+m).I reached uptil this that answer will be bitwise OR from range(max(0,n-m),n+m) but was not able to implement it, was this an easy implementation? because if it was an easy one i would work on my bitwise section
Or am i missing something? does just doing output OR of range(max(0,n-m),n+m) will not give the answer
It will give the correct answer, but not always in the time limit. To actually solve this problem you need to consider every bit individually and try to greedily find a number that has this bit set and lies in the range [max(0,n-m),n+m].
You can check out my submission. I also did the same observation as shviv1.
Here is my submission
Pure math + wrong difficulty estimation from coordinators. Typical Codeforces.
the authors cooked
C is not a C. D is not a D.
I think CDEF should be DEFG, and insert an easier C.
I hate it when a math problem (problem D) appears in my interesting interval
(the problem is nothing wrong tho, just I'm too skill issued)
Problem B seemed tougher as compared to normal div2B problem ...
Tough contest. We weren't given enough time.
What is wrong in this? 263494295. If someone can provide a testcase, it would be very helpful.
Brother, only the time was not unusual; To me, problem 'B' was also unusual, aaand the whole contest was unusual too!!!
my method for C
assume L is somewhere a[i]!=-1 ,R is next one that a[i]!=-1
then when a[L]>a[R] we can make a[L+1]=a[L]/2
when a[L]<=a[R] we can make a[R-1]=a[R]/2
if a[L]==a[R]==1 we can make a[L+1]=2
my english is so bad so dont critisize me
this is my code and i know it is ugly
https://mirror.codeforces.com/contest/1981/submission/263485331
Stucked on C for $$$45$$$ minutes and finally got 1 place lower than sevlll777, who solved 1 problem less than me. The slowest episode ever.
agony
Who can give me C's solution?
I did it for 1h30mins,but i have no ideas.
You can do 3 ops when moving from $$$i$$$ to $$$i+1$$$, namely divide by 2 (and floor), or multiply by 2, or multiply by 2 and add 1. It is easy to see that in enough steps, any number can be achieved with these operations. You compute the minimum operations, and if the distance is less than that, or the distance minus the minimum operations is odd, then it's impossible. The implementation is a bit tricky though...
Thanks for you comment. in the competition,i thought of this trick but i dont know how to calc the minnium distance lol.
Can anyone please help me find error in my solution for problem B ? It's failing on pretest 7. https://mirror.codeforces.com/contest/1981/submission/263482380
Nevermind I got my mistake.
I'm officially having skill issue with constructive problems (again) :D
same
Same
how to F
a B-like A a C-like B a D-like C and a C-like D Bruh...
BitForces (
I actually enjoyed solving problem C a lot. but aren't the rounds a little too hard? there was literally only one full solve which came from a person probably above div.2 level. still, cool problems
britishcat now an expert!
Orz
It wasn't fun at all
I couldn't agree more with this comment.
Will the rating changes of this round be calculated on the ratings before the EDU or on the updated ratings of the EDU?
Adhoc dominates codeforces nowadays a lot.
Can someone tell me how to solve A? I know it must be easy, but I couldn't come up with a solution.
p=2 works and hence, the largest power of 2 <= r is the answer
Oops! That was easy! I somehow made it in my mind to be much more complicated. Thank you!
Abnormal contest with CNOI-style problems.
Problem C did give me a lesson...
In contest i tried second question for 1 hour and 54 minutes still not able to solve it :(
not only not enough time but the problems were harder than usual div 2 problems
I love the $$$O(\frac{n^2}{\ln n})$$$ solution of problem F, however I spent my whole time in $$$O(n\log n)$$$ overcomplicated segment tree merging solution and mixed indices like tr[x<<1](should be tr[tr[x].ls]) then finally finished 10 minutes after the contest...
edit: I got the first blood!! so funny XD
can you elaborate the idea?
Basically we have $$$x\not\in A\Rightarrow\text{mex}(A)\le x$$$. Then we can apply DP: $$$f_{x,y}$$$ is the minimum cost in subtree $$$x$$$ such that $$$y$$$ doesn't appear in the top path, then segtree merging.
I had similar thought, but wouldn't it be N^2 though
you can check the different between my two submissions. In the first RE one I use array $$$g$$$ to maintain, and it was replaced by segment tree in the second one.
I think it will be more balanced to insert a *1500 problem between B and C.
Difficulty prediction (luogu): Orange Yellow Green Blue Blue (Black)
Difficulty prediction (Codeforces): 900 1400 1700 2200 2400 (3200)
After the Educational round I thought, "I am going to get a healthy positive delta". The rating is not updated yet. But after this unusual 949 round I am scared of being Pupil again!!!
Wait. maspy FSTed on problem F???
A 0-solve D2F??
yes bro
got RE on test case 2 of problem c and got accepted after contest. if just had 1 minute more whould get ac
worst feeling ever
a very nice D!! Thanks for the contest.
how can calculate rate and educational rate not calculated yet??
But I really didn't have fun ...
I think it is too hard for a Div.2 contest.
Day_Tao is so bright,/bx Day_Tao.
Hi, can someone tell me where my submission for B is going wrong?
https://mirror.codeforces.com/contest/1981/submission/263488201
I converted the decimal numbers (n-1) and (n+m) to binary, and then traversed (from MSB to LSB) and compared their bits. Where ever they differ, that means from that bit onwards all the bits will be 1
The left should be $$$l=max(n-m,0)$$$, not $$$n-1$$$. Also, Bitwise operations in C
Am I the only one who felt A is tough than usual div 2 rounds
wdym it's literally
int l, r; cin >> l >> r; cout << (int)log2(r) << endl;I got that idea after some time but initially I some how thought that we have to calculate the x in between l and r with maximum factors.I have to carefully read the question next time
small code does not generally mean the problem is easy.
Het can you tell me why this method leads to wrong answer sometimes as i got in this question Atcoder Question
This code resulted in AC
Also, here is AtCoder Test Cases (Dropbox Link). You can check them if you try a problem for a significant amount of time and still can't figure out your mistake :)
Damn I didn't know they provide Tc's to
CornerCaseForces
BitForces
Carrot is not working :( Any other working performance calculator extensions?
Sometimes Codeforces close the API during contests due to the heavy load, it doesn't work because it can't get the data to 'predict',
give it some time and it'll be working fine.
It might be Cloudflare's protection mechanic instead of Codeforces'. I can see an error message containing 403 and
!DOCTYPE htmlfollowed by someare you a humanwebpage contentChineseforces
It might be better to swap the D and E.
very correct
I think C>D=E(((
I hope someday I will be congratulated like this.
There are 10 types of people: 1. Those who like bit manipulation. 2. Those who don’t like it.
bro that's 2 not 10 man
Clearly, you are the second type of person.
deep within, most of us belong to type 2 only
10 in binary is indeed 2
Can anyone explain the approach of C
We can make the problem simpler ...
=> Given a and b in 'a -1 -1 -1 ...(k times) b', is it possible to fill the -1s with numbers >=1 and <=1e8 such that adjacent elements follow either A[i+1] = A[i]/2 or A[i] = A[i+1]/2 ?
Let's approach to solve it from both ends (now, from the left). Say A[i] = a and A[j] = b, so A[i+1] can be a/2 on division side (call it OP1) or 2a or 2a+1 on multiplication side (call it OP2). So we store the number of such operations in respective maps for both OP1 and OP2 till j-i number of operations.
Similarly, from the right-hand side. Since the hops between a and b are j-i for any common number x on map_OP1 or map_OP2, we have (say) t = map_OP1_left[x] + map_OP1_right[x] as the total number of hops. If (j-i) and t have different parity, it is not possible for such x to be a convergence point (obvious), so if they have the same parity and t > (j-i), one could just make x from a and b and fill between even hops by *2 and /2 alternatively. You can fill '-1 -1 -1 ... a' and 'b ... -1 -1 -1' ones similarly.
That's the approach and here's my submission 263482841.
When will the ratings get updated any idea ??
yeah, its pretty late
Author cooked
a contest where no one completes all the questions But it is useful
Can anyone please explain why my following approach for the problem B fails:
I observed each bit individually and checked for two possibilities:
I tried to find the greatest number smaller than 'n' whose ith bit is set. If it exists, check if the difference between this number and 'n' is less than or equal to 'm'. If this difference is less than or equal to 'm', the ith bit in the answer would be set.
In the second case, I tried to find the smallest number greater than 'n' whose ith bit is set, and then check if the difference between this number and 'n' is less than or equal to 'm'. If this difference is less than or equal to 'm', the ith bit in the answer would be set.
Here is my submission: https://mirror.codeforces.com/contest/1981/submission/263527422
I cant tell what but you were trying to do something like this 263477911
Your approach is 100% correct, and this is my AC submission which is the same tbh 263460829
Finding the smallest number greater than 'n' whose ith bit is set is easier. But can you please explain the approach to find the greatest number smaller than 'n' whose ith bit is set, because the number may or may not exist?
So we traverse from i+1th bit towards MSB, and the moment we find a 1, say at bit j, unset bit j and set all bits from j-1 till 0, call this number x. That is the closest number on its left with the ith bit set, and this is the nearest because as you increase from x, you won't get the ith bit set in any number till n.
Got the error in my code. orz
I was setting the bits from (i-1) to 0 instead of (j-1) to 0, where j is the first bit set while moving towards MSB from (i+1).
Nice idea,I never thought that instead I used pattern of bits at specific position
As a participant, this was a really fun math contest!
Basic idea of D was almost exactly same as https://mirror.codeforces.com/problemset/problem/367/C just had to account for self loops and print the path
Sorry but I didn't notice the problem before.
It was a nice problem anyways I remembered the problem because it was first time I used things taught in my discrete math class(complete graphs, eulerian path ) ,that too in a problem which seemed unrelated to graphs and you took it a step further by making it feel like a number theory problem
666
Why unrated participant came first, shouldn't untrusted participants not be allowed
after solving a problem of this contest i used to be able to add tags and remove them but now it says no tag edit access is it because i dropped 8 points below CM or its the contest ?
Hey! Check out my video solutions for the contest. I've covered Problem A-C from contest here.
Love D, but too simple for div2 round
Can any one tell me why my code is so slow? Submission: https://mirror.codeforces.com/contest/1981/submission/263742703
A probably high rated programmer type7shady, probably CM level has been livestreaming and leaking answers online, solutions upto C were leaked.
Here is the livestream for this round: https://www.youtube.com/watch?v=Px7R7j0uOtQ
Drive Link where all code is uploaded: https://drive.google.com/drive/folders/1T4jvLvOJwWq6R23xJjENJb4AgOHJjPmC
This person also leaked ABCD in the last edu contest, good enough to place cheaters at the high expert — early CM level. zltzlt and MikeMirzayanov please look into this.
Hi newbie isJaipal, I think you are new to Codeforces . The main crux of code i.e the logical part can be same for a numerous of people, implementation is what makes your code original, this includes of data structures you used and in what way you used that, of course algorithm may be same for many. Don't worry, You will learn it with time and practice. Also, the past plag I got in this account is because I used to use GPT for implementation in early days when I started cf, who used to give similar implementation to multiple users , but later , I stopped using that too and practiced a lot on my own to improve implementation ability.
Thanks for the concern tho, I am myself very much against cheating even in academics like college exams or any online competitions , I hope this answers your query, All the best
so how were you able to think and wrote these long codes in just 5-10 min , are you a grandmaster or some ? And that too very similar to ones available on telegram
I did not write them in 5-10 mins, I was trying E,F after B but I could not debug F1 first, so did C,D then did debugging for F1.That is why, there is a time gap between B and C. Also, you can use copilot in vs code for faster typing, which even many CMs use.
Nope you definitely cheated. Look at last contest’s E for example. You and a lot of other cheaters have nearly identical code. For example, you don’t meed to separately consider the case for n==m, but all cheaters have done so. Similarly, no need to find the transpose,you can just iterate rowwise and columnwise. Codes cannot coincide almost line by line for such implementation heavy problems.
Dont deny it, otherwise I will look into all of your submissions and prove that you cheated line by line, which will be more embarrassing for you.
This wouldn't be deemed cheating since problem E was previously featured on GeeksforGeeks as an article, and contestants are permitted to utilize pre-existing online resources. Consequently, it's not uncommon for multiple individuals to have similar code for problem E due to this allowance.
Hope, This round will be enjoyable.
for problem D, in the examples, i think for the last test case, p=5 is possibly a correct solution but the online judge says its wrong
bad problem C