DEQUEUE - EDITORIAL

editorial
, , ,
23

Hopefully you have got what his isGood function is doing if not then;
int r=mid;
now he is creating a new map and puting elements from r to m .
he is iterating from r=mid to m and keep on removing the rth item and adding the left item from index zero to make sure he has the map size of binary search answer.
if now map size is n then he is sure that removing mid no. of elements are giving the result. Now he is going to search for the minimum answer .

24

hello, can anyone help me to find what wrong here? CodeChef: Practical coding for everyone
i am just trying to solve this problem with dp , i know it will gave me TLE, but i expected that for other tc i will get AC. Please tell me whats wrong with my approach .

1 Like
25

Can you tell me why both below codes are different .
one is AC and second is WA (for 1 test cases);

Code1(AC) : CodeChef: Practical coding for everyone
Code2(WA): CodeChef: Practical coding for everyone

Wrong:

if(!s.empty())
{
Min=s.begin();
Max=(s.rbegin());
l=Max-Min+1;
}

Right:

if(!s.empty())
{
Min=(s.begin());
// Max=(s.rbegin());
l=m-Min;
}

Why we canā€™t use *(s.rbegin()) for finding max-elemnt frpm set? I also checked on gfg it is correct: Find Maximum and Minimum element in a Set in C++ STL - GeeksforGeeks .
Please help me

Thanks

26

Can anybody tell me why both below codes are different .
one is AC and second is WA (for 1 test cases);

Code1(AC) : CodeChef: Practical coding for everyone
Code2(WA): CodeChef: Practical coding for everyone

Wrong:

if(!s.empty())
{
Min=s.begin();
Max=(s.rbegin());
l=Max-Min+1;
}

Right:

if(!s.empty())
{
Min=(s.begin());
// Max=(s.rbegin());
l=m-Min;
}

Why we canā€™t use *(s.rbegin()) for finding max-elemnt frpm set? I also checked on gfg it is correct: Find Maximum and Minimum element in a Set in C++ STL - GeeksforGeeks .
Please help me

Thanks

27

1
4 9
4 3 3 1 2 1 4 3 3

your AC code gives: 5
your wrong code gives: 4

this is so because you are required to pop all the elements from the last till minimum index in the set. But doing s.rbegin() indicates that you are popping elements in the range max to min. where max is not necessarily the last index of given array.

I hope its clear.

2 Likes
28

Yes clear thanks :grinning:

30

Can you please explain your code a little bit?
line 54 to 60

31

Editorial is awesome !! I got to learn a new concept!!

32

Hi, can you please explain how itā€™s O(MlogN)?

33