include <bits/stdc++.h>

2 months ago, # |

+59

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

→ Reply

ParthProLegend

2 months ago, # ^ |

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

→ Reply

Axial-Tilted

2 months ago, # |

+43

as a tes, give me contribution

→ Reply

He_XY

2 months ago, # |

As a Div.3 contestant, RobinFromTheHood orz.

→ Reply

Aspergillus

2 months ago, # |

But is it AI proofed?

→ Reply

RobinFromTheHood

2 months 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

2 months ago, # |

← Rev. 2 →

-13

edited

→ Reply

ibrahimwq

2 months 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

2 months ago, # ^ |

but people break rules.

→ Reply

2 months 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

2 months ago, # ^ |

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

→ Reply

2 months 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

2 months ago, # ^ |

Hahaha. But there logic is bad but not worse.

→ Reply

Gusare

2 months ago, # |

+12

"You" are in black and red. so funny

→ Reply

2 months ago, # |

+10

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

→ Reply

2 months ago, # ^ |

Same

→ Reply

2 months 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

2 months ago, # ^ |

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

→ Reply

2 months 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

2 months 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

2 months ago, # ^ |

Yea but atleast d was easier than most div 2

→ Reply

wltt

2 months ago, # |

When did Robin last wear glasses?

→ Reply

one_lunch_man

2 months 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

2 months ago, # ^ |

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

→ Reply

sawantsukumar

2 months 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

2 months ago, # |

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

→ Reply

2 months 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

2 months ago, # ^ |

Thx bro, wish u luck in coming contests

→ Reply

2 months ago, # ^ |

glad to see you became green, thx.

→ Reply

Abid_Shahriar_Sakif

2 months 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

2 months 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

2 months 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

2 months ago, # |

+1500 rate ? lezgo

→ Reply

one_lunch_man

2 months 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

2 months ago, # |

I'm interested!

→ Reply

_looser__

2 months ago, # |

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

→ Reply

wedergebore

2 months ago, # ^ |

Upsolve after the contest and cheat however you like

→ Reply

_looser__

2 months ago, # ^ |

Haha yes tru

→ Reply

Depressed_C0der

2 months ago, # |

the robinhood gang in the picture is awesome. xd.

→ Reply

2 months ago, # ^ |

Thank you, honoured guest

→ Reply

terracottalite

2 months ago, # |

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

→ Reply

Nagerhide

2 months ago, # |

-8

As ChatGPT I can confirm I cannot solve the problems.

→ Reply

Jhin

2 months ago, # |

← Rev. 2 →

+18

this can't be just me

→ Reply

SamueleVid

2 months ago, # |

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

→ Reply

Blank_404

2 months ago, # ^ |

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

→ Reply

SamueleVid

2 months 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

2 months ago, # |

I am so excited for the contest!

→ Reply

Wind_Lyric

2 months ago, # |

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

→ Reply

2 months ago, # ^ |

Because of rating I suppose

→ Reply

Wind_Lyric

2 months ago, # ^ |

well am I rated?

→ Reply

kvaso

2 months ago, # ^ |

you are above 1600 so you cant register officially

→ Reply

xorfftdp

2 months ago, # |

Can't wait for this round!

→ Reply

Kryptonix

2 months ago, # ^ |

+22

Now wait 10 mins more.

→ Reply

puupil

2 months ago, # |

+11

