Блог пользователя RobinFromTheHood

Автор RobinFromTheHood, история, 2 года назад, По-английски

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:

  1. Vladosiya for brilliant coordination, and for improving all problems.

  2. 18o3, cry, ikrpprppp, pavlekn for orange testing.

  3. employed, raztun, Proof_by_QED for purple testing.

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

  5. gbula, Pa_sha, 1165MOHITSINGHAL, NotHosam for Div. 3 testing :)

  6. MikeMirzayanov for Polygon and Codeforces platforms.

  7. You for participating in the round!

Good luck!

UPDATE: Editorial is out!

Image by Zmarlen with our thanks!

  • Проголосовать: нравится
  • +248
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
 
Проголосовать: нравится +59 Проголосовать: не нравится

As a setter, if you cheat I'll be hiding under your bed

»
2 года назад, скрыть # |
 
Проголосовать: нравится +43 Проголосовать: не нравится

as a tes, give me contribution

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

As a Div.3 contestant, RobinFromTheHood orz.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

But is it AI proofed?

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -13 Проголосовать: не нравится

edited

»
2 года назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

"You" are in black and red. so funny

»
2 года назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

after such a bad contest in today's div2 hoping for some good delta positive in this div3 tomorrow

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

When did Robin last wear glasses?

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

The 3rd trial to be a pupil from Div.3 I hope it works this time :D

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I have love for coding but I get frustrated when I can't solve any problem... What is the solution?plz help me.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

+1500 rate ? lezgo

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +4 Проголосовать: не нравится

WOWSER! Cant wait for this round! Im gonna shoot an arrow straight through probem A in the first 2 minutes!!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

the robinhood gang in the picture is awesome. xd.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

This contest will get rating from specialists and will give it to newbies?

»
2 года назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

As ChatGPT I can confirm I cannot solve the problems.

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +18 Проголосовать: не нравится
this can't be just me
»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I turned blue in the last div2 so now this is unrated T_T

»
2 года назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

I am so excited for the contest!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

I'm trusted, why I'm "out of competition"?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can't wait for this round!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

one refresh costed me 10 mins :(

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

delayforces?

»
2 года назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

10 minute penalty for entering the contest.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

delay forces?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

why is it pending brof

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Types of headache meme was supposed to be about Div2 D

»
2 года назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится
  1. Not sure if it was just me being bad today, but I fell into a dilemma of absolutely hating G and feeling it should be something of my usual favorite and specialty a.k.a. simulation implementation. It still stings that the whole difficulties of G were based on the implementation of the simulation alone, the statements told you all you needed to do upfront...
  2. Is there anyone having a clean $$$\mathcal{O}(n \sqrt{n})$$$ solution for H? At first I TLE'd when doing $$$\mathcal{O}(n \sqrt{n} \log{n})$$$, and the reduction of the $$$\log$$$ is pretty tedious...
»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by RobinFromTheHood (previous revision, new revision, compare).

»
2 года назад, скрыть # |
 
Проголосовать: нравится -15 Проголосовать: не нравится

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



#include <bits/stdc++.h> using namespace std; bool check(int mid, vector<float> &arr) { float avg = 0; int sum = 0; for(int i = 0; i < arr.size(); i++) { sum += arr[i]; } sum += mid; avg = static_cast<float>(sum) / (2 * arr.size()); int pop = 0; for(int i = 0; i < arr.size(); i++) { if(arr[i] < avg) { pop++; } } return pop > arr.size()/ 2? true: false; } void solve(){ int n; cin>>n; vector<float> arr(n, 0); for(int i = 0; i < n;i++) { cin>>arr[i]; } if(n <= 2) { cout<<"-1"<<'\n'; return; } sort(arr.begin(), arr.end()); int left = 0, right = 1e6; int ans = -1; while(left <= right) { int mid = left + (right - left)/2; if(check(mid, arr)) { ans = mid; right = mid - 1; } else { left = mid + 1; } } cout<<ans<<'\n'; } int main() { ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int t; cin>>t; while(t--) { solve(); } return 0; }
»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I suck at questions like D. Can anyone give any guidance about how to approach questions involving ranges.

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    2 года назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      2 года назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      heap is just priority queue right ? if that is the case can you just briefly talk about your method thanks.

      • »
        »
        »
        »
        2 года назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Casino H

»
2 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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?

  • »
    »
    2 года назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    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}$$$.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Not good not bad contest D destroyed me today need to upsolve it

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is C intended to be binary search ? cuz i thought it is easier with maths 282287861

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

how did you solved Problem C with binary search? anyone?

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    2 года назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    (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.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

omg double dijkstra on E ??? Niceee.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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)

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Dijkstra problem was amazing!

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to do the range query for H efficiently?

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

H << E

H can be easily solved by Zobrist hashing 282353218

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Does using float types in problem C will get hacked? sorry for my poor english

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

My best contest so far

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

For Problem E , I think of a solution Its giving TLE so for person to meet at k , 1 -> k n -> k are two disjoint path with just one element common = k so we can binary search over it to find first path where the common element is just one logn * (nlogn)*mul -> mul is ig in my implementation is 2 or 3 which leads to TLE Accepted Version : Same idea with Binary search but reducing Complexity in Check function which i just realised when i am writing this Comment Instead of computing sets which can be visited from 1 and n again and again , just do once and count complexity : logn*n -> Accepted

Link : https://codeforces.me/contest/2014/submission/282393166

»
2 года назад, скрыть # |
 
Проголосовать: нравится -12 Проголосовать: не нравится

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)?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Please help, I am getting TLE even after using Dijkstra in E. Submission https://codeforces.me/contest/2014/submission/282399768

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

pls put the announcement link with the contest i could not find it

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Could someone please tell me why am I getting a TLE in this Submission

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

The Dashboard was so Hard as Steelboard!!!

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why is it unrated?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I have a friend who wants to ask why unrated.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

why is system testing frozen?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

what is vjudge btw tons of submission from named vjudge unrated chinese accounts are making trouble i guess

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Nice picture.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

estimated ratings

A — 800

B — 800

C — 1000

D — 1600

E — 1800

F — 2000

G — 2200

H — 2000

»
23 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

As a test, I have been tested