Codeforces Round 954 E - Beautiful Array

Codeforces Round 954 E : Beautiful Array Detailed Video Editorial | English Language | Number Theory + Data Structures
Subscribe and never miss a tutorial !!
/ @formidablechief27
0:00 - Question Explanation
1:20 - When is your answer possible ?
2:50 - Dividing your answer into subsets
4:44 - Even Subset Operations
6:36 - Code Explanation for subsets and Even Operations
7:18 - Odd Length Operations
8:13 - Checking for all i being the middle element works
12:22 - Code Explanation for Odd Length Operations

[@formidablechief27]

Accepted Submission Link : codeforces.com/contest/1986/submission/267067008

[@bhag7768]

Perfection ❤

[@nottheradbrad184]

nice solution.keep up the work

[@Jazzimus]

first of all great video, thanks for this soln.
I have a doubt (im new to code forces). When i submitted my soln using unordered_map (my approach was similar to yours) i was getting TLE at test case number 27, but when i used normal map instead, the submission passed. Isnt unordered_map supposed to be faster than map (O(1) vs O(logn)), or did this question have test cases which exploited the collisions in the unordered map, causing TLE.

[@formidablechief27]

Yes due to collisions it is always preferred to use ordered map.
Unordered map goes to o(n) at worst case leading to tle.
You gave 2 choices
If you can have an extra logn factor, you can use ordered map
If time limits are tight and u need o(1), you would need to use a custom hash function that avoids collisions

[@vthevoice5975]

many questions have tags dp(EX: this question) on codeforces
is we really need dp for that......i donnot know dp yet i solve few dp tag question'
is those who know dp solve these using dp??
asking coz if dp is necessary for these question i will learn dp first?

[@formidablechief27]

In majority of questions, there are more than 1 tags, like in this ques dp and sortings was there.
That means that the question is solvable by both dp techniques and sorting/greedy techniques. Weve used sorting techniques majorly for this question
U will find some ques which have only 1 tag dp, that means that this sum is solvable only by pure dp
So to solve those sums, its important to learn dp

[@vthevoice5975]

@@formidablechief27 Thanks for the help
6 month in codeforces then also don't know that
Upto know I thought if more than 1 tag that means it's a combined question of all concept

[@formidablechief27]

@vthevoice5975 mostly those are all the ways by which u can solve the ques
But learning dp always helps cause with few basic principles u can counter almost any sum. Even non dp sums can be solved

[@ankitghosh9873]

Explaination OK but also foucs more on intuition like how you think on that on contest to reach that solution then slowly slowly build the solution what beginner needs!

[@formidablechief27]

Great advice ! Thank you so much. Will keep in mind for upcoming videos

[@ankitghosh9873]

Thank you❤️

[@AnkitKumarGhosh-is4lf]

You didnt explain map tp;
for(long long ele : p.second) tp[ele]++;
vector test;
for(pair pp : tp) if(pp.second % 2 != 0) test.push_back(pp.first);
if(test.size() > 1) {
if(test.size() % 2 == 0) {
for(int i=0;i

[@formidablechief27]

I didnt because even without that the code will work quite as well.
The code was already so complex so i felt better if i dont bring that up. And it works without it as well so.
It was just an attempt on removing duplicates and making the size of subset smaller and then performing the operation.
But later realise it will work without it as well

[@AnkitKumarGhosh-is4lf]

@@formidablechief27 got it... then remove unnecessary codes and then submit once otherwise many folks will get confused after seeing that code ..

[@formidablechief27]

@@AnkitKumarGhosh-is4lf youre right! Thanks for the feedback :)

[@AnkitKumarGhosh-is4lf]

map tp;
for(long long ele : p.second) tp[ele]++;
vector test;
for(pair pp : tp) if(pp.second % 2 != 0) test.push_back(pp.first);
if(test.size() > 1) {
if(test.size() % 2 == 0) {
for(int i=0;i

[@formidablechief27]

The code works without this snippet as well. And hence i didnt explain it..
I was trying to remove multiples of 2. So if there are 3 3 3 that means 3 3 are removed since i can make them palindrome and then i only take forward 3.
But later realised it will work without this modification so felt better if i dont explain this part since code had already gotten quite complex

[@formidablechief27]

Why test.size () % 2 == 0 is the same operation done when the size of data set was even

[@formidablechief27]

But this condition will actually never come true since we are removing twice numbers and so the size never actually becomes even
I realised this later that we dont need this