include <bits/stdc++.h>

8 days ago, # |

+59

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

→ Reply

ParthProLegend

4 days ago, # ^ |

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

→ Reply

Axial-Tilted

8 days ago, # |

+43

as a tes, give me contribution

→ Reply

He_XY

7 days ago, # |

As a Div.3 contestant, RobinFromTheHood orz.

→ Reply

Aspergillus

7 days ago, # |

But is it AI proofed?

→ Reply

RobinFromTheHood

7 days ago, # ^ |

+23

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

→ Reply

wltt

7 days ago, # |

← Rev. 2 →

-13

edited

→ Reply

ibrahimwq

7 days ago, # ^ |

← Rev. 2 →

+41

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

6 days ago, # ^ |

but people break rules.

→ Reply

5 days ago, # ^ |

← Rev. 2 →

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

RajSarkar

5 days ago, # ^ |

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

→ Reply

5 days ago, # ^ |

← Rev. 2 →

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

→ Reply

RajSarkar

5 days ago, # ^ |

Hahaha. But there logic is bad but not worse.

→ Reply

Gusare

6 days ago, # |

+12

"You" are in black and red. so funny

→ Reply

6 days ago, # |

+10

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

→ Reply

6 days ago, # ^ |

Same

→ Reply

6 days ago, # ^ |

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

happy-frog

6 days ago, # ^ |

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

→ Reply

6 days ago, # ^ |

← Rev. 2 →

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

happy-frog

6 days ago, # ^ |

← Rev. 3 →

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

ducksson

5 days ago, # ^ |

Yea but atleast d was easier than most div 2

→ Reply

wltt

6 days ago, # |

When did Robin last wear glasses?

→ Reply

one_lunch_man

6 days ago, # ^ |

← Rev. 2 →

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

→ Reply

6 days ago, # ^ |

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

→ Reply

sawantsukumar

5 days ago, # ^ |

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

unknown-03

6 days ago, # |

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

→ Reply

6 days ago, # ^ |

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

unknown-03

4 days ago, # ^ |

Thx bro, wish u luck in coming contests

→ Reply

3 days ago, # ^ |

glad to see you became green, thx.

→ Reply

Abid_Shahriar_Sakif

4 days ago, # ^ |

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

T_A_Y_E_F_082

6 days ago, # |

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

→ Reply

6 days ago, # ^ |

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

→ Reply

Ylandolsi

6 days ago, # |

+1500 rate ? lezgo

→ Reply

one_lunch_man

6 days ago, # |

← Rev. 2 →

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

→ Reply

Chouba14N

6 days ago, # |

I'm interested!

→ Reply

_looser__

6 days ago, # |

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

→ Reply

wedergebore

5 days ago, # ^ |

Upsolve after the contest and cheat however you like

→ Reply

_looser__

5 days ago, # ^ |

Haha yes tru

→ Reply

Depressed_C0der

6 days ago, # |

the robinhood gang in the picture is awesome. xd.

→ Reply

6 days ago, # ^ |

Thank you, honoured guest

→ Reply

terracottalite

6 days ago, # |

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

→ Reply

Nagerhide

6 days ago, # |

-8

As ChatGPT I can confirm I cannot solve the problems.

→ Reply

Jhin

6 days ago, # |

← Rev. 2 →

+18

this can't be just me

→ Reply

SamueleVid

6 days ago, # |

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

→ Reply

Blank_404

5 days ago, # ^ |

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

→ Reply

SamueleVid

5 days ago, # ^ |

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

aliullah

5 days ago, # |

I am so excited for the contest!

→ Reply

Wind_Lyric

5 days ago, # |

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

→ Reply

5 days ago, # ^ |

Because of rating I suppose

→ Reply

Wind_Lyric

5 days ago, # ^ |

well am I rated?

→ Reply

kvaso

5 days ago, # ^ |

you are above 1600 so you cant register officially

→ Reply

xorfftdp

5 days ago, # |

Can't wait for this round!

→ Reply

Kryptonix

5 days ago, # ^ |

+22

Now wait 10 mins more.

→ Reply

puupil

5 days ago, # |

+11

