Hello Codeforces!
Greetings from Nottingham, England! We are delighted to invite you to Legend of Robin Hood, a round inspired by our local folklore.
Codeforces Round 974 (Div. 3) will start on Sep/21/2024 17:45 (Moscow time).
You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks. After open hacks all accepted solutions will be rejudged on successful hacks.
You will be given 6-8 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third 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 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Problems have been prepared by ChairmanFMao, Filikec and RobinFromTheHood.
We would like to thank:
Vladosiya for brilliant coordination, and for improving all problems.
employed, raztun, Proof_by_QED for purple testing.
Alenochka, FBI, macaquedev, Non-origination, JuicyGrape, umezo for blue testing.
gbula, Pa_sha, 1165MOHITSINGHAL, NotHosam for Div. 3 testing :)
MikeMirzayanov for Polygon and Codeforces platforms.
You for participating in the round!
Good luck!
UPDATE: Editorial is out!

Image by Zmarlen with our thanks!








As a setter, if you cheat I'll be hiding under your bed
as a tes, give me contribution
As a Div.3 contestant, RobinFromTheHood orz.
But is it AI proofed?
AI has been beaten to a pulp, but no trees (segmented, lazy or oak) have been harmed, in the preparation of this round.
edited
I think u guys should already stop with this gpt's discussion. It has nothing to do with the round, as usage of the AI for solving is not allowed in codeforces.
"You" are in black and red. so funny
after such a bad contest in today's div2 hoping for some good delta positive in this div3 tomorrow
Same
literally bro yesterday I got the idea of B really fast but doubted on myself then did something different which was wrong then again coded my first idea which got accepted but by that time it got so late :(
I think: idea for B was simple, interaction for C was the true kill.
I don't know how to solve interaction problems so it was out of my range but definitely gonna learn it now today only so that I can be ready for it and yeah B idea was simple but I did overthinking on it and got absolutely destroyed
Yea but atleast d was easier than most div 2
When did Robin last wear glasses?
Yes, I also come to CF rounds for historcal detail. How dare the setters try to add a bit of extra fun?!
Please excuse any anachronisms; the power of generative AI isn't strong enough.
The 3rd trial to be a pupil from Div.3 I hope it works this time :D
you'll be able to do it bro, only 20 more rating needed. Just solve 4 problems and you should be able to get at least 20 from it
I have love for coding but I get frustrated when I can't solve any problem... What is the solution?plz help me.
leave the problem, Do some other problem, or do something else like go play with your dog or go make some coffee.
+1500 rate ? lezgo
WOWSER! Cant wait for this round! Im gonna shoot an arrow straight through probem A in the first 2 minutes!!
the robinhood gang in the picture is awesome. xd.
Thank you, honoured guest
This contest will get rating from specialists and will give it to newbies?
As ChatGPT I can confirm I cannot solve the problems.
I turned blue in the last div2 so now this is unrated T_T
Congrats bro. But your graph is just unbeleivable. Do you have a second ID or did olympiads before?
Thank you so much ^^ I've actually won a silver medal in the Italian Olympiad in Informatics and I'm currently training to be potentially chosen for IOI :3
I am so excited for the contest!
I'm trusted, why I'm "out of competition"?
Because of rating I suppose
well am I rated?
Can't wait for this round!
Now wait 10 mins more.
one refresh costed me 10 mins :(
delayforces?
Yeah. But why the 10 min delay
It happens often a while last year, I remember the main reason is ddos attack (I mean today's round even has less people than yesterday's div2, so it can't be overcrowded)
10 minute penalty for entering the contest.
delay forces?
why is it pending brof
Lol rk1 solved till F in 12 mins and now it shows User is disabled
Live vac ban
Types of headache meme was supposed to be about Div2 D
nvm
Oh yeah, neat trick! Thanks!
UPD: Why editing? I think the trick is actually reasonable, it's just not trivial on sight.
Hey if you've solved H using Mo's can you please see where this code fails? I do not know where it's going wrong 282342460
At a glance, probably the sweeping order was wrong. Usually, I tend to check for moving the L/R pointers to increase the range (L to left, R to right) first before moving to decrease the range (L to right, R to left).
uhm, my way of moving the pointers worked for queries on distinct values in a range. the only change i did here was pertaining to frequency change, that's all
you were asking about sqrt solution, so I thought I wrote an off topic
Maybe that'd apply to other, but I absolutely won't mind an offtopic that is resourceful to everyone. So yeah, I have no issue with it at all, keep it!
You are not the only one in your opinion of Problem G. I also thought that it had straight forward idea for stimulation with the implementation difficulty as the deciding factor for the contestants.
For $$$O(n \sqrt n)$$$ in H, you can use Mo's while keeping track of frequencies. At the end you just need to check if there exist any odd frequency element or not. My Submission
I looked at your code and realized I have always implemented Mo's algorithm inefficiently, i.e. excessive case-handling when moving from a block to another. That's on me I guess.
just please someone tell me why in problem D last case the boy can't start at day 1 i read the statement 789 time and still have no clue
if the brother visits on day 3, he will overlap with 3 jobs. if he visits on day 1 he will only overlap with 2 jobs
The boy is the one to maximize visits. You gets three overlaps at $$$3$$$ ($$$2$$$, $$$3$$$ and $$$4$$$), while only two ($$$3$$$ and $$$4$$$) at $$$1$$$.
sorry I meant 2 if the the boy starts at day 2 he will intersect with (1,3) (2,3) (4,8)
Starting at $$$2$$$ only covers the day range $$$[2, 3]$$$. It doesn't touch $$$[4, 8]$$$ at all.
Auto comment: topic has been updated by RobinFromTheHood (previous revision, new revision, compare).
i think because it recalculates the number of overlaps for every possible starting day of the visits.
you will have to use prefix sums to avoid TLE
prefix as well as suffix sum array, there are days on which jobs are ending as well as starting
can someone please tell me what am I doing wrong in Problem C
right should have been 1e18
calculate the sum outisde the check function and add (x/n) to get new avg
how did you come into conclusion that we should add x/n?
if u add x then take avg isnt it same as adding x/n
Input in the vector should in int and it would be better if you take double for avg calculation. Also idk why you are taking sum as int when the variables in the array are float, complete mess of datatypes
I suck at questions like D. Can anyone give any guidance about how to approach questions involving ranges.
I solved with prefix sum range or whatever thats called. 282320011 Now i am also not that good at range problems cuz G is also a range type of problem and i couldnt do it
I used sort and heap to solve these 282360541. Overall the algo will also work with bigger l,r up to 10**9...
But I guess it's overkill because I don't notice the limit is small and can use other method to solve
heap is just priority queue right ? if that is the case can you just briefly talk about your method thanks.
yes you can say heap and priority queue are interchange-able.
Let's say I brute force of all time point from 1 to n-d+1 and calculate how many job intervals it collides.
First step is sort the job intervals [l,r] So the intervals I pushed in the heap at time point i, will no longer needed to check them again at time point i+1. So I can apply sliding pointer technique.
Second step is the pushed data in the heap is only r for each interval, because the job intersect with time point [i, i+d-1] is the heap size, and to maintain the heap you need to check the smallest r that r<i will need to be pushed out (they're no longer intersect with the current time point).
Bonus: if the time point limit is 10**9 and intervals limit also 10**9, then I won't for loop from 1 to n-d+1. I will check i = left interval.
Can someone please tell me why does my solution for D(282356603) get TL? I thought the complexity was O(n+k)
What do we need to do to solve H?
I think we just need to check whether all elements from l to r are the same. If they are, we then check whether the length is even or odd
we need to check if we have even number of every element
Casino H
how come when I view "common standings" I have some rank (e.g. 1500), but when I view "friend standings" I have a worse rank (e.g. 2000) ? I made sure to have "show unofficial" disabled both times.
If I look back at previous contests, it would appear that the one in "friends standings" is the actual rank.
same for me a 200 rank gap lol
yeah it's weird. 1433 on common, 1853 on friends. maybe the rank on common excludes untrusted participants, and then the discrepancy is resolved after the contest
what is the upper bound on x in problem C? my intial submission uses 1e12 and I fear hacks so I resubmitted with 1e18. can someone tell if 1e12 works, then why does it work?
I think $$$4 \cdot 10^{11}$$$ is one upper bound. The problem can be solved straight-up from maths.
In short, we need a person with $$$x$$$ golds at maximum to feel dissatisfied (so that there are at least strictly more than half people having no more than $$$x$$$ each). We need to satisfy $$$x \lt \frac{s}{2n}$$$, or $$$s \gt 2nx$$$, with $$$s$$$ being the total amount of golds from everyone. Clearly $$$2nx \le 2 \cdot 2 \cdot 10^5 \cdot 10^6$$$, or $$$2nx \le 4 \cdot 10^{11}$$$.
Not good not bad contest D destroyed me today need to upsolve it
? It is a good contest if we are talking about the variety and difficulty level of problems. Maybe not good for you as an individual which happens :)
yeah question wise really good performance wise bad for me I should have solved D
you are fairly new, you will do it next time. Good luck:)
Is C intended to be binary search ? cuz i thought it is easier with maths 282287861
The statement for problem C is probably the most try-hardest to be confusing statement I have ever seen. Why "half of the average"? On top of that, real number, really?
since everything is "strictly less" or "strictly more", you can simply round up.
for example, strictly half of the population = half of the population rounded up.
one's wealth is strictly less than half of the average wealth = average must be strictly greater than double that person's wealth. that person's wealth is always an integer so you can treat average as an integer too
how did you solved Problem C with binary search? anyone?
basically you want to test whether amount of gold makes robin hood appear. to do this, you make your guess (mid) and then find the average wealth: ceil(total + mid)/n.
now you simply compare this to the median wealth: a[n/2].
if the average is greater than 2*median, this pot will summon robinhood: r = mid.
if the average is less than or equal to 2*median, this pot will not summon robinhood: l = mid+1.
return l after binary search terminates, it is the smallest pot that will summon robinhood.
(Edit: I apologise for misreading the question. I mistakenly wrote the solution for D instead)
Let's say the guest's stay starts at day $$$i$$$. Then, the guest leaves at day $$$i+d$$$ (day $$$i+d$$$ is excluded). Which jobs are excluded? Only those which either stop before day $$$i$$$ starts, or start after or on day $$$i+d$$$. Note that there is no intersection between these 2 sets of jobs. Thus you can sort $$$l$$$ and $$$r$$$ separately and solve for each day using binary search.
Read the problem B wrong cost me 30 minutes. After that screw up implementation at problem D cost another 30 minutes. Then all I have is ~ 15 minutes for E, so I choose to stare in the ceiling to recollect my dumb mistakes...
Why not trying? E is (somewhat) basic Dijkstra though, it might still be tough for a green but not impossible.
Moral of the story: just fight to the very last seconds. You never know how much power you got if you resigned to fate.
Yep thanks for the advice. Probably I need to train in VC to strengthen my mental till the end of contest time limit...
Finally, It took me about an hour to AC the problem. But maybe I can do it faster next time.
omg double dijkstra on E ??? Niceee.
is it only me or i feel like H was easier than E in terms of the idea (I didn’t solve either of them :I)
yes, H is easier. tho on clist H is master or CM rated, while E is high expert XD
Can someone kindly help me in finding the mistake with my solution for question E: https://codeforces.me/contest/2014/submission/282371555
I have performed dijsktra with two distance arrays and two visited arrays (with horse and without horse), once from 0 and once from n-1. I am getting WA on test case 3 and not able to debug the mistake.
Realized overflow from the test cases. It was a typo — used long instead of long long :'(. Thanks a lot if you have taken a look at my submission in the mean time.
Dijkstra problem was amazing!
How to do the range query for H efficiently?
H << E
H can be easily solved by Zobrist hashing 282353218
I can't figure out why my C++ solution is timing out on problem E.
I'm duplicating the graph with the half weights and having edges between the two copies at all the horse locations. Then I run dijkstra from either end and check each vertex to see who gets to it last.
I'm thinking it should be O(E*log(V)) and while I've doubled E and V, that shouldn't be enough to time it out. I've tried tweaking things to account for any extra time that might have been spent copying or allocating, but no luck. Anyone else have an idea?
https://codeforces.me/contest/2014/submission/282381456
Try adding a visited set in your $$$dijk$$$ to avoid processing same nodes multiple times.
I added a fix to your code. Now it passes. 282391526
In $$$H$$$ answer is YES for a query if in that subarray all the numbers have even frequency otherwise NO but how to check that?
Hashing
282374148
Does using float types in problem C will get hacked? sorry for my poor english
My best contest so far
Congrats bro.. Can you pls tell me about your approach for D in short? Can't figure it out
Editorial is out
Link : https://codeforces.me/contest/2014/submission/282393166
HOW CAN THE PROBLEM D. Robert Hood and Mrs Hood test case 1 9 2 4 7 9 4 8 1 3 2 3 has output 3 4. Shouldn't it be 1 4 because valid days are 1 to n-d (2 2 2 1 1 2 2)?
Read the problem statement again
thanks
input: 1 9 2 4 7 9 4 8 1 3 2 3
jobs array: 2 2 3 1 1 2 2 . .
The answer: 3 4
The point: Robin wants his brother's visit to overlap with the maximum number of "distinct" jobs, and his mother's the minimum.
thanks
Please help, I am getting TLE even after using Dijkstra in E. Submission https://codeforces.me/contest/2014/submission/282399768
Check out the first issue on https://codeforces.me/blog/entry/132653
pls put the announcement link with the contest i could not find it
I don't know if it is a formatting issue, but showing the first lines of the statements in italics was very confusing. I assume the italics at the top are just part of the plot, but in this it seems the first paragraph of the actual statement was in italics
Could someone please tell me why am I getting a TLE in this Submission
The Dashboard was so Hard as Steelboard!!!
Why is it unrated?
why do you think its unrated? System testing is going on.
I have a friend who wants to ask why unrated.
why is system testing frozen?
what is vjudge btw tons of submission from named vjudge unrated chinese accounts are making trouble i guess
Nice picture.
estimated ratings
A — 800
B — 800
C — 1000
D — 1600
E — 1800
F — 2000
G — 2200
H — 2000
As a test, I have been tested