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.

Axial-Tilted, raztun, vgoofficial for purple testing.

Alenochka, FBI, macaquedev, Non-origination, SashaT9, umezo for blue testing.

gbula, Pa_sha, 1165MOHITSINGHAL, _Hosam 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

come, I will wait for you. It's been too long since I talked to some person IRL.

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.

but people break rules.

gpt can't affect round. in fact, I used gpt but solved only 2 problems. furthermore the gpt didn't provide me the right solution at first time.

That means you tried to cheat and Failed ? So you broke the rules. Codeforces I got a rule breaker...

haha! I just wanted to know only how much gpt can affect CF. I broke the rule but it is for CF.

Hahaha. But there logic is bad but not worse.

"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

It is not your fault, the blog does not mention the presence of interaction. Also it is problem C? Usually the interactive problem is D or later, but this seems too early for it. The ratio for C to A solves is very low here.

B for me was like yours actually. Luckily I trusted myself and went with the solution, but that does seem to feel in that it is difficult to prove in reasonable time and convince yourself the strategy works.

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.

i was able to try 3 questions but the questions were like a story ; its nice how problem setters can frame such questions with increasing difficulty .

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

Thx bro, wish u luck in coming contests

glad to see you became green, thx.

I actually came back to check if you really made it in this contest.

