RobinFromTheHood's blog

Codeforces Round 974 (Div. 3)
By RobinFromTheHood, history, 3 months ago, In English

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. Axial-Tilted, raztun, vgoofficial for purple testing.

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

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

  • Vote: I like it
  • +248
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +59 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 months ago, # |
  Vote: I like it +43 Vote: I do not like it

as a tes, give me contribution

→ Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

As a Div.3 contestant, RobinFromTheHood orz.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

But is it AI proofed?

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    AI has been beaten to a pulp, but no trees (segmented, lazy or oak) have been harmed, in the preparation of this round.

    → Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

edited

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it +41 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but people break rules.

      → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hahaha. But there logic is bad but not worse.

            → Reply
»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

"You" are in black and red. so funny

→ Reply
»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think: idea for B was simple, interaction for C was the true kill.

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yea but atleast d was easier than most div 2

          → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When did Robin last wear glasses?

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Yes, I also come to CF rounds for historcal detail. How dare the setters try to add a bit of extra fun?!

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please excuse any anachronisms; the power of generative AI isn't strong enough.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 .

      → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    leave the problem, Do some other problem, or do something else like go play with your dog or go make some coffee.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

+1500 rate ? lezgo

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm interested!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

the robinhood gang in the picture is awesome. xd.

→ Reply
»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

As ChatGPT I can confirm I cannot solve the problems.

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it
this can't be just me
→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Congrats bro. But your graph is just unbeleivable. Do you have a second ID or did olympiads before?

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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

      → Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I am so excited for the contest!

→ Reply
»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't wait for this round!

→ Reply
»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

one refresh costed me 10 mins :(

→ Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

delayforces?

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah. But why the 10 min delay

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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)

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

waitingforces

→ Reply
»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

10 minute penalty for entering the contest.

→ Reply
»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

delay forces?

→ Reply
»
3 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Codeforces just got 10 mins penalized for setting a wrong time

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Delayed!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why is it pending brof

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't wait to try it out

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Poor Robert ;(

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

DelayForces

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it should be unrated or increase the time

→ Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Types of headache meme was supposed to be about Div2 D

→ Reply
»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it
  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...
→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 3   Vote: I like it +28 Vote: I do not like it

    nvm

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      Oh yeah, neat trick! Thanks!

      UPD: Why editing? I think the trick is actually reasonable, it's just not trivial on sight.

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

            → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you were asking about sqrt solution, so I thought I wrote an off topic

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          ← Rev. 3   Vote: I like it +1 Vote: I do not like it

          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!

          → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like 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.

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry I meant 2 if the the boy starts at day 2 he will intersect with (1,3) (2,3) (4,8)

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Starting at $$$2$$$ only covers the day range $$$[2, 3]$$$. It doesn't touch $$$[4, 8]$$$ at all.

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      prefix as well as suffix sum array, there are days on which jobs are ending as well as starting

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
3 months ago, # |
  Vote: I like it -15 Vote: I do not like it

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;
}
→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    right should have been 1e18

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      getting TLE ;-;

      → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      calculate the sum outisde the check function and add (x/n) to get new avg

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        how did you come into conclusion that we should add x/n?

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          if u add x then take avg isnt it same as adding x/n

          → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like 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

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    we need to check if we have even number of every element

    → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Casino H

→ Reply
»
3 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same for me a 200 rank gap lol

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like 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 :)

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah question wise really good performance wise bad for me I should have solved D

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        you are fairly new, you will do it next time. Good luck:)

        → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yep thanks for the advice. Probably I need to train in VC to strengthen my mental till the end of contest time limit...

      → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Finally, It took me about an hour to AC the problem. But maybe I can do it faster next time.

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me why this is wrong:

https://mirror.codeforces.com/contest/2014/submission/282369897

and can someone tell me the answer/thought process

→ Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

omg double dijkstra on E ??? Niceee.