one refresh costed me 10 mins :(

→ Reply

iamfreeezing

5 days ago, # ^ |

they did warn us about the 10 minute penalty

→ Reply

Nathan4

5 days ago, # |

delayforces?

→ Reply

ray2060

5 days ago, # ^ |

Yeah. But why the 10 min delay

→ Reply

Nathan4

5 days ago, # ^ |

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

JTL_2.0

5 days ago, # |

waitingforces

→ Reply

Onitap

5 days ago, # |

10 minute penalty for entering the contest.

→ Reply

nukosya

5 days ago, # |

delay forces?

→ Reply

sarodesparsh

5 days ago, # |

-10

Codeforces just got 10 mins penalized for setting a wrong time

→ Reply

MildRain

5 days ago, # |

Delayed!

→ Reply

newbie234

5 days ago, # |

why is it pending brof

→ Reply

cuong2905say

5 days ago, # |

I can't wait to try it out

→ Reply

Pirate_King

5 days ago, # |

← Rev. 2 →

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

→ Reply

NexoGao

5 days ago, # |

Poor Robert ;(

→ Reply

DangerMouse

5 days ago, # |

DelayForces

→ Reply

DangerMouse

5 days ago, # |

I think it should be unrated or increase the time

→ Reply

Jhin

5 days ago, # |

Types of headache meme was supposed to be about Div2 D

→ Reply

5 days ago, # |

+12

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

ibrahimwq

5 days ago, # ^ |

← Rev. 3 →

+28

nvm

→ Reply

5 days ago, # ^ |

← Rev. 2 →

+13

Oh yeah, neat trick! Thanks!

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

→ Reply

TheoGermal

5 days ago, # ^ |

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

5 days ago, # ^ |

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

TheoGermal

5 days ago, # ^ |

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

ibrahimwq

5 days ago, # ^ |

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

→ Reply

4 days ago, # ^ |

← Rev. 3 →

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

Prakhars_alt

5 days ago, # ^ |

← Rev. 2 →

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

kHarsh3715

5 days ago, # ^ |

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

5 days ago, # ^ |

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

5 days ago, # |

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

5 days ago, # ^ |

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

5 days ago, # ^ |

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

5 days ago, # ^ |

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

→ Reply

5 days ago, # ^ |

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

→ Reply

5 days ago, # ^ |

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

→ Reply

RobinFromTheHood

5 days ago, # |

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

→ Reply

MaroMaxor

5 days ago, # ^ |

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

compounding

5 days ago, # ^ |

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

→ Reply

MaroMaxor

5 days ago, # ^ |

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

5 days ago, # |

-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;
}

→ Reply

i_would_win

5 days ago, # ^ |

right should have been 1e18

→ Reply

5 days ago, # ^ |

getting TLE ;-;

→ Reply

potatopop

5 days ago, # ^ |

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

→ Reply

i_would_win

5 days ago, # ^ |

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

→ Reply

5 days ago, # ^ |

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

→ Reply

i_would_win

5 days ago, # ^ |

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

→ Reply

compounding

5 days ago, # ^ |

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

5 days ago, # ^ |

I know sorry.. ;c

→ Reply

TCS_Bhediya

5 days ago, # |

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

→ Reply

5 days ago, # ^ |

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

5 days ago, # ^ |

← Rev. 2 →

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

5 days ago, # ^ |

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

→ Reply

5 days ago, # ^ |

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

5 days ago, # ^ |

← Rev. 2 →

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

AvoHado-_-

5 days ago, # |

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

→ Reply

desaidipesh2002

5 days ago, # |

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

→ Reply

Sanjay_7_

5 days ago, # |

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

MKasirloo

5 days ago, # ^ |

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

→ Reply

olegator2007

5 days ago, # |

Casino H

→ Reply

5 days ago, # |

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

→ Reply

5 days ago, # ^ |

same for me a 200 rank gap lol

→ Reply

5 days ago, # ^ |

← Rev. 2 →

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

puupil

5 days ago, # |

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

5 days ago, # ^ |

← Rev. 3 →

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

3FrenchOmelettes

5 days ago, # ^ |

← Rev. 2 →

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

5 days ago, # |

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

→ Reply

5 days ago, # ^ |

? 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

5 days ago, # ^ |

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

→ Reply

5 days ago, # ^ |

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

→ Reply

5 days ago, # |

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

→ Reply

m_nature

5 days ago, # |

← Rev. 2 →

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

5 days ago, # ^ |

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

5 days ago, # |

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

→ Reply

jha_rishi

5 days ago, # ^ |

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

→ Reply

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

5 days ago, # ^ |

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

→ Reply

NOTHING_2_LOSE

5 days ago, # ^ |

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

→ Reply

5 days ago, # ^ |

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

rcht

5 days ago, # ^ |

← Rev. 3 →

(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

5 days ago, # |

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

5 days ago, # ^ |

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

5 days ago, # ^ |

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

→ Reply

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

4 days ago, # ^ |

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

→ Reply

Enovax

5 days ago, # |

Can someone please tell me why this is wrong:

and can someone tell me the answer/thought process

→ Reply

SXZZ5

5 days ago, # |

omg double dijkstra on E ??? Niceee.

→ Reply

MaroMaxor

5 days ago, # |

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

1.618034

4 days ago, # ^ |

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

→ Reply

mintu.jupally

5 days ago, # |

← Rev. 2 →

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

mintu.jupally

5 days ago, # ^ |

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

Astroflexx

5 days ago, # |

Dijkstra problem was amazing!

→ Reply

rcht

5 days ago, # |

How to do the range query for H efficiently?

→ Reply

Sanjay_7_

5 days ago, # ^ |

use Mo algorithm

→ Reply

Sanjay_7_

5 days ago, # ^ |

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

→ Reply

cwz2024

5 days ago, # |

← Rev. 2 →

H << E

H can be easily solved by Zobrist hashing 282353218

→ Reply

Euphoriababy

5 days ago, # ^ |

why need rand ?(no hash)

→ Reply

_Will_W

5 days ago, # |

← Rev. 2 →

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

theleywin

5 days ago, # ^ |

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

_Will_W

5 days ago, # ^ |

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

→ Reply

Enovax

4 days ago, # ^ |

← Rev. 2 →

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

_Will_W

4 days ago, # ^ |

Yeah that was what I was trying. Thanks anyways!

→ Reply

Enovax

4 days ago, # ^ |

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

5 days ago, # |

-18

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

ajwesson0

5 days ago, # ^ |

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

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

5 days ago, # ^ |

Thank you for your reply. I really appreciate it.

→ Reply

ajwesson0

5 days ago, # |

← Rev. 2 →

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?

→ Reply

__Waled

5 days ago, # ^ |

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

→ Reply

llc5pg

5 days ago, # ^ |

← Rev. 2 →

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

→ Reply

O_SA

5 days ago, # |

i take place (4971) with unofficial

could i be green today ?

→ Reply

brave-kid

5 days ago, # |

← Rev. 2 →

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

5 days ago, # ^ |

← Rev. 2 →

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.

→ Reply

not_insync

5 days ago, # ^ |

Hashing

282374148

→ Reply

BehruzbekX

5 days ago, # |

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

→ Reply

5 days ago, # |

My best contest so far

→ Reply

avinav_patel

5 days ago, # ^ |

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

→ Reply

5 days ago, # ^ |

Editorial is out

→ Reply