Can somebody please explain the approach for PRFCTN (Perfection) From Nov lunchtime 2019 >?
its disjoint set union
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: Nov_lunchtime_question_3, Python 3 - rextester
I got ac in python using dsu(my unique approach)…I didn’t implement seg tree as seg tree is always tle in python
Hey, Can you tell me why my solution is giving TLE. I also used segment tree for range min query.
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.
1 Like