Approach for PRFCTN Nov Lunchtime 2019?

Can somebody please explain the approach for PRFCTN (Perfection) From Nov lunchtime 2019 >?

its disjoint set union

Could you explain the approach please? @kshitij_789

It was based on Segment Tree RMQ
Note that in worst case scenario, the maximum no of steps required for an array of size N is (N-1). The only way this number comes down is if there is a Mountain Sandwich Condition(Sorry for the Terminology :P). What this means is we need a subsequence of numbers such that the minimum of that subsequence is greater than the boundary sequence.
For Eg :
5 5 5 6 7 7 9 8 5
Here the 5 5 5 ------ 5 is the boundary sequence and 6 7 7 9 8 5 is the mountain sequence (Visualize Graphically). Normally to reduce this sequence, it would take 8 steps. But since after we reduce 6 7 7 9 8 to 6 6 6 6 6 , we can just reduce that sequence to 5 5 5 5 5 and get the solution, essentially skipping a move. Hence for each such Mountain Sandwich we find in the sequence, we deduct 1 from the existing number of steps required, which was initially n-1. A simple way to check for these sequences is to maintain a dictionary of element sequences and their indices. Then simply iterate over all possible pair of same element sequences and check if the minimum element in their interval (Segment Tree RMQ) is more than the element subsequences you are sandwiching. If the condition is satisfied, decrement number of steps. Finally print the remaining number of steps.

6 Likes

Thanks @jagreetdg. Could you also share your code and any reference like from where one could study this type of problem/concept.

1 Like

Oh I see. I was able to think of this kind of approach during the contest but was unsure of how to implement it and also if it was even right. Thanks dude you made it really easy.

1 Like

first every node is connected to it itself…so we remove ranges in decreasing order when removing a range we see if par[i+1] (where i is index of range)==same number as range i has if yes then don’t increment counter else do increment…after a range is done connect it to the range to the right of it

Python sucks…
I solved this question using segment tree in python why I am getting TLE in sub-task 2 I can bet if I have written this in cpp then it would be accepted.
help me…
here is my code: https://rextester.com/OXXH93660

I got ac in python using dsu(my unique approach)…I didn’t implement seg tree as seg tree is always tle in python

https://www.codechef.com/viewsolution/28010686

Hey, Can you tell me why my solution is giving TLE. I also used segment tree for range min query.

https://www.codechef.com/viewsolution/28033702

For everyone who’s getting TLE using SEGTREE, I forgot to highlight one part of my code which I personally thought was an overkill but now it seems isn’t. I combined the existing same element subsequences as a single element before processing them thereby assuring a relatively lower running time. You can see that assuming a block as a single element doesn’t change the final answer.
For Eg :
Initial Array : 1 2 3 3 4 5 5 5 5 7 6 6
After combining subsequences : 1 2 3 4 5 7 6
I hope this solves the TLE Problem.