DEQUEUE - EDITORIAL

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 .

hello, can anyone help me to find what wrong here? Solution: 47314260 | CodeChef
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

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

Code1(AC) : Solution: 47321454 | CodeChef
Code2(WA): Solution: 47321808 | CodeChef

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

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

Code1(AC) : Solution: 47321454 | CodeChef
Code2(WA): Solution: 47321808 | CodeChef

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

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

Yes clear thanks

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

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

Hi, can you please explain how itās O(MlogN)?