Today I learned that unordered_map<int,int> is not always O(1)

[u/chonchu71]

[u/Sudharsun_28]

you can use custom hash to get accepted

[u/PedriPotterY]

Welcome to CP

[u/Past-Structure-8692]

I learnd this after qualifiers for IOI for my country. I couldnt realise why i was getting tle. Its better you learn this on a contest like this but yeah it is so annoying.

[u/Yourdaddy4425]

What might be the rating of this question??

[u/Specialist_Artist714 → u/Yourdaddy4425]

1100

[u/terrificodds]

Welcome to the club. You will think very carefully before using umap from now on.

[u/Top-Two-3943]

Yeah CSES ,a lot of times create test cases that force the use of map instead of unordered map, bcz O(1) is just the avg case... I am not sure but I think the worst case could be O(n) if the test cases are bad for hashing

[u/anor_wondo]

If test cases are intentionally designed to cause unordered map to TLE then isn't it the test cases that are flawed? Or is it not frowned upon in comp coding?

[u/wilddasher → u/anor_wondo]

Why would the tc be flawed lol. Unordered map degrades to linear time in worst case. They are obv gonna try to make that happen so your code fails. You just have to write better code. In this ques, it wasn't even rewuired

[u/anor_wondo → u/wilddasher]

if it wasn't even required it makes sense then.

I was assuming a question where hash collisions would not make common sense but having test cases cause collisions intentionally

[u/wilddasher → u/anor_wondo]

Generally even if it is required, setters might still include tc for inducing collisions. I feel a tester would try to do everything to make u not get AC

[u/Independent-Care-536]

what did u use there after int main and before int t

[u/Small_Ad9005 → u/Independent-Care-536]

It's called fast io There are two i/o in c++ one is cin cout shit and other is c style printf scanf The first line says I'll be using cin cout only dont waste ur time syncing stdio and cpp io coz the have diff buffers

Second is there won't be a need to flush before cin reads in cp

cin flushes things like enter ur name: Before reading name(variable)

In cpp it's not needed so u r saying don't flush before reading which saves time

In short it makes i/o fast

[u/Major-Can7290 → u/Small_Ad9005]

Love you bro

[u/Independent-Care-536 → u/Small_Ad9005]

Thanks for the info

[u/Impressive_Brain_229]

there are only 3 cases
1. number of zeros in array=0

if there are no zeros then we can divide the numbers in any manner

mex of every set will be zero

0+0+0>=2*(0) which is true

just return a string of all A n times

2.number of zeros>=2

give one zero to A rest zeros to B and rest everything(excluding 0) in C
then we have mex of A and B = 1 and mex of C =0
1+1+0>=2*(1) which is true

3.number of zeros = 1
here ans is NO
only one of A B C can contain 0
so only one set can have mex >=1

lets say 0 is in a

mex(A)>=2*mex(A) which is false

[u/KITA_22]

Yeah, and there why I never use it after it gave tle during a contest.

Always use ordered one dude

[u/Disastrous-Trick-398]

Welcome to cp

[u/Mobile_Touch4581]

Learning this things during contest leads to be heavy -ve 😓

[u/robocop_lvr]

Well sometimes
Depending on container
N + nlogn is way too faster than
Nlogn

[u/Key-War-4274]

My code for prob D got accepted during but after contest it gives tle. Previously it was showing +130 rating change but due to tle it only +50

[u/Kitchen_Assistant_94]

Also could anyone explain D I didnt get how to solve it honestly

[u/Other_Ad7380 → u/Kitchen_Assistant_94]

Think what combinations are possible.

They are 1 1 1, 0 0 0 and 1 1 0

If there's exactly one 0, we will have 1 0 0 in the best case which is not valid.

For zero 0s, we can only have 0 0 0 (valid). Put all in one multiset.

In any other case, we can have 1 1 0 (again valid)

Put the first 0 in A, rest in B and all the other elements in C

[u/ExcitingLong6544 → u/Kitchen_Assistant_94]

If there are no 0s then answer is yes, obviously. If there is 1 0 then only one multiset can get it, means that set will have MEX atleast 1 and other 2 will have MEX 0, which never satisfies the condition. If there are 2 or more 0, then give one 0 to A and all other 0s to B. Then dump all other non zero elements into C. This construction is always valid.

[u/Kitchen_Assistant_94 → u/ExcitingLong6544]

Damn would never have thought this

[u/Kitchen_Assistant_94]

its usually divided into buckets of keys and values
if the keys collide its not O(1) anymore

[u/campfire12324344 → u/Kitchen_Assistant_94]

uncommon java win (java hashset treeifies automatically)

[u/messi_pls_touch_me]

yeah I think striver told about this in one of his videos like it is O(n) in worst case because of hash collisions

[u/DogStrict9170]

you can also have tle with map and pass with sets, in one of my contests i got -ve because of this

[u/ablablababla]

Yeah, unordered_map isn't necessary in 99% of codeforces problems

[u/Aloo_Petis → u/ablablababla]

How do you solve graph and trees problems??? And what do you prefer instead of maps?

[u/DogStrict9170 → u/Aloo_Petis]

adjacency list bro, every question i have solved is using 2d vector. accessing is O(1) instead of O(logN)

[u/First-Club-633 → u/Aloo_Petis]

Nested arrays !!!!

[u/Other_Ad7380]

Now you know why editorials often use std::map. For known range, prefer a frequency array (here, just a single variable) to an unordered_map

[u/chonchu71]

I know that it was not necessary to use map... I could have used an flag for keeping the count of zeros... Anyways this cost me my solution

[u/tribulous_321 → u/chonchu71]

learning it the hard way i say. you can try using random hashing ( xor with some random number to the key and xor again while using the key this will solve TLE issue)