→ Reply
»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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)

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    yes, H is easier. tho on clist H is master or CM rated, while E is high expert XD

    → Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone kindly help me in finding the mistake with my solution for question E: https://mirror.codeforces.com/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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Dijkstra problem was amazing!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do the range query for H efficiently?

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

H << E

H can be easily solved by Zobrist hashing 282353218

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah that was what I was trying. Thanks anyways!

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        //This is the code 


        void solve(){

        ll n,k;cin>>n>>k;
        ll startAt=max(1ll,n-k+1);
        ll count=0;
        if(startAt%2==0)startAt++;
        if(n%2==0)n--;
        count=((n-startAt)/2)+1;
        if(count%2==0)Y<<el;
        else N<<el;}
        → Reply
»
3 months ago, # |
  Vote: I like it -18 Vote: I do not like it

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() {

ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; // number of test cases
cin >> t;

while (t--) {
    int n; // total population
    cin >> n;

    vector<long long> wealth(n);
    long long total_wealth = 0;
    long long max_wealth = 0;

    for (int i = 0; i < n; ++i) {
        cin >> wealth[i];
        total_wealth += wealth[i];
        max_wealth = max(max_wealth, wealth[i]);
    }

    // Calculate the number of required unhappy people
    int required_unhappy_count = (n + 1) / 2; // ceil(n / 2)

    // Count current unhappy people
    int unhappy_count = 0;
    double unhappy_threshold = static_cast<double>(total_wealth) / (2 * n);

    for (int i = 0; i < n; ++i) {
        if (wealth[i] < unhappy_threshold) {
            unhappy_count++;
        }
    }

    // If already more than required unhappy people, no extra gold needed
    if (unhappy_count > required_unhappy_count) {
        cout << 0 << endl;
        continue;
    }

    // We need to find minimum x such that unhappy_count < required_unhappy_count
    long long low = 0, high = 1e18; // Set high to a large number
    long long answer = -1;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        long long new_total = total_wealth + mid;

        // Calculate the new unhappy count
        int new_unhappy_count = 0;
        double new_unhappy_threshold = static_cast<double>(new_total) / (2 * n);

        for (int i = 0; i < n; ++i) {
            if (wealth[i] < new_unhappy_threshold) {
                new_unhappy_count++;
            }
        }

        // Check if we have more unhappy people than allowed
        if (new_unhappy_count >= required_unhappy_count) {
            answer = mid; // Found a valid x, try for smaller
            high = mid - 1;
        } else {
            low = mid + 1; // Try larger x
        }
    }

    cout << answer << endl;
}

return 0;

}

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you for your reply. I really appreciate it.

      → Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like 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://mirror.codeforces.com/contest/2014/submission/282381456

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Try adding a visited set in your $$$dijk$$$ to avoid processing same nodes multiple times.

    → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    I added a fix to your code. Now it passes. 282391526

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i take place (4971) with unofficial

could i be green today ?

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My best contest so far

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Congrats bro.. Can you pls tell me about your approach for D in short? Can't figure it out

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Editorial is out

      → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it 

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://mirror.codeforces.com/contest/2014/submission/282393166

→ Reply
»
3 months ago, # |
  Vote: I like it -12 Vote: I do not like it

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Read the problem statement again

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like 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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The Dashboard was so Hard as Steelboard!!!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is it unrated?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a friend who wants to ask why unrated.

→ Reply
»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

why is system testing frozen?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
← Rev. 3   Vote: I like it -12 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Soon I'll be leaving for months

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice picture.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

estimated ratings

A — 800

B — 800

C — 1000

D — 1600

E — 1800

F — 2000

G — 2200

H — 2000

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/2014/submission/282356633 submission for 2014D https://mirror.codeforces.com/contest/2014/submission/282339264 submission for 2014C https://mirror.codeforces.com/contest/2014/submission/282249661 submission for 2014B https://mirror.codeforces.com/contest/2014/submission/282227387 submission for 2014A

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/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/

→ Reply
»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

was it Unrated? I found on the contest page

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

As a test, I have been tested

→ Reply