one refresh costed me 10 mins :(

→ Reply

iamfreeezing

2 months ago, # ^ |

they did warn us about the 10 minute penalty

→ Reply

Nathan4

2 months ago, # |

delayforces?

→ Reply

ray2060

2 months ago, # ^ |

Yeah. But why the 10 min delay

→ Reply

Nathan4

2 months 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

2 months ago, # |

waitingforces

→ Reply

Onitap

2 months ago, # |

10 minute penalty for entering the contest.

→ Reply

nukosya

2 months ago, # |

delay forces?

→ Reply

sarodesparsh

2 months ago, # |

-10

Codeforces just got 10 mins penalized for setting a wrong time

→ Reply

MildRain

2 months ago, # |

Delayed!

→ Reply

newbie234

2 months ago, # |

why is it pending brof

→ Reply

cuong2905say

2 months ago, # |

I can't wait to try it out

→ Reply

Pirate_King

2 months ago, # |

← Rev. 2 →

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

→ Reply

NexoGao

2 months ago, # |

Poor Robert ;(

→ Reply

DangerMouse

2 months ago, # |

DelayForces

→ Reply

DangerMouse

2 months ago, # |

I think it should be unrated or increase the time

→ Reply

Jhin

2 months ago, # |

Types of headache meme was supposed to be about Div2 D

→ Reply

2 months 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

2 months ago, # ^ |

← Rev. 3 →

+28

nvm

→ Reply

2 months 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

2 months 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

2 months 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

2 months 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

2 months ago, # ^ |

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

→ Reply

2 months 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

2 months 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

2 months 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

2 months 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

2 months 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

2 months 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

2 months 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

2 months ago, # ^ |

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

→ Reply

2 months ago, # ^ |

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

→ Reply

2 months ago, # ^ |

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

→ Reply

RobinFromTheHood

2 months ago, # |

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

→ Reply

MaroMaxor

2 months 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

2 months ago, # ^ |

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

→ Reply

MaroMaxor

2 months 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

2 months 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

2 months ago, # ^ |

right should have been 1e18

→ Reply

2 months ago, # ^ |

getting TLE ;-;

→ Reply

potatopop

2 months ago, # ^ |

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

→ Reply

i_would_win

2 months ago, # ^ |

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

→ Reply

2 months ago, # ^ |

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

→ Reply

i_would_win

2 months ago, # ^ |

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

→ Reply

compounding

2 months 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

2 months ago, # ^ |

I know sorry.. ;c

→ Reply

TCS_Bhediya

2 months ago, # |

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

→ Reply

2 months 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

2 months 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

2 months ago, # ^ |

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

→ Reply

2 months 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

2 months 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-_-

2 months 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

2 months ago, # |

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

→ Reply

Sanjay_7_

2 months 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

2 months ago, # ^ |

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

→ Reply

olegator2007

2 months ago, # |

Casino H

→ Reply

2 months 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

2 months ago, # ^ |

same for me a 200 rank gap lol

→ Reply

2 months 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

2 months 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

2 months 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

2 months ago, # ^ |

← Rev. 2 →

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

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

→ Reply

2 months ago, # |

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

→ Reply

2 months 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

2 months ago, # ^ |

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

→ Reply

2 months ago, # ^ |

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

→ Reply

2 months ago, # |

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

→ Reply

m_nature

2 months 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

2 months 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

2 months ago, # |

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

→ Reply

jha_rishi

2 months ago, # ^ |

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

→ Reply

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

2 months ago, # ^ |

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

→ Reply

NOTHING_2_LOSE

2 months 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

2 months 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

2 months 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

2 months 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

2 months 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

2 months 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://codeforces.net/contest/2014/submission/282369897

2 months ago, # ^ |

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

→ Reply

Enovax

2 months ago, # |

Can someone please tell me why this is wrong:

and can someone tell me the answer/thought process

→ Reply

SXZZ5

2 months ago, # |

omg double dijkstra on E ??? Niceee.

→ Reply

MaroMaxor

2 months 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

2 months ago, # ^ |

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

→ Reply

mintu.jupally

2 months ago, # |

← Rev. 2 →

Can someone kindly help me in finding the mistake with my solution for question E: https://codeforces.net/contest/2014/submission/282371555

I have performed dijsktra with two distance arrays and two visited arrays (with horse and without horse), once from 0 and once from n-1. I am getting WA on test case 3 and not able to debug the mistake.

→ Reply

mintu.jupally

2 months 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

2 months ago, # |

Dijkstra problem was amazing!

→ Reply

rcht

2 months ago, # |

How to do the range query for H efficiently?

→ Reply

Sanjay_7_

2 months ago, # ^ |

use Mo algorithm

→ Reply

Sanjay_7_

2 months ago, # ^ |

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

→ Reply

cwz2024

2 months ago, # |

← Rev. 2 →

H << E

H can be easily solved by Zobrist hashing 282353218

→ Reply

Euphoriababy

2 months ago, # ^ |

why need rand ?(no hash)

→ Reply

_Will_W

2 months 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

2 months 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

2 months ago, # ^ |

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

→ Reply

Enovax

2 months 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

2 months ago, # ^ |

Yeah that was what I was trying. Thanks anyways!

→ Reply

Enovax

2 months 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

2 months 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

2 months 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://codeforces.net/contest/2014/submission/282381456

2 months ago, # ^ |

Thank you for your reply. I really appreciate it.

→ Reply

ajwesson0

2 months 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

2 months ago, # ^ |

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

→ Reply

llc5pg

2 months ago, # ^ |

← Rev. 2 →

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

→ Reply

O_SA

2 months ago, # |

i take place (4971) with unofficial

could i be green today ?

→ Reply

brave-kid

2 months 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

2 months 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

2 months ago, # ^ |

Hashing

282374148

→ Reply

BehruzbekX

2 months ago, # |

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

→ Reply

2 months ago, # |

My best contest so far

→ Reply

avinav_patel

2 months ago, # ^ |

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

→ Reply

2 months ago, # ^ |

Editorial is out

→ Reply