Hi, Codeforces!
mesanu, SlavicG and I are very excited to invite you to Codeforces Round 944 (Div. 4)! It starts on May/10/2024 17:35 (Moscow time).
<begin-copy-pasted-part>
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 behavior. 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.
<end-copy-pasted-part>
Thanks a lot to the testers: Dominater069, nika-skybytska, ScarletS, Gheal, BucketPotato, JustJie, htetgm, Vladosiya!
We suggest reading all of the problems and hope you will find them interesting. Good luck!
UPD: Editorial is out!









FINALLY! I CAN SAY IT TOO.
definitely great feeling
congratulations to you too!
Let's say it :)
Finally!!!!! Unrated for me too
lmao
yes
Aiming to reach specialist this contest!
hope my last rated div 4
Hoping for the best Div.4 Round!
it was worst
it wasn't
yes it was
but why, where's the reasoning? right now it looks like you're just disappointed that you solved only 2 problems
because it was so boring to solve the first 2 that I started to fall asleep
div4 a-c are always like that. interesting tasks start are e-h, but icpc rules force you to solve this easy tasks first
but i do get your poing
yesterday I solved C and D from that div.4 from first! But not in the contest :( >_<
that's cool!
This will be mine first unrated contest.
hoping i can get pupil rank after this contest (and flamestorm orz btw)
I wish all trusted participants good luck and to learn something new from this contest!
Aiming to reach Pupil after this
What happens if I register to a contest and didn't show
Close your eyes,what do you see?
tiny flashing lights
What I see when I close my eyes:
In Codeforces, it is considered that you've not participated. So nothing happens.
In some platforms like AtCoder and Leetcode, if you've registered, then they'll consider your participation with 0 problems solved and you'll lose your rating.
<begin-copy-pasted-part></begin-copy-pasted-part>what is the mean of "trusted participants"?
Do you have any idea why am I not being shown on the trusted participants' standings?
Only trusted participants are included in the official standings table, and their performance will be used for rating calculations for all rated participants. Therefore, if you are not a trusted participant, your performance will not be used for rating calculations in the round.
This can prevent certain users, such as those with alternative accounts, from disrupting the round since they are not trusted participants.
NO Green Tester !!!!!!!!!!!!!!!! flamestorm
Letssz goo finally a great round that is coming! Nicee!!
First unrated contest :)
Aiming to reach specialist this contest!
html:
Also: where's
<img src="photo/writer-and-tester">As a tester, I hope all of you guys have fun and the trusted participants would get the dubs!
How can I become a tester too :(
Befriend a setter or another tester.
Wanna be my friend? ;)
Even Yukana Nogami would want me to be a tester :(
My first official unrated contest :)
Me too! Now I don't have to stress about negative delta... good luck not dropping to pupil haha.
wishing good luck to all participants. i can't participate due to an exam tomorrow sadly.
Me[being happy] who kept my rating for this round!!
It's my first Div4 contest hopefully I will done more than 3 problems InshaAllah
The queue is already so long.
Please don't hold div4 today.
At the beginning, there was a long queue, but fortunately after some minutes, it fixed
wasted so much time in problem D corner case . how to Solve F ????
Find the least value of x which satisfies the condition for some y(using binary search) then check while incrementing x check if it is a lattice point or not, if it is, ans+=4 as (all 4 quarants), else move to next value of y.
I created video editorial for G: XOUR. Here's the code associated with the video.
TF wrong with my code
extremely frustrating actually.
try with long long. i use long double it gave WA 7 after changing it long long i got AC
it worked for me although what's the diff b/w using long double and long long?
i always fear of accuracy issue using non integers and that's i why never use them until it's extremely necessary, and i think there is some accuracy error in using double here. may be some experienced person can tell the actual issue.
Your code may work slowly because you are using doubles although you don't need to, can you provide your full submission? based on your submission history you don't seem to have participated in this contest, quite weird.
Can anyone help me why my submission is wrong for problem E.
Your bound on r for the binary search is wrong, since you have an array of size k + 1 and it is only k.
I am not using the binary search function i created, i was using lower_bound().
check this submission
I used the binary search function you made, and added a check for if d is exactly one of the points in a in order to not get out of bounds when d == n, and it passed. I'm not sure, but a lot of solutions seem to be getting WA on test 2 for using the inbuilt lower_bound() / upper_bound() functions, so I didn't use them.
Thank you so much!!
I actually doubted myself and went for lower_bound() should have used it, anyways something to take away always. :)
try cout<<tot_t + dis/speed<<" ";
It will result in double, I have to print Integers.
No it will print an integer because dis in an integer
You are free to use my code and check it on your own.
I absolutely hate using doubles :(
Very nice problems btw :)
which problem requires double?
I am also thinking the same.
I used doubles in F (for sqrt), for finding suitable Y-coordinates.
bro you can square the whole equation and there will be no need for double
is H 2-sat?
It is.
if it's, someone please give us the idea and the source code if it's available
You can have at most one negative number in a column.
Let's say X, Y, Z are the three elements in a column.
In 2-sat terms, if X is negative, Y and Z must be positive. If Y is negative, X and Z must be positive. If Z is negative, X and Y must be positive.
Submission: 260360108
Slightly simpler: Just add the three clauses $$$X \lor Y$$$, $$$Y \lor Z$$$, $$$Z \lor X$$$, where $$$X$$$, $$$Y$$$, and $$$Z$$$ are the "actual" values of the variables (if $$$X$$$ is negative, then we take $$$\lnot X$$$ instead of $$$X$$$).
tough H
Couldn't solve D. Can someone please explain how to approach it?
Count the number of positions i where s[i] != s[i+1]. Reduce the answer by 1 if there exists at least one position where s[i] equals 0 and s[i+1] equals 1.
count how many $$$groups$$$ of consecutive zeros and ones are present, this can be done by checking $$$s[i] != [i+1]$$$.
Then you have 3 cases:
case 1 : you have more than 2 groups, the answer is always $$$groups-1$$$ ( you can always merge two groups together )
case 2 : you have exactly to groups, either the two groups are in the correct order, so the answer is $$$1$$$, or they are in reverse order, so the answer is $$$2$$$.
case 3 : you have exactly one group, so the answer is $$$1$$$.
CASE 1 got me bad.
I was trying to think of scenarios where a group like 00..11.. could be used to combine two individual groups of 00... and 11... Now writing this comment, its obvious it should be groups-1
Thank you for sharing the approach :)
There are many ways to solve this problem, and some of them are quite overthought. One can observe that the answer is $$$max(1, numberOfTransitionsFrom0to1) + numberOfTransitionsFrom1to0$$$. Code:
what's the solution for problem H ?
Consider each column. Since there’s only 3 rows, you must have at least two $$$1$$$ in the same column. From this, you can see that if there exists a $$$-1$$$ in a column, then you must force the other two to be $$$1$$$. You can build 2-SAT clauses with this thought. Then you can solve 2-sat using any $$$O(n)/O(n^2)$$$ SCC algorithm.
Thank you so much
See your grandpa without long long
I tried to hack this submission, but it showed "Unexpected verdict". What happened??
It's fixed now.
Thanks.
What is the idea in problems G and F
F: Binary search. Try to fix x = 1, 2, 3, 4, ... then find the range of corresponding y.
G: Group all elements which have the same bit in their binary representation when divided by 4, then sort them.
G: Since $$$a_i \oplus a_j \lt 4$$$ so there only $$$4$$$ values ($$$0, 1, 2, 3$$$). Let's call those values $$$c$$$. You can actually use dsu to merge $$$a_i$$$ and $$$c \oplus a_i$$$. But because these value is up to $$$10^9$$$. You can use a map to save $$$c \oplus a_i$$$'s index and merge their indices instead.
Here is my implementation: https://mirror.codeforces.com/contest/1971/submission/260443847
Testcase can not be longer than 256 KB
Why this restriction as long as my testcase is valid ? Do it a mb atleast
Use generators.
So output.txt file generated with my code is bad ?
When you submit a hack, you can upload a generator (a program that prints the input) instead of the input data itself. This way you can submit a hack that has bigger input data.
I used new line at end of input, Still some sort of error >> Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin, line 1)]. First time trying it so might be something silly
You must format the input data so that it exactly matches the format given in the problem statements, including newlines and spaces. Also, you must not print trailing spaces at the end of the line (each line must end with a non-space character).
It might be a good idea to start with smaller input data, so you can check your input locally.
if problem F removes this statement "The sum of r over all test cases does not exceed 1e5". Does anyone have a solution that can pass it?
What if we just hardcode the right answers for all possible r?
well, I think this source code will exceed 64kB, the limit of codeforces.
Anyone using Python to solve E? I can't get this to pass for some reason :( WA on T2. I think it might be precision issues, but I refuse to believe Python suffers from them as well, at least not on a Div 4. E
https://mirror.codeforces.com/contest/1971/submission/260435081
What do you mean by "precision issues"?
I am working with the floating point numbers directly. Perhaps in the way I store them, or divide them, there is a problem
Well, you don't need floating point numbers in this problem. Also, almost everytime you should avoid using them
Lesson learned :')
I just worked with speed = distance / time, since that's what I'm familiar with. Also didn't think Python would have a serious issue with it.
But yeah. Going forward, I will try to minimize floats, divisions, and the like. Thank you!
You can use
distance // time(floor division). Usually, floating point numbers are a recipe for disaster, so only use them if you really need to. If possible, stick to integer arithmetic, and if you really need to, usedoubleorlong doubleinstead (in C++).What is wrong with my E solution? 260398566
Hi Sayan, your solution is suffering from floating point errors. For example, if an answer is 6 exactly, your solution may produce 5.9999999999998, and therefore floor'ed to 5.
Replace printing floor(ans) with floor(ans + 1e-6) makes your solution AC.
whats the idea behind taking 1e-6 only ? why not 1e-7 or 1e-5 ?
It's arbitrary. To prevent getting hacked I would suggest you use a more tiny value.
thanks! that worked. Here I was scratching my head finding logical errors :(
you can use multiplay instead of division also a/(b/c) -> ac/b
which part are you talking about?
you are calculating the speed first alone right ? and then you do distance/speed
you can avoid that by multiplying the denominator of the speed with the distance
Yes I guess I can also do that
My joke solution to problem C:
https://mirror.codeforces.com/contest/1971/submission/260436859
is H red problem? I do think it's orange at least just by looking # of solve
I got to orange by solving all other problems in under 50 minutes. So probably high orange — low red(2300/2400).
A — 800 (700 if was available)
B — 800
C — 800
D — 900
E — 1200
F — 1500
G — 1500
H — 2300
My predictions for problems are: A 800 B 800 C 800 D 1000 E 1500 F 1600 G 1600 H 2100
G was easier then F
Yes, but I'm talking about cf rating distribution
ohh sure.. but i still didnt understand F
2D 2 pointer
Wrong answer on test 35, whats wrong here? I have tried adding 1e-6 too.
https://mirror.codeforces.com/contest/1971/submission/260462886
Ambiguous questions like this should not be a part of div 4 contests for beginners. I spent 90 mins on this problem with multiple wrong answers, I was very close to smashing my laptop at the end.
never use floating point, instead simplify your computation in single fraction (numerator)/(denominator) consists of only integer operator. for example
a / (b / c) = (a * c) / bI had exact same issue and it completely ruined contest experience.
why this submission got wa on t21
260348605
260496255
thx <3
In Problem E ,I submitted the following code : My Submission
but it gives wrong answer on test case : 1 6 1 1 6 45 2
the expected output is 15 but my code's output is 14
When i debug my code, i found that whole error occurs in the line long long ans=floorl(time); bcoz the value of time before was 15 but after taking floorl it became 14.I don't understand why this is happening on my system and also on online judge.Is this a bug of C++ 20?? or i have done something wrong in my code.I have also used fixed<<setprecision(0) to avoid printing of answer in scientific notation like 1e9 instead of 1000000000 . But it does not affect my answer but floorl does. Kindly help me out and explain this unexpected behaviour of floorl which can be used for long double numbers as per documentation.
multiply all numerators first then divide.
long double time=b[ind-1]+((dis-a[ind-1] * (b[ind]-b[ind-1]))/(a[ind]-a[ind-1]));
ok,but i don't get the logic behind it.Why not this way works??
Problem F reminded me of my Computer Graphics course, where we discussed how to draw a circle efficiently on the screen. (It involves avoiding FP computation and replacing multiplication with addition.)
So my solution works as follows. Let point P start at $$$(0, r)$$$. For every step, checks if $$$P$$$ falls in the range. Then, P moves to the right 1 unit, and if $$$|OP| \ge r+1$$$, revert the previous move and move P down 1 unit instead. Repeat until you reach $$$(r, 0)$$$, and multiply the answer by 4.
This algorithm works because the width is 1. The reason why CG introduced this algorithm is that it never requires calculating the $$$|OP|^2$$$ by performing 2 multiplications, but you can instead calculate the increment of $$$|OP|^2$$$ in O(1) additions for each iteration.
It's interesting that we competitive programmers work on the level of big-O, avoid letting the constant factor determine what solutions get AC instead of TLE. But CG course together with Parallel Distributive Computation (another course this semester) show us a big optimization on the constant will determine who's SOTA in practice, and I feel those engineers "One clock cycle (or I-O bandwidth, network communication, warp utilization in GPUs...)matters!"
Hey! Check out my video solutions for the contest. I've covered Problem A-G. https://youtu.be/WBECy_7Ux0I
Problem E has to be (div.0 — E), not (div.4 — E) because of precision errors...
How about just using integer types only :)
Hi, can someone explain why my solution for E doesn't work. I used doubles carefully but still got WA on test case 12.
Thanks.
260363341
Not careful enough:(
Perhaps add a really tiny eps can work, like 1e-11(the value of a correct eps is totally arbitrary and hard to calculate). But it's better to use integer types and not to use double or even long double.
Number of ACs in problem E has nearly halved after the main test:(
Problem E has successfully planted the fear of floating point numbers in my mind :|
amount of FST on E is quite frightening
Why are submssions after the contest in queue for such a long time???