I am really happy for you brow. Wish you good luck in your new journey, (maybe I'll look forward to the next contest to achieve green)

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!!

I'm interested!

Pro tip: if u wanna cheat and improve your skills participate as unrated participant.

Upsolve after the contest and cheat however you like

Haha yes tru

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.

this can't be just meI 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?

you are above 1600 so you cant register officially

Can't wait for this round!

Now wait 10 mins more.

one refresh costed me 10 mins :(

they did warn us about the 10 minute penalty

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)

waitingforces

10 minute penalty for entering the contest.

delay forces?

Codeforces just got 10 mins penalized for setting a wrong time

Delayed!

why is it pending brof

I can't wait to try it out

Lol rk1 solved till F in 12 mins and now it shows User is disabled

Live vac ban

Poor Robert ;(

DelayForces

I think it should be unrated or increase the time

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.

I was confused I thought d was 4 the whole time. thanks

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

you only need to track the active jobs as you move through the potential starting days so prefix sums accumulate counts as you progress through the days, without the need for a second pass to look backwards (as you would with a suffix sum).

can someone please tell me what am I doing wrong in Problem C

right should have been 1e18

getting TLE ;-;

(2e5)*(1e6) this will pass

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 know sorry.. ;c

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.

I spent maybe 4 hours today upsolving it and I found so many different ways of doing it Update range , prefixes, sliding window.... and there is many other unique approaches most people used the sliding window technique which include storing all the taken events end points in a multiset lets say current windows is L , R when our window move it will become L+1 ,R+1 now we should add to our multiset all the events that will start at R+1 and we should remove from our multiset all the events that ends before L+1 now the answer for our new window is just the size of our multiset

Can someone please tell me why does my solution for D(282356603) get TL? I thought the complexity was O(n+k)

282367057 guys what will be the error here, it is getting time limit exceeded in test case 3

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 < \frac{s}{2n}$$$, or $$$s > 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}$$$.

I used 4e11. Can someone try to hack mine? https://codeforces.net/contest/2014/submission/282293087

edit: Editorial says 4e11 is fine. The pretests are passing anything > 2e11

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?

we have to do binary search on x and after that check if particular x satisfy the condition.

can you please check this solution and please please let me know what's wrong

https://codeforces.net/contest/2014/submission/282369883

use double instead of float and also change the int of sum , left , right , mid , ans etc. to long long int because it may cause overflow.. also dont forget to change int to long long int in your check function parameter

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.

Can someone please tell me why this is wrong:

https://codeforces.net/contest/2014/submission/282369897

and can someone tell me the answer/thought process

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.net/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?

use Mo algorithm

you can learn form here : https://cp-algorithms.com/data_structures/sqrt_decomposition.html

H << E

H can be easily solved by Zobrist hashing 282353218

why need rand ?(no hash)

Hi I kind of suck at coding and stopped at problem B. As far as I know the optimal solution probably should be counting the amount of odd numbers to see whether if the answer is odd or even. However I just couldn't figure out a correct solution for some reason. Could someone kind of explain how to implement the solution and why my code is wrong? Much appreciated!! Here is my solution 282318886.

I don't know if this will help you,

I did B using that parity of i = parity of i^i

so you can calculate

`n(n+1)/2`

(the sum from 1-n) and subtract`x(x+1)/2`

where`x = n-k`

(this way you get the sum of the interval you need)

so be

`ans = n(n+1)/2 - x(x+1)/2`

you only have to check parity of ans.

Thanks for the solution, that actually makes a lot of sense. Don’t know how I didn’t thought of that.

You could think of it like this:

Odd*Odd=Odd

Even*Even=Even

Even+Even= Even

Odd+Even=Odd

Odd+Odd=Even

You will notice that you dont actually need to calculate n^n nor even do the addition to find out wether the result will be even or not just count the number off odds from n-k to n and if there are an even number they will cancel out and result is even,else result is odd

Yeah that was what I was trying. Thanks anyways!

//This is the code

I don't know what's wrong with my solution about problem C. plz lend me your hand. plz.plz.plz

//~~~~This is the code~~~~~

## include <bits/stdc++.h>

using namespace std;

int main() {

}

I did it a different way, so it would take a bit of time to check your whole code, but I think at least your

`required_unhappy_count`

should be`(n/2) + 1`

.If there are 4 or 5 people, you need 3 to be unhappy, but (4 + 1)/2 like in your current solution will think only 2 people need to be unhappy.

Thank you for your reply. I really appreciate it.

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.net/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

i take place (4971) with unofficial

could i be green today ?

In $$$H$$$ answer is

YESfor a query if in that subarray all the numbers haveevenfrequency otherwiseNObut how to check that?I thought of the same idea, but I didnt have enough time to code it up. I was considering using inverse indexed lists but I realized it would take too long.

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

Basically, you start with the meeting for the brother to be at {1,d}. Then, you check how many intervals end at 1 (which you will subtract off of the total) and the amount of intervals starting at d+1 (which you will add to the total). Find the minimum value of this for 1 to n-d for the mother, and the maximum of this from 1 to n-d for the brother. You can do this all in one loop, and it takes O(n) time.

Link : https://codeforces.net/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.net/contest/2014/submission/282399768

Check out the first issue on https://codeforces.net/blog/entry/132653

Thanks a lot!!!...Great Post learned some new stuff.

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

My rating is 834 and I've solved 3 problems successfully in this contest. But I didn't get the rating (contest is unrated for me). I don't understand why??

https://codeforces.net/contest/2014/submission/282533590 Does anyone have an idea why this gets WA on test 3? Apparently it outputs "yes" instead of a "no" but with the program being so simple I can't find what the problem may be, I solved it with an XOR segment tree, even though there probably are more simple and efficient approaches.

Edit: Discovered the case: 1 4 1 4 5 6 7 1 4

Where it should output "no" but it outputs "yes" and fixed the problem with random hashing because the values are only between 1 and 1e6

wtf is worng with codeforces submission server ..working very slowly..:(

Soon I'll be leaving for months

Nice picture.

estimated ratings

A — 800

B — 800

C — 1000

D — 1600

E — 1800

F — 2000

G — 2200

H — 2000

Dear Codeforces Team & @MikeMirzayanov,

I hope this message finds you well. I recently received a notification regarding my solution for Problem 2014C, stating that it coincides with other submissions. I would like to clarify that I did not engage in any form of cheating.

The overlap occurred unintentionally because I was using Ideone.com to test my code, and unfortunately, I left the default setting as "public," which made my solution visible to others. I had no intention of violating the rules, and I was unaware that my code could be accessed by others in this manner.

I sincerely apologize for any confusion caused by this, and I will ensure that in the future, I am more careful with the visibility settings when using such platforms.

Thank you for your understanding. I hope this clears up the situation, and I would appreciate it if you could reconsider the decision.

Best regards, @hmnshuu

Hello @MikeMirzayanov, I received a message regarding my submission for the problem 2014D that it was coincided with some other submission. I'm here to clear my side I did one mistake by testing my code on Ideone.com and I forget to change the default setting as the default setting is set as public. Also my other submissions for 2014A,2014B,2014C are also skipped. As There was no allegation for those problems I am totally heartbroken after seeing my rating changes As My submission for A,B,C was also skipped without any reasoning Please reconsider my submission https://codeforces.net/contest/2014/submission/282356633 submission for 2014D https://codeforces.net/contest/2014/submission/282339264 submission for 2014C https://codeforces.net/contest/2014/submission/282249661 submission for 2014B https://codeforces.net/contest/2014/submission/282227387 submission for 2014A

my total solve for this contest is counted as 0 and i was given -130

In D , Can someone explain the 5th test case, the job is from 2 to 8, so why my answer can't be 2(brother) and 1(mother) ?

Your solution 282344656 for the problem 2014C significantly coincides with solutions deepdblm/282267192, zodiac041/282344656. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

Actually I and deepblm are batchmates and the concept of the question not the exact question but a very similar approach was disscussed by our sir because of which there may be similarity in deep's and my code/

Actually me and user:zodiac041 are friends and we belong to the same college and in our college similar type of question was already discussed by one of our profs, I have attached the notes and would like to tell that we have not cheated, please give our ratings back.4

this is related to the submission 282267192 and 282344656 being similar

i was not able to attach the image of the notebook , if you can send me a mail where i could forward it you for checking then it would be great.

was it

Unrated? I found on the contest pageThe solutions I submitted for the contest, including the problems that have been flagged for significant coincidence, are based on concepts I studied from the book Data Structure Fundamentals by Prof. Md Rafiqul Islam et al. (Chapter 7 and Chapter 8) and Computer Algorithms by Ellis et al. (Chapter 4, Chapter 5 and Chapter 6). I used well-known methods which are standard approaches covered in multiple academic resources.